分布式id自增算法-雪花算法(snowflake)

Posted on | Edited on | In

雪花算法

1. 介绍

snowflake算法, 最早是twitter内部使用的分布式环境下的唯一ID生成算法。在2014年开源。开源的版本由scala编写
附: twitter源码github地址

2. 原理

雪花算法的原理非常简单. 取long类型的64位的bit, 然后分布如下:

  1. 0位. 固定0, 正数标识

  2. 1-41位. 41位的毫秒时间差统计值. 这里的42存储的并不是时间戳. 实际上算法需要预制一个”初始时间戳”, 这个42位标识与初始时间戳的时间跨度. 可以算一把42位所能表述的时间跨度(以毫秒计).

    1
    2^41/(1000*60*60*24*365) = 69

  3. 42-51位. 10位的机器标识位. 可以标识1024个机器节点

  4. 52-63位. 12位序列号位. 标识在单机器节点下, 同一毫秒时间能够产生的最大id个数为4096个

3. 代码

网上流传的基于twitter源码的java版本很多, 但基本大同小异

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
public class SnowflakeIdWorker {
    /** 开始时间截 (这个用自己业务系统上线的时间) */
    private final long twepoch = 1575365018000L;
 
    /** 机器id所占的位数 */
    private final long workerIdBits = 10L;
 
    /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
     
    /** 序列在id中占的位数 */
    private final long sequenceBits = 12L;
 
    /** 机器ID向左移12位 */
    private final long workerIdShift =  private final long maxWorkerId = -1L ^ (-1L << workerIdBits);;
 
    /** 时间截向左移22位(10+12) */
    private final long timestampLeftShift = sequenceBits + workerIdBits;
 
    /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
 
    /** 工作机器ID(0~1024) */
    private long workerId;
 
    /** 毫秒内序列(0~4095) */
    private long sequence = 0L;
 
    /** 上次生成ID的时间截 */
    private long lastTimestamp = -1L;
 
    /**
     * 构造函数
     * @param workerId 工作ID (0~1024)
     */
    public SnowflakeIdWorker(long workerId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("workerId can't be greater than %d or less than 0", maxWorkerId));
        }
        this.workerId = workerId;
    }
 
    /**
     * 获得下一个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)
                | (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();
    }
}

这里可以关注一下这一行代码

1
private final long sequenceMask = -1L ^ (-1L << sequenceBits);

代码的意思可以描述为: 对-1左移12位(sequenceBits在代码中取值为12)后, 在与-1进行异或. 这里可以用二进制数模拟一下这两步操作

大家都知道, 1的二进制可以表述为:

1
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001

-1的二进制是以补码的形式存在, 即对1的二进制取反加1, 得到-1的补码表述:

1
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111

-1左移12位得到:

1
11111111 11111111 11111111 11111111 11111111 11111111 11110000 00000000

再与上面的-1异或, 得到:

1
00000000 00000000 00000000 00000000 00000000 00000000 00001111 11111111

这时得到的这个数, 就是4095. 后面我们在讲这个操作的作用.

4. 实践注意点

4.1 bit位分布的调整

实际使用过程中, 如果作为一个大型高并发的业务系统, 其机器节点很可能是超过1024个的. 因而需要调整42位的毫秒时间统计位和12位的序列号位.

我们注意到, 在毫秒的时间维度下, 42位的序列号位, 使得允许在1毫秒内产生4096个id. 这种场景实在少见. 即使是顶级流量峰值场景的淘宝双十一, 2019年其峰值订单量也才54.4万单/秒, 即需要544个id/毫秒. 因而可以调整41位的毫秒时间差统计值和12位的序列号位.

同时时间维度也是可以调整的, 可以不用毫秒, 用10毫秒或者秒也可以. 只需要保证系统的流量峰值不会远大于序列号位所能保证的最大值. 否则就会阻塞进程直到当前这个时间维度单位过去

先看下面一组调整:

  1. 0位. 固定0, 正数标识
  2. 1-28位. 28位的秒时间差统计值.
  3. 29-50位. 22位的机器标识位.
  4. 51-63位. 13位序列号位.

调整带来的变化是什么呢?
我们先看28位秒时间所能表述的时间跨度为:

1
2^28/(60*60*24*365) = 8

即时间跨度变为8年; 允许的机器数为2^22=4194304个; 每秒允许的序列号数为2^13=8192个.

事实上, 这就是百度的UidGenerator中在实现雪花算法时对bit位的调整.

乍一眼可能会觉得百度读时间差统计位和机器位的调整不是很合理, 8年未免太短了, 而400万+个机器位未免太多.

首先是8年时间差的问题. 实际上百度实现的snowflake算法, 加了一层环形缓存(算法中的数据结构叫RingBuffer), 每次生成id都是从缓存中获取. 一般这个缓存容量是序列号容量的2的幂次方. 初始化时, 将当前时间戳T1下所有的id放进缓存; 缓存不足时, 将下一秒(百度的时间维度是秒)T+1时间戳下所有的id放进缓存, 目的 是充分利用了每个时间维度下生成的所有id.

而400万+的机器位, 则是因为百度使用了主键自增id来标识同一ip+port的服务, 将其范围扩大到22位, 正常启停, 运行很久都不会重复.

4.2 workerId的分配

在实体机器上面, workerId的分配并不会有啥问题, 一个机器对应1个ip. 只需要在机器上指定一个环境变量或者在配置文件中指定一个固定值即可.

但实际在当前的服务端架构中, docker容器化已经非常普遍. 实例的ip往往是动态分配的. 如何在这种情况下, 保证实例的机器标识位不会出现重复呢?

百度UidGenerator的方法是通过mysql来实现. 建一张带有ip/port的表, 然后每次往里插数据. 利用mysql主键的自增, 保证机器标识位在分布式环境下的唯一.

百度的方法, 机器位给了22位, 能支持400多万个机器ip. 这一点我觉得可以优化一把. 正常使用id生成的, 都是一组特定的服务, 正常这些服务都会一起启动. 即使出现个别机器重启, 也不会出现重启个几百上千次的情况, 因此可以通过将新生成的主键与最大机器个数做取余操作, 以达到workerId可复用的目的.

4.3 单节点同一时间点下id溢出

注意代码中的这一段, 当限定时间维度下id溢出时, 阻塞当前进程到下一时间维度(代码中是毫秒), 获取新的时间戳以及新的序列号0

1
2
3
4
5
6
sequence = (sequence + 1) & sequenceMask;
//毫秒内序列溢出
if (sequence == 0) {
    //阻塞到下一个毫秒,获得新的时间戳
    timestamp = tilNextMillis(lastTimestamp);
}

注意到之前描述的那段复杂的位移+异或操作的代码了么?

1
private final long sequenceMask = -1L ^ (-1L << sequenceBits);

被赋值的变量sequenceMask出场了, 它的作用就是为了生成低位都是1, 高位都是0的最大序列号值, 用于与新生成的序列号做”与”操作. 一方面提升计算效率, 另一方面防止id溢出, (4095+1)&4095=0.

5. 一个不算问题的问题

Q: 如果达到了最大时间跨度, 如twitter的开源的算法描述中, 当前时间到了69年之后. 此时该如何处理

A: 答案就是id已经被用光了, 算法无法再生效了.