Snowflake 雪花分布式ID生成算法

Snowflake 全局唯一 id 算法相关笔记

Snowflake 唯一ID算法

Snowflake 是 Twitter 提出来的一个算法，其目的是生成一个 64bit 的整数:

从左到右的位数作用：

1bit，一般是符号位，不做处理
41bit，用来记录时间戳，这里可以记录69年，如果设置好起始时间比如今年是2018年，那么可以用到2089年
10bit，用来记录机器ID，总共可以记录1024台机器，一般用前位代表数据中心，后面5位是某个数据中心的机器ID
12bit，循环位，用来对同一个毫秒之内产生不同的ID，12位可以最多记录4095个，也就是在同一个机器同一毫秒最多记录4095个，多余的需要进行等待下毫秒。

具体实现时，可以根据不同业务的具体场景来划分。

SnowFlake 可以保证：

所有生成的 ID 按时间趋势递增；
整个分布式系统内不会产生重复id（因为有 datacenterId 和 workerId 来做区分）；

优点：
毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。
可以根据自身业务特性分配bit位，非常灵活。

缺点：
强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。

分布式唯一id：snowflake算法思考
https://juejin.im/post/5a7f9176f265da4e721c73a8

时钟回拨问题

服务器有时会发生时钟回拨，比如服务器校时服务修正了系统时间导致时钟回拨。

snowflake 是强依赖机器时钟的，如果时间发生回拨，有可能会生成重复的ID

处理方法：
1、如果时间回拨时间较短，比如配置5ms以内，那么可以直接等待一定的时间，让机器的时间追上来。
2、如果时间的回拨时间较长，我们不能接受这么长的阻塞等待，那么又有两个策略:
2.1、直接拒绝，抛出异常，打日志，通知RD时钟回滚。
2.2、利用扩展位，当时间回拨比较长的时候，不需要等待，直接在扩展位加1。2位的扩展位允许我们有3次大的时钟回拨，一般来说就够了，如果其超过三次我们还是选择抛出异常，打日志。

//判断是否发生了时间回退，如果发生则判断是否小于5ms内，小于5ms则等待获取最新的时间戳，否则抛出异常。
if (timestamp < this.lastTimestamp) {
    long offset = lastTimestamp - timestamp;
    if (offset <= 5) {
        try {
            // 时间偏差大小小于5ms，则等待两倍时间
            wait(offset << 1);
            timestamp = timeGen();
            if (timestamp < lastTimestamp) {
                logger.error("Clock moved backwards.Refusing to generate id for {} milliseconds", (this.lastTimestamp - timestamp));
                throw new UDSSnowFlakeRuntimeException(
                        String.format("Clock moved backwards.Refusing to generate id for %d milliseconds",
                                (this.lastTimestamp - timestamp)));
            }
        } catch (InterruptedException e) {
            logger.error("Method nextId encounter InterruptedException:", e.getMessage());
            throw e;
        }
    } else {
        logger.error("Clock moved backwards.Refusing to generate id for {} milliseconds", (this.lastTimestamp - timestamp));
        throw new UDSSnowFlakeRuntimeException(String.format("Clock moved backwards.Refusing to generate id for %d milliseconds",
                (this.lastTimestamp - timestamp)));
    }
}

如果再有人问你分布式 ID，这篇文章丢给他
https://juejin.im/post/5bb0217ef265da0ac2567b42