漫谈分布式唯一ID

本系列

• 漫谈分布式唯一ID（本文）
• 分布式唯一ID生成（二）：leaf
• 分布式唯一ID生成（三）：uid-generator（待完成）
• 分布式唯一ID生成（四）：tinyid（待完成）

前言

在大多数业务场景中，需要对每条数据分配一个唯一ID作为标识。大部分关系型数据库提供了自增主键功能来支持该需求

但若数据量较大，需要分库分表时，就不能使用每个数据库实例提供的自增键功能，因为不能保证在所有表中唯一，分布式全局唯一ID的需求应运而生

分布式唯一ID有以下功能需求：

1. 全局唯一性：在某个业务场景下唯一，避免数据冲突，这是最基本的要求
2. 高性能：生成速度快，不能阻塞业务流程
3. 趋势递增：通常会将该ID作为数据库主键，由于mysql innoDB采用聚集索引，若新增的记录主键无序，可能造成 叶分裂 和 空间利用率不高 的问题，降低写入性能
4. 严格单调递增：适用于需要这种特性的场景，例如IM场景中需要根据此生成消息ID，用于给消息排序，并判断是否有消息丢失
5. 安全性：防止泄露业务信息，若生成的ID严格递增，在电商场景可根据一段时间的id差算出订单量
6. 方便追踪：例如在ID融入时间戳，就能知道是什么时间范围生成的

上述4，5需求是互斥的，无法同时满足。不同业务场景根据需求选择

还有一些非功能需求：

1. 高可用：可用性至少5个9

2. 低延迟：生成速度一定要快，TP50和TP99.9都要非常快，不能因为这个导致业务接口响应变慢

3. 高并发：假如一下来10w个生成分布式 ID 的请求，要能扛得住

接下来介绍一些常见的分布式ID生成方案

UUID

UUID（Universally unique identifier）一般包含32个十六进制的字符，128位，通过一定的算法计算出来，通常基于时间戳，mac地址，随机数等

优点为：

• 性能好：本地生成，无网络消耗
• 唯一性：可以认为不会发生冲突

某些版本基于命名空间能保证唯一性，某些版本基于随机数生成，不保证唯一性，但出现相同UUID的概率非常小，根据百度百科的说法，以java.util.UUID为例，每秒产生10亿笔UUID，100年后只产生一次重复的机率是50%

缺点：

• 没有趋势递增特性：作为数据库主键时插入性能不高，会导致叶分裂
• 数据较宽：通常UUID为128bit，不能用mysql的bigint存储，需使用字符串类型，对性能有一定影响
• 信息不安全：基于mac生成的uuid可能造成mac地址泄露

应用：生成traceId或logId

DB自增主键

以mysql为例，我们可以专门建一张表，利用其自增键来生成唯一ID

表结构如下：

CREATE TABLE unique_id (id bigint(20) unsigned NOT NULL auto_increment, value char(20) NOT NULL default '',PRIMARY KEY (id),UNIQUE KEY unique_v(value) 
) ENGINE=MyISAM;

使用以下sql获取id

begin; 
replace into unique_id (value) VALUES ('placeword'); 
select last_insert_id(); 
commit;

这里 使用replace而不是insert ，是为了保证整个表只有一条记录，因为不需要多余的记录也能生成自增id

这种方式利用数据库的自增主键保证生成id的唯一性，严格单调递增。缺点为：

1. 性能问题：每次生成id需要一次数据库远程IO，发号器的瓶颈取决于db的读写性能
2. 可用性问题：只用到一台db实例，存在单点问题，可用性没有保障

针对上面两个问题，可以引入多台mysql：每台实例的表使用不同的初始值

以2台mysql实例为例，分别做如下配置：

mysql1：

set @@auto_increment_offset = 1; -- 起始值 set @@auto_increment_increment = 2; -- 步长

mysql2：

set @@auto_increment_offset = 2; -- 起始值 set @@auto_increment_increment = 2; -- 步长

mysql1从 1 开始发号，mysql2从 2 开始发号，每次发号后递增2
这样mysql1生成的id序列为：

1,3,5,7,9....

mysql2为：

2,4,6,8....

当请求到来时，采用随机或轮询的方式请求这些实例，这样得到的id序列总体为趋势递增，既减少了单台实例的访问压力，也提高了可用性。缺点为：

1. 从单调递增变为趋势递增
2. 性能问题： 每次生成ID还是有一次远程数据库IO，对DB的压力还是大
3. 伸缩性问题：当需要扩展更多的机器时，需要调整之前所有实例的步长，且需要保证再次期间生成ID不冲突，实现起来较麻烦

Redis incr命令

为了解决数据库自增键遇到的性能问题，可以利用 redis的incr 命令来生成不重复的递增ID。该策略相较于数据库方案，优点为：

1. 从远程磁盘IO变为为远程内存IO，性能有一定提升，毕竟redis号称10w qps

但为了保证唯一性需要费一番功夫，依次讨论redis的各种持久化策略：

• 若不开启 redis 持久化，则redis宕机后会丢失已生成的ID，再生成会导致ID重复
• 若开启 RDB 或 AOF 中非AOF_FSYNC_ALWAYS模式的持久化，可能丢失最近一段时间的ID，一样会出现ID重复
• 若开启 AOF 中AOF_FSYNC_ALWAYS模式的持久化，能保证即使在宕机的情况下也不会出现ID重复，但性能会下降，相较于数据库方案没有太大的优势

号段模式

号段模式是为了解决数据库自增主键和redis incr方案中，每次获取ID都需要远程请求的问题

即每次从db获取一个ID范围，作为一个号段加载到内存，这样生成唯一ID时不需要每次都从数据库获取，而是从本地内存里获取，大大提高性能。本地缓存的号段用完时才请求db获取下一批号段

以mysql为例，数据库表结构如下：

CREATE TABLE unique_id ( id bigint(20) NOT NULL, max_id bigint(20) NOT NULL COMMENT '下个号段从哪开始分配', step int(10) NOT NULL COMMENT '一批ID的数量', PRIMARY KEY (`id`) ) ENGINE=InnoDB DEFAULT

每次获取一个号段时，执行如下sql：

update unique_id set max_id = {max_id} + step  where max_id = {max_id} 

当执行成功后判断 affectRows等于1，就能保证只有当前实例获得了 [max_id,max_id + step) 这个区间的号段，就能愉快地在内存发号了

若affectRows不等于1，说明有其他实例获取了这个号段，需要重试再次获取

号段模式的优点如下：

1. 性能很高：大部分情况下直接在内存发号，无需远程请求，号段范围越大，远程请求的比例越低
2. 可用性较高：若数据库宕机，可以使用之前获取的号段进行发号，号段范围越大，能撑的时间越久
3. 趋势递增

缺点如下：

1. 号段浪费：若某实例在号段没用完时就重启或宕机，则其号段剩余的ID就浪费了。解决方案为较小号段长度，但根据优点中的描述，这会降低性能和可用性，因此需要选择一个适中的号段长度

2. 不够平滑：当号段用完时，会请求一次数据库，如果此时网络抖动，会使得该次请求响应较慢

   1. 为了解决这种情况，可以在号段即将用完时就异步请求数据库获取下一个号段，而不是等到要用完再请求

3. 可用性问题：和数据库自增键策略一样的单点问题

如何解决上面提到的可用性问题呢？使用多台实例。这里还是以2台实例为例进行说明：

每次生获取完号段后，将max_id增加 号段长度 * 实例数量：

例如初始化时，mysql1.max_id=0，mysql2.max_id=1000。step都是1000

• 第一次访问mysql1，获取[0:1000)的号段，将mysql1.max_id更新成2000
• 第二次访问mysql2，获取[1000:2000)的号段，将mysql2.max_id更新成3000
• 第三次访问mysql1，获取[2000:3000)的号段，将mysql1.max_id更新成4000
• 第四次访问mysql2，获取[3000:4000)的号段，将mysql2.max_id更新成5000

这样既降低了单台数据库实例的访问压力，又提高了可用性

buffer数量设为多大？峰值qps的600倍，这样db宕机还能提供至少10分钟的服务（容灾性高）


优点：

1. id位64bit的数字，趋势递增
2. 对db的压力小
3. 可以很方便线性扩展：按照bizkey分库分表即可
4. 高可用：内部有缓存，如果数量为峰值qps的600倍，那么db宕机10分钟内都可用
5. id可以做到几乎单调递增
6. 可自定义maxId大小，方便原有业务迁移

缺点：

1. TP999波动大：其他时候查本地缓存，但当号段用完时要查读写一次db
   1. 解决：双buffer，例如当第一个buffer用到10%时就异步请求第二个buffer的号段
2. id不够随机，泄露发号数量

雪花算法

雪花算法使用一个64位的数字来表示唯一ID，而这64位中的每一位怎么用，就是其精髓所在

标准的雪花算法每一位含义如下：

• [0:0] 1位符号位：ID一般为正数，所以该位为0
• [1:41] 41位时间：通常用来表示 当前时间 - 业务开始时间 的时间差，而不是相对于1970年的时间戳，这样能支持的时间更久，若41位时间戳的单位为毫秒，则能支持大约(1 << 41) / (1000 * 60 * 60 * 24 * 365) = 69年
• [42:51] 10位机器：一般机器数没那么多，可以将 10位中分5位给机房，分5位给机器。这样就可以表示32个机房，每个机房下可以有32台机器
• [52:63] 12位自增序列号：表示某台机器上在某一毫秒（如果表示时间的单位为毫秒）内的生成的ID序列号，每毫秒支持1<<12 = 4096个ID，按照 qps算有409.6万

位的分配可以根据业务的不同进行调整，例如若机器数没那么多，不需要10位表示，可增大时间位，以支持更长的时间范围。或者业务并发量不高时，可将时间单位改为秒，将节省出来的位用于表示其他含义

只要每个实例的机器ID不同，则不同机器间生成的ID一定不同，因为其[42:51]位不一样

这样划分后，在一毫秒内一个数据中心的一台机器上可以产生4096个的不重复的ID

其优点为：

1. 不依赖数据库，性能和可用性非常好
2. 如果时间戳在高位，能保证ID趋势递增
3. 理论上支持超高的并发，因为qps有409万，基本不可能有业务的写操作能达到这个qps

缺点为：

1. ID的生成强依赖于服务器时钟，如果发生时钟回拨，则可能和以前生成过的ID产生冲突

时钟回拨：硬件时钟可能会因为各种原因发生不准的情况，网络中提供了ntp服务来做时间校准，做校准的时候就会发生时钟的跳跃或者回拨的问题

2. 10位的机器号较难指定，最好不要手工指定，而是实例去自动获取

针对时钟回拨问题，可分两种情况讨论：

• 实例运行过程中发生时钟回拨：此时可以在内存中 记录上次时间戳，若这次获取的时间戳比上次小，说明发生了时钟回拨，可以等待一段时间再进行ID生成，若回拨幅度较大，则可选择继续等待，或给上层报错，因为在短时间内无法生成正确的ID

也可以完全不依赖系统时间，例如百度的uid-generator使用一个原子变量，每次加一来生成下一个时间

• 实例重启过程中发生时钟回拨：此时没办法从内存中获取上次的时间戳，因此需要将上次时间戳放到外部存储中。美团leaf的方案为，每3s往zookeeper上报一次当前时间戳，这样在实例重启时，也能判断出是否发生了时钟回拨

但存在外部不能完全避免时钟回拨，例如在t时刻将t保存在zk，在 t+1 时刻分配了一个ID，在 t+2 时刻宕机，时钟回退了1s到t+1，此时检测 t+1 > zk 中的时间t，没问题。但依然会产生 t+1 时刻的重复ID

因此最保险的办法时：宕机后sleep一段时间再重启，这段时间要超过时钟回退的时间

针对机器号生成困难问题：有以下几种解决方案：

• 使用zookeeper：每次实例启动时，都去zookeeper下创建一个节点，利用其节点编号当做机器id，zookeeper保证每次生成的节点编号唯一

• 使用mysql：也可以在实例启动时，去数据库的表插入一条记录，利用自增主键当做机器ID，同样能保证机器ID的唯一性

适用场景：订单中，不想让别人根据早上和晚上的订单id号猜到销量的场景