分布式ID生成算法snowflake介绍及Go语言实现

snowflake是什么

snowflake单词原意为雪花,是twitter开源的一种分布式ID生成算法。该算法可以保证在不借助第三方服务或者说工具的情况下,在多台机器上持续生成保证唯一性的64位整型ID。

snowflake ID的组成

snowflake将ID的64位划分为四块区域,分别填入的是当前服务实例的数据中心ID,节点ID,时间戳,以及相同时间戳下的递增序号。

以下是snowflake原始算法中,各字段的顺序以及所占的位数:

ID组成图

小提示,在生产环境,使用snowflake的思想生成分布式ID时,这些字段所占的位数可以根据自身业务灵活调整。本文如无特殊说明,都是针对snowflake原始算法进行讲解。

数据中心ID和节点ID

不同的服务实例间,使用不同的数据中心ID和节点ID,可以保证生成的ID不重复。

从该算法使用数据中心ID加节点ID(而不是单个服务实例ID)的方式决定服务实例的唯一性,也可以看出,该算法设计之初是一个非常面向具体业务场景的算法。

数据中心ID和节点ID分别占5位。即整个系统最多可以有32个数据中心,每个数据中心最多可以有32个节点。为什么数据中心ID和节点ID是5位?额,应该也是twitter根据当时的业务拍脑袋拍的。

那么数据中心ID和节点ID怎么生成呢?这点不由snowflake负责,也即这两个ID在多个服务实例之间不重复是由snowflake的调用方保证的。比如一种简单的方式是直接使用静态配置,这种方式适用于节点数量比较少且相对固定的情况下。

时间戳

如前文图中展示,snowflake使用42位存储时间戳。

我们平时所说的UNIX时间戳,指的是从1970年1月1号0点到现在所经过的时间。如果单位是毫秒,需要使用64位整型存储。

由于在snowflake算法中,只需要保证时间戳随时间递增即可,所以snowflake中的时间戳是使用UNIX时间戳减去一个基准时间,这个基准时间在原版代码中是1288834974657,也即2010/11/4 9:42:54.657。你也可以换种方式理解,即从2010年11月4号xxx这个基准时间点到现在所经过的时间。

减去自定义的基准时间后,时间戳比UNIX时间戳小了很多,snowflake使用得到的时间戳的低42位作为ID的一部分(即ID的高42位)。如下图所示:

时间戳取值图

时间戳可能存在的问题

首先,时间戳随着系统时间增长,当时间戳的第42位增长到1时,ID的最高位也将变为1。由于snowflake默认使用有符号64位整型,最高位为符号位,这将导致生成的ID变为负数。

通过如下公式(1<<41) / 1000 / 60 / 60 / 24 / 365计算,可知道在基准时间上(snowflake默认的基准时间是2010/11/4)再过69.7年,将出现ID为负数的情况。

这里展开说明下,如果想要生成的ID永远不为负数,可以保持ID的最高位始终为0,其他的字段减少1位,比如说时间戳只使用41位。这样时间戳出现翻转归零的时长缩短1倍,大概为35年,基本上是可接受的。你可能会说,69.7年已经足够长啦,到出现负数的时候我早退休了,哪管它洪水滔天。但是假设你要设计一个32位的分布式ID生成器呢?此时你必然需要考虑哪些字段可以缩短,时间戳多久出现翻转(也即ID可能翻转)不影响业务。

第二,假如单台机器上,获取当前时间的方法出现时间回退,那么可能出现ID重复的情况。

第三,假如服务重启,重启后时间戳没变(即1毫秒内重启成功),那么此时snowflake丢失了重启前当前时间戳的递增序号,递增序号重新从0开始,也可能出现和重启前生成的ID重复的情况。

最后一点值得注意的是,一个服务上线后,基准时间点不应该随意修改。避免造成时间戳回退。

递增序号

如前文图中展示,snowflake使用12位存储递增序号。

为什么在时间戳的基础之上,还需要递增序号?因为即使是在单个服务实例中,我们也可能需要在1毫秒内生成多个ID,这种情况下,同1毫秒下的seq会从0开始顺序递增。12位的seq范围为[0, 4095],如果1毫秒内生成的ID数量超过4096怎么办呢,snowflake会阻塞直到时间戳更新后,再生成可用的ID返回给调用方。相关代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
now = time.Now().UnixNano() / 1e6

// 时间戳回退,返回错误
if now < n.lastTs {
return -1, ErrGen
}

// 时间戳相同时,使用递增序号解决冲突
if now == n.lastTs {
n.seq = (n.seq + 1) & n.seqMask
// 递增序号翻转为 0,表示该时间戳下的序号已经全部用完,阻塞等待系统时间增长
if n.seq == 0 {
for now <= n.lastTs {
now = time.Now().UnixNano() / 1e6
}
}
} else {
n.seq = 0
}
n.lastTs = now

完整代码见:https://github.com/q191201771/naza/blob/master/pkg/snowflake/snowflake.go

snowflake 1毫秒可产生多少ID?

32(5位数据中心ID) * 32(5位节点ID) * 4096(递增序号) = 4194304

所生成ID的特点

单个服务实例生成的ID是递增的;多个服务实例生成的ID,受限于系统时间不一致,或者是节点ID的大小,可能出现整体ID不递增的情况。

总结

好了,至此,snowflake算法就基本介绍完毕了。算法的实现部分十分简单,不到100行代码,基本上就是一些位操作。

感兴趣的可以看看我写的一份Go语言实现:snowflake.go,在twitter原始scala实现版本的基础上,额外支持配置所有的字段所占的位数(比如支持将数据中心ID所占位数设置为0,从而只使用节点ID),支持配置基准时间,支持配置是否永远不返回负数ID,支持并发调用。

twitter放在github上的原始版本,master分支的代码已经删了,只能在release下载老版本的源码压缩包。

最后,感谢阅读,如果觉得文章还不错,可以给我的github项目naza来个star哈。该项目是我学习Go时写的一些轮子代码集合,后续我还会写一些文章逐个介绍里面的轮子以及一些写Go代码的技巧。

naza项目地址: https://github.com/q191201771/naza

naza的其他的文章:

原文链接: https://pengrl.com/p/20041/
原文出处: yoko blog (https://pengrl.com)
原文作者: yoko (https://github.com/q191201771)
版权声明: 本文欢迎任何形式转载,转载时完整保留本声明信息(包含原文链接、原文出处、原文作者、版权声明)即可。本文后续所有修改都会第一时间在原始地址更新。

fccxy

0%