Github

分布式ID

在分布式场景下，特别是在高并发，高数据量的情况下，ID的生成策略尤其重要。

分布式ID的特点？

  1. 分布式环境下全局唯一性

  2. 有序性，单调性

  3. 信息安全，如果是单纯的规律ID，可能会造成私密数据的推断，ID可能会泄露导致被爬取

  4. 高可用性

  5. 高并发

如何设计一个分布式ID的生成方案？

设计一个分布式 ID 的生成方案需要两个步骤：

  1. 生成二进制的 ID，通常从伪随机数、时间、节点ID 中选取

  2. 将该二进制的 ID 转成人类可读、易于传输的字符串文本

1. 生成二进制ID

生成二进制ID，又可以划分为三大类生成策略：

方案
描述
方案

伪随机数

完全由伪随机数保证唯一性

UUID、Nano ID

时间 + 伪随机数

高位由时间组成，低位由伪随机数组成。在同一时间下，用伪随机数保证唯一性。

ULID、KSUID

时间 + 节点 ID + 递增计数

高位由时间组成，低位由节点 ID 和递增计数组成，取代了上面方案中的伪随机数。在同一时间下的某个节点上，用递增计数保证唯一性。

Snowflake ID、Mongdb objectID

基于伪随机数方案

完全由伪随机数保证唯一性。

方案
伪随机数(bit)
总位数

UUID v4

122

(122+6) 128

Nano ID

126

126

UUID v4 使用了 122 位的伪随机数，然后另外有 4 位表示版本号为 4；以及 2 位表示变体种类。但由于一旦采用了确定的方案，这个值是不会再发生改变的，所以虽然总长 128 位，但实际保证唯一性的位数为 122 位。

基于时间+伪随机数方案

高位由时间组成，低位由伪随机数组成。在同一时间下，用伪随机数保证唯一性。因为时间排在高位，故使用使时间内进行排序。

方案
时间(bit)
伪随机数(bit)
总位数

ULID

48

80

128

KSUID

32

128

160

注意，ULID 使用的伪随机数并非是完全随机的，它号称实现了同一时间内单调自增；但这是有争议的，具体在 单调性 一节中讨论这个问题。

基于时间+节点ID+递增计数的方案

方案
时间(bit)
节点ID(bit)
进程ID(bit)
递增计数(bit)
二进制(bit)

Snowflake ID

41

10

-

12

(63+1) 64

MongoDB ObjectID

32

24

16

24

96

可以注意到 Snowflake ID 的二进制位数被表示成了 (63+1)，这是因为 Snowflake ID 被用于保证唯一性的位数有 63 位，以及最高 1 bit 被留作备用。

MongoDB ObjectID 还进一步使用了自身进程的 PID。

尽管 Snowflake ID 和 MongoDB ObjectID 都使用递增计数，但它们的实现方式稍有差异。同一个时间下，Snowflake ID 的递增计数从 0 开始自增，到下一个时间点重置为 0；MongoDB ObjectID 从一开始就生成一个伪随机数作为递增计数，在相同时间的情况下该数自增，到下一个时间点不会重置。

可以注意到，Sonyflake 受到了来自 Snowflake 的启发，它们使用了相同的思路，但实现方式稍有差异。另外借鉴其思想的还有美团的 Leaf，百度的 uid-generator，可见 Snowflake 算法是比较热门的选择。

2、将二进制编码成文本

在上一步中，我们已经得到了二进制形式的 ID，接下来要把它转成可打印和方便传输的字符串。

方案
二进制(bit)
文本(bit/byte)
编码(变体)
alphabet

UUID v4

128

256/32

base16

[0-9A-F]

Nano ID

126

168/21

base64

[0-9A-Za-z_-]

ULID

128

208 / 26

base32

(?![ILOU])[0-9A-Z]

KSUID

160

216 / 27

base62

[0-9A-Za-z]

Snowflake ID

64

-

自选

自选

MongoDB ObjectID

96

192 / 24

base16

[0-9A-F]

ID关键信息的获取/生成方式

伪随机数的生成方式

UUID v4 和 Nano ID，就是完全由伪随机数组成的。随机数的位数越多，碰撞概率越低。使用伪随机数的方案，相比不使用伪随机数的方案，能额外提供不可预测性。

生成伪随机数依赖系统的伪随机数发生器，有两个 API 可供调用：

  • Math.random，生成的随机数更有规律，更容易预测

  • Crypto API，实际是从 /dev/urandom 中获取

Crypto API是指JCA（Java Cryptography Architecture）中的API，那么可以使用SecureRandom类来生成加密级别的安全随机数：

// 创建一个SecureRandom实例
SecureRandom secureRandom = new SecureRandom();

// 生成一个int类型的随机数
int randomInt = secureRandom.nextInt(); // 生成所有32位int范围内的随机数
System.out.println("Random integer: " + randomInt);

// 若要生成指定范围内的随机数，例如1到100
int boundedRandomInt = secureRandom.nextInt(100) + 1;
System.out.println("Random integer between 1 and 100: " + boundedRandomInt);

如果需要线程安全支持：

// 使用ThreadLocalRandom生成一个介于1和100之间的随机数
int threadSafeRandom = ThreadLocalRandom.current().nextInt(1, 101);
System.out.println("Thread-safe random integer between 1 and 100: " + threadSafeRandom);

时间的生成方式

引入时间能有效降低 ID 总长度，因为这样可以不需要太多的伪随机数来保证唯一性：

方案
时间精度
位数(bit)
计时起点

ULID

ms

48

Unix epoch

KSUID

s

32

2014年3月5日

Snowflake ID

ms

41

Twitter epoch

MongoDB ObjectID

s

32

Unix epoch

一个 ID 方案的时间可以从 Unix 纪元开始计时，因为该方法比较通用。也可以从自定义的时间开始，就比如 Twitter 主导的 Snowflake 算法使用了它定义的 Twitter epoch，是从 2010 年 11 月 4 日 01:42:54 UTC 开始计时的，并且允许用户修改成其他时间。

所有带有时间的 ID 方案都在宣称自己是可排序的 (lexicographically sortable)。但要注意它们是粗略的 (roughly/loosely) 排序，在相同时间下不能区分先后。

为此，时间一定会放在 ID 的最高位，并且使用大端字节序 (big-endian)。

必须注意，ID 中的时间不代表它就是现实时间！它应该使用时间戳，而且是 单调时间 (monotonic clock)。想直接从 ID 中获取时间信息的想法是脱离实际的，因为单调时间不是 墙上时间 (wall clock)。该时间是用来保证唯一性和可排序性的，而不是为了将时间信息嵌入到 ID 中。不能依赖它来获知 ID 的创建时间！

所以，需要注意时钟回拨问题：即使发生墙上时钟回拨，单调时钟依旧在增加。单调时间依赖进程保持运行，只有进程存在，才能记录运行时间。在进程重启后，丢失了之前进程记录的单调时间，这时单调时钟也不可避免地遭遇时钟回拨。

节点ID的生成

可以从一个节点环境中获取各种 ID，再汇入到最终结果的节点 ID 中。可以从：

  • MAC 地址

  • 主机名

  • dmi product_uuid

    • DMI (Desktop Management Interface) 是一种标准，它允许系统硬件信息被操作系统和管理工具以标准化的方式访问。

    • 在DMI数据结构中，product_uuid 是一个特定的属性，代表了系统的唯一标识符（Universally Unique Identifier, UUID）。

  • PID，进程ID

  • UID，GID 系统用户的用户ID和组ID

  • CUID，浏览器指纹 中获取。只要是节点所在环境中能被利用的 ID，统统都可以纳入节点 ID 中。

正如引入时间可以减少伪随机数的位数一样，节点 ID 可以进一步减少对伪随机数的依赖，snowflake 完全放弃了伪随机数，使用一个从 0 开始递增的序号。

相关特性和问题

伪随机数的不可预测性

伪随机数在每次生成都是一个新的不可预知的随机数，这是伪随机数的不可预测性。不可预测性可以有效避免暴露一些数据信息，比如如果使用自增id，很容易被推算出一天的订单量。

xid实现方式是在初始化时生成一个伪随机数，然后每次生成新 ID 时在该伪随机数上递增，他不具备不可预测性。

实现不可预测性，必须使用强有力的随机数，像估计Snowflak算法的ID范围也是比较容易的。

时钟偏移问题

请先注意墙上时钟 (wall clock) 和单调时钟 (monotonic clock) 的区别。

ID 方案使用了单调时间，意思是它的时间永远单调递增，而不会因为 NTP发生时间回拨；另一方面，代表着时间很可能不是现实时间。

基于「时间 + 节点 ID」中使用了递增计数，在时钟回拨发生的情况下可能会产生重复 ID。基于「时间 + 伪随机数」则没这个问题，因为伪随机数就是用来防止同一时间内发生碰撞的。

常见的解决办法有，如果时间滞后，生成 ID 时直接失败，等待时间超过先前生成的 ID 的时间。在多节点冗余的情况下，已时间回拨的节点不提供服务，另外一些节点先不校准时间而是继续提供服务，可以保证服务不宕机。再比如，百度的 uid-generator 方案，在实现 Snowflake 算法时，使用了未来时间，突破了时钟限制。所以很重要的一点要再次强调，ID 方案中的时间部分完全可以不与真实时间关联，它并非是为了传递信息，而仅仅是作为保证 ID 唯一性的组成部分。

K-sorted

上面提到的 4 种带时间的 ID 方案，除了 ULID，剩下 3 种都不是完全排序的，它们在同一时间 ( 秒或毫秒) 内不保证顺序。设想同一个事务中，有 A 和 B 两个步骤，B 要在 A 之后发生。如果为 A 和 B 生成 ID 时恰好在同一个时间点内 (这很常见)，那么在分布式环境中，为 B 生成的 ID 不能保证比 A 大。

所以它们确实是可排序的，但是要注意是 K-sorted，意思是生成了总个数为 n 的 ID 数组，分为 k 组，每组的 ID 不保证排序，但是后一组中的所有 ID 一定比前一组大。

关于如何保证在相同的时间点内也保证排序，这需要在分布式环境中存在一种同步机制，比如严格的自增序号，数据库生成的自增 ID 来保证强顺序。

单调性

ULID 号称实现了一项特性，叫做单调性。它采取了两种方式来保证生成的 UUID 是可以按时间排序的。在同一个时间 (毫秒) 内，随机数单调递增。在 golang 的实现中，增长幅度既可等长，也可以是随机步长。实际上是通过维护一个 Monotonic 结构体，多个 ID 生成实例从该结构体中生成 ID，那么在同一个时间点中，后生成的 ID 确实比前一个大。如果到了下一时间点，将从一个完全的随机数开始。

但是真正的问题是，在分布式环境中是无法保证这个单调性的。首先，时间不能保证同步。其次，Monotonic 结构体要在分布式环境中共享才行。所以，保持单调性要有额外且复杂的同步机制，这显然不是通过使用 ULID 就能保证的。

ULID 在单调性方面存在争议：Issue 11。考虑到 ULID 只是一份规范，它的各种语言实现不一定完全遵守规范，所以在使用 ULID 的库时还请多加留意。

时钟序列

时钟序列问题是为了解决同一时间戳下可能会发生大量的id生成请求，这是可以使用时钟序列，他是一个自增的数字，没生成一次id都会自增一次，当时间戳发生变化时，时钟序列会进行重置。

编码方式

baseXX

直接将二进制按 ASCII 映射到字符肯定是行不通的，这样做会有很多不可见的字符。所以实际上要用到 baseXX 编码来转。

baseXX 编码可以理解成 XX 进制，将二进制数映射到一个 alphabet，该 alphabet 可以包含字母、数字以及其他可见符号。这里提供一个简单的理解：

  • base16 二进制每4位转为一个字符

  • base32 二进制每5位转为一个字符

  • base64 二进制每6位转为一个字符

由于字符要占 8 位，所以转成文本后总位数变长。

base16 就是常见的 Hex 编码。使用该方式的典型代表就是 UUID。base64 使用大小写字母区分，所以相应地 Nano ID 是大小写敏感的。base32 不包含字母的大小写，所以相应地 ULID 是大小写不敏感的。

我们都知道，无论是base32还是base64等编码方式，如果末尾位数不足的情况下要进行补 0，标准情况下还要填充=。实际上这个=可有可无，所以在所有的生成 ID 的方案中，都不要求填充=。

Nano ID 不需要在末尾补 0，它采用 126 位的伪随机数，那么按照 base64 的规则，每 6 位对应 1 个字符的话，结果正好是 21 个字符。

这些 ID 方案都采用了 BaseXX 编码的变体形式。

Nano ID 使用的是在 URL 中安全的 alphabet，包含A-Z，a-z，0-9，-和_，而不包含原始标准中的+和/，这样就不会再次被 URL 编码了。在 URL 中安全的 alphabet：

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_ ULID 用的是 base32 的变体形式 Crockford’s Base32，这种编码不包含 I L O U 这些容易产生误解的字符。

标准 base32 采用的字符有两种：

ABCDEFGHIJKLMNOPQRSTUVWXYZ234567

或者

0123456789ABCDEFGHJKMNPQRSTVWXYZ

而 Crockford’s Base32 采用的字符：

0123456789ABCDEFGHJKMNPQRSTVWXYZ

想一想，你能轻易区分数字和字母 1 l L，0 o O 吗？这需要一个重视此方面的、辨识度高的字体。但并不是所有环境中的字体都能做到。很多无衬线字体是很难分辨清楚这些字符的。

人类可读

ID 足够短，不是编码是否优秀的唯一考量。还需要考虑人类可读 (human-readable)，这取决于具体的应用场景。对人类友好的 ID 首先要足够短小精简那是肯定的，除此之外还要考虑大小写问题、字符的辨认问题。

所以，奇奇怪怪的特殊字符就不用考虑啦。一般都优先使用 A-Za-z0-9 这些常见字符。

就比如 ULID 做到了大小写不敏感，其采用的编码方式 Crockford’s Base32 只包含容易辨认的字符。这样在分辨 ID 和输入 ID 的时候更加轻松。

Nano ID 则为了追求更加紧凑，需要区分大小写，引入字符-和_，虽然牺牲了一点可读性，但是获得了更短的长度。

由于 UUID 只使用 16 进制字符，容易理解和转换成原始的二进制数据，但代价是它的字符串最长。

URL-safe

/和+需要经过 URL 编码，才能在 URL 中使用。所以在选择 alphabet 的时候，应该有意避开这两个字符。标准的 base64 就显得不合适了，所有还有个对 URL 友好的 base64 版本，使用-和_，我们可以看到 Nano ID 就选择了这种编码。

通常还有个看法，那就是 URL-safe 中的-和_是不受搜索引擎欢迎的，容易被误判成分隔符，导致使用了这两个字符的 ID 被语义分隔了。所以 base32 等编码，它们不需要使用除字母和数字之外的字符，在此刻发挥了价值。

其他方案

集群数据库保证seq的唯一性

分布式场景下，热点模块数据可能过多（比如订单库），导致一台数据库无法存储全量数据：

img

那么在生成订单时，如果使用sequence在每个库中生成订单ID，很容易造成订单ID的重复。首先想到的最简单的方式就是使用步长，错开id：

-- 数据库1的OrderId生成策略
create sequence seq_order_id start 1 step by 2;
-- 数据库2的OrderId生成策略
create sequence seq_order_id start 2 step by 2;

这种方式较为简单，其数据的唯一性是有保证的。但是如果再扩充一台机器，可能要面临数据迁移的情况，相对来说不是很灵活。当然，你可以将step增大，为扩充预留Id值。

使用全局唯一数据库生成ID

这种方式也较为简单，就是再整个环境中搭建一台专门用于生成ID的数据库：

img

各个服务会从ID数据库中取出自己所需要的ID数据。ID数据的生成策略也有多种：

  • 预先插入一堆唯一ID到ID数据库中，供其他服务读取使用

  • ID数据库使用SEQ生成

全局唯一数据的缺点也很明显：

  • 很难做到高可用，有单点故障

  • 性能较低，扩展性较差

  • 预插方式需要维护程序，并且每个服务的ID生成策略可能都不同

  • 有多种数据库产品，每个数据库产品的相关操作可能不同，不方便程序扩展

使用Zookeeper的临时节点

Zookeeper具有高可用、原子性的特点，用于作为唯一的ID生成策略也是较为合适的：

  • 有序，使用临时序号节点

  • 使用节点的数据版本号

  • 高并发下性能较差

使用Redis的incr

由于Redis的原子性以及高性能，使用Redis作为ID生成策略是很多公司采用的解决方案，主要采用 incr 和 incr by，它具有以下特点：

  • 高性能

  • 数字ID，有序，分页较为方便

  • 局部有序，全局无法保证有序

上一页Dubbo分布式治理下一页分布式ID生成策略总结

最后更新于

这有帮助吗？