分布式ID方案SnowFlake雪花算法分析

1、算法

SnowFlake算法生成的数据组成结构如下：

在java中用long类型标识，共64位（每部分用-分开）：
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 0000000000 00

1位标识，0表示正数。
41位时间戳，当前时间的毫秒减去开始时间的毫秒数。可用 (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年。
5位数据中心标识，可支持(1L << 5) = 32个数据中心。
5位机器标识，每个数据中心可支持(1L << 5) = 32个机器标识。
12位序列号，每个节点每一毫秒支持(1L << 12) = 4096个序列号。

2、Java版本实现


/**
 * 雪花算法<br>
 * 在java中用long类型标识，共64位（每部分用-分开）：<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 0000000000 00<br>
 * 1位标识，0表示正数。<br>
 * 41位时间戳，当前时间的毫秒减去开始时间的毫秒数。可用 (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年。<br>
 * 5位数据中心标识，可支持(1L << 5) = 32个数据中心。<br>
 * 5位机器标识，每个数据中心可支持(1L << 5) = 32个机器标识。<br>
 * 12位序列号，每个节点每一毫秒支持(1L << 12) = 4096个序列号。<br>
 */
public class SnowflakeIdWorker {
    /**
     * 机器标识
     */
    private long workerId;
    /**
     * 数据中心标识
     */
    private long dataCenterId;
    /**
     * 序列号
     */
    private long sequence;
    /**
     * 机器标识占用5位
     */
    private long workerIdBits = 5L;
    /**
     * 数据中心标识占用5位
     */
    private long dataCenterIdBits = 5L;
    /**
     * 12位序列号
     */
    private long sequenceBits = 12L;

    /**
     * 12位序列号支持的最大正整数
     * ....... 00001111 11111111
     * 2^12-1 = 4095
     */
    private long sequenceMask = ~(-1L << sequenceBits);

    /**
     * The Worker id shift.
     * 12位
     */
    private long workerIdShift = sequenceBits;
    /**
     * The Data center id shift.
     * 12 + 5 = 17位
     */
    private long dataCenterIdShift = sequenceBits + workerIdBits;
    /**
     * The Timestamp shift.
     * 12 + 5 + 5 = 22位
     */
    private long timestampShift = sequenceBits + workerIdBits + dataCenterIdBits;
    /**
     * 开始时间戳毫秒
     */
    private long startEpoch = 29055616000L;
    /**
     * The Last timestamp.
     */
    private long lastTimestamp = -1L;

    public SnowflakeIdWorker(long workerId, long dataCenterId, long sequence) {
        // 检查workerId是否正常
        /*
          机器标识最多支持的最大正整数
          -1的补码：
          11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
          -1 左移 5 位，高位溢出，低位补0：
          11111111 11111111 11111111 11111111 11111111 11111111 11111111 11100000
          取反：
          00000000 00000000 00000000 00000000 00000000 00000000 00000000 00011111
          转10进制：
          16 + 8 + 4 + 2 + 1 = 31
         */
        long maxWorkerId = ~(-1L << workerIdBits);
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("工作Id不能大于%d或小于0", maxWorkerId));
        }

        /*
          数据中心最多支持的最大正整数31
         */
        long maxDataCenterId = ~(-1L << dataCenterIdBits);
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("数据中心Id不能大于%d或小于0", maxDataCenterId));
        }

        this.workerId = workerId;
        this.dataCenterId = dataCenterId;
        this.sequence = sequence;
    }

    private synchronized long nextId() {
        //获取当前时间毫秒数
        long timestamp = timeGen();

        //如果当前时间毫秒数小于上一次的时间戳
        if (timestamp < lastTimestamp) {
            System.err.printf("时钟发生回调，拒绝生成ID,直到： %d.", lastTimestamp);
            throw new RuntimeException(String.format("时钟发生回调，  拒绝为 %d 毫秒生成ID。",
                    lastTimestamp - timestamp));
        }

        //当前时间毫秒数与上次时间戳相同，增加序列号
        if (lastTimestamp == timestamp) {
            //假设sequence=4095
            //(4095 + 1) & 4095
            //4096:  ....... 00010000 00000000
            //4095:  ....... 00001111 11111111
            //       ....... 00000000 00000000
            //最终sequence为0，即sequence发生溢出。
            sequence = (sequence + 1) & sequenceMask;
            //如果发生序列号为0，即当前毫秒数的序列号已经溢出，则借用下一毫秒的时间戳
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            //当前毫秒数大于上次的时间戳，序列号为0
            sequence = 0;
        }

        //更新
        lastTimestamp = timestamp;

        //生成ID算法，左移几位，则后面加几个0。
        //1、当前时间的毫秒数-开始时间的毫秒数，结果左移22位
        // 假设：timestamp - startEpoch = 1
        // 二进制:
        // 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
        // 左移22位:
        // 00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000
        //2、dataCenterId左移17位
        // 假设：dataCenterId = 1
        // 二进制:
        // 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
        // 左移17位:
        // 00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000

        //3、workerId左移12位
        // 假设：workerId = 1
        // 二进制:
        // 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
        // 左移12位:
        // 00000000 00000000 00000000 00000000 00000000 00000000 00010000 00000000
        //4、最后的所有结果按位`或`
        //假设：sequence = 1
        //00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000
        //00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000
        //00000000 00000000 00000000 00000000 00000000 00000000 00010000 00000000
        //00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
        //00000000 00000000 00000000 00000000 00000000 01000010 00010000 00000001
        //结果： 0 - 0000000 00000000 00000000 00000000 00000000 01 - 00001 - 00001 - 0000 00000001

        return ((timestamp - startEpoch) << timestampShift) |
                (dataCenterId << dataCenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

    /**
     * 获取下一秒
     *
     * @param lastTimestamp the last timestamp
     * @return the long
     */
    private long tilNextMillis(long lastTimestamp) {
        //获取当前毫秒数
        long timestamp = timeGen();
        //只要当前的毫秒数小于上次的时间戳，就一直循环，大于上次时间戳
        while (timestamp <= lastTimestamp) {
            //获取当前毫秒数
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 获取当前毫秒数
     *
     * @return the long
     */
    private long timeGen() {
        return System.currentTimeMillis();
    }


    public static void main(String[] args) {
        SnowflakeIdWorker worker = new SnowflakeIdWorker(1, 1, 1);
        for (int i = 0; i < 10000; i++) {
            long id = worker.nextId();
            System.out.println(id);
            System.out.println(Long.toString(id).length());
            System.out.println(Long.toBinaryString(id));
            System.out.println(Long.toBinaryString(id).length());
        }
    }

}

3、难点

Tips: 左移几位，则后面加几个0。

3.1、计算机器标识最多支持的最大正整数

1 2	private long workerIdBits = 5L; long maxWorkerId = ~(-1L << workerIdBits);

计算过程：

-1的补码：

11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
-1 左移 5 位，高位溢出，低位补0：

11111111 11111111 11111111 11111111 11111111 11111111 11111111 11100000
取反：

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00011111
转10进制：

16 + 8 + 4 + 2 + 1 = 31

3.2、sequence溢出处理

1	sequence = (sequence + 1) & sequenceMask;

计算过程:

假设sequence=4095：

(4095 + 1) & 4095
4096: ……. 00010000 00000000
4095: ……. 00001111 11111111
按位与 ……. 00000000 00000000
最终sequence为0，即sequence发生溢出。

3.3、ID计算

((timestamp - startEpoch) << timestampShift) |
(dataCenterId << dataCenterIdShift) |
(workerId << workerIdShift) |
sequence

计算过程：

当前时间的毫秒数-开始时间的毫秒数，结果左移22位

假设：timestamp - startEpoch = 1

二进制: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001

左移22位: 00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000

dataCenterId左移17位

假设：dataCenterId = 1

二进制: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001

左移17位: 00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000

workerId左移12位

假设：workerId = 1

二进制: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001

左移12位: 00000000 00000000 00000000 00000000 00000000 00000000 00010000 00000000