九种分布式ID解决方案,总有一款适合你! 下

本文涉及的产品
服务治理 MSE Sentinel/OpenSergo,Agent数量 不受限
注册配置 MSE Nacos/ZooKeeper,118元/月
云原生网关 MSE Higress,422元/月
简介: 九种分布式ID解决方案,总有一款适合你! 下

5、雪花算法

Snowflake,雪花算法是有Twitter开源的分布式ID生成算法,以划分命名空间的方式将64bit位分割成了多个部分,每个部分都有具体的不同含义,在Java中64Bit位的整数是Long类型,所以在Java中Snowflake算法生成的ID就是long来存储的。具体如下:

  • 第一部分: 占用1bit,第一位为符号位,不适用
  • 第二部分: 41位的时间戳,41bit位可以表示241个数,每个数代表的是毫秒,那么雪花算法的时间年限是(241)/(1000×60×60×24×365)=69
  • 第三部分: 10bit表示是机器数,即 2^ 10 = 1024台机器,通常不会部署这么多机器
  • 第四部分: 12bit位是自增序列,可以表示2^12=4096个数,一秒内可以生成4096个ID,理论上snowflake方案的QPS约为409.6w/s

雪花算法案例代码:

public class SnowflakeIdWorker {
    // ==============================Fields===========================================
    /**
     * 开始时间截 (2020-11-03,一旦确定不可更改,否则时间被回调,或者改变,可能会造成id重复或冲突)
     */
    private final long twepoch = 1604374294980L;
    /**
     * 机器id所占的位数
     */
    private final long workerIdBits = 5L;
    /**
     * 数据标识id所占的位数
     */
    private final long datacenterIdBits = 5L;
    /**
     * 支持的最大机器id,结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)
     */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    /**
     * 支持的最大数据标识id,结果是31
     */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    /**
     * 序列在id中占的位数
     */
    private final long sequenceBits = 12L;
    /**
     * 机器ID向左移12位
     */
    private final long workerIdShift = sequenceBits;
    /**
     * 数据标识id向左移17位(12+5)
     */
    private final long datacenterIdShift = sequenceBits + workerIdBits;
    /**
     * 时间截向左移22位(5+5+12)
     */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    /**
     * 生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
    /**
     * 工作机器ID(0~31)
     */
    private long workerId;
    /**
     * 数据中心ID(0~31)
     */
    private long datacenterId;
    /**
     * 毫秒内序列(0~4095)
     */
    private long sequence = 0L;
    /**
     * 上次生成ID的时间截
     */
    private long lastTimestamp = -1L;
    //==============================Constructors=====================================
    /**
     * 构造函数
     *
     */
    public SnowflakeIdWorker() {
        this.workerId = 0L;
        this.datacenterId = 0L;
    }
    /**
     * 构造函数
     *
     * @param workerId     工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    public SnowflakeIdWorker(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }
    // ==============================Methods==========================================
    /**
     * 获得下一个ID (该方法是线程安全的)
     *
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();
        //如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
        //如果是同一时间生成的,则进行毫秒内序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //时间戳改变,毫秒内序列重置
        else {
            sequence = 0L;
        }
        //上次生成ID的时间截
        lastTimestamp = timestamp;
        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }
    /**
     * 阻塞到下一个毫秒,直到获得新的时间戳
     *
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
    /**
     * 返回以毫秒为单位的当前时间
     *
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }
    /**
     * 随机id生成,使用雪花算法
     *
     * @return
     */
    public static String getSnowId() {
        SnowflakeIdWorker sf = new SnowflakeIdWorker();
        String id = String.valueOf(sf.nextId());
        return id;
    }
    //=========================================Test=========================================
    /**
     * 测试
     */
    public static void main(String[] args) {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
        for (int i = 0; i < 1000; i++) {
            long id = idWorker.nextId();
            System.out.println(id);
        }
    }
}

雪花算法强依赖机器时钟,如果机器上时钟回拨,会导致发号重复。 通常通过记录最后使用时间处理该问题。

6、美团(Leaf)

由美团开发,开源项目链接:

Leaf同时支持号段模式和snowflake算法模式,可以切换使用。

snowflake模式依赖于ZooKeeper,不同于原始snowflake算法也主要是在workId的生成上,Leaf中workId是基于ZooKeeper的顺序Id来生成的,每个应用在使用Leaf-snowflake时,启动时都会都在Zookeeper中生成一个顺序Id,相当于一台机器对应一个顺序节点,也就是一个workId。

号段模式是对直接用数据库自增ID充当分布式ID的一种优化,减少对数据库的频率操作。相当于从数据库批量的获取自增ID,每次从数据库取出一个号段范围,例如 (1,1000] 代表1000个ID,业务服务将号段在本地生成1~1000的自增ID并加载到内存。

7、百度(Uidgenerator)

源码地址:

中文文档地址:

UidGenerator是百度开源的Java语言实现,基于Snowflake算法的唯一ID生成器。它是分布式的,并克服了雪花算法的并发限制。单个实例的QPS能超过6000000。需要的环境:JDK8+,MySQL(用于分配WorkerId)。

百度的Uidgenerator对结构做了部分的调整,具体如下:

image.png

时间部分只有28位,这就意味着UidGenerator默认只能承受8.5年(2^28-1/86400/365),不过UidGenerator可以适当调整delta seconds、worker node id和sequence占用位数。

8、滴滴(TinyID)

由滴滴开发,开源项目链接:

Tinyid是在美团(Leaf)的leaf-segment算法基础上升级而来,不仅支持了数据库多主节点模式,还提供了tinyid-client客户端的接入方式,使用起来更加方便。但和美团(Leaf)不同的是,Tinyid只支持号段一种模式不支持雪花模式。Tinyid提供了两种调用方式,一种基于Tinyid-server提供的http方式,另一种Tinyid-client客户端方式。

总结比较


优点 缺点
UUID 代码实现简单、没有网络开销,性能好 占用空间大、无序
数据库自增ID 利用数据库系统的功能实现,成本小、ID自增有序 并发性能受Mysql限制、强依赖DB,当DB异常时整个系统不可用,致命
Redis INCR 性能优于数据库、ID有序 解决单点问题带来的数据一致性等问题使得复杂度提高
雪花算法 不依赖数据库等第三方系统,性能也是非高、可以根据自身业务特性分配bit位,非常灵活 强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。
号段模式 数据库的压力小 单点故障ID不连续
Leaf、Uidgenerator、TinyID 高性能、高可用、接入简单 依赖第三方组件如ZooKeeper、Mysql


相关实践学习
基于MSE实现微服务的全链路灰度
通过本场景的实验操作,您将了解并实现在线业务的微服务全链路灰度能力。
相关文章
|
3月前
|
存储 SQL 微服务
常用的分布式事务解决方案(三)
常用的分布式事务解决方案(三)
|
3月前
|
关系型数据库 MySQL
常见分布式事务的解决方案(一)
常见分布式事务的解决方案(一)
|
15天前
|
算法 关系型数据库 MySQL
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
在分布式系统中,确保每个节点生成的 ID 唯一且高效至关重要。Snowflake 算法由 Twitter 开发,通过 64 位 long 型数字生成全局唯一 ID,包括 1 位标识位、41 位时间戳、10 位机器 ID 和 12 位序列号。该算法具备全局唯一性、递增性、高可用性和高性能,适用于高并发场景,如电商促销时的大量订单生成。本文介绍了使用 Go 语言的 `bwmarrin/snowflake` 和 `sony/sonyflake` 库实现 Snowflake 算法的方法。
26 1
分布式唯一ID生成:深入理解Snowflake算法在Go中的实现
|
29天前
|
NoSQL 算法 关系型数据库
分布式 ID 详解 ( 5大分布式 ID 生成方案 )
本文详解分布式全局唯一ID及其5种实现方案,关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
分布式 ID 详解 ( 5大分布式 ID 生成方案 )
|
3月前
|
消息中间件 中间件 关系型数据库
常用的分布式事务解决方案(四)
常用的分布式事务解决方案(四)
|
3月前
常用的分布式事务解决方案(二)
常用的分布式事务解决方案(二)
|
4月前
|
存储 NoSQL Java
一天五道Java面试题----第十一天(分布式架构下,Session共享有什么方案--------->分布式事务解决方案)
这篇文章是关于Java面试中的分布式架构问题的笔记,包括分布式架构下的Session共享方案、RPC和RMI的理解、分布式ID生成方案、分布式锁解决方案以及分布式事务解决方案。
一天五道Java面试题----第十一天(分布式架构下,Session共享有什么方案--------->分布式事务解决方案)
|
4月前
|
存储 监控 数据可视化
性能监控之JMeter分布式压测轻量日志解决方案
【8月更文挑战第11天】性能监控之JMeter分布式压测轻量日志解决方案
96 0
性能监控之JMeter分布式压测轻量日志解决方案
|
2月前
|
NoSQL Java Redis
太惨痛: Redis 分布式锁 5个大坑,又大又深, 如何才能 避开 ?
Redis分布式锁在高并发场景下是重要的技术手段,但其实现过程中常遇到五大深坑:**原子性问题**、**连接耗尽问题**、**锁过期问题**、**锁失效问题**以及**锁分段问题**。这些问题不仅影响系统的稳定性和性能,还可能导致数据不一致。尼恩在实际项目中总结了这些坑,并提供了详细的解决方案,包括使用Lua脚本保证原子性、设置合理的锁过期时间和使用看门狗机制、以及通过锁分段提升性能。这些经验和技巧对面试和实际开发都有很大帮助,值得深入学习和实践。
太惨痛: Redis 分布式锁 5个大坑,又大又深, 如何才能 避开 ?
|
4月前
|
NoSQL Redis
基于Redis的高可用分布式锁——RedLock
这篇文章介绍了基于Redis的高可用分布式锁RedLock的概念、工作流程、获取和释放锁的方法,以及RedLock相比单机锁在高可用性上的优势,同时指出了其在某些特殊场景下的不足,并提到了ZooKeeper作为另一种实现分布式锁的方案。
115 2
基于Redis的高可用分布式锁——RedLock