前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。
据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子组成。在雪花形成过程中,会形成不同的结构分支,所以说大自然中不存在两片完全一样的雪花,每一片雪花都拥有自己漂亮独特的形状。雪花算法表示生成的id如雪花般独一无二。
snowflake是Twitter开源的分布式ID生成算法,结果是一个long型的ID。其核心思想是:使用41bit作为毫秒数,10bit作为机器的ID(5个bit是数据中心,5个bit的机器ID),12bit作为毫秒内的流水号(意味着每个节点在每毫秒可以产生 4096 个 ID),最后还有一个符号位,永远是0。
核心思想:分布式,唯一。
雪花算法是 64 位 的二进制,一共包含了四部分:
由于41位是时间戳,我们的时间计算是从1970年开始的,只能使用69年,为了不浪费,其实我们可以用时间的相对值,也就是以项目开始的时间为基准时间,往后可以使用69年。获取唯一ID的服务,对处理速度要求比较高,所以我们全部使用位运算以及位移操作,获取当前时间可以使用System.currentTimeMillis()
。
在获取时间的时候,可能会出现时间回拨
的问题,什么是时间回拨问题呢?就是服务器上的时间突然倒退到之前的时间。
解决方案
+1
。由于时间回拨导致的生产重复的ID的问题,其实百度和美团都有自己的解决方案了,有兴趣可以去看看,下面不是它们官网文档的信息:
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年我写了什么?
开源编程笔记