前提

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位，则