【分布式】分布式ID

前言

分布式场景下，一张表可能分散到多个数据结点上。因此需要一些分布式ID的解决方案。

分布式ID需要有几个特点：

• 全局唯一（必要） ：在多个库的主键放在一起也不会重复
• 有序（必要） ：避免频繁触发索引重建
• 信息安全：ID连续，可以根据订单编号计算一天的单量，造成信息泄露
• 包含时间戳：能够快速根据ID得知生成时间

下面几种方案按推荐顺序排序，越推荐使用越靠前。

一、雪花算法snowflake

64 位的 long 类型的唯一 id

1. 组成

1）1位不用

带符号整数第1位是符号位，正数是0，ID一般为正数，此位不用。

2）41位毫秒级时间戳

41位存储当前时间截 – 开始时间截得到的差值，可以表示$2^{41}$个毫秒的值，转化成单位年则是:$\frac{2^{41}}{1000\ast 60\ast 60\ast 24\ast 365}=69年$

注：开始时间截由程序指定，一般是id生成器开始使用的时间，设置好后避免更改。依赖服务器时间，服务器时钟回拨时可能会生成重复 id。

3）10位机器ID

生成ID的服务可以部署在1024台机器上

4）12位序列号
能够表示4096个序列号。

因此，某一毫秒，同一台机器，最多能生成4096个序号。理论上单机QPS最大为4096*1000=409.6w/s

2. 优缺点

优点：

• ID不重复：用时间戳+机器+序号生成不重复ID
• 性能高：在内存中生成
• 有序

缺点：

依赖服务器时间，存在时钟回拨的问题。

3. 时钟回拨怎么解决

时钟回拨可能产生重复ID进而影响关联系统。

a. 时钟回拨

什么是时钟回拨： 服务器上的时间倒退回之前的时间

哪些情况造成时钟回拨：

• 人为修改服务器时间
• 时钟同步后，由于机器之间时间不同，可能产生时钟回拨

b. 解决方案

算法中会记录当前服务上次生成ID的最后时间，只需要保证我下次生成ID的时间大于上次最后时间即可。根据回拨后时间距离上次生成最后时间大小，可以有不同的解决方案。

• 相差0~100ms ：等待直至当前时间超过上次最后生活时间
• 相差100ms~1s：采用等待方式可能导致接口超时。可以记录已生成ID的最大ID，在这个基础上++。（预留扩展位，在扩展位上增加。回拨后又回拨可能有问题）
• 相差1s~5s：采用最大ID增加的方式，时间过长可能导致范围溢出。可以生成ID服务响应异常，由调用方例如基于Ribbon调用其他生成ID服务。
• 相差超过5s：采用Ribbon循环调用的方式，下次访问到时钟回拨的服务可能还没达到上次生成最后时间，浪费时间。可以让超过5s的服务主动下线，并通知运维，人工介入，等待时钟正常后再重启。

4. 项目中如何使用

时钟回拨的处理逻辑在nextId()里的if (timestamp < lastTimestamp) 逻辑下。这里直接抛出异常。

public class SnowflakeIdWorker {

    // ==============================Fields===========================================
    /** 开始时间截 (2020-01-01) */
    private final long twepoch = 1577808000000L;

    /** 机器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=====================================
    /**
     * 构造函数
     * @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();
    }

    //==============================Test=============================================
    /** 测试 */
    public static void main(String[] args) {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);

        for (int i = 0; i < 100; i++) {
            long id = idWorker.nextId();
            System.out.println(id);
        }
    }
}

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
129
130
131
132
133

二、基于Redis

三、基于Zookeeper

四、号段模式

数据库中保存号段表，每次从数据库获取一个号段范围，由服务在内存中自增生成ID，直到达到号段范围再去获取。

update 表 set 最大可用ID = 3000, version = version + 1 where version = 0 and biz_type = xxx
1

采用乐观锁的方式避免长时间锁表。

优点：

• ID有序递增
• 对数据库压力比较小

缺点：

• 存在安全问题，用ID可以判断数据量
• 存在单点问题，集群实现困难

五、指定步长的自增ID

多主集群模式下，表主键设置自增ID，多节点之间会有重复ID。需要采用指定初始值的自增步长
举例：两台数据库A，B。A初始值和步长为（1,2），B初始值和步长为（2,2）。两张表生成的主键分别为
A：1,3,5,7…
B：2,4,6,8…

设置方法：

set @@auto_increment_offset = 1;     -- 起始值
set @@auto_increment_increment = 2;  -- 步长
1
2

优点：

• 简单、解决单点问题

缺点：

• 扩容困难

六、UUID

128位长的字符标识串，由32个16进制数字组成，用-连接，共36个字符。如：03425604-5462-11ee-80ad-80fa5b8732b1

生成算法与重复性：

• 基于随机数：不重复
• 基于MAC地址：不重复
• 基于时间戳：可能重复

作为分布式ID的优缺点：

• 优点：本地生成，性能高，无网络损耗
• 缺点：
  • 无序：造成索引重建，入库性能差
  • 字符串长：需要36字符

参考

• UUID会重复吗？
• 雪花算法视频
• 9种分布式ID生成方式

六、扩展

• 百度：UidGenerator
• 美团：Leaf

总结

基因算法