后面文章在议论分布式惟一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年我写了什么？

开源编程笔记