拆解雪花算法生成规则 | 京东物流技术团队-六虎

1 介绍

雪花算法（Snowflake）是一种生成分布式全局仅有ID的算法，生成的ID称为Snowflake IDs或snowflakes。这种算法由Twitter创立，并用于推文的ID。现在仓储渠道生成ID是用的雪花算法修改后的版别。

雪花算法几个特性

生成的ID分布式仅有和依照时刻递加有序，毫秒数在高位，自增序列在低位，整个ID都是趋势递加的。
不依靠数据库等三方体系，稳定性更高，功能非常高的。
能够依据本身事务特性分配bit位，非常灵敏。

2 其他分布式仅有ID生成计划

2.1 数据库生成

以MySQL为例，单库单表，给字段设置auto_increment来生成全局仅有ID

长处:

非常简略，维护本钱比较低
ID仅有，单调递加，能够设置固定步长

缺陷:

可用性难以确保，每次生成ID都需求访问数据库，瓶颈在于单台MySQL读写功能上，假如数据库挂掉会造成服务不可用，这是一个致命的问题

2.2 UUID

UUID是由一组32位数的16进制数字所构成，故UUID理论上的总数为16^32=2^128，约等于3.4 x 10^38。也便是说若每纳秒产生1兆个UUID，要花100亿年才会将一切UUID用完。UUID的规范型式包括32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的32个字符。示例：550e8400-e29b-41d4-a716-446655440000

长处:

本地生成ID，不需求进行远程调用，没有网络耗时
基本没有功能上限

缺陷:

可读性差
长度过长，16字节128位，生成的UUID通常是36位(包括-)，有些场景或许不适用。假如用作数据库主键，在MySQL的InnoDB引擎下长度过长，二级索引(非主键索引)会占用很大的空间。
无法确保趋势递加，在MySQL的InnoDB引擎下，新插入数据会依据主键来寻觅合适方位，会导致频频的移动、分页增加了许多开销。

3 snowflake算法完成细节

3.1 拆解64bit位

snowflake生成的id通常是一个64bit数字，java中用long类型。

图1：snowflake算法中的64-bit区分方法

1-bit不用于生成ID(符号位) long 规模[-2^(64-1), 2^(64-1) ] , (64-1)中的1代表的便是符号位
41-bit时刻戳(毫秒)能够表明1 x 2^41 / (1000 x 3600 x 24 x 365) = 69年的时刻
10-bit能够别离表明1 x 2^10 = 1024台机器,规模[0,1023]
12-bit表明1ms内自动递加的序列号，1 x 2^12 = 4096个规模[0,4095]。单机1ms能够生成4096个不重复的ID

经过上述方法进行生成ID，能够确保1024台机器在恣意69年的时刻段里不会呈现重复的ID，并且单台机器支撑一秒能够生成409.6万个ID。

这种方法能够支撑大部分事务，假如不满足，能够依据本身事务特点来调整不同命名空间占用的bit数。假如咱们有区分IDC的需求，能够将10-bit分5-bit给IDC，分5-bit给工作机器。这样就能够表明32个IDC，每个IDC下能够有32台机器。假如咱们的机器位比较特殊，数值相对较大，可是对并发要求不高，还能够将时刻位调整为秒级，时刻位节省出10-bit留给机器位。

1-bit符号位
31-bit时刻戳(秒)1 x 2^31/ (3600 x 24 x 365) = 68年
22-bit机器位运维渠道给供给的数值规模 [0,2^22-1]
10-bit序列号规模[0, 2^10 – 1]共1024个

经过上述方法进行生成ID，能够确保4194303台机器在恣意68年的时刻段里不会呈现重复的ID，并且单台机器支撑一秒能够生成1024个ID。

3.2 Java完成

public class IdGenerator {
    // 开始时刻
    private final long from = 1422720000000L;
    // 机器位所占bit位数
    private final long instanceIdBits = 10L;
    // 序列号所占bit位数
    private final long sequenceBits = 12L;
    // 机器位左移长度
    private final long instanceIdShift = sequenceBits;
    // 时刻位左移长度
    private final long timestampLeftShift = sequenceBits + instanceIdBits;
    // 序号1: 最大机器ID
    private final long maxInstanceId = -1L ^ (-1L << instanceIdBits);
    // 最大序列号
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
    private long instanceId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;
    public IdGenerator(long instanceId) {
        if (instanceId > maxInstanceId || instanceId < 0) {
            throw new IllegalArgumentException(String.format("instance Id can't be greater than %d or less than 0", maxInstanceId));
        }
        this.instanceId = instanceId;
    }
    //  序号2:
    public synchronized long nextId() {
        long timestamp = timeGen();
        //  序号3:
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
        //  序号4:
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextSecs(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }
        lastTimestamp = timestamp;
        //  序号5:
        return ((timestamp - from) << timestampLeftShift)  // (当时时刻 - 开始时刻) 向左移位
                | (instanceId << instanceIdShift)  // 机器位 向左移位
                | sequence; // 序列位
    }
    private long tilNextSecs(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
    private long timeGen() {
        return System.currentTimeMillis();
    }
}

3.3 一些疑问

3.3.1 为什么bit方位只使用了63位？

由于long在java中占8字节，每字节8bit，一共64bit，其间有1个bit位是符号位不能用做生成ID，假如符号位也用来做ID中的1个bit为会导致ID呈现负数，影响趋势递加特性。

3.3.2 核算最大机器ID

见代码中注释序号1
maxInstanceId = -1L ^ (-1L<<instanceIdBits)
等价于 maxInstanceId = -1 ^( -1<<10)
① -1二进制

1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111

② -1左移10位 -1<<10 二进制

1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1100 0000 0000

①与②进行异或运算异或运算:同为假，异为真,所以终究成果应该为

0000 0000 0000 0000 0000 0000 0000 00000000 0000 0000 0000 0000 0011 1111 1111

最终:maxInstanceId = 2^10 – 1 = 1023
sequenceMask 核算方法相同，成果为2^12 – 1 = 4095

3.3.3 核算序列号位

见代码中注释序号4

if (lastTimestamp == timestamp) {
    sequence = (sequence + 1) & sequenceMask;
    if (sequence == 0) {
        timestamp = tilNextSecs(lastTimestamp);
    }
} else {
    sequence = 0L;
}

其间这段代码的是核算序列号的代码首要逻辑是，假如上个生成ID的时刻位与当时ID的时刻位抵触，则会生成一个序列号进行区分，假如序列号竭尽，则等候下一个时刻点再生成。假如上个生成ID的时刻位与当时ID的时刻位不抵触，则将序列号设置成0。

sequence = (sequence + 1) & sequenceMask，序列号最大值sequenceMask为4095，等价于如下这种写法。

sequence = (sequence + 1);
if(sequence == 4095){
    sequence = 0;
}

其实这两种写法的成果是共同的，便是对(sequence + 1)进行取余。
这儿有个位运算知识点 k % m = k & (m – 1),m需求满足 m = 2^n,sequenceMask = 2^12 – 1。所以刚好能够用与运算进行取余操作，功率杠杠滴。

3.3.4 生成ID

见代码中注释序号5:
此时咱们拿到了时刻位(timestamp – from)、机器位(instanceId )、序列号位(sequence),所以就能够核算终究的ID了。

((timestamp - from) << timestampLeftShift)  // (当时时刻 - 开始时刻) 向左移位
| (instanceId << instanceIdShift)  // 机器位 向左移位
| sequence; // 序列位

①((timestamp – from) << timestampLeftShift) 核算时刻位
from是固定的1422720000000, timestampLeftShift = 12 + 10.咱们假定timestamp = 1422720000001。也便是from刚刚曩昔1毫秒。1毫秒也是咱们时刻位倒数第二小的值，由于0是最小值。时刻位取值规模[0, 2^41 – 1],从这也能够看出上边描述时刻位时为什么把时刻段特意标示了，由于时刻位存的不是具体时刻，而是以from为开始来算的曩昔了多少时刻。

来看下 1<<22 成果

图2: 时刻位移位成果

图2能够看出，时刻位向左移位22，方位正好到第一个时刻位。

②(instanceId << instanceIdShift) 核算机器位
为了便利核算，这儿咱们假定instanceId 等于1,机器位取值规模[0,-1]。
那么机器位便是 1 << 12

图3: 机器位移位成果

图3能够看出，机器位左移12位，方位正好到第一个机器位。

③依照 ① | ② | sequence 进行或运算进行生成ID

现在咱们有了时刻位的值，机器位的值，就只差序列号位的值，序列号是上面3描述代码生成的，规模是[0, 2^12-1]。为了便利核算，咱们假定sequence = 1

那么 ID = ① | ② | 1。进行或运算

图4: ID = ① | ② | 1

下图是依照上面逻辑生成的ID

图5: 程序生成成果

3.3.5 注意:雪花算法需求用单例方法生成ID

由于雪花算法会依靠上一次生成的ID的时刻来判别是否需求对序列号进行增加的操作，假如不是单例，两个事务用两个目标同时获取ID，则或许会生成相同的ID

4 关于雪花算法的一些考虑

机器位怎么取值

主机仅有标识假如运维渠道有机器仅有标识，能够在运维渠道取。不过需求考虑机器位能否容纳下仅有标识，或许会过长，也需求考虑运维渠道的仅有标识未来改变。
可依据ip进行核算假如能确保不同机房的机器ip不重复，能够使用ip来核算机器位，IP最大 255.255.255.255。而（255+255+255+255) < 1024，因此选用IP段数值相加即可生成机器位，不受IP位限制。不过这种方法也不是肯定ok，要依据本身情况在挑选，比如10.0.5.2 与 10.0.2.5 核算出来也是相同的。使用这种IP生成机器位的方法,必须确保IP段相加不能重复
经过数据库/redis/zk等进行协调，在使用发动的时分给每个机器分配不会重复的机器位id。

时钟回拨问题

雪花算法强依靠时刻，假如时刻产生回拨，有或许会生成重复的ID，在咱们上面的nextId中咱们用当时时刻和上一次的时刻进行判别，假如当时时刻小于上一次的时刻那么肯定是产生了回拨，雪花算法的做法是简略的抛出了一个反常。

if (timestamp < lastTimestamp) {
   throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}

假如事务的反常容忍度低，这儿咱们能够对其进行优化,假如时刻回拨时刻较短，比如装备5ms以内，那么能够直接等候一定的时刻，让机器的时刻追上来。也能够使用扩展位，将64-bit的机器位或者序列号位预留出2-bit的防止时钟回滚的扩展位。

5 ID逆运算

假如线上呈现ID重复，怎么进行问题定位？对ID进行逆运算拿到ID的时刻位、机器位、序号位。就能够进行下一步分析了。以上述生成的4198401为例

5.1时刻

时刻位 = ID / 2^(机器位 + 序列号位) + from
时刻位 = 4198401 / 2^(12 + 10) + 1422720000000 = 1422720000001
与上述生成ID时用时刻位相符
注意:ID / 2^(机器位 + 序列号位) 是整数

5.2机器

机器位 = (ID / 2^序列号位 ) % 2^(机器位)
机器位 = (4198401 / 2^12) % 2^10= (1025) % 1024 = 1
与上述生成ID时用机器位数值相符

5.3序列号

ID % 2^序列号位
序列号 = 4198401 % = 4198401 % 1024 = 1
与上述生成ID时用的序列号数值相符

6 材料

开源代码scala版别：github.com/twitter-arc…

作者：京东物流马红岩

来历：京东云开发者社区自猿其说Tech

拆解雪花算法生成规则 | 京东物流技术团队