什么是分布式ID?

你好,我是猿java

最近,今天,我们一起来聊聊几种常见的分布式ID 生成的几种方式。

为什么需要分布式ID?

在复杂的分布式系统中,常常需要一个全局唯一的 ID来标识数据,消息或者请求,比如:订单号,消息的唯一标识,接口的幂等ID 等等。

分布式 ID需要具备什么条件

作为分布式 ID,通常建议需要具备以下 4个要求:

1.全局唯一

全局唯一,是指在支撑的业务范围内能保持全局唯一,这里的全局范围可大可小,大到成千上万部门的集团,小到某个团队内的几个系统,
所以在设计分布式 ID的时候,一定要清晰地定位受众范围。

2.数量够用

既然是分布式ID,那就一定要保证数量够用,需要根据公司具体业务来评估,在一定时间范围内会消耗多个ID,
比如,用于订单号,需要预估每年会产生多少订单,消耗需要多少个订单号,需要支持几年。

3.安全性

分布式 ID生成的算法应该是安全的,防止恶意用户预测或推断出其他ID,甚至恶意篡改。

4.有序性

通常建议分布式ID具备有序性,不过需要根据实际的业务来。

生成算法

UUID

UUID,Universally Unique Identifier(通用唯一识别码),由 128位(理论上限是 2^128个,绝对够用),通常表示成 32个十六进制数字,并且以“-”分隔成五组(8位-4位-4位-4位-12位),
比如:62f77d2d-aefe-41ba-b0f8-4c4c39ab670e。

UUID有 5种常见的生成方式,这里总结了构成,用途和特点:

1.基于时间戳和 MAC地址

  • 构成:基于当前时间戳、时钟序列和机器的MAC地址。
  • 用途:可以确保跨空间(不同机器)和时间的唯一性。
  • 特点:可能会暴露生成 UUID的机器地址和时间。

Java的实现代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
// gradle 依赖: implementation 'com.fasterxml.uuid:java-uuid-generator:5.0.0'
/** maven依赖
<dependency>
<groupId>com.fasterxml.uuid</groupId>
<artifactId>java-uuid-generator</artifactId>
<version>5.0.0</version>
</dependency>
*/
import com.fasterxml.uuid.Generators;
public static void generateUUID() {
UUID uuid = Generators.timeBasedGenerator().generate();
System.out.println(uuid); // 比如:de02864c-eda8-11ee-a793-dd2f40a50976
}

2.DCE安全的UUID

  • 构成:与方法1类似,但将一部分空间用于包含 POSIX的 UID或 GID。
  • 用途:用于DCE(分布式计算环境)的安全性。
  • 特点:并不常用,和方法1相似,但提供了额外的用户或组识别信息。

3.基于名字的MD5散列

  • 构成:使用名字空间(Namespace)和特定名字生成 MD5散列。java.util.UUID 提供了这种方式,需要传入指,使用比较少。
  • 用途:为相同名字生成相同的 UUID,但不同名字空间下的相同名字将生成不同的 UUID。
  • 特点:相同输入产生相同输出,但由于 MD5容易被破解,不安全,因此现在使用较少。

Java的实现代码示例:

1
2
3
4
5
6
7

import java.util.UUID;
public static void generateUUID() {
String key = "xxxxx"; // 自己指定的key
UUID uuid3 = UUID.nameUUIDFromBytes(key.getBytes()).toString();
System.out.println(uuid); // 比如:ea416ed0-759d-36a8-9e58-f63a59077499
}

4.随机生成

  • 构成:使用随机数或伪随机数生成,java.util.UUID 是基于这种方式,使用比较多。
  • 用途:不需要基于时间或名字,仅需要快速生成UUID。
  • 特点:简单,没有时间顺序,不具备可预测性。

Java的实现代码示例:

1
2
3
4
5
import java.util.UUID;
public static void main(String[] args) {
String uuid = UUID.randomUUID().toString();
System.out.println(uuid); //比如:ea416ed0-759d-36a8-9e58-f63a59077499
}

5.基于名字的 SHA-1散列

  • 构成:与方法3类似,使用 SHA-1散列算法代替 MD5。
  • 用途:为相同名字生成相同的UUID,通常用于避免 MD5弱点的场景。
  • 特点:比方法3的 MD5更安全,但SHA-1目前也已被认为不够安全,比较少使用。

Java的实现代码示例:

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
import java.security.MessageDigest;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.util.UUID;

public static UUID generateUUID(String namespace, String name) {
try {
MessageDigest sha1 = MessageDigest.getInstance("SHA-1");
sha1.update(namespace.getBytes());
byte[] result = sha1.digest(name.getBytes());

// Set the version to 5
result[6] &= 0x0f; // clear version
result[6] |= 0x50; // set to version 5

// Set the variant to 2
result[8] &= 0x3f; // clear variant
result[8] |= 0x80; // set to IETF variant

ByteBuffer buffer = ByteBuffer.wrap(result);
buffer.order(ByteOrder.BIG_ENDIAN);
return new UUID(buffer.getLong(), buffer.getLong());
} catch (Exception e) {
throw new RuntimeException("Unable to generate Version 5 UUID", e);
}
}
// 使用namespace和name生成Version 5 UUID
UUID uuid5 = generateType5UUID("namespace", "name"); // 比如:c717c842-f1d0-5079-a123-4a86d058c64f

到此,我们对 UUID有了一个全面的认识,最后,总结下 UUID的优缺点以及一些使用建议:

优点

  1. 生成方式简单,各种语言都有成熟的类库
  2. 本地生成,性能高,不依赖网络
  3. 随机机行强,不容被预测

缺点

  1. 无序,不利于排序,用于 MySQL主键时对索引不够友好
  2. 32位,字符串太长,存储需要消耗更多的空间
  3. 具体生成 UUID算法的缺点

使用建议

  • 日常工作为了使用更美观,一般会把 UUID中的 “-”去掉
  • 如果对 UUID的缺点没有任何要求,完全可以采用这种方式来生成分布式 ID,比如,作为接口的幂等ID
  • UUID有重复的概率,但是几乎可以忽略不计

ULID

ULID 是 Universally Unique Lexicographically Sortable Identifier的缩写,它是一种全局唯一、按字典序可排序的标识符。

ULID 由 48-bit的时间戳 + 80-bit 的随机数组成,时间戳表示自 1970 年 1 月 1 日 UTC 起的毫秒数,可以支持大约 280 年的时间范围。

下面借助三方库 Sulky ULID 演示如何使用 Java 生成 ULID:

1
2
3
4
5
6
7
8
import de.huxhorn.sulky.ulid.ULID;
public class ULIDTest {
public static void main(String[] args) {
ULID ulid = new ULID();
String id = ulid.nextULID();
System.out.println("ULID: " + id); // 01HTBBBDYK0YMQ8X1Z50QGDH9E
}
}

最后总结下 ULID 的优缺点:

优点:

  • 可排序:ULID 由 48-bit 时间戳开头,可以按照生成时间进行排序

  • 高性能:由于 ULID 使用时间戳和随机数,生成速度较快。

缺点:

  • ULID 依赖于时间戳,极端情况可能会出现时间回拨导致 ID冲突

基于 Redis

在 Redis中,可以通过 INCR 和 INCRBY 等自增原子命令,来实现有序的分布式ID

img.png

下面总结下 Redis的优缺点:

优点

  • 高性能
  • 生成的ID有序

缺点

  • 需要增加 Redis的成本
  • 强依赖 Redis,因此需要保证 Redis服务的稳定性
  • 生成的ID 有序,对于敏感业务,ID容易被预测

基于MySQL数据库

通过 MySQL数据表的主键(int 或 bigint)自增来生成 ID。

int(或 integer)

  • 无符号的范围是 0 到 4294967295(42亿多)
  • 有符号的范围是 -2147483648 到 2147483647

bigint

  • 无符号的范围是 0 到 18446744073709551615
  • 有符号的范围是 -9223372036854775808 到 9223372036854775807

假如每天消耗 1亿个,使用的总年数:18446744073709551615 / 100,000,000 / 365 ≈ 505061753 年。

假如每天消耗 1万亿个,使用的总年数:18446744073709551615 / 100,000,000,000,0 / 365 ≈ 50506 年(5万年)。

使用 MySQL的 bigint,就算业务体量每天消耗一万亿个 ID,需要 5万年才能消耗完,绝对够用。

接下来分析基于MySQL 的2种实现方式:

乞丐版

首先,创建一张 distributed_ids表,用于记录已经生成的 ID(如果 ID不想从 1开始,可以在创建表时给主键 ID设置一个起始值),表设计如下:

1
2
3
4
5
6
7
8
9
10
11
CREATE TABLE `distributed_ids` (
`id` BIGINT(20) NOT NULL AUTO_INCREMENT,
`created_at` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
PRIMARY KEY (`id`)
) ENGINE=InnoDB;
-- 或者
CREATE TABLE `distributed_ids` (
`id` BIGINT(20) NOT NULL AUTO_INCREMENT,
`created_at` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT 1000000; -- 1000000可以设置成具体的起始值

接着,我们需要包装一个 ID生成的服务对外提供给业务使用,整体架构思路图如下:

img.png

下面为对外提供服务核心步骤的 java伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
@Controller
public class IdGeneratorController {
@GetMapping("/generateId")
public Long generateId() {
Long id = null;
synchronized (this) {
// generate id; sql: UPDATE distributed_ids SET id = id + 1(step);
// select max id; sql: SELECT id FROM distributed_ids ORDER BY id desc limit 1;
}
return id;
}
}

到此,一个简单的 ID生成系统就完成了,总结下该方案的优缺点:

优点

  • 实现简单,维护成本低
  • ID单调递增
  • 可以用较少的成本实现体量较小的业务需求

缺点

  • 每次获取 ID时候需要进行两次 DB操作
  • 强依赖于 DB,DB性能以及稳定性直接影响 ID生成系统的稳定性,而且这里有 DB单节点的风险

对于缺点中单台 MySQL存在性能问题,我们自然会想到增加一台 MySQL,一台使用奇数自增(1,3,5,7,2n-1),一台使用偶数自增(2,4,6,8,2n),这样是不是就可以分摊压力了?
如果 2台 MySQL还不够用,那我们可以使用 N台,每台的初始值依次为 1, 2, 3 … N-1,步长是N(机器的数量),整个架构思路图如下:

img.png

仔细观察上述架构图可以发现,对于 MySQL节点选择其实本质上是一个 Hash算法,因此,该方案存在 Hash算法典型的缺点:水平扩容困难,扩容时,需要涉及到大量的数据迁移。

那么,有没有一个更优的设计方案,既能减少对 DB的操作,又能避免 DB的性能瓶颈?

号段版

号段版是指每次获取一批 ID(比如 1000,10000),而不是一个 ID,然后在内存中去分发号段内的号码。 对此,表结构该如何设计呢?

这里我们引入了号段最大值(max_id) 和步长(step)两个概念,max_id是指表中末次获取号段时的最大 ID号,step是指每次获取多少个 ID。
比如,初始值是 1,第一次获取 1000个ID,那 max_id=1000, step=1000,第二获取 1000个ID,那么 max_id=2000, step=1000,表结构设计如下:

1
2
3
4
5
6
7
-- 号段 + 步长step
CREATE TABLE `distributed_ids` (
`max_id` BIGINT(20) NOT NULL AUTO_INCREMENT,
`step` INT(11) NOT NULL,
`created_at` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT 1; -- 1可以设置成具体的起始值

整体架构思路图:

img.png

对于这个方案中的 step设置多大比较合理,一般会参考流量高峰期的是QPS/TPS, 假设高峰期的 QPS是 1000(1s会消耗 1000个ID),
如果想取用一次号段持续使用 10分钟,那么 step=1000 * 60 * 10,即 step是 QPS的 600倍,以此类推,
也可以参考以往业务流量分布,确认峰值一般会维持多长时间,根据这个时间来设定一个合理的 step,这样就可以避免业务高峰期频繁去操作 DB获取号段。

总结下方案的优缺点

优点

  • 一次批量获取 ID,大大降低了对 MySQL的压力,比如QPS是 1万,如果 step设置为1000, 那么对 MySQL的压力就从 10000降到 10
  • step可以更具业务压力灵活调整,可以将此参数设置为配置变量

缺点

  • DB不可用导致整个ID生成系统不可用
  • ID规律性太强,很容易识别语义,比如,用于订单号时,可以根据某一个订单号轻易地猜测出其他订单号

对于缺点1,可以采用高可用容灾方案:主从(一主多从) + 多活(2地3活),当主节点挂了,可以切换到从节点,当机房A 出现问题,
可以切换到机房B,这样充分保证服服务器的高可用,思路看起来简单,但是实施起来比较困难,特别是主从切换的时候,如何保证数据一致性是一个比较大的挑战。

对于缺点2,可以采用雪花算法等方案来生成随机且递增的 ID,这部分内容会在其他的文章中分享。

整个高可用容灾方案如下图:

img.png

雪花算法

Snowflake,雪花算法是由 Twitter开源的分布式 ID生成算法,整个 ID保含有 64 bit,对表 Java的 Long类型,如下图:

img.png

以划分命名空间的方式将 64-bit位分割成多个部分,每个部分代表不同的含义。而 Java中64bit的整数是Long类型,所以在 Java 中 SnowFlake 算法生成的 ID 就是 long 来存储的。

为了更好的说明,我将 64bit 分成A,B,C,D 4部分:

  • A部分,占用 1-bit,代表符号位,其值始终是0
  • B部分,占用 41-bit,代表时间戳,可表示 2^41 个数,每个数代表毫秒,那么雪花算法可用的时间年限是(1L<<41)/(1000L360024*365)=69 年的时间。
  • C部分,占用 10-bit,代表机器数或者 IDC(数据中心)+机器数,如果是机器数,即 2^10 = 1024 台机器,如果是 IDC+机器数, 一般会将它分成 5-bit 给 ID(最大 32个IDC)C,分5-bit给工作机器(最大 32太机器),这里可以根据自身业务特性看来灵活使用。
  • D部分,占用 12-bit,代表自增序列,可表示2^12 = 4096个数。

因此,基于上述的划分可以看出,每豪秒能产生 1024 * 4096个有序的不重复的ID。

总结下雪花算法的优缺点:

优点

  • 本地生成,不依赖数据库等第三方系统,稳定性高
  • ID是趋势递增,对于敏感,不具备可预测性
  • 可以根据自身业务特性灵活分配 bit位

缺点

  • 强依赖机器时钟,如果时钟回拨,可能会导致 ID重复

三方工具

1.美团的 Leaf

Leaf是美团开源的分布式 ID生成工具,它包含 Leaf-segment 和 Leaf-snowflake两种方案, Leaf-segment是基于 MySQL数据库,它是针对上述 MySQL方案的更优秀设计,Leaf-snowflake 是基于雪花算法,并且解决雪花算法中时钟回拨的问题。

详情参考美团官方 Leaf文档:https://tech.meituan.com/2017/04/21/mt-leaf.html

2.百度-UidGenerator

UidGenerator 百度开源的一款用 Java语言实现,基于 Snowflake算法的唯一ID生成器。
包含 DefaultUidGenerator 和 CachedUidGenerator 2种实现方式:

  • DefaultUidGenerator 是基于时间戳和机器位还有序列号的生成方式,和雪花算法很相似,对于时钟回拨也只是抛异常处理。仅有一些不同,如以秒为为单位而不再是毫秒和支持Docker等虚拟化环境。
  • CachedUidGenerator 是使用 RingBuffer 缓存生成的id。数组每个元素成为一个slot。RingBuffer容量,默认为Snowflake算法中sequence最大值(2^13 = 8192)。可通过 boostPower 配置进行扩容,以提高 RingBuffer 读写吞吐量。

详情参考百度 UidGenerator文档:https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

总结

上述我们分析了几种常见的分布式 ID生成方式,具体选用哪种可以根据自身业务:

  • UUID,简单高校,但是无序,作为ID主键不友好;

  • MySQL 乞丐版,相对简单,但是不适合大流量的场景

  • MySQL 号段版,适合大流量的场景,当MySQL故障需要主从切换时需要保持数据的一致性

  • 三方工具,经过生产环境的考验,是很不错的方式,如果不想重复造轮子,可以三方工具

交流学习

如果文章存在缺点和错误,欢迎批评指正。更多干货和面试经,关注公众号:猿java。

drawing