发号器设计漫谈

本质上发号器解决的问题就是分布式环境之下 ID 的唯一性，但是由于不同的业务场景差异悬殊，发号器的设计也有很大的不同，而且由于很多互联网公司的业务数据都是用的关系数据库，因而需要 ID 是自增的数字以满足数据库索引的要求，比如数字对 MySQL 的索引 B+ 就很友好，本文就常见发号器设计进行了详细的阐述和对比，希望对你有所帮助。

MySQL 发号器

Flickr 在技术博客 Ticket Servers: Distributed Unique Primary Keys on the Cheap 中透露了他们是如何设计发号器的，主要是利用了 MySQL 的自增技术。

如何用 MySQL 的自增来设计发号器？要弄清楚这些问题，我们需要一点一点从 MySQL 的自增主键开始讲起。

last_insert_id() 函数

我们先在 MySQL 中创建一个带自增列的表，基于Innodb 引擎：

CREATE TABLE `test_auto_increment` (
  `id` bigint(11) unsigned NOT NULL AUTO_INCREMENT,
  PRIMARY KEY (`id`)
)

然后再插入几条数据：

insert into `test_auto_increment` (id) values (0);
insert into `test_auto_increment` (id) values (0);

执行这条语句：

select LAST_INSERT_ID();

在我的机器上这条语句返回的是 2，也就是插入两条数据之后 auto_increment 列的值。last_insert_id() 这个函数在不带参数的情况下，返回的是一个 64 位无符号整数，表示在 MySQL 中最近的一次执行 Insert 语句时 auto_increment 列产生的值，注意是最近，也就是说如果我们再创建一个表，插入数据之后再执行这个函数，结果就会发生变化，如果没有执行过任何 insert 语句，那么多次执行这个函数结果是一样的。

需要注意的是当前执行的 insert 语句不会对 last_insert_id() 函数产生影响，比如说通过在 insert 语句中引用 last_insert_id 函数，last_insert_id 的返回值也是这条 insert 语句上次的 insert 产生的递增的值。

insert into test_auto_increment select LAST_INSERT_ID();

在 MySQL 中，last_insert_id() 产生的值实际上是 MySQL server 维护在每个 connection 上的 ，这就意味着不同的 client 的看到返回值是不同的，他们看到的都是最近通过他们自身的 session 执行的 insert 语句产生的自增值，对其他的 client 没有影响。

获取最新的一个自增值

我们的目的是设计发号器，由于只有 insert 语句才会产生一个自增值，也就是我们想要获得一个自增的值必须先要插入一条数据，然后想办法获得该值。上面我们已经创建了一个带自增列的表，于是想要获得一个自增的主键我们可以在同一个 session 中执行下面的操作：

insert into `test_auto_increment` (id) values (0);
select LAST_INSERT_ID();

到现在为止，设计一个全局唯一的发号器好像已经完成了。Anybody and any question？😁 这位优秀的同学有话要说：虽然全局唯一的发号器的目标已经达到了，但是无形之中 insert 语句会产生很多无用的数据，比如像 flick 一秒钟要上传 60 张图片，还不包括其他元数据，一天也要产生 500 万的数据量，一个月就要 1.5 亿数据，很快这个发号器的表就会变得很大。这个问题提的很好，我们来一起思考一下如何解决发号器表数据量过快增长的问题。

防止自增表数据过大

由于 insert 语句会不断产生数据，那有没有一种办法既可以让自增键不断得增长，还能让数据量不至于过大呢？有几种办法。

1. 由于我们只关心自增的值，表中已经产生的数据是没有意义的，可以定时进行清除。
2. 由于我们只关心自增的值，获得自增的数据之后，原来的值就可以顺手删除了，实时清除无意义数据。
3. 利用 MySQL 提供的 REPLACE 语句

方法 1 和 2 本质上是一样的，都是需要开发者自己去处理，但是 3 利用了 MySQL 的特性 replace，更便捷。要想利用 replace 语句需要我们对之前的表结构做一下变更，新增一个具有唯一性索引的字段：

alter table test_auto_increment add column stub int unique key;
delete * from test_auto_increment; //清楚之前产生的数据

这里的唯一性的索引是必须的，因为 replace 的原理是先删除具有相同主键或唯一性索引的行，然后再插入新的行。改变之后再执行下面的语句，表的数据不再增长：

replace into `test_auto_increment` (stub) values (2019);
SELECT LAST_INSERT_ID();

高可用的发号器

我们已经通过 MySQL 的自增设计了可以满足需求的发号器，但是我们的发号器是单点的，只能用一个 MySQL 实例来发号，一旦 MySQL 故障就发号器就不可用了。我们需要一个高可用的发号器架构来消除单点的问题。

幸运的是 MySQL 提供了 auto_increment_increment 和 auto_increment_offset 。原本 auto_increment_increment 和 auto_increment_offset 为解决 MySQL master-master 架构中 auto_increment 冲突的问题，这两个变量在 MySQL 中既可以在全局中设置，也可以在具体的一个 session 中更改，他们具体的值是 1~65535，接下来我们详细阐述他们对 auto_increment 的影响。

auto_increment_increment 这个变量控制的是自增列的 interval，查看 MySQL 的默认设置：

mysql> show variables like 'auto_inc%';
+--------------------------+-------+
| Variable_name            | Value |
+--------------------------+-------+
| auto_increment_increment | 1     |
| auto_increment_offset    | 1     |
+--------------------------+-------+
2 rows in set (0.00 sec)

mysql>

然后我们把这个值改为 10：

mysql> SET @@auto_increment_increment=10;
Query OK, 0 rows affected (0.05 sec)

mysql> show variables like 'auto_inc%';
+--------------------------+-------+
| Variable_name            | Value |
+--------------------------+-------+
| auto_increment_increment | 10    |
| auto_increment_offset    | 1     |
+--------------------------+-------+
2 rows in set (0.00 sec)

mysql>

然后我们创建一个表进行测试并且插入一些数据：

mysql> CREATE TABLE `test_auto_increment2` (
    ->   `id` bigint(11) unsigned NOT NULL AUTO_INCREMENT,
    ->   PRIMARY KEY (`id`)
    -> );
Query OK, 0 rows affected (0.31 sec)

mysql> INSERT INTO test_auto_increment2 VALUES (0), (0), (0), (0);
Query OK, 4 rows affected (0.14 sec)
Records: 4  Duplicates: 0  Warnings: 0
mysql> select * from test_auto_increment2;
+----+
| id |
+----+
|  1 |
| 11 |
| 21 |
| 31 |
+----+
4 rows in set (0.00 sec)

mysql>

可以看到自增列的值间隔是 10。

auto_increment_offset 这个变量决定了自增列的起始值，接着在刚才我们打开的 session 中设置这个值：

mysql> SET @@auto_increment_offset=5;
Query OK, 0 rows affected (0.02 sec)
mysql> show variables like 'auto_inc%';
+--------------------------+-------+
| Variable_name            | Value |
+--------------------------+-------+
| auto_increment_increment | 10    |
| auto_increment_offset    | 5     |
+--------------------------+-------+
2 rows in set (0.00 sec)

然后插入一些数据查看变化：

mysql> INSERT INTO test_auto_increment2 VALUES (0), (0), (0), (0);
Query OK, 4 rows affected (0.29 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> select * from test_auto_increment2;
+----+
| id |
+----+
|  1 |
| 11 |
| 21 |
| 31 |
| 45 |
| 55 |
| 65 |
| 75 |
+----+
8 rows in set (0.00 sec)

mysql>

可以看到自增列接下来的值变成 45、55、65、75，实际上 MySQL 是根据下面的公式计算自增列的值：

auto_increment_offset + N × auto_increment_increment

N 是 正整数，新行插入产生的自增值都会比已经存在的自增值要大，则根据上面的规则应该是 5 + N * 10 = [10, 15, 25, 35, 45,…]，根据上面的计算规则 MySQL 的官方给出的答案是 35，但是实际上 5.7.6 版本中则是从 45 开始的，具体原因我猜测因为 auto_increment_increment 规定了 interval 必须要是 10，而如果是从 35 的话，35 和 31 的 interval 就不是 10 了 ：）。

既然可以通过 auto_increment_increment 和 auto_increment_offset 控制步长和起始值，那么我们就可以利用这个特性来水平扩展我们的发号器。

如图所示，发号器从一台扩展到 2 台，再扩展到 4 台，每次扩展我们都需要重新改变 offset ，调到一个比之前已经生成的 id 更大的值，并且调整 increment 为扩展的发号器数量，这样才能保证新扩展之后的发号器不冲突。

不难看出基于 MySQL 的发号器有一个很大的问题：扩展麻烦，每次扩展都需要调整步长和初始值，而且为了达到性能要求只能水平加 MySQL 机器。

Twitter Snowflake

Twitter 在 2010 年开源了一个全局 ID 生成器的算法叫 Snowflake，如图所示：

该算法用一个 64 位整数来表示唯一性 ID，64 按照不同的段位进行划分：

1. 首位 1 bit 不用，固定是 0 ，由于计算机中正数的最高位是 0，ID 是正数
2. 41 位表示时间戳，精确到毫秒，这 41 位可以表示的数字范围是 0 ~ 2^41-1，这里只需要无符号数，也就是说如果从某个时间戳开始算起，这 41 位能够容纳的最长时间是 (2^41-1) / 10003600\24*365 ≈ 69 年
3. 10 位工作机器 id，可以根据业务需要把这 10 位用作机器节点 id 或者数据中心 id，比如有 3 个数据中心就可以留 2 位出来，剩下的作为机器节点 id。
4. 12 位序列号，可以表示 2^12-1 = 4095 个整数，表示同一时间戳能产生的所有序号。

snowflake 算法理论上每秒可以产生 40951000 个 id，能够满足很大的业务量需求，相比使用 MySQL 的自增进行发号，这个*算法容易实现，水平扩展方便，只要保证扩展之后的 10 位工作机器 id 是唯一即可，需要注意的是由于算法依赖机器的时间戳，如果机器的时间戳发生过回拨，也就是回退到之前的某个时间可能会导致 id 重发。

snowflake 算法的具体实现可以参考如下文章：

• https://juejin.im/post/5a7f9176f265da4e721c73a8
• https://segmentfault.com/a/1190000011282426

美团点评的 Leaf 方案

前段时间美团开源了自家的分布式 ID 生成方案 Leaf https://github.com/Meituan-Dianping/Leaf ，其在博客文章 https://tech.meituan.com/2017/04/21/mt-leaf.html 谈过其设计思路，大致如下。

Leaf 是基于 MySQL 的分布式 ID 生成方案，但是不同于使用 MySQL 自增的方式，Leaf 做了改良：

1. 由于 MySQL 自增方案中每做一次发号就要写一次数据库，在并发量大的情况下，MySQL 压力太大，Leaf 每做一次发号不是发一个号，而是发一个号段，比如 1 ~ 1000 这个号段，这样可以大大减少 MySQL 写的压力
2. 通过调整步长和初始值来进行水平扩展非常复杂，难以精确控制，Leaf 为不同业务（通过 tag 区分）定义了不同的号段长和初始值，每个业务获取 ID 都相互隔离，互不影响
3. Leaf 不是直接从 MySQL 中获取 ID，而是通过 proxy，proxy 会把从 MySQL 获取的号段做缓存，有了 proxy 之后如果需要对发号器进行扩展，直接扩展 proxy 并且多分配一些号段即可，不需要变更 MySQL

整个 Leaf 的架构如下：

其中 MySQL 的表定义了：

Filed	type	comment
biz_tag	varchar(128)	业务 tag
max_id	bigint	已发号的最大值
step	int(11)	号段长
desc	varchar(256)
update_time	timestamp

具体业务实现以上图 test_tag 为例，比如 proxy-2 节点上没有 test_tag 的号段，然后需要从 DB 更新号段，更新号段就是把 test_tag 对应的 max_id 增加一个步长：

Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=test_tag
SELECT tag, max_id, step FROM table WHERE biz_tag=test_tag
Commit

变更之后 test_tag 的 max_id = 4000，之后每个 proxy 如果号段消耗完成就又以这种方式获取。

除此之外 Leaf 还针做了如下优化：

第一，如果 proxy 特别多，有可能会有多个 proxy 会在同时获取同一个 tag 的号段，这会导致 DB 有短时间的卡顿 proxy 更新号段线程发生阻塞从而影响发号。因而 Leaf 在 proxy 做了预更新机制，也就是在号段消耗约 10% 左右就开始更新下一批号段，并且 Leaf 中号段的长度是峰值 QPS 的百倍之多，这样能让 DB 即使出现短暂故障也不会影响发号。

第二，Leaf 的 DB 采用一主多从的方式部署，同时分机房，并且 DB 的主从切换采用 https://github.com/Meituan-Dianping/DBProxy 保证了 Leaf 服务的高可用

Leaf 这种架构能够做到：

• Leaf服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景。
• ID号码是趋势递增的 8 byte的64位数字，满足主流关系型数据库存储的主键要求。
• 容灾性高：Leaf服务内部有号段缓存，即使DB宕机，短时间内Leaf仍能正常对外提供服务。
• 可以自定义max_id的大小，非常方便业务从原有的ID方式上迁移过来

由于 Leaf 是通过递增号段的方式发号，很容易让竞品根据号段猜出一些商业数据，Leaf 根据 snowflake 做了改进设计了 Leaf-snowflake， 并且使用 zookeeper 同步 Leaf-snowflake 服务的时间戳以及 worker id 来解决由于机器时钟回拨和节点变更的问题，详细可以见 https://tech.meituan.com/2017/04/21/mt-leaf.html

MongoDB ObjectID

MongoDB 的 ObjectID 也是一个可以在分布式环境之下使用的唯一性 ID，并且他是根据它的生成规则可以轻松在 client 端生成，这样 ID 的开销就转移到了 client 端。

ObjectID 总共有 12字节分别是：

• a 4-byte value representing the seconds since the Unix epoch 时间戳
• a 5-byte random value 随机值
• a 3-byte counter, starting with a random value 计数器

MongoDB 的 ID 带有时间戳信息，可以推断出生成 ID 的时间，而且这个 ID 也是趋势递增的，在客户端生成速度快是他的优势。MongoDB 的 ObjectID 结合 MongoDB 的环境使用最高效，有些场景可以替换 UUID 来用。

UUID

UUID(Universally Unique Identifier) 标准型式包含 32 个 16 进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字符，示例：550e8400-e29b-41d4-a716-446655440000，到目前为止业界一共有5种方式生成UUID，详情见IETF发布的UUID规范 http://www.ietf.org/rfc/rfc4122.txt 。

UUID 比 MongoDB 的 ObjectID 还要长，占用 16 字节，不易于在类似 MySQL 这样的系统中存储检索，由于在客户端生成，效率很高，但是依赖于客户端的 MAC 地址，有暴露 MAC 地址的风险，

小结

行文至此，我们一起来分析总结一下几种发号方案的优缺点。

方案一，MySQL 自增

优势：实现简单，能够应付大部分场景，易于存储索引

缺点：水平扩展复杂，数据库在并发场景高的场景下压力大

方案二，snowflake 算法

优势：实现不算复杂，水平扩展容易，并发量大，能够应付绝大数业务场景，趋势递增，易于存储索引

缺点：依赖于时间戳，机器时间回拨会导致 ID 重复发送

方案三，MongoDB ObjectID

优势：client 端生成，速度快，效率高，配合 MongoDB 在分布式环境中使用，自带时间戳，一些场景可以替换 UUID

缺点：不利于 MySQL 这样的关系型数据库存储索引

方案四，UUID

优势：client 端生成，效率高

缺点：太长，不易关系型数据库存储索引，有一定的安全风险

开源实现

以上方案的部分开源实现：

• https://github.com/Meituan-Dianping/Leaf
• https://github.com/baidu/uid-generator
• https://github.com/edwingeng/wuid
• https://github.com/bwmarrin/snowflake