[编程技术] 放弃snowflake-我们重新设计了新的分布式ID生成方案
作者:CC下载站 日期:2022-04-22 13:00:51 浏览:5 分类:编程开发
背景
在之前的文章中,我们讲了分布式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-序列号
1
2
3
4
create table `unique_id_tab` (
`id` BIGINT AUTO_INCREMENT,
PRIMARY KEY ( `id` )
)ENGINE=InnoDB DEFAULT CHARSET=utf8;
这样每次我们插入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性能问题,很容易想到可用如下方案解决
在分布式系统中我们可以多部署几台数据库的实例,每台实例设置不同的初始值,且步长和数据库实例数相等。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
create table `unique_id_1_tab` (
`id` BIGINT AUTO_INCREMENT,
PRIMARY KEY ( `id` )
)ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT=1;
create table `unique_id_2_tab` (
`id` BIGINT AUTO_INCREMENT,
PRIMARY KEY ( `id` )
)ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT=2;
...
create table `unique_id_10_tab` (
`id` BIGINT AUTO_INCREMENT,
PRIMARY KEY ( `id` )
)ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT=10;
set session auto_increment_increment=10; //设置步长为10,和数据库实例的数据相等。
mysql> SHOW VARIABLES LIKE 'auto_inc%';
+--------------------------+-------+
| Variable_name | Value |
+--------------------------+-------+
| auto_increment_increment | 10 |
| auto_increment_offset | 1 |
+--------------------------+-------+
我们设置10台MySQL来进行ID生成,那么整体的QPS就可以增加10倍。
这个时候我们测试一下插入数据:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
mysql> INSERT INTO `unique_id_1_tab` values (NULL);
Query OK, 1 row affected (0.00 sec)
mysql> INSERT INTO `unique_id_1_tab` values (NULL);
Query OK, 1 row affected (0.00 sec)
mysql> INSERT INTO `unique_id_1_tab` values (NULL);
Query OK, 1 row affected (0.00 sec)
mysql> select * from unique_id_1_tab;
+----+
| id |
+----+
| 1 |
| 11 |
| 21 |
+----+
3 rows in set (0.00 sec)
这样假设我们的服务器有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表。
1
2
3
4
create table `unique_id_tab` (
`id` BIGINT AUTO_INCREMENT,
PRIMARY KEY ( `id` )
)ENGINE=InnoDB DEFAULT CHARSET=utf8;
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的访问导致的生成过慢的问题,也算是一个比较好的解决方案。
<全文完>
猜你还喜欢
- 03-29 [编程相关] Winform窗体圆角以及描边完美解决方案
- 03-29 [前端问题] has been blocked by CORS policy跨域问题解决
- 03-29 [编程相关] GitHub Actions 入门教程
- 03-29 [编程探讨] CSS Grid 网格布局教程
- 10-12 [编程相关] python实现文件夹所有文件编码从GBK转为UTF8
- 10-11 [编程算法] opencv之霍夫变换:圆
- 10-11 [编程算法] OpenCV Camshift算法+目标跟踪源码
- 10-11 [Python] python 创建 Telnet 客户端
- 10-11 [编程相关] Python 基于 Yolov8 + CPU 实现物体检测
- 03-15 [脚本工具] 使用go语言开发自动化脚本 - 一键定场、抢购、预约、捡漏
- 01-08 [编程技术] 秒杀面试官系列 - Redis zset底层是怎么实现的
- 01-05 [编程技术] 《Redis设计与实现》pdf
取消回复欢迎 你 发表评论:
- 精品推荐!
-
- 最新文章
- 热门文章
- 热评文章
[课程] 面授系统课-王氏中药外治疗法6节
[课程] 职场必备生存法则体制内经验课
[课程] 外贸话术实战营系统课,让你不再不知所措,减少试错时间,脱变成外贸拿单达人
[课程] 餐饮人必修课
[课程] 千峰教育-小沐老师Python教程基础语法到项目实战(flask博客网站的实现) - 带源码课件
[课程] 极客时间-从 0 开发一款 iOS App
[网赚相关] 最新网易云梯计划网页版,单机月收入5000+!!
[游戏娱乐] 《永恒空间2》v1.1.39656中文版
[摄影] 玩转手机摄影 | 滤镜手机支架
[美食] 春天最不能忘记吃的菜,脆甜爽口营养高,减肥、控糖都很合适
[资料] [大学期末救急课] 猴博士+高斯课堂+斐多课堂,全集视频合集
[云资源] 价值2万元的老男孩Python教程
[书库] 史上最全摄影书推荐(附700本PDF版打包下载)
[云资源] 花了一千多元买的私人健身教程
[下载工具] Internet Download Manager 6.42.7 (IDM)
[影视] 灌篮高手 WEB-DL版下载/Slam Dunk/スラムダンク/灌篮高手:THE FIRST/灌篮高手电影版 2022 The First Slam Dunk 61.35G
[即时通讯] 腾讯QQ PC版9.7.22.29315去广告绿色纯净版
[开发环境] PhpStorm2023中文激活版v2023.3.3 正式版
[资料] 3000 套电影电视剧 LOGO 宣传片常用音效合集包
[安卓软件] 酷我音乐APP_v10.7.6.4 去广告破解豪华VIP版
[云资源] 价值2万元的老男孩Python教程
[影视] 灌篮高手 WEB-DL版下载/Slam Dunk/スラムダンク/灌篮高手:THE FIRST/灌篮高手电影版 2022 The First Slam Dunk 61.35G
[云资源] 花了一千多元买的私人健身教程
[书库] 史上最全摄影书推荐(附700本PDF版打包下载)
[动画] 北斗神拳(1984) [两季合集] [MKV]
[资料] 抗战阵亡将士资料+续编
[电视剧] 三体 (2024) 全8集 网飞版本 中文字幕 合集
[影视] 三大队 WEB-DL版下载/Endless Journey/请转告局长,三大队任务完成了 2023 三大队 6.7G
[纪录片] 河西走廊【10集 国语 中文字幕 1080P 10.8G MP4】
[影视] 涉过愤怒的海 WEB-DL版下载/怒海 / Across the Furious Sea 2023 涉过愤怒的海 26.3G
- 最新评论
-
我想看看mw2ddyy 评论于:04-26 好东西阿zfy123123 评论于:04-18 谢谢楼主xiaoqi 评论于:04-12 勿在线解压,勿手机解压,请在电脑上用最新款压缩软件解压!推荐360压缩或者好压CC下载站 评论于:04-10 无法解压啊,客服能不能给个解压教程ravengrey 评论于:04-10 谢谢支持!!CC下载站 评论于:03-26 很棒的资源,感谢分享云体风身 评论于:03-26 感谢分享,好东西云体风身 评论于:03-26 谢谢支持!CC下载站 评论于:03-14 央视精品,感谢付出提供。qwer9009 评论于:03-14
- 热门tag