10分钟拿下雪花算法

道阻且长，行则将至。请相信我，你一定会更优秀！

「 人人都听过的雪花算法，你真的推敲过吗？」

很多人听过或用过雪花算法，可是到底一个ID是如何计算出来的，没几个讲明白。别上来就跟我聊时钟回拨的问题，貌似你很懂一样，首先这是个算法，你先给我写个代码我看看？大牛请绕道，文章还是比较基础的。

技术人要对自己写的每一行代码负责，静下心来，我带你吃透雪花算法。关于分布式ID的文章有很多，你可以自己去查阅，此处我们不再赘述，本文只聊雪花算法。

目录

一、为啥叫雪花？

二、技术设计点剖析

1、技术背景

a. 我们希望一个id有以下2个特性足以：

b. 我们希望id服务有以下几个特点：

c. 综上，雪花算法的id由以下部分组成，完美匹配我们想要的规则：

d. 为啥不用纳秒？纳秒不是更精确吗，更不容易冲突吗？

2、twepoch 这个是干嘛的？

a. 那这个时间起啥作用？我们用的时候，这个时间写什么呢？

3、假如同一毫秒内，12个bit位的序列自增用完了，咋办？

4、如何判断序列号用完了？比大小吗？

5、计算 id的移位操作，是如何移位的？

6、生成的 id是单调递增、趋势递增的，会出现第2次拿到的比第1次拿到的id小吗？

7、生成 id的长度有多长？

8、这个 id的位数分配规则，自己能调整吗？

9、workerId怎么计算的？

三、安全问题

1、时钟回拨，即时间走着走着却倒回去了，如何解决？

2、新起的节点中，机器时间不对，那就压根不能提供服务，如何校正？

3、业务上，通过 getById 接口遍历能拿走多少越权数据？

4、友商是否可以解析你的 id大概计算出你的业务量？

一、为啥叫雪花？

世界上没有两片完全相同的雪花。任何一个技术设计，都值得有一个代号，都值得有自己的 slogan 并为之努力让它产生价值。

二、技术设计点剖析

雪花算法的源代码或者优秀代码示例有很多，但思想是一样的。我们这里不再一行行写代码，把里边的关键代码拿出来解析即可。这里提供一个代码示例：GitHub - Meituan-Dianping/Leaf: Distributed ID Generate Service，是美团的雪花算法代码实现（个人认为，美团开源出的代码真的很糟糕，内部一定是有另外一套，这个代码只是供大家参考的，不过不影响核心逻辑）。不管你有没有读过雪花算法代码，关键的代码我会在下边一个个剖析，读懂这些关键点，你就掌握了雪花算法。

1、技术背景

a. 我们希望一个id有以下2个特性足以：

• 纯正整数，占用内存小
• 递增，后一个大于前一个，且多节点时依然这样

第1条，纯数字好说，十进制，不出现字母就行。表中用 bigint表示，对应 java中用 long表示即可（均占用8个byte，64个bit）；

第2条，递增，那我们就想，什么是递增的？时间呀，时间天然是递增的；那多个节点在同一时间不就生成了相同的id了？再加上每个节点的唯一标识；同一时间内有多个请求咋办？再加上个序列号。就这点事。

b. 我们希望id服务有以下几个特点：

• 速度快，并发高
• 支持集群高可用HA
• 对业务系统无侵入，与业务系统松耦合

第1条，速度快：纯内存操作就可以，1s出100万，够用吧

第2条，可集群部署，且id也是递增状态，且单节点故障不影响集群HA

第3条，与业务系统松耦合，遵循业务各服务间调用方式即可，如业务系统服务调用使用Dubbo，此id服务也是Dubbo服务提供出去就好

c. 综上，雪花算法的id由以下部分组成，完美匹配我们想要的规则：

from: 美团leaf > 雪花算法（图中序列化应为12-bit）

分析：一共 64个bit，占用 8个字节，MySQL中是 bigint表示，java中是 long表示。注意是64个bit运算表示出一个数字，而不是几个段的数字用字符串拼接起来！

1个bit：第0位，符号位，0只要正数

41个bit：毫秒时间戳的数字，注意，和时间本身没有任何关系，只是借助了时间戳的数字。要理解清楚，很重要

10个bit：集群部署的话，为避免不同节点生成出相同的id，给每个节点一个唯一的数字标识

12个bit：同1毫秒内，同一节点，需要多个id的话，用序列号自增           

记住上边的位数分配，下边会逐个解析。

d. 为啥不用纳秒？纳秒不是更精确吗，更不容易冲突吗？

1. 你的业务并发需要纳秒级别的吗？1ms=1,000,000ns 我的业务并发连毫秒都到不了，然后我这里花时间、花内存去计算/存储纳秒？再说了，CPU主频2G的时钟周期算下来才 0.5ns，你上层建筑空想啥呢？毫无意义！
2. 我们一共只有64个bit，要做好几件事情呢，合理分配，省着点，留着bit给其他段用吧；
3. 所以，用毫秒ms时间戳表示足以；

2、twepoch 这个是干嘛的？

SnowflakeIDGenImpl#SnowflakeIDGenImpl

注意这行注释：

//Thu Nov 04 2010 09:42:54 GMT+0800 (中国标准时间)           

首先要清楚，这个时间对于我们来说，不是什么特殊的时间点，对我们来讲没有意义，或许是美团内部开始用雪花算法的时间点，我们不用研究这个时间。

a. 那这个时间起啥作用？我们用的时候，这个时间写什么呢？

上边说过用 41个bit表示时间戳，如果41个bit都占满，能表示的最大数字是：2199023255551，也就是 2199023255551个毫秒，这么多毫秒换算下来是大概 69年。

2199023255551 / 1000 / 60 / 60 / 24 / 365 ≈ 69
毫秒          / 秒   /分钟/ 小时 / 天 /  年           

也就是说，从这 41个bit都是0开始计算，到 41个bit都用满，需要 69年的毫秒时间戳才能填满。

可关键是不可能是从0开始呀，当前、现在的时间戳已经是一个很大的数字，那要是从现在开始算的话，能用多少年呢？（从0开始算只是理论值而已）

ok，继续看代码：

long id = ((timestamp - twepoch) << timestampLeftShift) | (workerId << workerIdShift) | sequence;           

为啥要减去 twepoch呢？(timestamp - twepoch)，如果不减这个 twepoch，问题就出现了，我们的 69年算的是从 0开始计算，但是假如我们是 2021-05-05才开始用的雪花算法，也就是说我们第一次使用的时候，就已经从 1620179006000时间戳开始了，不是从 0开始的，这个数字会浪费掉我的 41bit能表示的数据集中的一大部分，所以，必须要减，因为我才今天刚开始用，要从我的投产时间开始算的。如果不减我们会浪费掉多少呢？

1620179006000 / 1000 / 60 / 60 / 24 / 365 ≈ 51
毫秒          / 秒   /分钟/ 小时 / 天 /  年           

也就是说，本来我的 41个bit够我用 69年，但是刚一投产，就耗掉了51年的，剩下的只够我用 69-51=18年！

那么我们的这个 twepoch设置为多少呢？

比方说我们是 2021-05-05 上线，虽然是我们第一次使用的时间，但是我们不能这么设置，因为我们有业务历史数据，如果这个时间设置的不对，一定会遇到和现有id冲突的情况！可以设置一个公司成立或者业务线开始的时间，现在的时间和指定的时间点的差集耗掉的数字，我们认了。如果你是全新的开始，那完全可以设置为投产时间即可。

3、假如同一毫秒内，12个bit位的序列自增用完了，咋办？

12个bit能表示的最大数字是 4095，一共 4096个 [0, 4095]。

首先这个计算是在单个 JVM中计算的，按照美团的位数分配，即同一毫秒同一个worker最大能生成 4096个id，如果同一毫秒内，用完了，就等待到下一毫秒。

根据这个情况我们可以推理出，我们的批量获取的接口中，一定要加上数量限制，如果不限制，如果业务端传过来的是 Integer.MAX_VALUE，那就是说这一次调用需要等待的时间大概为：

2147483647 / 4096 ≈ 524287ms ≈ 524s ≈ 8.7min           

忽略调用时超时时间的问题，单纯说这个事情，CPU打满8分钟... 我这里建议批量接口中数量参数不要超过1000，甚至是100。什么样的业务场景中会一下子需要这么多id？业务上能处理过来吗？自己根据情况权衡下。

4、如何判断序列号用完了？比大小吗？

SnowflakeIDGenImpl#get

注意这行代码，很有意思：

sequence = (sequence + 1) & sequenceMask;           

sequenceMask为序列号的最大值，也就是序列号的 bit位都占满，都是1。那 sequence的值在正常增长情况下，任何一个 bit &1，都是1，怎么可能会出现 if (sequence == 0) 这个情况呢？

只有一种情况，就是超出了 bit位，这些 bit位已经装不下了，进位了。后面全是 0，所以 &出来结果成 0了。

5、计算 id的移位操作，是如何移位的？

long id = ((timestamp - twepoch) << timestampLeftShift) | (workerId << workerIdShift) | sequence;           

• (timestamp - twepoch) 是时间戳计算值，是long类型，64个bit。timestampLeftShift 是 12+10=22
• (timestamp - twepoch) << timestampLeftShift) 意思是将这 64个bit 左移22位，也就是原值的后 42个bit留下为有效的，这步完成后后面还有22个bit可用；
• (workerId << workerIdShift) 同理，这个是将 workerId 左移12位，12位为sequence的bit数，这步完成后后面还有12个bit可用，供sequence使用，sequence在末位，不用移位；
• ((timestamp - twepoch) << timestampLeftShift) | (workerId << workerIdShift)  | sequence 或运算，将时间戳和 workerID和sequence 的bit位进行计算、整合；
• 最后64个bit都整合完毕，为64个bit，8个byte

这个过程一定要搞明白，如果搞不明白先去复习下二进制运算，这个搞明白后可以帮你在业务上做一些别的事情的，比如 Zookeeper客户端的 auth位、redis的 bitmap等等。

6、生成的 id是单调递增、趋势递增的，会出现第2次拿到的比第1次拿到的id小吗？

基本不用考虑这个问题，生成的id是单调递增、趋势递增的。在极高并发的情况下，比如有两个workerID，1和2，前提是同一毫秒，先去2拿到的是大值，再去1拿到的是小值。这样计算的话，我们的并发至少得有2000了。

而且，如果出现了这种情况，不会影响业务使用的。可能会受影响的只有 InnoDB中 B+tree出现先小后大的效率差问题，不过有这个时间还是想想如何优化业务代码吧。如果单论技术的话，业务从我这里拿走的id，不一定怎么处理呢，可能会因为业务的原因，导致大的先进表了，小的后进去。所以不要假装在这里钻研技术，实际上业务代码写的一团糟。

为什么会影响 InnoDB的 B+tree？

比如叶子节点的某一个页中放了1000个主键id，首先，叶子节点中这些id是有序递增排列的，如果你后边来了一个小的，那就有可能之前的页中放不下了，需要重排列和分页。

7、生成 id的长度有多长？

最长19位！一定不会超！表中的主键id bigint(20)足够用！19位就是百亿亿了！

id的大小区间是：[1, 9223372036854775807]
最小的id是：1（twepoch为当前时间，并且workerId是0，序列号为1）
最大的id是：9223372036854775807（64个bit，第1个bit是0不变，其余位都占满，即是最大数，为9223372036854775807，也就是java Long类型的 MAX_VALUE）           

8、这个 id的位数分配规则，自己能调整吗？

当然可以，根据自己的业务情况调整。我们这儿将 bit位数分配调整为：1+42+5+16

• 1个bit 用来表示0，正数；
• 42个bit 用来表示毫秒时间戳；42个bit，最大是4398046511103，4398046511103个毫秒值，换算大约是 139年，也就是说从开始投入使用，可以使用 139年；
• 5个bit 用来表示workerID；最大31，也就是目前支持最多31个worker，一般小单位没有这个量级，如果有这种体量了，再调整也可以的，不用怕重复，因为时间戳是在高位，并且时间戳肯定是递增的，高位的大小决定了数字的大小；
• 16个bit 用来表示sequence，自增值；同一毫秒，同一 worker上，最多生成 65536个，也就是不考虑外界条件的话，单纯的这块，纯理论每秒可以出 65536000个id，大约是 6553万个。

9、workerId怎么计算的？

美团代码中，依赖 zookeeper + 本地文件缓存 双机制来生成 workerId，详细参考美团文章（GitHub - Meituan-Dianping/Leaf: Distributed ID Generate Service），讲的很清楚，这里不再赘述。

三、安全问题

上边的搞清楚之后再来看安全问题，1和2 的问题都可以参考美团文章（GitHub - Meituan-Dianping/Leaf: Distributed ID Generate Service），上边讲的很清晰了。这里不再赘述。

1、时钟回拨，即时间走着走着却倒回去了，如何解决？

2、新起的节点中，机器时间不对，那就压根不能提供服务，如何校正？

3、业务上，通过 getById 接口遍历能拿走多少越权数据？

首先雪花算法生成的id不是+1递增的，比依赖数据库的自增id要安全很多，另外还要看你的业务设计上，数据权限的控制是否存在漏洞。

4、友商是否可以解析你的 id大概计算出你的业务量？

不存在。首先有 twepoch存在，我不是时间戳，你解析出来只是数字，无法知道具体时间的；另外，后面的自增 sequence，不同的ms内，是随机生成的，不是都从0开始的，无法知道我的业务量；这两个条件加起来，足以保证 id的安全性。

【总结】本文我们主要聊了雪花算法到底是怎么算出来一个 id的。其实基本功是二进制运算，基础扎实的话，很快就可以 get到它的设计思想。但是，一定要清楚，所有的技术都是为了解决业务问题，也不存在一种技术设计完全适用所有公司的所有业务场景，具体使用的时候根据自己的情况进行调整，但就意味着你必须清楚原理，别瞎改。否则 3.25甚至更惨，哈哈。对自己的每一行代码负责是技术人的默认选项。

努力改变自己和身边人的生活。

特别希望本文可以对你有所帮助，原创不易，感谢你留个赞和关注，道阻且长，我们并肩前行！

转载请注明出处。感谢大家留言讨论交流。