本篇博客的视频教程首发于 Youtube:科技小飞哥,加入 电报粉丝群 获得最新视频更新和问题解答。

背景

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

雪花算法(Snowflake)有着很多的优点,适用于大多数的业务场景。

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

可是随着我们业务的发展壮大,这个分布式ID生成方案对我们的业务来说已经有了一定的限制,所以我们在考虑一种新的方案来替代snowlfake算法

避免有些人不是很了解snowflake算法,这里简单描述下:

snowflake算法

雪花算法(Snowflake)是twitter公司内部分布式项目采用的ID生成算法,开源后广受国内大厂的好评,在该算法影响下各大公司相继开发出各具特色的分布式生成器。

Twitter的snowflake分布式ID的算法是目前广泛使用的分布式ID算法,尽管有很多变种,比如位数的不同,时间片大小不同、node bit数放在最后等各种变种,但是主要思想还是来自于snowflake的思想。

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-序列号

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分成

db_buffer

是不是跟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表。

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

流程:

  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生成完全在内存中操作,避免中途因为访问数据库导致的延迟抖动。

db_buffer

  • 初始化的时候的确只有一个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的访问导致的生成过慢的问题,也算是一个比较好的解决方案。

<全文完>