雪花算法

SnowFlake，雪花算法是Twitter开源的一款分布式ID生成算法，基本可以满足在分布式的的情况下生成具有唯一性的自增的ID。

雪花算法生成的ID由64位组成

1bit：符号位，正数为0，负数为1，我们生成的ID都是正数所以这里一般是0
41bit：时间戳，这里通常会用系统时间（毫秒）减去基准时间，用毫秒计算，41位bit可以表示69年的时间
10bit：这10位分别是5位数据中心ID（dataCenterId）和5位机器ID（workerId）
12bit：序列号，避免相同节点相同毫秒内生成重复ID

Java代码

public class SnowflakeId {

    // 用64位表示雪花算法ID
    // 1 + 41 + 10 +12
    
    // 1 符号位，生成的ID都是整数所以是0
    // 41 使用毫秒记录时间戳
    // 10 5位分布式数据中心ID 5位分布式机器节点ID
    // 12 序列号 用来记录同毫秒产生的不同ID

    private long workerId;
    private long datacenterId;
    private long sequence;

    public SnowflakeId(long workerId, long datacenterId, long sequence){
        // sanity check for workerId
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0",maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0",maxDatacenterId));
        }
        System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
                timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);

        this.workerId = workerId;
        this.datacenterId = datacenterId;
        this.sequence = sequence;
    }

    private long twepoch = 1288834974657L;

    private long workerIdBits = 5L;
    private long datacenterIdBits = 5L;
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);
    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    private long sequenceBits = 12L;

    private long workerIdShift = sequenceBits;
    private long datacenterIdShift = sequenceBits + workerIdBits;
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    private long sequenceMask = -1L ^ (-1L << sequenceBits);

    private long lastTimestamp = -1L;

    public long getWorkerId(){
        return workerId;
    }

    public long getDatacenterId(){
        return datacenterId;
    }

    public long getTimestamp(){
        return System.currentTimeMillis();
    }

    public synchronized long nextId() {
        //获取当前时间戳
        long timestamp = timeGen();
        //判断时钟回调 ***
        if (timestamp < lastTimestamp) {
            System.err.printf("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp);
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds",
                    lastTimestamp - timestamp));
        }

        //生成序列号 如果毫秒数相同 启用序列号 让序列号自增
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0;
        }

        lastTimestamp = timestamp;

        // 1. 时间戳 左移22位  5 + 5 + 12
        // 2. 数据中心ID 左移17位  5 + 12
        // 3. 节点机器ID 左移12位  12
        // 4. 序列号
        return ((timestamp - twepoch) << timestampLeftShift) |
                (datacenterId << datacenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    private long timeGen(){
        return System.currentTimeMillis();
    }

    //---------------测试---------------
    public static void main(String[] args) {
        SnowflakeId worker = new SnowflakeId(1,1,1);
        for (int i = 0; i < 20; i++) {
            System.out.println(worker.nextId());
        }
    }
}

分析生成ID流程

主要分为3个步骤，查看nextId()方法

获取时间戳
判断是否为相同毫秒，不相同序列号为0，相同就用序列号自增
通过与（|）运算合并时间戳、工作机器ID、序列号

public synchronized long nextId() {
    //获取当前时间戳
    long timestamp = timeGen();
    //判断时钟回调 
    if (timestamp < lastTimestamp) {
        System.err.printf("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp);
        throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds",
                lastTimestamp - timestamp));
    }

    //生成序列号 如果上毫秒数相同 启用序列号 让序列号自增
    if (lastTimestamp == timestamp) {
        sequence = (sequence + 1) & sequenceMask;
        if (sequence == 0) {
            timestamp = tilNextMillis(lastTimestamp);
        }
    } else {
        sequence = 0;
    }

    lastTimestamp = timestamp;

    // 1. 时间戳 左移22位  5 + 5 + 12
    // 2. 数据中心ID 左移17位  5 + 12
    // 3. 节点机器ID 左移12位  12
    // 4. 序列号
    return ((timestamp - twepoch) << timestampLeftShift) |
            (datacenterId << datacenterIdShift) |
            (workerId << workerIdShift) |
            sequence;
}

各部分bit合并原理

在下面这段代码中，通过合并时间戳、机器ID和序列号得出最终结果

return ((timestamp - twepoch) << timestampLeftShift) |
        (datacenterId << datacenterIdShift) |
        (workerId << workerIdShift) |
        sequence;

先看一下左移操作后各项数据的值

时间戳：
41bit     00000       00000       0000 0000 0000 0000
          dataID(空) workerID(空)    序列号(空)

数据中心ID：
10101     00000     0000 0000 0000 0000
dataID  workerID(空)    序列号(空)

机器ID：
11001       0000 0000 0000 0000
               序列号(空)

序列号：
1101 0101 1101 1101

左移后的各项数据刚好会让其他结构的bit位保留为0，而与运算会保留1。这样对这四项数据做与运算就像把它们拼接在了一起，最终组成了雪花算法的ID。

twepoch是什么

可以看到获取的时间戳并不是普通的timestamp，而是用timestamp - twepoch。如果直接使用timestamp，起始值会从我们当前时间开始，这样就会浪费0~第一次使用的时间。所以twepoch可以设置为这个业务开始的时间或者公司成立的时间（为了兼容历史数据）。

sequence最大长度

雪花算法使用12bit表示序列号，按规则来说最多表示2^12，4096个数字，就是说同一毫秒生成的ID大于4096就要等到下一毫秒再生成，否则就会出现重复ID的问题。

根据这个情况我们可以推理出，我们的批量获取的接口中，一定要加上数量限制，如果不限制，如果业务端传过来的是 Integer.MAX_VALUE，那就是说这一次调用需要等待的时间大概为：2147483647 / 4096 ≈ 524287ms ≈ 524s ≈ 8.7min

忽略调用时超时时间的问题，单纯说这个事情，CPU打满8分钟… 我这里建议批量接口中数量参数不要超过1000，甚至是100。什么样的业务场景中会一下子需要这么多id？业务上能处理过来吗？自己根据情况权衡下。https://blog.csdn.net/weixin_35586546/article/details/116403429

所以雪花算法相当于1秒可生成 4096 * 1000 个ID，也就是QPS可以到 409.6 w/s

ID最大长度

1
2
3

id的大小区间是：[1, 9223372036854775807]
最小的id是：1（twepoch为当前时间，并且workerId是0，序列号为1）
最大的id是：9223372036854775807（64个bit，第1个bit是0不变，其余位都占满，即是最大数，为9223372036854775807，也就是java Long类型的 MAX_VALUE）

时钟回拨问题

抛异常

遇到时钟回拨问题，最简单的方式就是通过校验当前时间和上一毫秒的时间，判断时钟是否回拨，抛出异常，这种方式简单且有效，但是不适合高并发系统。

延迟等待

校验时间时发现异常不直接抛出，先延时几毫秒，重新尝试获取ID，如果超过一定时间再抛出异常，这种方式是二次尝试的策略，但是治标不治本，也不适合高并发系统。

增加时钟序列位

拆分10bit的机器码，增加3bit的时钟序列，当发生时钟回拨时让时钟序列+1，类似序列号处理同毫秒问题。但是这种方案的时钟序列需要存储在其他地方，以防重启丢失。

润秒问题：什么是闰秒？

闰秒是偶尔运用于协调世界时（UTC）的调整，经由增加或减少一秒，以消弥精确的时间（使用原子钟测量）和不精确的观测太阳时（称为UT1)，之间的差异，这种做法已被证明具有破坏性，特别是在二十一世纪，尤其是在依赖精确时间戳或时间关键程序控制的服务中。2022年11月，在第27届国际计量大会上，科学家和政府代表投票决定到2035年取消闰秒

闰秒会导致雪花算法出现时钟回拨的问题。

java - 理解分布式id生成算法SnowFlake - 不折腾会死 - SegmentFault 思否

雪花算法的详解及时间回拨解决方案 - 白露~ - 博客园 (cnblogs.com)