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

后面文章在议论分布式惟一 ID 生成的时候，有提到雪花算法，这一次，咱们具体点解说，只讲它。

据国家大气钻研核心的查尔斯·奈特称，个别的雪花大概由 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-…
- 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);
    }

}

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

机器位或者机房位，一共 10 bit，如果全副示意机器，那么能够示意 1024 台机器，如果拆分，5 bit 示意机房，5bit 示意机房外面的机器，那么能够有 32 个机房，每个机房能够用 32 台机器。

因为工夫戳只能用 69 年，咱们的计时又是从 1970 年开始的，所以这个 twepoch 示意从我的项目开始的工夫，用生成 ID 的工夫减去 twepoch 作为工夫戳，能够应用更久。

示意 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 位的二进制能示意的最大数值。

在获取工夫戳小于上一次获取的工夫戳的时候，不能生成 ID，而是持续循环，直到生成可用的 ID，这里没有应用拓展位避免时钟回拨。

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

雪花算法其实是依赖于工夫的一致性的，如果工夫回拨，就可能有问题，个别应用拓展位解决。而只能应用 69 年这个工夫限度，其实能够依据本人的须要，把工夫戳的位数设置得更多一点，比方 42 位能够用 139 年，然而很多公司首先得活下来。当然雪花算法也不是银弹，它也有毛病，在单机上递增，而多台机器只是大抵递增趋势，并不是严格递增的。

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

【作者简介】：
秦怀，公众号【秦怀杂货店 】作者，技术之路不在一时，山高水长，纵使迟缓，驰而不息。集体写作方向：Java 源码解析，JDBC，Mybatis，Spring，redis， 分布式 ， 剑指 Offer，LeetCode等，认真写好每一篇文章，不喜爱题目党，不喜爱花里胡哨，大多写系列文章，不能保障我写的都完全正确，然而我保障所写的均通过实际或者查找材料。脱漏或者谬误之处，还望斧正。

剑指 Offer 全副题解 PDF

2020 年我写了什么？

开源编程笔记

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

SnowFlake 算法

算法具体介绍

优化

工夫回拨问题

代码展现

问题剖析

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

2. 机器位怎么用？

3. twepoch 示意什么？

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

5. 工夫戳比拟

6. 前端间接应用产生精度失落

秦怀の观点

Just My Socks（注册教程内含优惠码）

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

SnowFlake 算法

算法具体介绍

优化

工夫回拨问题

代码展现

问题剖析

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

2. 机器位怎么用？

3. twepoch 示意什么？

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

5. 工夫戳比拟

6. 前端间接应用产生精度失落

秦怀の观点

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）