前提 Snowflake
(雪花)是Twitter
开源的高性能ID
生成算法(服务)。
上图是Snowflake
的Github
仓库,master
分支中的REAEMDE
文件中提示:初始版本于2010
年发布,基于Apache Thrift
,早于Finagle
(这里的Finagle
是Twitter
上用于RPC
服务的构建模块)发布,而Twitter
内部使用的Snowflake
是一个完全重写的程序,在很大程度上依靠Twitter
上的现有基础架构来运行。
而2010
年发布的初版Snowflake
源码是使用Scala
语言编写的,归档于scala_28
分支。换言之,大家目前使用的Snowflake
算法原版或者改良版已经是十年前(当前是2020
年)的产物,不得不说这个算法确实比较厉害 。scala_28
分支中有介绍该算法的动机和要求,这里简单摘录一下:
动机:
Cassandra
中没有生成顺序ID
的工具,Twitter
由使用MySQL
转向使用Cassandra
的时候需要一种新的方式来生成ID
(印证了架构不是设计出来,而是基于业务场景迭代出来)。要求:
高性能:每秒每个进程至少产生10K
个ID
,加上网络延迟响应速度要在2ms
内。 顺序性:具备按照时间的自增趋势,可以直接排序。 紧凑性:保持生成的ID
的长度在64 bit
或更短。 高可用:ID
生成方案需要和存储服务一样高可用。 下面就Snowflake
的源码分析一下他的实现原理。
Snowflake方案简述 Snowflake
在初版设计方案是:
时间:41 bit
长度,使用毫秒级别精度,带有一个自定义epoch
,那么可以使用大概69
年。 可配置的机器ID
:10 bit
长度,可以满足1024
个机器使用。 序列号:12 bit
长度,可以在4096
个数字中随机取值,从而避免单个机器在1 ms
内生成重复的序列号。
但是在实际源码实现中,Snowflake
把10 bit
的可配置的机器ID
拆分为5 bit
的Worker ID
(这个可以理解为原来的机器ID
)和5 bit
的Data Center ID
(数据中心ID
),详情见IdWorker.scala
:
也就是说,支持配置最多32
个机器ID
和最多32
个数据中心ID
:
由于算法是Scala
语言编写,是依赖于JVM
的语言,返回的ID
值为Long
类型,也就是64 bit
的整数,原来的算法生成序列中只使用了63 bit
的长度,要返回的是无符号数,所以在高位补一个0
(占用1 bit
),那么加起来整个ID
的长度就是64 bit
:
其中:
41 bit
毫秒级别时间戳的取值范围是:[0, 2^41 - 1]
=> 0 ~ 2199023255551
,一共2199023255552
个数字。5 bit
机器ID
的取值范围是:[0, 2^5 - 1]
=> 0 ~ 31
,一共32
个数字。5 bit
数据中心ID
的取值范围是:[0, 2^5 - 1]
=> 0 ~ 31
,一共32
个数字。12 bit
序列号的取值范围是:[0, 2^12 - 1]
=> 0 ~ 4095
,一共4096
个数字。那么理论上可以生成2199023255552 * 32 * 32 * 4096
个完全不同的ID
值。
Snowflake
算法还有一个明显的特征:依赖于系统时钟 。41 bit
长度毫秒级别的时间来源于系统时间戳,所以必须保证系统时间是向前递进,不能发生时钟回拨 (通说来说就是不能在同一个时刻产生多个相同的时间戳或者产生了过去的时间戳)。一旦发生时钟回拨,Snowflake
会拒绝生成下一个ID
。
位运算知识补充 Snowflake
算法中使用了大量的位运算。由于整数的补码才是在计算机中的存储形式,Java
或者Scala
中的整型都使用补码表示,这里稍微提一下原码和补码的知识。
原码用于阅读,补码用于计算。 正数的补码与其原码相同。 负数的补码是除最高位其他所有位取反,然后加1
(反码加1
),而负数的补码还原为原码也是使用这个方式。 +0
的原码是0000 0000
,而-0
的原码是1000 0000
,补码只有一个0
值,用0000 0000
表示,这一点很重要,补码的0
没有二义性。简单来看就是这样:
1 2 3 4 5 6 7 * [+ 11] 原码 = [0000 1011] 补码 = [0000 1011] * [- 11] 原码 = [1000 1011] 补码 = [1111 0101] * [- 11]的补码计算过程: 原码 1000 1011 除了最高位其他位取反 1111 0100 加1 1111 0101 (补码)
使用原码、反码在计算的时候得到的不一定是准确的值,而使用补码的时候计算结果才是正确的,记住这个结论即可,这里不在举例。由于Snowflake
的ID
生成方案中,除了最高位,其他四个部分都是无符号整数,所以四个部分的整数使用补码进行位运算的效率会比较高,也只有这样才能满足Snowflake高性能设计的初衷 。Snowflake
算法中使用了几种位运算:异或(^
)、按位与(&
)、按位或(|
)和带符号左移(<<
)。
异或 异或的运算规则是:0^0=0
0^1=1
1^0=1
1^1=0
,也就是位不同则结果为1,位相同则结果为0。主要作用是:
特定位翻转,也就是一个数和N
个位都为1
的数进行异或操作,这对应的N
个位都会翻转,例如0100 & 1111
,结果就是1011
。 与0
项异或,则结果和原来的值一致。 两数的值交互:a=a^b
b=b^a
a=a^b
,这三个操作完成之后,a
和b
的值完成交换。 这里推演一下最后一条:
1 2 3 4 5 6 7 8 9 10 11 12 13 * [+ 11] 原码 = [0000 1011] 补码 = [0000 1011] a * [- 11] 原码 = [1000 1011] 补码 = [1111 0101] b a=a^b 0000 1011 1111 0101 ---------^ 1111 1110 b=b^a 1111 0101 ---------^ 0000 1011 (十进制数:11) b a=a^b 1111 1110 ---------^ 1111 0101 (十进制数:-11) a
按位与 按位与的运算规则是:0^0=0
0^1=0
1^0=0
1^1=1
,只有对应的位都为1的时候计算结果才是1,其他情况的计算结果都是0。主要作用是:
清零,如果想把一个数清零,那么和所有位为0
的数进行按位与即可。 取一个数中的指定位,例如要取X
中的低4
位,只需要和zzzz...1111
进行按位与即可,例如取1111 0110
的低4
位,则11110110 & 00001111
即可得到00000110
。 按位或 按位或的运算规则是:0|0=0
0|1=1
1|0=1
1|1=1
,只要有其中一个位存在1则计算结果是1,只有两个位同时为0的情况下计算结果才是0。主要作用是:
对一个数的部分位赋值为1
,只需要和对应位全为0
的数做按位或操作就行,例如1011 0000
如果低4
位想全部赋值为1
,那么10110000 | 00001111
即可得到1011 1111
。 带符号左移 带符号左移的运算符是<<
,一般格式是:M << n
。作用如下:
M
的二进制数(补码)向左移动n
位。左边(高位)移出部分直接舍弃,右边(低位)移入部分全部补0
。 移位结果:相当于M
的值乘以2
的n
次方,并且0、正、负数通用。 移动的位数超过了该类型的最大位数,那么编译器会对移动的位数取模,例如int
移位33
位,实际上只移动了33 % 2 = 1
位。 推演过程如下(假设n = 2
):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 * [+ 11] 原码 = [0000 1011] 补码 = [0000 1011] * [- 11] 原码 = [1000 1011] 补码 = [1111 0101] * [+ 11 << 2]的计算过程 补码 0000 1011 左移2位 0000 1011 舍高补低 0010 1100 十进制数 2^2 + 2^3 + 2^5 = 44 * [- 11 << 2]的计算过程 补码 1111 0101 左移2位 1111 0101 舍高补低 1101 0100 原码 1010 1100 (补码除最高位其他所有位取反再加1) 十进制数 - (2^2 + 2^3 + 2^5) = -44
可以写个main
方法验证一下:
1 2 3 4 public static void main (String[] args) { System.out.println(-11 << 2 ); System.out.println(11 << 2 ); }
组合技巧 利用上面提到的三个位运算符,相互组合可以实现一些高效的计算方案。
计算n个bit能表示的最大数值:
Snowflake
算法中有这样的代码:
1 2 3 4 private val workerIdBits = 5L ;private val maxWorkerId = -1L ^ (-1L << workerIdBits);
这里的算子是-1L ^ (-1L << 5L)
,整理运算符的顺序,再使用64 bit
的二进制数推演计算过程如下:
1 2 3 4 5 * [-1] 的补码 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 左移5位 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11100000 [-1] 的补码 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 异或 ----------------------------------------------------------------------- ^ 结果的补码 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00011111 (十进制数 2^0 + 2^1 + 2^2 + 2^3 + 2^4 = 31)
这样就能计算出5 bit
能表示的最大数值n
,n
为整数并且0 <= n <= 31
,即0、1、2、3...31
。Worker ID
和Data Center ID
部分的最大值就是使用这种组合运算得出的。
用固定位的最大值作为Mask避免溢出:
Snowflake
算法中有这样的代码:
1 2 3 4 5 6 7 var sequence = 0L ...... private val sequenceBits = 12L private val sequenceMask = -1L ^ (-1L << sequenceBits)...... sequence = (sequence + 1 ) & sequenceMask
最后这个算子其实就是sequence = (sequence + 1) & 4095
,假设sequence
当前值为4095
,推演一下计算过程:
1 2 3 4 * [4095] 的补码 00000000 00000000 00000000 00000000 00000000 00000000 00000111 11111111 [sequence + 1] 的补码 00000000 00000000 00000000 00000000 00000000 00000000 00001000 00000000 按位与 ----------------------------------------------------------------------- & 计算结果 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 (十进制数:0)
可以编写一个main
方法验证一下:
1 2 3 4 5 6 7 8 9 public static void main (String[] args) { int mask = 4095 ; System.out.println(0 & mask); System.out.println(1 & mask); System.out.println(2 & mask); System.out.println(4095 & mask); System.out.println(4096 & mask); System.out.println(4097 & mask); }
也就是x = (x + 1) & (-1L ^ (-1L << N))
能保证最终得到的x
值不会超过N
,这是利用了按位与中的”取指定位”的特性。
Snowflake算法实现源码分析 Snowflake
虽然用Scala
语言编写,语法其实和Java
差不多,当成Java
代码这样阅读就行,下面阅读代码的时候会跳过一些日志记录和度量统计的逻辑。先看IdWorker.scala
的属性值:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 val twepoch = 1288834974657L var sequence = 0L private val workerIdBits = 5L private val datacenterIdBits = 5L private val maxWorkerId = -1L ^ (-1L << workerIdBits)private val maxDatacenterId = -1L ^ (-1L << datacenterIdBits)private val sequenceBits = 12L private val workerIdShift = sequenceBitsprivate val datacenterIdShift = sequenceBits + workerIdBitsprivate val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBitsprivate val sequenceMask = -1L ^ (-1L << sequenceBits)private var lastTimestamp = -1L if (workerId > maxWorkerId || workerId < 0 ) {exceptionCounter.incr(1 ) throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0" .format(maxWorkerId))} if (datacenterId > maxDatacenterId || datacenterId < 0 ) {exceptionCounter.incr(1 ) throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0" .format(maxDatacenterId))} log.info("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d" , timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId)
接着看算法的核心代码逻辑:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 protected [snowflake] def nextId () : Long = synchronized { var timestamp = timeGen() if (lastTimestamp == timestamp) { sequence = (sequence + 1 ) & sequenceMask if (sequence == 0 ) { timestamp = tilNextMillis(lastTimestamp) } } else { sequence = 0 } if (timestamp < lastTimestamp) { exceptionCounter.incr(1 ) log.error("clock is moving backwards. Rejecting requests until %d." , lastTimestamp); throw new InvalidSystemClock("Clock moved backwards. Refusing to generate id for %d milliseconds" .format(lastTimestamp - timestamp)); } lastTimestamp = timestamp genCounter.incr() ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence } protected def timeGen () : Long = System.currentTimeMillis()protected def tilNextMillis (lastTimestamp: Long) : Long = { var timestamp = timeGen() while (timestamp <= lastTimestamp) { timestamp = timeGen() } timestamp }
最后一段逻辑的位操作比较多,但是如果熟练使用位运算操作符,其实逻辑并不复杂,这里可以画个图推演一下:
四个部分的整数完成左移之后,由于空缺的低位都会补充了0
,基于按位或的特性,所有低位只要存在1
,那么对应的位就会填充为1
,由于四个部分的位不会越界分配,所以这里的本质就是:四个部分左移完毕后最终的数字进行加法计算 。
Snowflake算法改良 Snowflake
算法有几个比较大的问题:
低并发场景会产生连续偶数,原因是低并发场景系统时钟总是走到下一个毫秒值,导致序列号重置为0
。 依赖系统时钟,时钟回拨会拒绝生成新的ID
(直接抛出异常)。 Woker ID
和Data Center ID
的管理比较麻烦,特别是同一个服务的不同集群节点需要保证每个节点的Woker ID
和Data Center ID
组合唯一。这三个问题美团开源的Leaf
提供了解决思路,下图截取自com.sankuai.inf.leaf.snowflake.SnowflakeIDGenImpl
:
对应的解决思路是(不进行深入的源码分析,有兴趣可以阅读以下Leaf
的源码):
序列号生成添加随机源,会稍微减少同一个毫秒内能产生的最大ID
数量。 时钟回拨则进行一定期限的等待。 使用Zookeeper
缓存和管理Woker ID
和Data Center ID
。 Woker ID
和Data Center ID
的配置是极其重要的,对于同一个服务(例如支付服务)集群的多个节点,必须配置不同的机器ID
和数据中心ID
或者同样的数据中心ID
和不同的机器ID
(简单说就是确保Woker ID
和Data Center ID
的组合全局唯一 ),否则在高并发的场景下,在系统时钟一致的情况下,很容易在多个节点产生相同的ID
值,所以一般的部署架构如下:
管理这两个ID
的方式有很多种,或者像Leaf
这样的开源框架引入分布式缓存进行管理,再如笔者所在的创业小团队生产服务比较少,直接把Woker ID
和Data Center ID
硬编码在服务启动脚本中,然后把所有服务使用的Woker ID
和Data Center ID
统一登记在团队内部知识库中。
自实现简化版Snowflake 如果完全不考虑性能的话,也不考虑时钟回拨、序列号生成等等问题,其实可以把Snowflake
的位运算和异常处理部分全部去掉,使用Long.toBinaryString()
方法结合字符串按照Snowflake
算法思路拼接出64 bit
的二进制数,再通过Long.parseLong()
方法转化为Long
类型。编写一个main
方法如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 public class Main { private static final String HIGH = "0" ; private static final long EPOCH = 1596211200000L ; public static void main (String[] args) { long workerId = 1L ; long dataCenterId = 1L ; long seq = 4095 ; String timestampString = leftPadding(Long.toBinaryString(System.currentTimeMillis() - EPOCH), 41 ); String workerIdString = leftPadding(Long.toBinaryString(workerId), 5 ); String dataCenterIdString = leftPadding(Long.toBinaryString(dataCenterId), 5 ); String seqString = leftPadding(Long.toBinaryString(seq), 12 ); String value = HIGH + timestampString + workerIdString + dataCenterIdString + seqString; long num = Long.parseLong(value, 2 ); System.out.println(num); } private static String leftPadding (String value, int maxLength) { int diff = maxLength - value.length(); StringBuilder builder = new StringBuilder(); for (int i = 0 ; i < diff; i++) { builder.append("0" ); } builder.append(value); return builder.toString(); } }
然后把代码规范一下,编写出一个简版Snowflake
算法实现的工程化代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 public interface PrimaryKeyGenerator { long generate () ; } public class SimpleSnowflake implements PrimaryKeyGenerator { private static final String HIGH = "0" ; private static final long MAX_WORKER_ID = 31 ; private static final long MIN_WORKER_ID = 0 ; private static final long MAX_DC_ID = 31 ; private static final long MIN_DC_ID = 0 ; private static final long MAX_SEQUENCE = 4095 ; private final long workerId; private final long dataCenterId; private final long epoch; private long sequence = 0L ; private long lastTimestamp = -1L ; public SimpleSnowflake (long workerId, long dataCenterId, long epoch) { this .workerId = workerId; this .dataCenterId = dataCenterId; this .epoch = epoch; checkArgs(); } private void checkArgs () { if (!(MIN_WORKER_ID <= workerId && workerId <= MAX_WORKER_ID)) { throw new IllegalArgumentException("Worker id must be in [0,31]" ); } if (!(MIN_DC_ID <= dataCenterId && dataCenterId <= MAX_DC_ID)) { throw new IllegalArgumentException("Data center id must be in [0,31]" ); } } @Override public synchronized long generate () { long timestamp = System.currentTimeMillis(); if (timestamp < lastTimestamp) { throw new IllegalStateException("Clock moved backwards" ); } if (lastTimestamp == timestamp) { sequence = sequence + 1 ; if (sequence == MAX_SEQUENCE) { timestamp = untilNextMillis(lastTimestamp); sequence = 0L ; } } else { sequence = 0L ; } lastTimestamp = timestamp; String timestampString = leftPadding(Long.toBinaryString(timestamp - epoch), 41 ); String workerIdString = leftPadding(Long.toBinaryString(workerId), 5 ); String dataCenterIdString = leftPadding(Long.toBinaryString(dataCenterId), 5 ); String seqString = leftPadding(Long.toBinaryString(sequence), 12 ); String value = HIGH + timestampString + workerIdString + dataCenterIdString + seqString; return Long.parseLong(value, 2 ); } private long untilNextMillis (long lastTimestamp) { long timestamp; do { timestamp = System.currentTimeMillis(); } while (timestamp <= lastTimestamp); return timestamp; } private static String leftPadding (String value, int maxLength) { int diff = maxLength - value.length(); StringBuilder builder = new StringBuilder(); for (int i = 0 ; i < diff; i++) { builder.append("0" ); } builder.append(value); return builder.toString(); } public static void main (String[] args) { long epoch = LocalDateTime.of(1970 , 1 , 1 , 0 , 0 , 0 , 0 ) .toInstant(ZoneOffset.of("+8" )).toEpochMilli(); PrimaryKeyGenerator generator = new SimpleSnowflake(1L , 1L , epoch); for (int i = 0 ; i < 5 ; i++) { System.out.println(String.format("第%s个生成的ID: %d" , i + 1 , generator.generate())); } } } 第1 个生成的ID: 6698247966366502912 第2 个生成的ID: 6698248027448152064 第3 个生成的ID: 6698248032162549760 第4 个生成的ID: 6698248033076908032 第5 个生成的ID: 6698248033827688448
通过字符串拼接的写法虽然运行效率低,但是可读性会比较高,工程化处理后的代码可以在实例化时候直接指定Worker ID
和Data Center ID
等值,并且这个简易的Snowflake
实现没有第三方库依赖,拷贝下来可以直接运行。上面的方法使用字符串拼接看起来比较低端,其实最后那部分的按位或,可以完全转化为加法 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class Main { private static final long EPOCH = 1596211200000L ; public static void main (String[] args) { long workerId = 1L ; long dataCenterId = 1L ; long seq = 4095 ; long timestampDiff = System.currentTimeMillis() - EPOCH; long num = (long ) (timestampDiff * Math.pow(2 , 22 )) + (long ) (dataCenterId * Math.pow(2 , 17 )) + (long ) (workerId * Math.pow(2 , 12 )) + seq; System.out.println(num); } }
这样看起来整个算法都变得简单,不过这里涉及到指数运算和加法运算,效率会比较低。
小结 Snowflake
算法是以高性能为核心目标的算法,基于这一点目的巧妙地大量使用位运算,这篇文章已经把Snowflake
中应用到的位运算和具体源码实现彻底分析清楚。最后,基于Twitter
官方的Snowflake
算法源码,修订出了一版Java
实现版本,并且应用前面提到的改良方式,修复了低并发场景下只产生偶数的问题,并且已经应用于生产环境一段时间 ,代码仓库如下(代码没有任何第三方库依赖,拷贝出来就直接可用):
Github
:https://github.com/zjcscut/framework-mesh/tree/master/java-snowflake
参考资料:
(本文完 c-3-d e-a-20200809 封面图来源于国漫《灵笼》)