深入剖析 snowflake 算法
前言
约 7~8 年之前，针对分布式 UUID 的解决方案我还是更倾向于淘系的多机 SequenceId 方案，毕竟在那个年代，既要解决全局 UUID 生成时的唯一性和连续性，同时又要考虑生成性能、内存占用率等诸多问题，市面上几乎也没有什么太好的解决方案。但随着 14 年 twitter 的 snowflake 算法问世，多机 SequenceId 方案的弊端开始被无限放大，复杂的算法、冗长的核心逻辑、繁琐的事务控制，以及线上存储系统面临的单点风险都是无法逃避的事实。
snowflake 算法的基本原理
为什么 twitter 会命名为 snowflake 算法？不重要，你高兴怎么叫就怎么叫，心情好，你甚至可以实现个叫做 fingerprint 的算法变种，名字是其次，重要的是名字可以表述 ID 在分布式全局环境中的唯一性。大家思考下，生成 UUID 最简单的做法是什么？如果抛开业务耍流氓，时间戳就是一个典型的 UUID；其次 Java 的UUID.randomUUID()也是一种有效的技术手段，只是在大部分情况下，我们并不会太在意 ID 的碰撞概率，位长问题才是主要矛盾。那么理想中的 UUID 应该具备哪些特征？唯一性、连续性、位长短，并且 ID 生成器也应该同时具备高性能和高容错性，否则就算生成的 UUID match 业务需求，低效的生成率，也足以在峰值流量场景下拉长 RT 时间，拖垮整个系统，导致雪崩效应。
如图 1 所示，snowflake-id 是一个由 u8/64bit long 类型构成的 UUID，整体被分成了 5 部分，二进制的最高位为 sign-bit，这个 1bit 空间不对外开放，缺省为 0，也就是正数，而真正可用的数据空间只有 63bit。符号位的右边是一个占 41bit 的 timestamp 空间，但这个数据空间并非是用来存储广义上的 timestamp，具体下个小节会重点进行分析；排列在 timestamp 空间右边的就是 5bit 的 idc-id 和 5bit 的 worker-id 组合，用以区分不同的 IDC 机房；最后的 12bit 数据空间则用于存储 sequence-id，它的递增规则与 timestamp 的数据空间相对应。
timestamp 数据空间与 snowflake-id 可用率问题
41bit 的 timestamp 空间是一个用于存储 timemillis 的数据空间，但它并不是广义上我们所理解的那样，用于存储 current-timemillis。41bit 能够存储的最大十进制数为2199023255551，也就是说，2199023255551ms所对应的真实时间为2039-09-07 23:47:35，假设当前北京时间为 2022 年，那所生成的 snowflake-id 则只能支撑≈17 年左右？显然不能这么理解，虽然 41bit 的 timestamp 空间所能够存储的最大十进制数为2199023255551，但我们可以通过下述算法来有效提升 snowflake-id 的可用率：
一般而言，我们会结合具体的业务场景设定一个 init-timestamp 时间（比如：业务的上线时间），假设 init-timestamp 时间为 2000 年，timestamp 数据空间所储存的 timemillis 就是当前时间-初始时间的毫秒差值，也就是有≈47 年可用，而2199023255551ms所能表示的最大可用率(2199023255551ms/1000/60/60/24/365)≈69 年。
sequence 数据空间的递增策略
之前我曾经提及过，低位的 12bit 数据空间用于存储 sequence-id，它的递增规则与 timestamp 的数据空间相对应，也就是说，同一个单位时间内（ms），最大能够连续生成 4095 个 sequence-id。如果sequence-id>4095时，ID 生成器则会产生自旋，直至进入到下一个时间区间，如下所示：
那么在 snowflake 算法中应该如何判断 sequence-id 是否已经递增到所允许的最大值了？看过 snowflake 源码的同学应该都清楚，上述代码中，sequence = (++sequence) & MAX_SEQUENCE就是关键，而对于位运算功底不好的同学来说，似乎看不懂这段代码。简单来说，12bit 的最大十进制数是4095，所对应的二进制原码为1111-1111-1111，假设 sequen-id 递增到 4096 后，其二进制原码为1-0000-0000-0000，&运算的运算法则为两位比较，如果都为 1 则为 1，反之为 0，所以最终结果如下所示：
如果 sequence-id 的数据区间在 0~4095 之间，那么 &4095 后的结果都是其自身。而当 sequence-id 为 0 时（sequence-id>4095），就表示同一单位时间内（ms）的可用 sequence 已耗尽，需要自旋等待下一个时间区间，如下所示：
这里有些同学可能会产生疑问，如果某些特殊的业务场景需要的snowflake-id>4095/ms时应该怎么办呢？如果业务上真的有这么大的并发量，那么我们唯一能做的就是对原生 snowflake 算法的数据结构进行变更，比如：将 10bit 的 IDC 机房编码缩短为 5bit，腾出更多的空间给 sequence，假设将 sequence 空间变更为 17bit 后，最大并发将支持≈13w+/ms，但你真的有这样的业务体量吗？无论是淘系还是支付宝，我至今都从未见过如此惊人的并发量。
如图 2 所示，sowflake 算法的整体流程还是比较简单和清晰的。在生成 snowflake-id 之前，会首先获取 last-timemillis，如果current-timemillis<last-timemillis时，则表示触发了时钟回拨（即：当前时间<上一个 sowflake-id 的生成时间）；反之就判断是否是在同一单位时间内（ms），如果在同一单位时间内就递增 sequence，当 sequence 结果为 0 时，就代表 4095 个 sequence 已耗尽，需要自旋等待进入下一个时间区间，并记录 last-timemillis 为本次 snowflake-id 的生成时间，最后生成 snowflake-id。
大家思考下，如果在实际的开发过程中我们使用 snowflake-id 作为 order-id，那么别人是否能够通过抓包 order-id 来估算你的业务体量？
原生的 snowflake 算法会存在这样的可能性，但我们规则是死的，人是活的，我们可以通过变更 sequence 的递增规则来解决这个问题。首先 snowflake-id 仅仅只是相对有序，且 timestamp 数据空间内存储的并非是广义上的 current-timemillis，别人无法解析到具体时间；上述代码示例中，sequence 并不是从 0 开始递增，而是基于随机值，这样一来，别人自然也就无法猜测到你单位时间内的业务体量。
snowflake 算法核心
snowflake 算法的本质，就是在计算好各个数据空间所需的数值后，再根据 snowflake 的固定数据结构进行相应位的位移拼接即可，如下所示：
假设 timestamp 数据空间所存储的十进制数据为 1652962585889，转换为二进制数后左移可用位数(63)-41bit=22bit，如下所示：
假设 idc-id 的十进制数据为 10，转换为二进制数后左移可用位数(63)-(41bit+5bit)=17bit，如下所示：
假设 worker-id 的十进制数据为 10，转换为二进制数后左移可用位数(63)-(41bit+10bit)=12bit，如下所示：
假设 sequence-id 的十进制数据为 4095，转换成二进制数后不再需要位移，只需跟之前的结果进行拼接即可，如下所示：
后记
有一点大家需要明确，结合历史经验来看，任何的 UUID 算法都不可能保证 ID 绝对不会产生碰撞，哪怕是 snowflake 算法也不例外，而我们唯一能做的就是尽最大努力降低碰撞概率发生的可能性。最后，关于 snowflake 算法的 Java 和 Scala 实现，大家可以参考此处。而位运算功底较差的同学，建议使用此工具来提升你的位运算能力。
至此，本文内容全部结束。如果在阅读过程中有任何疑问，欢迎在评论区留言参与讨论。
推荐文章：
版权声明: 本文为 InfoQ 作者【九叔】的原创文章。
原文链接:【http://xie.infoq.cn/article/128066fc447acbaffa4b2e2dc】。文章转载请联系作者。
twitter:@gao_xianglong 2020.03.25 加入
前「阿里巴巴」高级技术专家，ArchSummit&GIAC架构峰会讲师，《超大流量分布式系统架构解决方案》、《人人都是架构师》、《Java虚拟机精讲》等畅销书作者
评论