⾯试官：讲讲雪花算法，越详细越好
前⾯⽂章在谈论分布式唯⼀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：
UidGenerator是Java实现的, 基于算法的唯⼀ID⽣成器。UidGenerator以组件形式⼯作在应⽤项⽬中, ⽀持⾃定义workerId位数和初始化策略, 从⽽适⽤于等虚拟化环境下实例⾃动重启、漂移等场景。在实现上, UidGenerator通过借⽤未来时间来解决sequence天然存在的并发限制; 采⽤RingBuffer来缓存已⽣成的UID, 并⾏化UID的⽣产和消费，同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。
美团Leaf:
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) {
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++) {
}
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等，认真写好每⼀篇⽂章，不喜欢标题党，不喜欢花⾥胡哨，⼤多写系列⽂章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查资料。遗漏或者错误之处，还望指正。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论