关于分布式:面试官讲讲雪花算法越详细越好

后面文章在议论分布式惟一 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()。

工夫回拨问题

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

1. 人为起因，把零碎环境的工夫改了。
2. 有时候不同的机器上须要同步工夫，可能不同机器之间存在误差，那么可能会呈现工夫回拨问题。

解决方案

1. 回拨工夫小的时候，不生成 ID，循环期待到工夫点达到。
2. 下面的计划只适宜时钟回拨较小的，如果距离过大，阻塞期待，必定是不可取的，因而要么超过肯定大小的回拨间接报错，拒绝服务，或者有一种计划是利用拓展位，回拨之后在拓展位上加 1 就能够了，这样 ID 仍然能够放弃惟一。然而这个要求咱们提前预留出位数，要么从机器 id 中，要么从序列号中，腾出肯定的位，在工夫回拨的时候，这个地位 +1。

因为工夫回拨导致的生产反复的 ID 的问题，其实百度和美团都有本人的解决方案了，有趣味能够去看看，上面不是它们官网文档的信息：

• 百度 UIDGenerator：https://github.com/baidu/uid-…

  • UidGenerator 是 Java 实现的, 基于 Snowflake 算法的惟一 ID 生成器。UidGenerator 以组件模式工作在利用我的项目中, 反对自定义 workerId 位数和初始化策略, 从而实用于 docker 等虚拟化环境下实例主动重启、漂移等场景。在实现上, UidGenerator 通过借用将来工夫来解决 sequence 人造存在的并发限度; 采纳 RingBuffer 来缓存已生成的 UID, 并行化 UID 的生产和生产, 同时对 CacheLine 补齐，防止了由 RingBuffer 带来的硬件级「伪共享」问题. 最终单机 QPS 可达 600 万。

• 美团 Leaf:https://tech.meituan.com/2019…

  • 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 年我写了什么？

开源编程笔记