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

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

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、计算机器标识最多支持的最大正整数

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

计算过程：

  • -1的补码：<br>

    11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111

  • -1 左移 5 位，高位溢出，低位补0：<br>

    11111111 11111111 11111111 11111111 11111111 11111111 11111111 11100000

  • 取反：<br>

    00000000 00000000 00000000 00000000 00000000 00000000 00000000 00011111

  • 转10进制：<br>

    16 + 8 + 4 + 2 + 1 = 31

3.2、sequence溢出处理

sequence = (sequence + 1) & sequenceMask;

计算过程:<br>

假设sequence=4095：<br>

  • (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<br>

二进制: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001<br>

左移22位: 00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000<br>

  • dataCenterId左移17位

假设：dataCenterId = 1<br>

二进制: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001<br>

左移17位: 00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000<br>

  • workerId左移12位

假设：workerId = 1<br>

二进制: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001<br>

左移12位: 00000000 00000000 00000000 00000000 00000000 00000000 00010000 00000000<br>

  • 最后的所有结果按位或

假设：sequence = 1<br>

00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000<br>

00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000<br>

00000000 00000000 00000000 00000000 00000000 00000000 00010000 00000000<br>

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001<br>

00000000 00000000 00000000 00000000 00000000 01000010 00010000 00000001<br>

  • 结果：

0 - 0000000 00000000 00000000 00000000 00000000 01 - 00001 - 00001 - 0000 00000001<br>

符合SnowFlake算法数据组成结构。

参考

理解分布式id生成算法SnowFlake

Twitter雪花算法SnowFlake算法的java实现

以上是 分布式ID方案SnowFlake雪花算法分析 的全部内容， 来源链接： utcz.com/z/511533.html

回到顶部