分布式唯一全局 ID 解决方案之一

1、分布式 ID 简介

1.1、业务背景

在复杂的分布式系统中,往往需要对大量的数据和消息进行唯一标识。比如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中数据日渐增长,对数据分库分表后需要有一个唯一 ID 来标识一条数据或消息。具体一点的如订单、骑手、优惠劵也都需要有唯一标识,此时一个能够生成全局唯一 ID 的系统是非常必要的。

1.2、ID 生成规则的硬性要求

  • 全局唯一:不能出现重复的 ID ,既然是唯一标识,这是最基本的要求
  • 单调递增:保证下一个 ID 大于上一个 ID,例如事务版本号、IM 增量信息、排序等特殊需求
  • 趋势递增:在 MySQL 的 InnoDB 存储引擎中使用的是聚集索引,由于多数 RDBMS 使用 BTree 的数据结构来存储索引数据,在主键的选择上面应该尽量使用有序的主键来保证写入性能
  • 信息安全:如果 ID 是连续的,恶意用户的爬取工作就非常容易做了,直接按照顺序下载指定 URL 即可 所以在一些应用场景下,需要 ID 无规则或者不规则,让竞争对手不好猜

上述的全局唯一、单调递增、趋势递增需求分别对应三类不同的业务场景,但单调递增和信息安全这两个需求是互斥的,无法使用同一个方案满足

1.3、ID 生成系统的可用性要求

  • 低延迟:发一个获取分布式 ID 的请求,服务器就要快,极速
  • 高可用:一个获取分布式 ID 的请求,服务器就要在保证 99.999% 成功率的情况下创建一个唯一分布式 ID
  • 高 QPS:假如并发一堆创建分布式 ID 的请求同时杀过来,服务器要顶得住且一下子成功创建 10 万个唯一分布式 ID

2、UUID 生成 ID

2.1、概述

UUID 按照 OSF 制定的标准计算,用到了以太网卡地址、纳秒级时间、芯片 ID 码和许多可能的数字,并由以下几部分的组成:当前日期和时间、时钟序列、全局唯一的 IEEE 机器识别号。UUID 的标准形式包含 32 个 16 进制的数字,以连字号分为 5 段,形式为 cb6ce510-74fe-4e18-ac3d-05a5c96d3a0f 的 36 个字符。特别注意,基于 MAC 地址生成 UUID 的算法可能会造成 MAC 地址泄露,这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。

2.2、优缺点

  • 优点:性能高,本地生成,没有网络消耗。如果只考虑唯一性,那么可以使用
  • 缺点:无序,长度较长,入库性能差,作为数据库主键时,会导致索引效率下降,空间占用较多
  • 适用场景:只要对存储空间没有苛刻要求的都能够适用,比如各种链路追踪、日志存储等

为什么无序的 UUID 会导致入库性能变差?

  • 无序:即无法预测 ID 的生成顺序,不能生成递增的有序数字
  • ID 长度过长:分布式 ID 一般都是作为主键,但是 MySQL 官方推荐主键尽量越短越好,36 个字符长度的 UUID 不是很推荐
  • B+ 树索引分裂:既然分布式 ID 是主键,然后主键是包含索引的,MySQL 的索引是通过 B+ 树来实现的,每一次新的 UUID 数据的插入,为了查询的优化,都会对索引的底层 B+ 树进行修改。因为 UUID 数据是无序的,所以每一次 UUID 的数据插入都会对主键底层的 B+ 树进行很大的修改,这一点非常不好。插入的 ID 完全无序,不但会导致一些中间节点产生分裂,也会白白的创造出很多的不饱和节点,这样大大的降低了数据库的插入性能

3、数据库自增 ID

3.1、概述

在分布式应用里,数据库的自增 ID 机制的主要原理是使用:MySQL 数据库自增 ID 和 replace into 来实现的。利用给字段设置 auto_incrementauto_increment_offset 来保证 ID 自增,每次业务使用下列 SQL 读写 MySQL 得到 ID。

mysql-replace-into

这里的 replace intoinsert 功能类似,不同点在于 replace into 首先会尝试插入数据到表中,如果发现表中已经有此行数据(根据主键或者唯一索引判断),则先删除旧数据,否则直接插入新数据

3.2、优缺点

优点:

  • 非常简单,利用现有数据库系统的功能实现,成本小
  • ID 单调自增,可以实现一些对 ID 有特殊要求的业务

缺点:

  • 生成的是单调递增的 ID,同时 ID 是可计算的,不适用于订单 ID 生成场景,否则竞争对手很从容易猜到
  • 分库分表后,同一数据表的自增 ID 容易重复,无法直接使用(可以设置自增步长,但局限性很明显)
  • 强依赖数据库,当数据库异常时整个系统不可用,属于致命问题。配置主从复制可以尽可能的增加可用性,但是数据一致性在特殊情况下难以保证,主从切换时的不一致可能会导致重复生成 ID
  • 生成 ID 的性能瓶颈限制在单台 MySQL 的读写性能,如果设计一个单独的数据库来实现分布式应用的数据唯一性,即使使用预生成方案,也会因为事务锁的问题,高并发场景容易出现单点瓶颈

适用场景:

  • 单数据库实例的表 ID(包含主从同步场景),部分按天计数的流水号等,不适用于分库分表场景、全局唯一 ID 场景

数据库的自增 ID 机制为什么不适合作为分布式 ID?

  • 在高并发的场景下,数据库压力还是很大,每次获取 ID 都得读写一次数据库,非常影响性能,不符合分布式 ID 里面的低延迟和高 QPS 的规则
  • 系统水平扩展比较困难,为了提高 MySQL 的性能,如果要增加 MySQL 数据库该怎么做?

3.3、MySQL 集群场景

在分布式系统中可以多部署几台机器,每台机器设置不同的初始值,且自增步长和机器数相等。比如有 2 台机器,设置自增步长为 2,TicketServer1 的初始值为 1(1,3,5,7,9,11 …)、TicketServer2 的初始值为 2(2,4,6,8,10 …)。如下所示,分别设置两台机器对应的参数,TicketServer1 从 1 开始生成 ID ,TicketServer2 从 2 开始生成 ID ,两台机器每次生成 ID 之后都递增 2。

1
2
3
4
5
6
7
TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1

TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2

假设要部署 N 台机器,自增步长需设置为 N,每台的初始值依次为 0,1,2 … N-1,那么整个架构就变成了如下图所示:

global-unique-id-mysql

这种架构貌似能够满足性能的需求,但有以下几个缺点:

  • 数据库压力还是很大,每次获取 ID 都得读写一次数据库,只能靠堆机器来提高性能
  • ID 没有了单调递增的特性,只能趋势递增,这个缺点对于一般业务需求不是很重要,可以容忍
  • 系统水平扩展比较困难,比如定义好了自增步长和机器台数之后,如果要添加机器该怎么做?假设现在只有一台机器生成 ID 是 1,2,3,4,5(自增步长是 1),这个时候需要扩容机器一台。可以这样做:把第二台机器的初始值设置得比第一台超过很多,比如 14(假设在扩容时间之内第一台不可能发到 14),同时设置自增步长为 2,那么这台机器下发的号码都是 14 以后的偶数。然后摘掉第一台,把 ID 值保留为奇数,比如 7,然后修改第一台的自增步长为 2。让它符合我们定义的号段标准,对于这个例子来说就是让第一台以后只能产生奇数。扩容方案看起来复杂吗?貌似还好,现在想象一下如果线上有 100 台机器,这个时候要扩容该怎么做?简直是噩梦,所以系统水平扩展方案复杂难以实现。

4、基于 Redis 生成全局 ID 策略

4.1、概述

因为 Redis 是单线程的,天生保证了原子性,可以使用原子操作 INCRINCRBY 来生成分布式唯一 ID

4.2、优缺点

优点:

  • 整体吞吐量比数据库方案要高

缺点:

  • Redis 实例或集群宕机后,找回最新的 ID 值有点困难
  • Redis 单机环境下,存在单点故障问题,导致 ID 生成服务不可用
  • 生成的是单调递增的 ID,同时 ID 是可计算的,不适用于订单 ID 生成场景,否则竞争对手很从容易猜到

适用场景:

  • 比较适合计数场景,如用户访问量,订单流水号(日期 + 流水号)等

4.3、Redis 集群场景

通过 Redis 集群来生成唯一 ID 时,需要设置相同的自增步长,且自增步长等于节点数,同时 Key 要求设置相同的有效期,以此来获得更高的吞吐量。假设一个集群中有 5 台 Redis,此时可以初始化每台 Redis 的值分别是 1,2,3,4,5,然后自增步长都是 5,那么各个 Redis 生成的 ID 为:

  • A:1,6,11,16,21
  • B:2,7,12,17,22
  • C:3,8,13,18,23
  • D:4,9,14,19,24
  • E:5,10,15,20,25

这种方式最大的缺点是复杂性太高,需要严重依赖第三方服务,集群管理繁琐,而且代码配置繁琐。一般来说,越是复杂的方案,越不可靠。

5、SnowFlake(雪花算法)

5.1、概述

SnowFlake 算法来源于 Twitter,使用 Scala 语言实现,利用 Thrift 框架实现 RPC 接口调用,最初的项目起因是数据库从 MySQL 迁移到 Cassandra,而 Cassandra 没有现成可用的 ID 生成机制,就催生了该算法。SnowFlake 的特性如下:

  • SnowFlake 生成 ID 能够按照时间有序生成
  • 经测试 SnowFlake 每秒能够产生 26 万个自增可排序 ID
  • 分布式系统内不会产生 ID 碰撞(由 datacenterworkerId 做区分),并且生成效率较高
  • SnowFlake 算法生成 ID 的结果是一个 64 bit 大小的整数,刚好为一个 Long 型,转换成字符串后长度最多是 19

5.2、结构

SnowFlake 算法的特性是有序、全局唯一、高性能、低延迟(响应时间在 2ms 以内),可在分布式环境(多集群,跨机房)下使用,因此使用 SnowFlake 算法得到的 ID 是分段组成的:

  • 与指定日期的时间差(毫秒级),41 位,够用 69 年
  • 集群 ID + 机器 ID,10 位,包括 5 位 datacenterId 和 5 位 workerId,最多支持 1024 台机器
  • 序列,12 位,每台机器每毫秒内最多产生 4096 个序列号

snowflake-1

  • 1bit:符号位,固定是 0,表示全部 ID 都是正整数
  • 41bit:时间戳(毫秒数时间差),从指定的日期算起,够用 69 年,用 Long 类型表示的时间戳是从 1970-01-01 00:00:00 开始算起的
  • 10bit:机器 ID,有异地部署,多集群的也可以配置,需要线下规划好各地机房,各集群,各实例 ID 的编号
  • 12bit:序列 ID,前面都相同的话,最多可以支持到 4096 个

5.3、优缺点

优点:

  • 可以根据自身业务特性分配 bit 位,非常灵活
  • 毫秒数在高位,自增序列在低位,整个 ID 都是趋势递增的
  • 不依赖数据库等三方系统,以服务的方式部署,稳定性更高,生成 ID 的效率也是非常高,低延迟

缺点:

  • 强依赖机器时钟,如果机器的时钟回拨了,会导致生成重复的 ID
  • 若生成环境中使用了容器化技术,实例的个数随时有变化,那么 SnowFlake 需要一定的改造才能更好地应用到生产环境中
  • 在单机上是递增的,但是由于涉及到分布式环境,每台机器上的时钟不可能完全同步(如时钟回拨),有时候可能会出现不是全局递增的情况(此缺点可认为无所谓,一般分布式 ID 只是要求趋势递增,并不会严格要求递增,90% 的业务需求都只需要趋势递增)

适用场景:

  • 分布式应用环境的数据主键

5.4、Java 版实现

Java 版的代码实现来自这里,在企业的项目开发中,一般可以直接使用封装好 SnowFlake 算法的 Java 工具库(如 Hutools 工具库),不再需要自己实现一遍,完整的代码如下:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/**
* twitter的snowflake算法 -- java实现
*
* @author beyond
* @date 2016/11/26
*/
public class SnowFlake {

/**
* 起始的时间戳
*/
private final static long START_STMP = 1480166465631L;

/**
* 每一部分占用的位数
*/
private final static long SEQUENCE_BIT = 12; //序列号占用的位数
private final static long MACHINE_BIT = 5; //机器标识占用的位数
private final static long DATACENTER_BIT = 5;//数据中心占用的位数

/**
* 每一部分的最大值
*/
private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

/**
* 每一部分向左的位移
*/
private final static long MACHINE_LEFT = SEQUENCE_BIT;
private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;

private long datacenterId; //数据中心
private long machineId; //机器标识
private long sequence = 0L; //序列号
private long lastStmp = -1L;//上一次时间戳

public SnowFlake(long datacenterId, long machineId) {
if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
}
if (machineId > MAX_MACHINE_NUM || machineId < 0) {
throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
}
this.datacenterId = datacenterId;
this.machineId = machineId;
}

/**
* 产生下一个ID
*
* @return
*/
public synchronized long nextId() {
long currStmp = getNewstmp();
if (currStmp < lastStmp) {
throw new RuntimeException("Clock moved backwards. Refusing to generate id");
}

if (currStmp == lastStmp) {
//相同毫秒内,序列号自增
sequence = (sequence + 1) & MAX_SEQUENCE;
//同一毫秒的序列数已经达到最大
if (sequence == 0L) {
currStmp = getNextMill();
}
} else {
//不同毫秒内,序列号置为0
sequence = 0L;
}

lastStmp = currStmp;

return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分
| datacenterId << DATACENTER_LEFT //数据中心部分
| machineId << MACHINE_LEFT //机器标识部分
| sequence; //序列号部分
}

private long getNextMill() {
long mill = getNewstmp();
while (mill <= lastStmp) {
mill = getNewstmp();
}
return mill;
}

private long getNewstmp() {
return System.currentTimeMillis();
}

public static void main(String[] args) {
SnowFlake snowFlake = new SnowFlake(2, 3);

for (int i = 0; i < (1 << 12); i++) {
System.out.println(snowFlake.nextId());
}

}
}

上面的代码基本上通过位移操作,将每段含义的数值,移到相应的位置上。如机器 ID 这里由数据中心 + 机器标识组成,所以,机器标识向左移 12 位,就是它的位置,数据中心的编号向左移 17 位,时间戳的值向左移 22 位,每部分占据自己的位置,各不干涉,由此组成一个完整的 ID 值。


了解 SnowFlake 的基本实现原理,可以通过提前规划好机器标识来实现,但目前的分布式生产环境,借用了多种云计算、容器化技术,实例的个数随时有变化,而且还需要处理服务器实例的时钟回拨问题,固定规划 ID 然后通过配置来使用 SnowFlake 的场景可行性不高。一般是自动启停,增减机器,这样就需要对 SnowFlake 进行一些改造才能更好地应用到生产环境中。

下篇 - 分布式唯一全局 ID 解决方案之二