雪花算法（snowflake）生成Id重复问题

前言

最近工作上遇到一个雪花算法生成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的组成

不用： 1bit，因为最高位是符号位，0表示正，1表示负，所以这里固定为0 时间戳： 41bit，服务上线的时间毫秒级的时间戳（为当前时间-服务第一次上线时间），这里为（2^41-1）/1000/60/60/24/365 = 49.7年 工作机器id： 10bit，表示工作机器id，用于处理分布式部署id不重复问题，可支持2^10 = 1024个节点 序列号： 12bit，用于离散同一机器同一毫秒级别生成多条Id时，可允许同一毫秒生成2^12 = 4096个Id，则一秒就可生成4096*1000 = 400w个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就有可能重复了