写点什么

深入剖析 snowflake 算法

作者:九叔
  • 2022 年 5 月 21 日
  • 本文字数:4173 字

    阅读完需:约 14 分钟

深入剖析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整体结构

如图 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 生成器则会产生自旋,直至进入到下一个时间区间,如下所示:

if (ct == lts) {    sequence = (++sequence) & MAX_SEQUENCE;    ct = 0 == sequence ? tilNextMillis() : ct;} else {    sequence = 0;}
复制代码

那么在 snowflake 算法中应该如何判断 sequence-id 是否已经递增到所允许的最大值了?看过 snowflake 源码的同学应该都清楚,上述代码中,sequence = (++sequence) & MAX_SEQUENCE就是关键,而对于位运算功底不好的同学来说,似乎看不懂这段代码。简单来说,12bit 的最大十进制数是4095,所对应的二进制原码为1111-1111-1111,假设 sequen-id 递增到 4096 后,其二进制原码为1-0000-0000-0000,&运算的运算法则为两位比较,如果都为 1 则为 1,反之为 0,所以最终结果如下所示:

&运算0-1111-1111-11111-0000-0000-0000================二进制原码:0-0000-0000-0000 | 十进制数:0
复制代码

如果 sequence-id 的数据区间在 0~4095 之间,那么 &4095 后的结果都是其自身。而当 sequence-id 为 0 时(sequence-id>4095),就表示同一单位时间内(ms)的可用 sequence 已耗尽,需要自旋等待下一个时间区间,如下所示:

private long tilNextMillis() {    var ct = System.currentTimeMillis();    while (ct <= lts) {        ct = System.currentTimeMillis();    }    return ct;}
复制代码

这里有些同学可能会产生疑问,如果某些特殊的业务场景需要的snowflake-id>4095/ms时应该怎么办呢?如果业务上真的有这么大的并发量,那么我们唯一能做的就是对原生 snowflake 算法的数据结构进行变更,比如:将 10bit 的 IDC 机房编码缩短为 5bit,腾出更多的空间给 sequence,假设将 sequence 空间变更为 17bit 后,最大并发将支持≈13w+/ms但你真的有这样的业务体量吗?无论是淘系还是支付宝,我至今都从未见过如此惊人的并发量

图2 snowflake算法整体流程

如图 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 来估算你的业务体量?

if (ct == lts) {    sequence = (++sequence) & MAX_SEQUENCE;    if (0 == sequence) {        sequence = (int) (Math.random() * 100);        ct = tilNextMillis();    }} else {    sequence = (int) (Math.random() * 100);}
复制代码

原生的 snowflake 算法会存在这样的可能性,但我们规则是死的,人是活的,我们可以通过变更 sequence 的递增规则来解决这个问题。首先 snowflake-id 仅仅只是相对有序,且 timestamp 数据空间内存储的并非是广义上的 current-timemillis,别人无法解析到具体时间;上述代码示例中,sequence 并不是从 0 开始递增,而是基于随机值,这样一来,别人自然也就无法猜测到你单位时间内的业务体量。

snowflake 算法核心

snowflake 算法的本质,就是在计算好各个数据空间所需的数值后,再根据 snowflake 的固定数据结构进行相应位的位移拼接即可,如下所示:

return ((ct - INIT_TIMESTAMP) << TIMESTAMP_SHIFT)        | (idcId << IDC_ID_SHIFT)        | (workerId << WORKER_ID_SHIFT)        | sequence;
复制代码

假设 timestamp 数据空间所存储的十进制数据为 1652962585889,转换为二进制数后左移可用位数(63)-41bit=22bit,如下所示:

十进制数1652962585889的二进制原码:0000-0000-0000-0000-0000-0001-1000-0000-1101-1100-0011-1111-0110-1101-0010-0001<< 22bit:0110-0000-0011-0111-0000-1111-1101-1011-0100-1000-0100-0000-0000-0000-0000-0000
复制代码

假设 idc-id 的十进制数据为 10,转换为二进制数后左移可用位数(63)-(41bit+5bit)=17bit,如下所示:

十进制数10的二进制原码:0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-1010<< 17bit:0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0001-0100-0000-0000-0000-0000
timestamp|idc-id0110-0000-0011-0111-0000-1111-1101-1011-0100-1000-0100-0000-0000-0000-0000-00000000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0001-0100-0000-0000-0000-0000===============================================================================结果如下:0110-0000-0011-0111-0000-1111-1101-1011-0100-1000-0101-0100-0000-0000-0000-0000
复制代码

假设 worker-id 的十进制数据为 10,转换为二进制数后左移可用位数(63)-(41bit+10bit)=12bit,如下所示:

十进制数10的二进制原码:0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-1010<< 12bit:0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-1010-0000-0000-0000
(timestamp|idc-id) | worker-id0110-0000-0011-0111-0000-1111-1101-1011-0100-1000-0101-0100-0000-0000-0000-00000000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-1010-0000-0000-0000===============================================================================结果如下:0110-0000-0011-0111-0000-1111-1101-1011-0100-1000-0101-0100-1010-0000-0000-0000
复制代码

假设 sequence-id 的十进制数据为 4095,转换成二进制数后不再需要位移,只需跟之前的结果进行拼接即可,如下所示:

十进制数4095的二进制原码:0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-1111-1111-1111
(timestamp|idc-id|worker-id) | sequence-id0110-0000-0011-0111-0000-1111-1101-1011-0100-1000-0101-0100-1010-0000-0000-00000000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-1111-1111-1111===============================================================================二进制原码结果如下:0110-0000-0011-0111-0000-1111-1101-1011-0100-1000-0101-0100-1010-1111-1111-1111十进制结果如下:6933027585845932031
复制代码

后记

有一点大家需要明确,结合历史经验来看,任何的 UUID 算法都不可能保证 ID 绝对不会产生碰撞,哪怕是 snowflake 算法也不例外,而我们唯一能做的就是尽最大努力降低碰撞概率发生的可能性。最后,关于 snowflake 算法的 Java 和 Scala 实现,大家可以参考此处。而位运算功底较差的同学,建议使用此工具来提升你的位运算能力。


至此,本文内容全部结束。如果在阅读过程中有任何疑问,欢迎在评论区留言参与讨论。



推荐文章:


发布于: 刚刚阅读数: 3
用户头像

九叔

关注

twitter:@gao_xianglong 2020.03.25 加入

前「阿里巴巴」高级技术专家,ArchSummit&GIAC架构峰会讲师,《超大流量分布式系统架构解决方案》、《人人都是架构师》、《Java虚拟机精讲》等畅销书作者

评论

发布
暂无评论
深入剖析snowflake算法_算法_九叔_InfoQ写作社区