放弃snowflake-我们重新设计了新的分布式ID生成方案
本篇博客的视频教程首发于 Youtube:科技小飞哥,加入 电报粉丝群 获得最新视频更新和问题解答。
背景
在之前的文章中,我们讲了分布式ID生成方案-snowflake算法
。这也是我们的生产系统过去几年一直使用的分布式ID生成方案。
雪花算法(Snowflake)
有着很多的优点,适用于大多数的业务场景。
有兴趣的可以查看我之前的文章。 https://www.techxiaofei.com/
可是随着我们业务的发展壮大,这个分布式ID生成方案对我们的业务来说已经有了一定的限制,所以我们在考虑一种新的方案来替代snowlfake算法
。
避免有些人不是很了解snowflake算法,这里简单描述下:
snowflake算法
雪花算法(Snowflake)是twitter公司内部分布式项目采用的ID生成算法,开源后广受国内大厂的好评,在该算法影响下各大公司相继开发出各具特色的分布式生成器。
Twitter的snowflake分布式ID的算法是目前广泛使用的分布式ID算法,尽管有很多变种,比如位数的不同,时间片大小不同、node bit数放在最后等各种变种,但是主要思想还是来自于snowflake的思想。
snowflake算法采用64bit存储ID, 最高位备用,暂时不使用。接下来的41 bit做时间戳
,最小时间单位为毫秒
。再接下来的10 bit做机器ID
(worker id),然后最后12 bit
在单位时间(毫秒)递增。
-
41 bit表示时间戳
大约可以使用69年(2^41 -1), 为了尽可能的表示时间,时间戳可以从第一次部署的时候开始计算,比如2020-02-02 00:00:00, 这样可以使用69年。 -
10 bit区分机器
所以可以支持1024台机器。 你也可以把10bit分成两部分,一部分做数据中心的ID,一部分做机器的ID,比如55分的话,可以支持32个数据中心,每个数据中心最多可以支持32台机器。 -
12 bit自增值
可以表示4096的ID,也就是说每台机器每毫秒最多产生4096个ID,这是它的最大性能。
snowflake算法对我们业务的限制
对我们来说,限制就是10 bit-工作机器id
,也就是每个服务只能支持1024台工作机器。在服务规模不大的情况下,snowflake算法是一个相当优秀的算法,但是我们的业务规模发展太快,导致1024台机器成了我们的限制。
可能你要问了:1024台机器都成了限制,你们得有多大的流量啊?
这不是snowflake算法的问题,是因为我们的服务(Service)是最底层的服务,不允许依赖任何外部服务,所以我们的分布式ID生成算法
就在我们的Service里面生成。就是它是我们服务的一部分,也就是我们服务的机器数量,取决于整个服务业务的规模。
我们当时就想了两种方案:
- 把ID生成拆分成独立的服务。
- 调整
工作机器id
的bit数量。
作为最底层的服务,我们并不想依赖任何外部服务,所以方案1
被我们排除了。
方案2
的话,由于41位时间戳
本身是一个有意义的数据,为了兼容性和数据本身的意义考虑,我们不想动它,所以只能动最右边的12bit-序列号
。但是考虑到下次可能继续增长,我们最终决定一劳永逸,直接废除机器id
的设定。
这就是我们需要找一些替代方案的原因。
但是我不否认,上述的方案是可行的。
数据库方案
数据库的方案是最简单也是最容易想到的唯一ID生成方案。
数据库本身生成的ID是自增唯一的,用来做分布式唯一ID很合适。但是我们为了与之前的snowflake方案保持一致,同时也为了让生成的唯一ID不容易被算出来。我们保留前面41位时间戳
不变,数据库的自增ID只做为后边的22位,来代替10bit-工作机器id
+12bit-序列号
这样每次我们插入ID的时候
last_insert_id = INSERT INTO `unique_id_tab` values (NULL)
unique_id = ms<<22 + last_insert_id%2^22
这种ID的实现完全不依赖于服务器的节点数量。每次需要生成ID,就INSERT一次获得LAST_INSERT_ID
即可。
这种方案的优缺点都很明显。
优点:
- 非常简单,利用现有数据库系统的功能实现,成本小。
缺点:
- 强依赖DB,当DB异常时整个系统不可用,属于致命问题。
- ID生成的性能瓶颈限制在单台MySQL的读写性能。在我们的测试机器上测试大概有20K的QPS, 对于小业务还可以,但是对于高并发的业务来说,完全不够。
多台数据库方案
对于单台MySQL性能问题,很容易想到可用如下方案解决
在分布式系统中我们可以多部署几台数据库的实例,每台实例设置不同的初始值,且步长和数据库实例数相等。
|
|
我们设置10台MySQL来进行ID生成,那么整体的QPS就可以增加10倍。
这个时候我们测试一下插入数据:
|
|
这样假设我们的服务器有M台,数据库有N台,那么就是M*N的连接。每次要生成ID的时候就随机访问其中的一台数据库实例,就把所有流量分散。能支撑更多的QPS了。
这种架构的确可以支撑更多的ID生成的QPS,但是也有一些缺点:
- 系统水平扩展比较困难,比如定义好了步长和机器台数之后,如果要添加机器该怎么做?假设现在是10台数据库实例,这个时候需要扩容机器一台就比较复杂了。
- 随着业务的增长,数据库压力还是很大,每次获取ID都得读写一次数据库,只能靠堆机器来提高性能。
由于过于复杂的设计,我们就排除了这种方案,就考虑是否有其他方案。
DB+Buffer方案
综合对比上述几种方案,每种方案都不完全符合我们的要求。于是我们最终考虑了一种方案
首先我们依旧使用DB的方案,只是不是每次生成ID都需要访问DB,比如我们把ID分成
是不是跟snowflake算法有点类似,只不过我们不用固定的机器ID
,因为会限制服务器机器的数量。而是用了数据库自增ID,不与机器相绑定,每台机器自己去申请自增的ID。
Buffer的作用是什么呢,就是为了不要每次都去数据库申请ID,每一次申请ID都可以产生一个buffer以供下次使用的时候递增buffer的值,下次生成ID的时候就不需要访问DB了。
问题:
- 数据库自增ID不会超过16位吗? – 当然会,我们是使用
auto_increment_id%2^16
。这样用完之后就可以重新生成。 - 这样不会导致生成的唯一ID重复吗?– 我们最前面有一个毫秒级别的时间戳,如果一毫秒能走完一圈的话是可能重复的。
QPS=2^16*2^6*1000 = 4 Billion
。我们整个系统的QPS也才10M左右,更何况需要生成ID的QPS就更低了。大概100K。我们假设他不会重复。
我们继续使用最简单的unique_id_tab
作为数据库的自增ID表。
6位的Buffer是在内存中递增的,不依赖DB。
type BufferPool struct {
inited bool // 初始化
ms int64 // 当前的获取ID的时间戳
last_insert_id int64 // 上次从数据库取出的值
buffer int64 // buffer的值,[0, 2^6-1]
}
流程:
- 第一次需要生成ID的时候,DB中拿出一个值后,我们就把buffer置为0。
- 每次需要生成ID的时候,把buffer加1。
- 当
buffer == 2^6-1
的时候,用完当前的buffer。 - 下次继续从DB拿出一个值,把buffer重置为0。
这样我们的ID就为:
unique_id = ms<<22 + last_insert_id%2^16 + buffer
ms是为了与之前的snowflake算法的timestamp保持一致 (ms的初始值时第一次部署服务器的时间,所以可以使用69年)。
// 可以设置成系统第一次上线的时间,单位:毫秒。占用41位,可以使用69年。
var minTS int64 = 1288834974657
// 从设定的时间戳到现在经历的毫秒数
ms := time.Since(minTS).Nanoseconds() / 1000000
如果你从其他的算法中迁移过来,可以取出之前的算法的max_id值,
初始的时间戳可以设置为minTS = current_timestamp - max_id>>22 + 1
。这样的话,随着current_timestamp一直在增大,你新生成的最小值一定比之前的最大值大。
优点:
- 可以很方便的线性扩展,性能完全能够支撑大多数业务场景。
- 生成的ID满足上述数据库存储的主键要求。(我们需求特殊加上时间戳,保证趋势递增以及带有有用的时间戳信息)。
- 容灾性高:服务内部有缓存,即使DB宕机,短时间内ID生成器仍能正常对外提供服务。
缺点:
- 每次DB访问的时候可能产生TP999数据波动大,当缓存使用完时,TP999数据会出现偶尔的尖刺。
- DB宕机会造成整个系统不可用。
双buffer优化
对于第一个缺点,我们做了一些优化,简单的说就是:
不要每次都用完Buffer再去数据库取下一个自增ID
,二是在Buffer用到一定程度就开始异步取下一个自增ID
, 提前缓存,做到ID生成完全在内存中操作,避免中途因为访问数据库导致的延迟抖动。
- 初始化的时候的确只有一个
BufferPool current
- 当buffer指针走到一半(31)的时候,异步执行DB写入操作,拿到新的last_insert_id,把数据写入
BufferPool next
- 当buffer指针走完的时候,内存切换buffer,使
BuffferPool current = next
- 当buffer指针走到一半的时候,继续上述DB写入操作,创建新的
BufferPool next
采用双buffer的方式,每个服务的实例内部有两个号段缓存区BufferPool
。我们初始启动时会初始化一个缓存区,在第一个缓存区使用一半时候,会异步生成第二个缓存区。当前缓存区数据用完之后,把第二个缓存区挪到第一个缓存区继续使用,循环往复,这样保证DB的操作一直都是异步的,平时生成ID的时候都是内存操作,极大提升了性能。
后续
当然了,分布式ID生成方案有很多,各个大厂都有自己设计的方案:美团(Leaf)
、滴滴(Tinyid)
、百度(uid-generator)
等等。
我们新设计的方案也不一定是最好的,但是极大的解决了我们当前服务的一些限制。
当然另一种解决方案就是把ID生成器独立成服务,这样使用snowflake算法
的1024台实例也足够绝大多数的场景使用了。
不过双buffer的异步方案,尽可能的降低了DB的访问导致的生成过慢的问题,也算是一个比较好的解决方案。
<全文完>