Posted in

别再用雪花算法生成 ID 了!试试这个吧 – 掘金_AI阅读总结 — 包阅AI

包阅导读总结

1. 唯一ID生成、短数字ID、账号表、自增ID、预申请ID

2. 本文主要探讨服务器中短数字账号ID的生成方案。从最初的雪花算法因ID过长需改进,到基于数据库自增ID特性的方案及出现的死锁问题,再到多个其他方案的尝试,最终采用预申请一批ID的方式并进行优化,该方案经生产环境测试运转正常。

3.

– 背景

– 需求:为用户账号生成简短数字ID

– 问题:UUID存储和传输性能稍逊,不利于记忆和传播

– 初步版本

– 雪花算法:生成64位数字ID,太长

– 改进版本

– 利用数据库自增ID特性

– 账号表分表,通过单独的ID生成表实现

– 出现死锁问题,放弃此方案

– 其他方案1

– 参考美团方案,使用多个mysqlserver,因部署限制和消耗大被pass

– 尝试设置自增步长和起始值,因变量级别限制无法实现

– 其他方案2

– 读写分离思想,写表自增ID,定期迁移数据,因运维复杂被pass

– 其他方案3(最终方案)

– 预申请一批ID,减少请求量和并发

– 优化减少浪费的ID,去除空洞号段,兼容扩容与容灾

– 方案经生产环境测试正常运转

思维导图:

文章地址:https://juejin.cn/post/7393656776540291087

文章来源:juejin.cn

作者:码财同行

发布时间:2024/7/22 4:43

语言:中文

总字数:4399字

预计阅读时间:18分钟

评分:83分

标签:唯一ID生成,雪花算法,数据库自增ID,分布式系统,账号系统


以下为原文内容

本内容来源于用户推荐转载,旨在分享知识与观点,如有侵权请联系删除 联系邮箱 media@ilingban.com

大家好啊,我是码财同行。今天继续聊服务器中唯一ID生成。唯一ID生成中雪花算法大家都比较熟,那如果加一个要求呢:

尽量短的数字ID

image.png

背景

之前的项目有个需求:为用户账号生成账号ID。最开始用的是UUID(长字符串ID),但是字符串账号相对于数字账号,存储和传输性能都稍逊,也不利于记忆和传播。

因此,生成一套业务内的数字账号,并且尽量简短就是当务之急。

初步版本

我们最开始考虑的是雪花算法方案,使用的是经典的 twitter开源的算法 snowflake。这个算法非常强大,生成的是 64bit 的数字id,天然支持分布式。

有关这个算法的详细分析,可以查看我前一段时间发的这篇文章:【收藏级】唯一ID生成探讨:论ID与猪肉?

雪花算法看起来无懈可击,但是唯一的问题就是生成的64位 ID 太长了。账号ID希望能控制的尽量短,个人理解有以下原因:

  • 账号id一般显示在个人设置里,会暴露给用户,需要便于输入 + 记忆,这样客服查询起来更方便;
  • 账号id短并且有序能提高账号库的写入性能;

于是着手改进。

改进版本

一个比较可行的方案是利用数据库的自增 ID 特性。

为了便于理解,我们先来看一下业务里的账号登录流程:

  • 客户端上传第三方openid及token来登录,登录服拿到openid后需要查询是否已经注册账号
  • 如果能查到账号ID,表明已经注册,再根据查到的数字账号来做后续登录逻辑
  • 如果查不到,则需要新注册一个账号到账号表
  • 新建账号首先需要生成一个数字的账号ID,在目前的机制中,通过一张专门的ID生成表来做的。

OK,先来看我们如何在mysql中存储账号相关信息的:

  • 账号表,accid就是我们说的数字账号。考虑到账号数量级可能到千万甚至上亿,单表的性能肯定不理想,因此我们分了10张表。其表结构为

    CREATE TABLE `tbl_global_user_map_00` (  `account` varchar(32) NOT NULL,  `accid` bigint(20) NOT NULL,  `created_at` datetime DEFAULT NULL,  PRIMARY KEY (`account`) USING BTREE) ENGINE=InnoDB DEFAULT CHARSET=utf8 
  • 账号ID生成表,其表结构为

    CREATE TABLE `tbl_accid` (  `id` bigint(20) NOT NULL AUTO_INCREMENT,  `stub` char(1) NOT NULL DEFAULT '',  PRIMARY KEY (`id`) USING BTREE,  UNIQUE KEY `UQE_tbl_accid_stub` (`stub`) USING BTREE) ENGINE=InnoDB DEFAULT CHARSET=utf8 

数据为

整个表只有一行数据,id列为自增列,它的值就是最新生成的账号ID值。这个ID生成的原理是:

  • 设置id列为自增,这样每插入一列id值就会自动递增
  • 如果没有其他限制,这张表的数据就会随着insert的次数越来越多,假如账号有几千万,这张表就有几千万行数据
  • 为此,我们增加了一列 stub,设置其为 unique key,并且每次insert其值都是一样的(例如设置为 ‘a’),这样就保证整个表只有一行数据,而id会随着每次insert自动递增。
  • 如果直接用 insert into 语句来做插入,肯定每次都返回错误(除了第1次),因为 stub 为 ‘a’ 的记录已经存在了,每次插入都会失败。
  • 我们改用 MySQL 扩展的 SQL 语句 replace into 来实现。replace 必须要配合唯一索引来使用。

于是 SQL 语句就是

REPLACE INTO tbl_accid(`stub`) VALUES('a');

它的效果如下:

  • 如果 stub 为 ‘a’ 的记录不存在,则插入,类似 insert 操作
  • 如果 stub 为 ‘a’ 的记录已经存在,则先 delete 该条记录,再 insert 新记录。由于删除已有的记录时,表的自增值不会变化,再新增记录时 id 会在老的自增值基础上继续递增

有同学可能要问了,为什么要搞一个单独的ID生成表来生成自增id?将自增字段直接放到账号表中不行么?

关键的问题在于业务要分表。假如账号表分了10张,要合并自增id列的话,需要划分好每张表的生成范围。

例如我们设计每张表可以生成 100w 个id,那 10 张表的起始id 分别是 1, 1000001,2000001, …

跨度非常大,和我们当初的设计:简短并尽量连续的要求违背。

因此,专门的账号ID生成表是必要的。

问题暴露

上述方案完成之后,我就去吃火锅唱歌去了。

image.png

然后,就出现了一个比较棘手的问题。某天晚上QA同事反馈压力测试有报错,登录服会间歇性返回db错误,如下:

ERROR : Deadlock found when trying to get lock; try restarting transaction

登录服收到该返回后打印了错误日志,提示客户端服务器发生错误。很明显,这个方案有死锁问题。

image.png

google了一下 replace 在并发情况下的死锁问题,大致和 replace 被分解成 delete + insert 有关,而 innodb又是行锁机制。详细的原因非常复杂,有关资料为

yq.aliyun.com/articles/41…

techlog.cn/article/lis…

blog.itpub.net/7728585/vie…

很多博客也给出了建议:

通过几个死锁案例,我们强烈建议在生产环境中尽量避免使用REPLACE INTO和INSERT INTO ON DUPLICATE UPDATE语句,改用普通INSERT操作,并对INSER操作部分代码加入异常加查,当INSERT失败时改为UPDATE操作。

为了再验证一次死锁的并非语言或者API的bug,我用了 mysql 自带的压测工具 mysqlslap 做了个简单测试:

mysqlslap -uroot -p --create-schema="db_global_200" --concurrency=2 --iterations=5 --number-of-queries=500 --query="replace_innodb.sql"mysqlslap: Cannot run query REPLACE INTO tbl_yptest_innodb(`stub`) VALUES('a'); ERROR : Deadlock found when trying to get lock; try restarting transaction

结果显示并发数为 2 时就出现了死锁问题。然后我又尝试将表引擎改为 myisam,再次压测,虽然没有出现死锁问题,但是MYISAM引擎更新数据的效率比较低。因此我们不得不放弃了mysql自增ID的方案,再想其他方案。

image.png

其他方案1

继续尝试其他方案。其实,我们最新的ID生成方案参考了美团技术团队的一篇文章,有兴趣的可以查阅:Leaf——美团点评分布式ID生成系统

文中提到了一种Flickr团队的改进方案:

即:使用 N 个mysqlserver,来提高可用性,降低每个 mysqlserver的压力和并发数。如果 replace into 不支持并发,那就部署尽可能多的 mysqlserver,每次 replace into 时串行。

然而这种方式部署限制和消耗都太大,而且我们的登录服是多开的,即使在单登录服内控制串行,多个进程也不好控制,因此这个初始的方案只能被pass。

回到开始的思路,能不能将自增id合并到 账号表_xx 中,从而放弃 replace 呢?

我们可以将每个 tbl_global_user_map 分表类比成上图中的 mysql-01, mysql-02, …

然后自增时,采取 间隔步长N 的方式(默认的自增步长是1,每次自增加1)

举例:

tbl_global_user_map_00 表,起始id 20000,每次加10,其生成的 id 每次是 20000, 20010, 20020, 20030…

tbl_global_user_map_01 表,起始id 20001,也是每次加10,其生成的 id 每次是 20001, 20011, 20021, 20031…

这个id看起来间隔很小,看起来非常理想。

需要做的事情就是设置 auto_increment_increment 和 auto_increment_offset 两个mysql中的变量。

然后很可惜,这两个变量属于 全局 或者 session(连接会话) 级别,没有 table 级别的设置。

如果我们设置了这两个变量,很容易影响其他表,产生其他错误。

其他方案2

再想其他方案。

仔细整理一下我们的需求,就会发现我们的账号表一般只有新增,没有删除和修改。能不能利用读写分离的思想,在插入新映射关系(同时生成自增账号ID)时,只有一张表可写,自增id可以每次只加1;而查询时,属于读,读的数据可以分布在10张表中。我们要做的就是定期将可写表中已有的一些数据迁移到只读的这10张表中(根据账号ID做shard),控制可写表的数量级不能太大。

账号ID在写表中自增,相当于自动分配账号ID。

image.png

这个机制有点类似于我们的日志滚动,当前正在写的日志文件不停被写入(插入日志),当超过一定大小或者日期切换时会滚动成只读的文件。

这个方案理论上可行,但是有运维复杂性:需要配合运维来做数据迁移,维护成本比较高,因此组内讨论后我们决定pass掉。

其他方案3(最终方案)

我之前所在的成熟项目也用过上述【其他方案1】中类似美团的方案,即预申请一批ID的方式。

对比来看,我们之前申请ID都是一次自增1,而这种预申请一批的方式,是一次申请N个ID,自增N,可以减少请求量和并发。当请求量明显下降后,之前方案里担忧的问题:ID生成表插入行数过多也就不存在了。

唯一的问题是:预申请的ID可能会被浪费。如果申请了一段区间的id,但是没有用完,服务器停服再启动后会再申请一段新的,原来未使用的ID就被浪费了。

因此我们着手优化这种算法,目的很明显:

减少浪费的ID,去除空洞号段,并自动兼容登录服扩容与容灾的情况。

如果这个目的能达成,那就完美契合了我们当初的需求。

image.png

短ID方案细节

设计发号表 tbl_account_freeid

号段编号,自增 svr编号 号段内剩余freeid数量
segment loginsvr left

每个登陆服要申请一批账号ID时,就来表中插入一行,规定每次申请1000个,由于segment自增,相当于申请了 [(segment – 1) * 1000, segment * 1000) 这段区间,申请时候默认 left 是 0

登录服正常停服维护时将剩余未用完的数量写入 left,防止浪费,下次启动时候还可以再利用。

以下分析各种case:

a) 初始 tbl_account_freeid 没有数据,假如 loginsvr 开3个实例,实例编号分别是1,2,3。

服务器启动时候需要做一次查找,要找对应 实例编号的segment。如果找到了,且 left 不为 0,则说明该号段还可以用;如果找不到,或者left为0,则需要新申请(新插入一行记录)。

于是第一次启服后数据为

号段编号,自增 svr编号 号段内剩余freeid数量
segment loginsvr left
1 2 0 内存中号段为 1-1000
2 1 0 内存中号段为1001-2000
3 3 0 内存中号段为2001-3000

b) 如果loginsvr发现内存中号段用完了,就不用再查找,直接申请,往数据库插入一行数据,假定实例编号 1 和 3 的 号段用完了,新申请。

然后各个登录服正常停服,left 回写。可能的数据情况如下:

号段编号,自增 svr编号 号段内剩余freeid数量
segment loginsvr left
1 2 200
2 1 0 (使用完毕,该行可删)
3 3 0 (使用完毕,该行可删)
4 1 800
5 3 750

c) 再次起服时,查找到各个编号的实例都有号段可用。无需新插入数据,但是对应的 left 要改为0(相当于申请了 left 个)

号段编号,自增 svr编号 号段内剩余freeid数量
segment loginsvr left
1 2 0 登录服内存中号段为 801-1000(剩余的200个)
2 1 0 (使用完毕,该行可删除)
3 3 0 (使用完毕,该行可删除)
4 1 0 登录服内存中号段为3201-4000(剩余的800个)
5 3 0 登录服内存中号段为4251-5000 (剩余的750个)

d) 如果此时 loginsvr 扩容,新增编号 4 – 10 的 svr,和初始情况类似,需要先查找,没有则申请。此时数据可能为

号段编号,自增 svr编号 号段内剩余freeid数量
segment loginsvr left
1 2 0 登录服内存中号段为 801-1000(剩余的200个)
2 1 0 (使用完毕,该行可删除)
3 3 0 (使用完毕,该行可删除)
4 1 0 登录服内存中号段为3201-4000(剩余的800个)
5 3 0 登录服内存中号段为4251-5000 (剩余的750个)
6 4 0 登录服内存中号段为5001-6000
7 5 0 登录服内存中号段为6001-7000
8 6 0 登录服内存中号段为7001-8000
9 7 0 登录服内存中号段为8001-9000
10 8 0 登录服内存中号段为9001-10000
11 9 0 登录服内存中号段为10001-11000
12 10 0 登录服内存中号段为11001-12000

这种方式的特点就是,登录服服务过程中,对应数据库里的 left 为 0,如果停了,数据库里 left 为号段内剩余的可用数量。

如果登录服宕机,则没有回写 left 的过程,则对应号段内没有用完的(最多1000)会浪费。

结尾

以上就是我们在账号短ID生成上的探索,最终方案经历了长时间的生产环境的测试,运转正常。如果小伙伴们有更优秀的经验欢迎一起交流。

好了,看了这么多,一定很费脑力吧。来个笑话放松一下 🙂

【笑话一则】喝多了准备打车回家,本来想叫嘀嘀打车,结果叫成了滴滴代驾。等代驾到了,我们对视了10秒,异口同声得说:“你车呢?”

感谢您花时间阅读这篇文章!如果觉得有趣或有收获,请来个关注、评论、点赞吧,您的鼓励是我持续创作的动力,蟹蟹!

image.png