面试官：讲讲雪花算法，越详细越好

2021 年 11 月 15 日
本文字数：5087 字
阅读完需：约 17 分钟

前面文章在谈论分布式唯一 ID 生成的时候，有提到雪花算法，这一次，我们详细点讲解，只讲它。

SnowFlake 算法

据国家大气研究中心的查尔斯·奈特称，一般的雪花大约由 10^19 个水分子组成。在雪花形成过程中，会形成不同的结构分支，所以说大自然中不存在两片完全一样的雪花，每一片雪花都拥有自己漂亮独特的形状。雪花算法表示生成的 id 如雪花般独一无二。
snowflake 是 Twitter 开源的分布式 ID 生成算法，结果是一个 long 型的 ID。其核心思想是：使用 41bit 作为毫秒数，10bit 作为机器的 ID（5 个 bit 是数据中心，5 个 bit 的机器 ID），12bit 作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是 0。

核心思想：分布式，唯一。

算法具体介绍

雪花算法是 64 位的二进制，一共包含了四部分：

1 位是符号位，也就是最高位，始终是 0，没有任何意义，因为要是唯一计算机二进制补码中就是负数，0 才是正数。
41 位是时间戳，具体到毫秒，41 位的二进制可以使用 69 年，因为时间理论上永恒递增，所以根据这个排序是可以的。
10 位是机器标识，可以全部用作机器 ID，也可以用来标识机房 ID + 机器 ID，10 位最多可以表示 1024 台机器。
12 位是计数序列号，也就是同一台机器上同一时间，理论上还可以同时生成不同的 ID，12 位的序列号能够区分出 4096 个 ID。

优化

由于 41 位是时间戳，我们的时间计算是从 1970 年开始的，只能使用 69 年，为了不浪费，其实我们可以用时间的相对值，也就是以项目开始的时间为基准时间，往后可以使用 69 年。获取唯一 ID 的服务，对处理速度要求比较高，所以我们全部使用位运算以及位移操作，获取当前时间可以使用System.currentTimeMillis()。

时间回拨问题

在获取时间的时候，可能会出现时间回拨的问题，什么是时间回拨问题呢？就是服务器上的时间突然倒退到之前的时间。

人为原因，把系统环境的时间改了。
有时候不同的机器上需要同步时间，可能不同机器之间存在误差，那么可能会出现时间回拨问题。

解决方案

回拨时间小的时候，不生成 ID，循环等待到时间点到达。
上面的方案只适合时钟回拨较小的，如果间隔过大，阻塞等待，肯定是不可取的，因此要么超过一定大小的回拨直接报错，拒绝服务，或者有一种方案是利用拓展位，回拨之后在拓展位上加 1 就可以了，这样 ID 依然可以保持唯一。但是这个要求我们提前预留出位数，要么从机器 id 中，要么从序列号中，腾出一定的位，在时间回拨的时候，这个位置 +1。

由于时间回拨导致的生产重复的 ID 的问题，其实百度和美团都有自己的解决方案了，有兴趣可以去看看，下面不是它们官网文档的信息：

百度 UIDGenerator：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
UidGenerator 是 Java 实现的, 基于Snowflake算法的唯一 ID 生成器。UidGenerator 以组件形式工作在应用项目中, 支持自定义 workerId 位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。在实现上, UidGenerator 通过借用未来时间来解决 sequence 天然存在的并发限制; 采用 RingBuffer 来缓存已生成的 UID, 并行化 UID 的生产和消费, 同时对 CacheLine 补齐，避免了由 RingBuffer 带来的硬件级「伪共享」问题. 最终单机 QPS 可达 600 万。
美团 Leaf:https://tech.meituan.com/2019/03/07/open-source-project-leaf.html
leaf-segment 方案
优化：双 buffer + 预分配
容灾：Mysql DB 一主两从，异地机房，半同步方式
缺点：如果用 segment 号段式方案：id 是递增，可计算的，不适用于订单 ID 生成场景，比如竞对在两天中午 12 点分别下单，通过订单 id 号相减就能大致计算出公司一天的订单量，这个是不能忍受的。
leaf-snowflake 方案
使用 Zookeeper 持久顺序节点的特性自动对 snowflake 节点配置 workerID
1.启动 Leaf-snowflake 服务，连接 Zookeeper，在 leaf_forever 父节点下检查自己是否已经注册过（是否有该顺序子节点）。
2.如果有注册过直接取回自己的 workerID（zk 顺序节点生成的 int 类型 ID 号），启动服务。
3.如果没有注册过，就在该父节点下面创建一个持久顺序节点，创建成功后取回顺序号当做自己的 workerID 号，启动服务。
缓存 workerID，减少第三方组件的依赖
由于强依赖时钟，对时间的要求比较敏感，在机器工作时 NTP 同步也会造成秒级别的回退，建议可以直接关闭 NTP 同步。要么在时钟回拨的时候直接不提供服务直接返回 ERROR_CODE，等时钟追上即可。或者做一层重试，然后上报报警系统，更或者是发现有时钟回拨之后自动摘除本身节点并报警

代码展示

public class SnowFlake {
    // 数据中心(机房) id    private long datacenterId;    // 机器ID    private long workerId;    // 同一时间的序列    private long sequence;
    public SnowFlake(long workerId, long datacenterId) {        this(workerId, datacenterId, 0);    }
    public SnowFlake(long workerId, long datacenterId, long sequence) {        // 合法判断        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;    }
    // 开始时间戳（2021-10-16 22:03:32）    private long twepoch = 1634393012000L;
    // 机房号，的ID所占的位数 5个bit 最大:11111(2进制)--> 31(10进制)    private long datacenterIdBits = 5L;
    // 机器ID所占的位数 5个bit 最大:11111(2进制)--> 31(10进制)    private long workerIdBits = 5L;
    // 5 bit最多只能有31个数字，就是说机器id最多只能是32以内    private long maxWorkerId = -1L ^ (-1L << workerIdBits);
    // 5 bit最多只能有31个数字，机房id最多只能是32以内    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    // 同一时间的序列所占的位数 12个bit 111111111111 = 4095  最多就是同一毫秒生成4096个    private long sequenceBits = 12L;
    // workerId的偏移量    private long workerIdShift = sequenceBits;
    // datacenterId的偏移量    private long datacenterIdShift = sequenceBits + workerIdBits;
    // timestampLeft的偏移量    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    // 序列号掩码 4095 (0b111111111111=0xfff=4095)    // 用于序号的与运算，保证序号最大值在0-4095之间    private long sequenceMask = -1L ^ (-1L << sequenceBits);
    // 最近一次时间戳    private long lastTimestamp = -1L;

    // 获取机器ID    public long getWorkerId() {        return workerId;    }

    // 获取机房ID    public long getDatacenterId() {        return datacenterId;    }

    // 获取最新一次获取的时间戳    public long getLastTimestamp() {        return lastTimestamp;    }

    // 获取下一个随机的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;
            // sequence序列大于4095            if (sequence == 0) {                // 调用到下一个时间戳的方法                timestamp = tilNextMillis(lastTimestamp);            }        } else {            // 如果是当前时间的第一次获取，那么就置为0            sequence = 0;        }
        // 记录上一次的时间戳        lastTimestamp = timestamp;
        // 偏移计算        return ((timestamp - twepoch) << timestampLeftShift) |                (datacenterId << datacenterIdShift) |                (workerId << workerIdShift) |                sequence;    }
    private long tilNextMillis(long lastTimestamp) {        // 获取最新时间戳        long timestamp = timeGen();        // 如果发现最新的时间戳小于或者等于序列号已经超4095的那个时间戳        while (timestamp <= lastTimestamp) {            // 不符合则继续            timestamp = timeGen();        }        return timestamp;    }
    private long timeGen() {        return System.currentTimeMillis();    }
    public static void main(String[] args) {        SnowFlake worker = new SnowFlake(1, 1);        long timer = System.currentTimeMillis();        for (int i = 0; i < 10000; i++) {            worker.nextId();        }        System.out.println(System.currentTimeMillis());        System.out.println(System.currentTimeMillis() - timer);    }
}

复制代码

问题分析

1. 第一位为什么不使用?

在计算机的表示中，第一位是符号位，0 表示整数，第一位如果是 1 则表示负数，我们用的 ID 默认就是正数，所以默认就是 0，那么这一位默认就没有意义。

2.机器位怎么用？

机器位或者机房位，一共 10 bit，如果全部表示机器，那么可以表示 1024 台机器，如果拆分，5 bit 表示机房，5bit 表示机房里面的机器，那么可以有 32 个机房，每个机房可以用 32 台机器。

3. twepoch 表示什么？

由于时间戳只能用 69 年，我们的计时又是从 1970 年开始的，所以这个twepoch表示从项目开始的时间，用生成 ID 的时间减去twepoch作为时间戳，可以使用更久。

4. -1L ^ (-1L << x) 表示什么？

表示 x 位二进制可以表示多少个数值，假设 x 为 3：

在计算机中，第一位是符号位，负数的反码是除了符号位，1 变 0，0 变 1, 而补码则是反码+1：

-1L 原码：1000 0001-1L 反码：1111 1110-1L 补码：1111 1111

复制代码

从上面的结果可以知道，-1L 其实在二进制里面其实就是全部为 1,那么 -1L 左移动 3 位，其实得到 1111 1000，也就是最后 3 位是 0，再与-1L异或计算之后，其实得到的，就是后面 3 位全是 1。-1L ^ (-1L << x) 表示的其实就是 x 位全是 1 的值，也就是 x 位的二进制能表示的最大数值。

5.时间戳比较

在获取时间戳小于上一次获取的时间戳的时候，不能生成 ID，而是继续循环，直到生成可用的 ID，这里没有使用拓展位防止时钟回拨。

6.前端直接使用发生精度丢失

如果前端直接使用服务端生成的 long 类型 id，会发生精度丢失的问题，因为 JS 中 Number 是 16 位的（指的是十进制的数字），而雪花算法计算出来最长的数字是 19 位的，这个时候需要用 String 作为中间转换，输出到前端即可。

秦怀の观点

雪花算法其实是依赖于时间的一致性的，如果时间回拨，就可能有问题，一般使用拓展位解决。而只能使用 69 年这个时间限制，其实可以根据自己的需要，把时间戳的位数设置得更多一点，比如 42 位可以用 139 年，但是很多公司首先得活下来。当然雪花算法也不是银弹，它也有缺点，在单机上递增，而多台机器只是大致递增趋势，并不是严格递增的。

没有最好的设计方案，只有合适和不合适的方案。

【作者简介】：

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

剑指Offer全部题解PDF

2020年我写了什么？

开源编程笔记

发布于: 2021 年 11 月 15 日阅读数: 7

原文链接:【http://xie.infoq.cn/article/1e88e09a6973f6efabc13228d】。文章转载请联系作者。