分布式ID选型与实现

分布式ID的特性

• 唯一性：确保生成的ID是全网唯一的。
• 有序递增性：确保生成的ID是对于某个用户或者业务是按一定的数字有序递增的。
• 高可用性：确保任何时候都能正确的生成ID。
• 自主性：分布式环境下不依赖中心认证即可自动生成ID
• 安全性：防止恶意用户根据id的规则来获取数据 如，订单数用户数等

分布式ID的生成方案

1. UUID

算法的核心思想是结合机器的网卡、当地时间、一个随记数来生成UUID。

• 优点：本地生成，生成简单，性能好，没有高可用风险
• 缺点：长度过长，存储冗余，且无序不可读，查询效率低

2. 数据库自增ID

使用数据库的id自增策略，如 MySQL 的 auto_increment。并且可以使用两台数据库分别设置不同步长，生成不重复ID的策略来实现高可用。

• 优点：数据库生成的ID绝对有序，高可用实现方式简单
• 缺点：需要独立部署数据库实例，成本高，有性能瓶颈

3. 批量生成ID

一次按需批量生成多个ID，每次生成都需要访问数据库，将数据库修改为最大的ID值，并在内存中记录当前值及最大值。

• 优点：避免了每次生成ID都要访问数据库并带来压力，提高性能
• 缺点：属于本地生成策略，存在单点故障，服务重启造成ID不连续

4. Redis生成ID

Redis的所有命令操作都是单线程的，本身提供像 incr 和 increby 这样的自增原子命令，所以能保证生成的 ID 肯定是唯一有序的。

• 优点：不依赖于数据库，灵活方便，且性能优于数据库；数字ID天然排序，对分页或者需要排序的结果很有帮助。
• 缺点：如果系统中没有Redis，还需要引入新的组件，增加系统复杂度；需要编码和配置的工作量比较大。

5. Twitter的snowflake算法

Twitter 利用 zookeeper 实现了一个全局ID生成的服务 Snowflake：https://github.com/twitter-archive/snowflake

如上图的所示，Twitter 的 Snowflake 算法由下面几部分组成：

• 1位符号位：

由于 long 类型在 java 中带符号的，最高位为符号位，正数为 0，负数为 1，且实际系统中所使用的ID一般都是正数，所以最高位为 0。

• 41位时间戳（毫秒级）：

需要注意的是此处的 41 位时间戳并非存储当前时间的时间戳，而是存储时间戳的差值（当前时间戳 - 起始时间戳），这里的起始时间戳一般是ID生成器开始使用的时间戳，由程序来指定，所以41位毫秒时间戳最多可以使用 (1 << 41) / (1000x60x60x24x365) = 69年。

• 10位数据机器位：

包括5位数据标识位和5位机器标识位，这10位决定了分布式系统中最多可以部署 1 << 10 = 1024 s个节点。超过这个数量，生成的ID就有可能会冲突。

• 12位毫秒内的序列：

这 12 位计数支持每个节点每毫秒（同一台机器，同一时刻）最多生成 1 << 12 = 4096个ID

加起来刚好64位，为一个Long型。

• 优点：高性能，低延迟，按时间有序，一般不会造成ID碰撞
• 缺点：需要独立的开发和部署，依赖于机器系统时钟（多台服务器时间一定要一样）时间回拨 + workid相同的问题

6. 百度UidGenerator

UidGenerator是百度开源的分布式ID生成器，基于于snowflake算法的实现，看起来感觉还行。不过，国内开源的项目维护性真是担忧。

具体可以参考官网说明：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

7. 美团Leaf

Leaf 是美团开源的分布式ID生成器，能保证全局唯一性、趋势递增、单调递增、信息安全，里面也提到了几种分布式方案的对比，但也需要依赖关系数据库、Zookeeper等中间件。

依赖于Zookeeper增加了系统的复杂度。

具体可以参考官网说明：https://tech.meituan.com/2017/04/21/mt-leaf.html

分布式ID解决方案

MybatisPlus 自带分布式id带来的问题

时钟回拨

避免不同服务器workerId（0-31） 和 datacenterId （0-31）的值相同

组合起来最多也就是最多支持1024台机器

新版的mybatisplus 分布式默认情况下，并不需要我们主动去配置datacenterId和workerId的值。mybatis-plus框架会根据应用所在服务器IP地址来生成datacenterId和workerId

此算法依赖MAC地址后两位散列来保证DataCenterId不重复，同时由于打包镜像的原因，WorkerId的随机效果无效，同一服务在数量较多时，DataCenterId和WorkerId相同概率极高，数量>32时，一定会产生DataCenterId和WorkerId相同

解决方案

手动

在CI流程中，手动指定要启动的Pod(服务)的DataCenterId和WorkerId，写入环境变量，服务内部接收环境变量并用此参数初始化Sequence对象，MybatisPlus提供了对应的自定义配置。 但是这样很鸡肋每次加机器的时候都需要配置，如果忘记了会造成很大的生产事故

自动

比如：参考美团的唯一ID生成器，使用ZK配合虚拟节点来获取当前已经被占用的WorkerId，计算本服务的WorkerId，并使用心跳保持。 使用了ZK 带来了系统复杂度 需要额外去维护。 还有其他方案也可以参考

自动维护实现

这里使用redis的方案去维护workerId 和 datacenterId

我是在mybatisplus的配置类加载后去定义我们的workerId, datacenterId的值的。需要借助redis和redisson分布式锁。原理就是workerId, datacenterId会逐个递增，直到两个值都最大，然后都归零，重新开始。只要服务数量不大于900（30x30）多，理论上重启就不会重复。

   public void changeIdWorker(){
        RLock lock = redisson.getLock(RedisKeyConstant.SYS_REDIS_LOCK_PREFIX + "id:worker");
        try{
            lock.lock();
            long workId = 0;
            long dataId;
            while(true){
                //redis中取值
                Object workIdStr =  redisTemplate.opsForValue().get(RedisKeyConstant.SYS_WORK_INCREMENT);
                if(workIdStr != null){
                    workId = workIdStr instanceof Integer ? (Integer) workIdStr : (Long) workIdStr;
                }
                //判断值
                dataId = redisTemplate.opsForValue().increment(RedisKeyConstant.SYS_DATA_INCREMENT, 1);
                if(dataId > 30){
                    redisTemplate.opsForValue().set(RedisKeyConstant.SYS_DATA_INCREMENT,0);
                    workId = redisTemplate.opsForValue().increment(RedisKeyConstant.SYS_WORK_INCREMENT, 1);
                    if(workId > 30){
                        redisTemplate.opsForValue().set(RedisKeyConstant.SYS_WORK_INCREMENT,0);
                    }
                    continue;
                }
                break;
            }
            log.info("changeIdWorker workId:{},dataId:{}",workId,dataId);
            IdWorker.initSequence(workId,dataId);
        }finally{
            lock.unlock();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

这种方案解决了 重启 可能会造成DataCenterId和WorkerId 重复的问题

雪花id是19位的 会导致前端js获取进度问题，为了避免前后端改动大，进行了对雪花算法的魔改生成16位的id（解决了前端js进度丢失的问题）

public class CustomIdGenerator implements IdentifierGenerator {

    private IdGenerator idGenerator;

    private Redisson redisson = SpringUtils.getBean("redisson");

    private RedisTemplate redisTemplate = SpringUtils.getBean("redisTemplate");

    public CustomIdGenerator() {
        RLock lock = redisson.getLock(RedisKeyConstant.SYS_REDIS_LOCK_PREFIX + "id:worker");
        try{
            lock.lock();
            long workId = 0;
            long dataId;
            while(true){
                //redis中取值
                Object workIdStr =  redisTemplate.opsForValue().get(RedisKeyConstant.SYS_WORK_INCREMENT);
                if(workIdStr != null){
                    workId = workIdStr instanceof Integer ? (Integer) workIdStr : (Long) workIdStr;
                }
                //判断值
                dataId = redisTemplate.opsForValue().increment(RedisKeyConstant.SYS_DATA_INCREMENT, 1);
                if(dataId > 30){
                    redisTemplate.opsForValue().set(RedisKeyConstant.SYS_DATA_INCREMENT,0);
                    workId = redisTemplate.opsForValue().increment(RedisKeyConstant.SYS_WORK_INCREMENT, 1);
                    if(workId > 30){
                        redisTemplate.opsForValue().set(RedisKeyConstant.SYS_WORK_INCREMENT,0);
                    }
                    continue;
                }
                break;
            }
            log.info("changeIdWorker workId:{},dataId:{}",workId,dataId);
            idGenerator = new IdGenerator(workId,dataId);
        }finally{
            lock.unlock();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

魔改后的雪花算法生成策略（16位）

public class IdGenerator {

    private static final Log logger = LogFactory.getLog(IdGenerator.class);
    /**
     * 起始的时间戳
     */
    private static final long START_TIMESTAMP = 1622505600000L;

    // 各部分占用的位数
    private static final long SEQUENCE_BITS = 6;
    private static final long WORKER_ID_BITS = 5;
    private static final long DATA_CENTER_ID_BITS = 5;

    // 各部分的最大值
    private static final long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BITS);
    private static final long MAX_WORKER_ID = -1L ^ (-1L << WORKER_ID_BITS);
    private static final long MAX_DATA_CENTER_ID = -1L ^ (-1L << DATA_CENTER_ID_BITS);

    // 各部分的位移
    private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;
    private static final long DATA_CENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;
    private static final long TIMESTAMP_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATA_CENTER_ID_BITS;

    // 工作节点ID
    private final long workerId;

    // 数据中心ID
    private final long dataCenterId;

    // 序列号
    private long sequence = 0L;

    // 上次生成ID的时间戳
    private long lastTimestamp = -1L;

    //IP地址
    private InetAddress inetAddress;

    public IdGenerator(long workerId, long dataCenterId) {
        this.workerId = workerId;
        this.dataCenterId = dataCenterId;
    }

    public IdGenerator() throws UnknownHostException {
        this.inetAddress = InetAddress.getLocalHost();
        this.dataCenterId = getDatacenterId(MAX_DATA_CENTER_ID);
        this.workerId = getMaxWorkerId(dataCenterId, MAX_WORKER_ID);
        logger.warn(" IdGenerator init success. dataCenterId:" + dataCenterId + " workerId:" + workerId + " InetAddress:" + inetAddress);

    }

    /**
     * 获取 maxWorkerId
     */
    protected long getMaxWorkerId(long datacenterId, long maxWorkerId) {
        StringBuilder mpid = new StringBuilder();
        mpid.append(datacenterId);
        String name = ManagementFactory.getRuntimeMXBean().getName();
        if (StringUtils.isNotBlank(name)) {
            /*
             * GET jvmPid
             */
            mpid.append(name.split(StringPool.AT)[0]);
        }
        /*
         * MAC + PID 的 hashcode 获取16个低位
         */
        return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
    }

    /**
     * 数据标识id部分
     */
    protected long getDatacenterId(long maxDatacenterId) {
        long id = 0L;
        try {
            if (null == this.inetAddress) {
                this.inetAddress = InetAddress.getLocalHost();
            }
            NetworkInterface network = NetworkInterface.getByInetAddress(this.inetAddress);
            if (null == network) {
                id = 1L;
            } else {
                byte[] mac = network.getHardwareAddress();
                if (null != mac) {
                    id = ((0x000000FF & (long) mac[mac.length - 2]) | (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
                    id = id % (maxDatacenterId + 1);
                }
            }
        } catch (Exception e) {
             logger.warn(" getDatacenterId: " + e.getMessage());
        }
        return id;
    }

    public synchronized long generateId() {
        long currentTimestamp = System.currentTimeMillis();

        if (currentTimestamp < lastTimestamp) {
            throw new RuntimeException("Clock moved backwards. Refusing to generate ID.");
        }

        if (currentTimestamp == lastTimestamp) {
            sequence = (sequence + 1) & MAX_SEQUENCE;
            if (sequence == 0) {
                currentTimestamp = getNextTimestamp(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = currentTimestamp;

        return ((currentTimestamp - START_TIMESTAMP) << TIMESTAMP_SHIFT)
                | (dataCenterId << DATA_CENTER_ID_SHIFT)
                | (workerId << WORKER_ID_SHIFT)
                | sequence;
    }

    private long getNextTimestamp(long lastTimestamp) {
        long currentTimestamp = System.currentTimeMillis();
        while (currentTimestamp <= lastTimestamp) {
            currentTimestamp = System.currentTimeMillis();
        }
        return currentTimestamp;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

压测

前提是在生成 16位 不维护workid 和 dataid 的 前提下

16位 单机测试 2000个线程同时压测

1台机器压测 work dataid 为 1,1

2台机器压测 同环境 workid dataid 为1,1

可以看出错误率为3.16% 0.03164556962025317

3 台机器压测 同环境 workid dataid 为1,1

可以看出错误率为3.93% 0.03929384965831435

根据上面 private static final long SEQUENCE_BITS = 6; 来看 每毫秒能生成 26（64）个不同的id

单机情况下只要并发不是很大的情况下 就不会发生重复

以此类推，说明在同一台机器上面部署的机器越多，重复的概率就越高

由于用到了第三方服务 redis 考虑到第三方服务不稳定 导致服务不可用

现有如下的解决方案：

1. 使用mysql 去维护 workid 和 dataid
2. 使用随机数去实现 随机生成workid 和 dataid 0-32 的随机数

但是会产生一个弊端 由于随机的浮动概率不大 容易发生碰撞 导致 workid 和 dataid 重复

3. 加一个和mp 一样的根据ip自动获取workid 和 dataid 的方法

也会存在跟上面一样有概率出现重复的问题，概率应该不大

其他问题

时间回拨

对于分布式系统部署之前，记得先进行系统时钟的校准同步，这样在部署之后不用再进行校准，对于大并发的场景不会产生分布式ID重复的异常。

附，系统时钟调整校准命令，在部署业务系统之前执行：

yum install ntpdate -y
ntpdate time.windows.com
1
2

雪花算法精度丢失问题（前端接收，精度丢失 （在生成19位的前提下））

Number精度是16位（雪花ID是19位的），So：JS的Number数据类型导致的精度丢失。

docker容器内读取不到宿主机的硬件地址

https://github.com/baomidou/mybatis-plus/issues/3077

分布式ID的使用

需要多租户的类才加对应的注解

对应的DO类加上

@TableId(type = IdType.ASSIGN_ID)

这样就表示当前模块使用分布式id了

参考链接

https://blog.csdn.net/w1014074794/article/details/125607205

https://github.com/baomidou/mybatis-plus/issues/3077

https://github.com/baomidou/mybatis-plus/issues/212

https://www.modb.pro/db/150947

https://mp.weixin.qq.com/s/e-hEYALJXVKAP18WheJjRg

https://www.kancloud.cn/hanxt/mybatisplus/1898543

https://www.tpfuture.top/views/issue/MybatisPlusSequenceCollision.html#datacenterid生成逻辑

https://gitee.com/AhooWang/CosId#snowflakeid之机器号分配问题

https://blog.csdn.net/qq_36268452/article/details/112647617