放弃snowflake-我们重新设计了新的分布式ID生成方案

原文地址：码农在新加坡的个人博客

在之前的文章中，我们讲了分布式ID生成方案-snowflake算法。这也是我们的生产系统过去几年一直使用的分布式ID生成方案。

雪花算法（Snowflake）有着很多的优点，适用于大多数的业务场景。

有兴趣的可以查看我之前的文章。 https://www.leftpocket.cn/

可是随着我们业务的发展壮大，这个分布式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里面生成。就是它是我们服务的一部分，也就是我们服务的机器数量，取决于整个服务业务的规模。

我们当时就想了两种方案：

1. 把ID生成拆分成独立的服务。
2. 调整工作机器id的bit数量。

作为最底层的服务，我们并不想依赖任何外部服务，所以方案1被我们排除了。 方案2的话，由于41位时间戳本身是一个有意义的数据，为了兼容性和数据本身的意义考虑，我们不想动它，所以只能动最右边的12bit-序列号。但是考虑到下次可能继续增长，我们最终决定一劳永逸，直接废除机器id的设定。

这就是我们需要找一些替代方案的原因。

但是我不否认，上述的方案是可行的。

数据库方案

数据库的方案是最简单也是最容易想到的唯一ID生成方案。

数据库本身生成的ID是自增唯一的，用来做分布式唯一ID很合适。但是我们为了与之前的snowflake方案保持一致，同时也为了让生成的唯一ID不容易被算出来。我们保留前面41位时间戳不变，数据库的自增ID只做为后边的22位，来代替10bit-工作机器id+12bit-序列号

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性能问题，很容易想到可用如下方案解决

在分布式系统中我们可以多部署几台数据库的实例，每台实例设置不同的初始值，且步长和数据库实例数相等。

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倍。

这个时候我们测试一下插入数据：

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了。

1. 数据库自增ID不会超过16位吗？ – 当然会，我们是使用auto_increment_id%2^16。这样用完之后就可以重新生成。
2. 这样不会导致生成的唯一ID重复吗？– 我们最前面有一个毫秒级别的时间戳，如果一毫秒能走完一圈的话是可能重复的。QPS=2^16*2^6*1000 = 4 Billion。我们整个系统的QPS也才10M左右，更何况需要生成ID的QPS就更低了。大概100K。我们假设他不会重复。

我们继续使用最简单的unique_id_tab作为数据库的自增ID表。

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]
}

流程：

1. 第一次需要生成ID的时候，DB中拿出一个值后，我们就把buffer置为0。
2. 每次需要生成ID的时候，把buffer加1。
3. 当buffer == 2^6-1的时候，用完当前的buffer。
4. 下次继续从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的访问导致的生成过慢的问题，也算是一个比较好的解决方案。

<全文完>

欢迎关注我的微信公众号：码农在新加坡，有更多好的技术分享。