⭐⭐⭐ Spring Boot 项目实战	⭐⭐⭐ Spring Cloud 项目实战
《Dubbo 实现原理与源码解析 —— 精品合集》	《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》	《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》	《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》	《Java 面试题 + Java 学习指南》

摘要: 原创出处 juejin.cn/post/7393656776540291087 「码财同行」欢迎转载，保留摘要，谢谢！

🙂🙂🙂关注微信公众号：【芋道源码】有福利：

RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表

RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址

您对于源码的疑问每条留言都将得到认真回复。甚至不知道如何读源码也可以请教噢。

新的源码解析文章实时收到通知。每周更新一篇左右。

认真的源码交流微信群。

今天聊聊服务器中唯一ID生成。唯一ID生成中雪花算法大家都比较熟，那如果加一个要求呢：

尽量短的数字ID

背景

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

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

初步版本

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

有关这个算法的详细分析，可以移步：

https://juejin.cn/post/7386243179278041128

雪花算法看起来无懈可击，但是唯一的问题就是生成的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) NOTNULL,

`accid`bigint(20) NOTNULL,

`created_at` datetime DEFAULTNULL,

  PRIMARY KEY (`account`) USING BTREE

) ENGINE=InnoDBDEFAULTCHARSET=utf8

账号ID生成表，其表结构为

CREATE TABLE`tbl_accid` (

`id`bigint(20) NOTNULL AUTO_INCREMENT,

`stub`char(1) NOTNULLDEFAULT'',

  PRIMARY KEY (`id`) USING BTREE,

UNIQUEKEY`UQE_tbl_accid_stub` (`stub`) USING BTREE

) ENGINE=InnoDBDEFAULTCHARSET=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生成表是必要的。

问题暴露

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

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

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

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

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

很多博客也给出了建议：

通过几个死锁案例，我们强烈建议在生产环境中尽量避免使用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的方案，再想其他方案。

其他方案1

继续尝试其他方案。其实，我们最新的ID生成方案参考了美团技术团队的一篇文章，有兴趣的可以查阅：

https://tech.meituan.com/2017/04/21/mt-leaf.html

文中提到了一种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。

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

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

其他方案3（最终方案）

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

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

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

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

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

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

短ID方案细节

设计发号表 tbl_account_freeid

每个登陆服要申请一批账号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，则需要新申请（新插入一行记录）。

于是第一次启服后数据为

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

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

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

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

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

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

结尾

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

芋道源码 —— 纯源码解析博客

唯一ID生成,除了用雪花算法,还可以试试这个...

背景