前言

最近工作上遇到一个雪花算法生成Id重复导致数据库中表主键冲突，导致入库失败的问题，所以顺便学习了一下雪花算法，下面是学习的笔记以及讨论如果解决雪花算法在分布式部署中生成重复Id的问题。

基础概念

snowflake中文的意思是雪花，所以常被称为雪花算法

它是twitter用scala语言编写的一个用于简单规则运算就能高效生成唯一ID的算法，下面是源码地址：

github源码地址

网上还有各种其他语言的版本，思路基本上都是参考上述源码

特性

生成的ID不重复
生成性能高
基于时间戳，可以基本保证有序递增

设计原理

准备工作

bit与byte
bit(位)：电脑中存储的最小单位，可以存储二进制中的0或1
byte(字节)：一个byte由8个bit组成
如图：

byte和bit.png

而在java中，每个数据类型存储所占的字节数不一样，常用的如下：
int：4 个字节。
short：2 个字节。
long：8 个字节。
byte：1 个字节。
float：4 个字节。
double：8 个字节。
char：2 个字节。

而雪花算法生成的数字，我们定义为long，所以就是8个byte，64bit
假设我们定义 long a = 1L；则在计算机中的存储如下：

long类型的存储.png

也就是可表示的范围为：-9223372036854775808（-2的63次方） ~ 9223372036854775807（2的63次方-1），考虑到生成的唯一值用于数据库主键，所以理论值为0~9223372036854775807（2的63次方-1），容量上肯定能满足业务方了

组成原理

雪花算法生成的Id由：1bit 不用 + 41bit时间戳+10bit工作机器id+12bit序列号，如下图：

雪花ID的组成

说明：上面总体是64位，具体位数可自行配置，如想运行更久，需要增加时间戳位数；如想支持更多节点，可增加工作机器id位数；如想支持更高并发，增加序列号位数

Java版本的具体实现

public class SnowflakeIdWorker {
    /** 开始时间截 (建议用服务第一次上线的时间，到毫秒级的时间戳) */
    private final long twepoch = 687888001020L;

    /** 机器id所占的位数 */
    private final long workerIdBits = 10L;

    /** 支持的最大机器id，结果是1023 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /** 序列在id中占的位数 */
    private final long sequenceBits = 12L;

    /** 机器ID向左移12位 */
    private final long workerIdShift = sequenceBits;

    /** 时间截向左移22位(10+12) */
    private final long timestampLeftShift = sequenceBits + workerIdBits;

    /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
     * <<为左移，每左移动1位，则扩大1倍
     * */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /** 工作机器ID(0~1024) */
    private long workerId;

    /** 毫秒内序列(0~4095) */
    private long sequence = 0L;

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

    //==============================Constructors=====================================
    /**
     * 构造函数
     * @param workerId 工作ID (0~1023)
     */
    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;
    }

    // ==============================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) {
            //如果毫秒相同，则从0递增生成序列号
            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;
    }

    /**
     * 返回以毫秒为单位的当前时间，从1970-01-01 08:00:00算起
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }
}

上述代码中，有涉及到位运算，这里对雪花算法中需要用到的挑出来介绍一下：

原码、反码、补码

我们为什么要知道这三个概念呢？首先要知道，计算机中的运算都是以补码的形式进行运算的

原码就是二进制的形式，反码和补码跟本身的正负有关，定义如下：

我们先来看原码，数字转换成二进制就是这个数字的原码，比如之前提到的long a = 1L；如下：

1的源码.png

要注意的是最高位是符号位，1标识负，0表示正，则long a = -1L的原码，如下：

-1的原码.png

long a = 1L，反码和补码是跟原码一致，我们主要来看-1L的情况：

-1的原码、反码、补码.png

左移<<

a << b， 表示a的二进制数值整体向左移动b位，符号位不变，低位空出来的补0，相当于a * (2^b)

比如-1L << 12， 表示-1L的二进制往左移动12位，刚才提了负数的二进制是以补码的形式存在，则运算过程如下：

-1L左移12.png

异或^

规则 两个操作数进行异或时，对于同一位上，如果数值相同则为 0，数值不同则为 1。
1 ^ 0 = 1,
1 ^ 1 = 0,
0 ^ 0 = 0;
比如，-1L ^(-1L << 12),也就是-1L ^-4096，运算过程如下：

-1异或-4096.png

或 |

规则 或运算时，进行运算的两个数，从最低位到最高位，一一对应。如果某 bit 的两个数值对应的值只要 1 个为 1，则结果值相应的 bit 就是 1，否则为 0。
0 | 0 = 0,
0 | 1 = 1,
1 | 1 = 1

比如：3 | 5
如下图：

3或5.png

如果想了解得更详细，可以看：位运算

雪花算法的细节

1. 线程安全

    /**
     * 获得下一个ID (该方法是线程安全的)
     * @return SnowflakeId
     */
    public synchronized long nextId() {

可以看到，生成ID的方法是加了synchronized 关键词，确保了线程安全，否则在并发情况下，生成的Id就有可能重复了

2. 同一毫秒,生成多个Id时

根据雪花算法的组成，可以看出，如果同一台机器同一毫秒需要生成多个Id，因为毫秒的时间戳、机器工作id一样，则前52位一致，所以需要靠后12位的序列号来区分

image.png

具体关键性代码如下:

        //如果是同一时间生成的，则进行毫秒内序列
        if (lastTimestamp == timestamp) {
            //如果毫秒相同，则从0递增生成序列号
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }

lastTimestamp 记录了上一次生成Id的毫秒级的时间戳；timestamp为当前生成Id时毫秒级的时间戳，如果同一毫秒生成多个id，则两者相等

然后通过下面的代码来生成序列

//如果毫秒相同，则从0递增生成序列号
sequence = (sequence + 1) & sequenceMask;

sequence开始为0，sequenceMask为生成序列号的掩码，定义如下：

    /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
     * <<为左移，每左移动1位，则扩大1倍
     * */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

上述的sequenceBits为序列号，这里定义的为12，则要运算下面代码

-1L ^(-1L << 12)

我们在上面异或的运算中，有算过这个值，为4095，不记得的可以看上面 异或部分，也就是同一毫秒，可以逐步生成0~4095序列号

如果sequence递增到4095重新回到0时，证明当前毫秒已经产生了4096个序列号，则使用tilNextMillis(lastTimestamp)方法阻塞到下一毫秒并赋值给timestamp，此时sequence=0，我们看看tilNextMillis(lastTimestamp)是怎么阻塞到下一毫秒的

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

可以看到，直接就是不断获取当前时间和最近生成Id的时间戳进行判断，如果还在当前毫秒级别，则空转，直到下一毫秒

3.移位并通过或运算拼到一起组成64位的ID

        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (workerId << workerIdShift) //
                | sequence;

我们再回顾下64位的Id是怎么组成的

ID的组成

我们举个例子，假设twepoch为当前时间，timestamp为twepoch之后1000ms，即（timestamp - twepoch）=1000；工作机器id为1，即workerId = 1；当前毫秒值第一次生成，即sequence = 0，则ID为：
((1000) << 22)
| (1 << 12)
| 0
即生成的Id：4194308096
我们先看1000、1、0的二进制，以及进行位移并或运算之后的结果

运算结果0.png

假设同一毫秒值，又生成了一次id，则：
((1000) << 22)
| (1 << 12)
| 1
即生成的Id：4194308097，所以同一台机器人上基本保证了递增

雪花算法生成Id重复问题

我们之前提到，同一机器同一毫秒级，我们能生成4096个不同序列，即不同Id，但是如果我们使用的是微服务架构，那不同机器人是否会可能生成相同Id呢？

ID的组成

其实我们之前有提到工作机器Id的作用，就是用于解决分布式Id重复的问题，这个workerId是通过构造方法传入的，如果我们用10位来存储这个值，那就是最多支持1024个节点

    /**
     * 构造函数
     * @param workerId 工作ID (0~1023)
     */
    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;
    }

那么关键问题就回归到如何去把我们的服务器和workerId对应起来？如果不是容器化部署，部署是固定的机器，我们用机器的唯一名来做key，那我们可以对这些机器名和workerId建立一个对应关系，如果存在就用之前的workerId，不存在就往上累加比如我们用计算机名做key：

image.png

非容器化部署.png

这样机器如果不断累加，最多支持1024台服务器

但是如果是容器化部署，需要支持动态增加节点，并且每次部署的机器不一定一样时，就会有问题，如果发现不同，就往上累加，经过多次发版，就可能会超过1023，这个时候生成雪花Id时，工作机器id左移12位后，当进行或运算时，时间戳的位置就会被影响，比如workerId=1024，我们拿之前的举例第1000ms，那它和第1001ms、workerId=0配置，可能生成重复的Id，如下图所示：

机器id溢出情况.png

先来看看我司之前生成workerId的规则：

        private static void Init()
        {
            if (worker == null)
            {
                //初始化为1
                long workerId = 1;
                //得到服务器机器名称
                string hostName = System.Net.Dns.GetHostName();
                if (RedisHelper.Exists(hostName))
                {
                    // 如果redis中存在改服务器名称，则直接取得workerId
                    workerId =long.Parse(RedisHelper.Get(hostName));
                }
                else
                {
                    //如果redis不存在，则用hashcode对32取模
                    var code = hostName.GetHashCode();
                    var Id = code % 32;
                    //如果取模以后的Id，大于15，则从0~15中随机一个数字，也就是把16~31中转换到0~15，并存入redis
                    //原因是，我司只给了4个bit存储workerId，所以只能支持0~15
                    if (Id>15||Id<0)
                    {
                        Id = new Random().Next(0, 15);
                    }
                    workerId = (long)Id;
                    RedisHelper.Set(hostName, workerId);
                }
                //把workerId传入构造方法
                worker = new IdWorker(workerId);
            }
        }

上述代码有2个问题：

1. hashcode对32取模，本身就可能会重复，比如460141958和3164804对32取模都是4，那生成的workerId就重复了
2. 如果hashcode>15,随机取一个，那每次都有1/16的概率重复

我司考虑的优化方案为：

1. 在redis中存储一个当前workerId的最大值
2. 每次生成workerId时，从redis中获取到当前workerId最大值，并+1作为当前workerId，并存入redis
3. 如果workerId为1023，自增为1024，则重置0，作为当前workerId，并存入redis

上述逻辑，其实可以参考序列号的位运算，简化为：
workerId= (workerId+ 1) & (-1L ^ (-1L << workerIdBits))
其中：workerIdBits为机器人Id所占的位数
如果workerIdBits = 10，则为0增长到1023后，继续从0开始自增

上述方案确保了，任何时间点不同服务器的workerId一定不一致，假设我们有6个pod，多轮启动的情况如下：

确保同一时间点workerId不一致.png

上述方案是否一定没问题呢？其实是有的，如果自增1新分配的workerId还没释放掉，这个时候就会冲突了

比如我们第一个pod(workerId=0)一直没有重启过，但是第二个pod一直在重启，达到1024时回到0，则同时会有两个pod的workerId为0, 这两台pod上程序生成的Id就有可能重复。

我们算极端情况下，workerIdBits=10，即1024个节点的情况下，可以支持到两次发版中间第一个pod一直不重启，其余5个pod一直重启的极端情况下，也能支持204次。但是只要发一次版本，所有pod都会到最近redis中记录的最大workerId，像我们一周一个版本的情况，不会存在这个问题。

部分pod不重启的情况.png

我们主要是关注pod个数和workerId运行的最大值，如果想支持两次发版间更多次非所有pod的重启，我们可以扩充workerIdBits，比如workerIdBits=10，支持workerId最大为1023，但如果workerIdBits=12，则支持workerId最大为4095

几个注意的点

1. twepoch为开始的时间戳，建议为服务第一次上线的时间，虽然我们41bit的时间戳支持49.7年，但是其实是说的距离twepoch的时间，如果两者差值超过了49.7年，左右左移22位，就会导致部分有效数据丢失，生成的Id数据不能保证大致是递增的
2. 雪花算法生成的id的组成位数，可以根据自己的实际需求可调整，如果需要支持更长，增加时间戳所占位数；如果想支持更多服务器或者更多次重启，增加工作机器人id所占位数；如果想支持同一时间更多并发，增加序列号所占位数
3. 生成雪花算法的类，需要使用单例模式，并且需要保证线程安全

workerId重复的其他方案