SnowFlake分布式唯一ID生成器

写在前面

架构是权衡的结果，架构也是一层层的组件拼接起来的，如果没有好用的组件，架构势必会做阉割，架构的理想态是建立在一堆友好、易用、标准化的组件之上的。在我过去的经验中，有两类组件经常会出现在我的架构方案中，一个是唯一ID生成器，一个是推拉结合配置中心，有了他们我可以解决分布式系统下的时序问题，不会再因数据不一致问题手足无措，推拉结合的数据中心也让架构的事件驱动能力成为可能。

今天简单聊下分布式唯一ID生成器。

SnowFlake最早应该是Twitter提出的。SnowFlake生成一个64bit大小的整数，结构如下：

• 1 位，不用。二进制中最高位为 1 的都是负数，但是我们生成的 id 一般都使用整数，所以这个最高位固定是 0。
• 41 位，用来记录时间戳（毫秒）。41 位可以表示 2^41 个数字；如果只用来表示正整数（计算机中正数包含 0），可以表示的数值范围是：0 至 2^41−1，也就是说 41 位可以表示 2^41 个毫秒的值，转化成单位年则是 2^41 / (1000 * 60 * 60 * 24 * 365) = 69年。
• 10 位，用来记录工作机器 id，可以部署在 2^10 = 1024个节点，包括 5 位 idcId 和 5 位 workerId ；5 位（bit）可以表示的最大正整数是2^5-1 = 31，即可以用 0、1、2、3、....31 这 32 个数字，来表示不同的 idcId 或 workerId。
• 12 位，序列号，用来记录同毫秒内产生的不同 id。12位（bit）可以表示的最大正整数是 2^12-1 =4095，即可以用 0、1、2、3、....4095 这 4096 个数字，来表示同一机器同一时间截（毫秒）内产生的 4096 个ID序号。

所以SnowFlake可以保证生成的ID按时间趋势递增（不是严格的递增），由于有了idc和worker的区分，整个分布式系统内不会产生重复的id。

在生产环境服务是无状态的，特别是在容器时代，容器指定固定ID不太现实，这是我们可以基于Redis/Tair/MySql等存储生成服务自增的hostid，作为全局的idcId和workerId，因为机器数量普遍较少，对于存储压力不大，运行时根据当前host获取存储的IdcId和workerId，结合SnowFlake生成唯一分布式id。

SnowFlake实现时需要考虑两个问题。

1. 时钟回拨问题

机器的时间不是严格一致的，可能会出现几毫秒的差别，如果基于这个错误时间生成的id，可能会出现重复的id。

解决方案是，进程启动之后，我们将当前时间作为分布式id服务的起始时间并记录下来，后续的递增操作是在这个时间片内的递增+1，当到达这个时间窗口最大值时，时间戳+1，到达下一个时间窗口，序号归0，为解决不同容器启动延迟问题，一般的开始时间是采用了延迟10s的处理。

1. 机器id分配及回收

前面说了，应用服务是无状态的，每台机器的id都是不一样的，而且在运行时，每台机器都有可能宕机，也可能扩容，如果机器宕了对应生成的id应该怎么处理才能不产生数据问题呢？

方案是前面介绍的，基于MySql、Tair等为每一个host生成一个idcId/workerId，这样服务启动或是宕机其实还是可以把之前生成的id续上的，机器下线不销毁生成的id。维护一个活跃的服务节点队列，节点有值代表节点活跃，则跳过，否则占用此节点，当地址空间满之后调整指针回到头部。这样可以复用已经生成的id，不会浪费掉。

如果自己写一个SnowFlake应该怎么搞呢？

写一个Java版的SnowFlake

核心算法：

public class SnowFlake {
    /*
    起始时间戳
     */
    private final static long START_TIMESTAMP = 1611573333870L;
    /*
    序号占用的位数
     */
    private final static long SEQUENCE_BIT = 12;
    /*
    机器标识占用的位数
     */
    private final static long MACHINE_BIT = 5;
    /*
    数据中心占用的位数
     */
    private final static long IDC_BIT = 5;
    /*
    数据中心位数最大值
     */
    private final static long MAX_IDC_NUM = ~(-1L << IDC_BIT);
    /*
    机器标识位数最大值
     */
    private final static long MAX_MACHINE_NUM = ~(-1L << MACHINE_BIT);
    /*
    序号占用位数最大值
     */
    private final static long MAX_SEQUENCE = ~(-1L << SEQUENCE_BIT);
    /*
    各部分索引
     */
    private final static long MACHINE_INDEX = SEQUENCE_BIT;
    private final static long IDC_INDEX = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTAMP_INDEX = IDC_INDEX + IDC_BIT;

    /*
    数据中心标识
     */
    private long idcId;
    /*
    机器标识
     */
    private long machineId;
    /*
    序列号
     */
    private long sequence = 0L;
    /*
    上一次时间戳
     */
    private long lastStamp = -1L;

    public SnowFlake(long idcId, long machineId) {
        if (idcId > MAX_IDC_NUM || idcId < 0) {
            throw new IllegalArgumentException("idcId error");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("machineId error");
        }
        this.idcId = idcId;
        this.machineId = machineId;
    }

    /**
     * ID生成
     *
     * @return
     */
    public synchronized long generateId() {
        long currentTime = getCurrentTime();
        // 时钟回拨，抛异常
        if (currentTime < lastStamp) {
            throw new RuntimeException("clock moved backwards.  Refusing to generate id");
        }

        // 同一毫秒内，做自增处理
        if (currentTime == lastStamp) {
            sequence = (sequence + 1) & MAX_SEQUENCE;
            // 位运算，同一毫秒序列数达到最大
            if (sequence == 0L) {
                currentTime = getNextMillis();
            }
        } else {
            // 下一毫秒，从0开始
            sequence = 0L;
        }

        lastStamp = currentTime;

        // 位或计算
        return (currentTime - START_TIMESTAMP) << TIMESTAMP_INDEX // 时间戳部分值
                | idcId << IDC_INDEX                              // 数据中心部分值
                | machineId << MACHINE_INDEX                      // 机器标识部分值
                | sequence;                                       // 序号递增部分值
    }

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

    /**
     * 获取下一毫秒
     *
     * @return
     */
    private long getNextMillis(){
        long millis = getCurrentTime();
        while (millis <= lastStamp){
            millis = getCurrentTime();
        }
        return millis;
    }
}

测试一下：

public class IDTest {
    private final static ExecutorService bizExecutorService = Executors.newFixedThreadPool(2);

    public static void main(String[] args) {
        bizExecutorService.execute(new Runnable() {
            @Override
            public void run() {
                long maxId = 0L;
                SnowFlake snowFlake = new SnowFlake(2, 10);
                for (int i = 0; i < 100; i++) {
                    long id = snowFlake.generateId();
                    System.out.println("id = " + id);
                    if (maxId <= id) {
                        maxId = id;
                        System.out.println("true index = " + i);
                    }
                }
            }
        });
    }
}

输出结果：

id = 20122937106432
true index = 0
id = 20122941300736
true index = 1
id = 20122941300737
true index = 2
id = 20122941300738
true index = 3
id = 20122941300739
true index = 4
id = 20122941300740
true index = 5
id = 20122941300741
true index = 6
id = 20122941300742
true index = 7
id = 20122941300743
true index = 8
id = 20122941300744
true index = 9
id = 20122941300745
true index = 10
id = 20122941300746
true index = 11
id = 20122941300747
true index = 12
id = 20122941300748
true index = 13
id = 20122941300749
true index = 14
id = 20122941300750
true index = 15
id = 20122941300751
true index = 16
id = 20122941300752
true index = 17
id = 20122941300753
true index = 18
id = 20122941300754
true index = 19
id = 20122945495040
true index = 20
id = 20122945495041
true index = 21
id = 20122945495042
true index = 22
id = 20122945495043
true index = 23
id = 20122945495044
true index = 24
id = 20122945495045
true index = 25
id = 20122945495046
true index = 26
id = 20122945495047
true index = 27
id = 20122945495048
true index = 28
id = 20122945495049
true index = 29
id = 20122945495050
true index = 30
id = 20122945495051
true index = 31
id = 20122945495052
true index = 32
id = 20122945495053
true index = 33
id = 20122945495054
true index = 34
id = 20122945495055
true index = 35
id = 20122945495056
true index = 36
id = 20122945495057
true index = 37
id = 20122945495058
true index = 38
id = 20122949689344
true index = 39
id = 20122949689345
true index = 40
id = 20122949689346
true index = 41
id = 20122949689347
true index = 42
id = 20122949689348
true index = 43
id = 20122949689349
true index = 44
id = 20122949689350
true index = 45
id = 20122949689351
true index = 46
id = 20122949689352
true index = 47
id = 20122949689353
true index = 48
id = 20122949689354
true index = 49
id = 20122949689355
true index = 50
id = 20122949689356
true index = 51
id = 20122949689357
true index = 52
id = 20122949689358
true index = 53
id = 20122949689359
true index = 54
id = 20122949689360
true index = 55
id = 20122949689361
true index = 56
id = 20122949689362
true index = 57
id = 20122949689363
true index = 58
id = 20122953883648
true index = 59
id = 20122953883649
true index = 60
id = 20122953883650
true index = 61
id = 20122953883651
true index = 62
id = 20122953883652
true index = 63
id = 20122953883653
true index = 64
id = 20122953883654
true index = 65
id = 20122953883655
true index = 66
id = 20122953883656
true index = 67
id = 20122953883657
true index = 68
id = 20122953883658
true index = 69
id = 20122953883659
true index = 70
id = 20122953883660
true index = 71
id = 20122953883661
true index = 72
id = 20122953883662
true index = 73
id = 20122953883663
true index = 74
id = 20122953883664
true index = 75
id = 20122953883665
true index = 76
id = 20122953883666
true index = 77
id = 20122953883667
true index = 78
id = 20122958077952
true index = 79
id = 20122958077953
true index = 80
id = 20122958077954
true index = 81
id = 20122958077955
true index = 82
id = 20122958077956
true index = 83
id = 20122958077957
true index = 84
id = 20122958077958
true index = 85
id = 20122958077959
true index = 86
id = 20122958077960
true index = 87
id = 20122958077961
true index = 88
id = 20122958077962
true index = 89
id = 20122958077963
true index = 90
id = 20122958077964
true index = 91
id = 20122958077965
true index = 92
id = 20122958077966
true index = 93
id = 20122958077967
true index = 94
id = 20122958077968
true index = 95
id = 20122958077969
true index = 96
id = 20122962272256
true index = 97
id = 20122962272257
true index = 98
id = 20122962272258
true index = 99

通过输出值看起来是递增的。