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 没有二义性。
复杂来看就是这样：
* [+ 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 的值完成交流。
这里推演一下最后一条：
* [+ 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 )：
* [+ 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 办法验证一下：
public static void main(String[] args) {
System.out.println(-11 << 2); // -44
System.out.println(11 << 2); // 44
}
组合技巧
应用下面提到的三个位运算符，相互组合可以完成一些高效的计算方案。
计算n个bit能表示的最大数值：
Snowflake 算法中有这样的代码：
// 机器ID的位长度
private val workerIdBits = 5L;
// 最大机器ID -> 31
private val maxWorkerId = -1L ^ (-1L << workerIdBits);
这里的算子是 -1L ^ (-1L << 5L) ，整理运算符的顺序，再运用 64 bit 的二进制数推演计算进程如下：
(责任编辑：admin)