口试官：讲讲雪花算法，越具体越好

前方文章在议论分布式唯一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年，但是很多公司起首得活下去。固然雪花算法也不是银弹，它也有缺陷，在单机上递增，而多台机器只是大抵递增趋向，并不是严厉递增的。

没有最好的计划方案，仅有切合和不切合的方案。