漫谈分布式唯一ID

文章目录

本系列
前言
UUID
DB自增主键
Redis incr命令
号段模式
雪花算法

本系列

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

前言

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

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

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

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

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

还有一些非功能需求：

高可用：可用性至少5个9
低延迟：生成速度一定要快，TP50和TP99.9都要非常快，不能因为这个导致业务接口响应变慢
高并发：假如一下来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的唯一性，严格单调递增。缺点为：

性能问题：每次生成id需要一次数据库远程IO，发号器的瓶颈取决于db的读写性能
可用性问题：只用到一台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序列总体为趋势递增，既减少了单台实例的访问压力，也提高了可用性。缺点为：

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

Redis incr命令

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

从远程磁盘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，说明有其他实例获取了这个号段，需要重试再次获取

号段模式的优点如下：

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

缺点如下：

号段浪费：若某实例在号段没用完时就重启或宕机，则其号段剩余的ID就浪费了。解决方案为较小号段长度，但根据优点中的描述，这会降低性能和可用性，因此需要选择一个适中的号段长度
不够平滑：当号段用完时，会请求一次数据库，如果此时网络抖动，会使得该次请求响应较慢
1. 为了解决这种情况，可以在号段即将用完时就异步请求数据库获取下一个号段，而不是等到要用完再请求
可用性问题：和数据库自增键策略一样的单点问题

如何解决上面提到的可用性问题呢？使用多台实例。这里还是以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分钟的服务（容灾性高）

优点：

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

缺点：

TP999波动大：其他时候查本地缓存，但当号段用完时要查读写一次db
1. 解决：双buffer，例如当第一个buffer用到10%时就异步请求第二个buffer的号段
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

其优点为：