# 分布式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`类来生成加密级别的安全随机数：

```java
// 创建一个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);
```

如果需要线程安全支持：

```java
// 使用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](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-92af16da6063dcf7b578afbca14583597fdd0ff0%2F1571707524322.png?alt=media)

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

```sql
-- 数据库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](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-d7cd0287ba0b488eb3d7258f03dda3267ed89bf1%2F1571708725336.png?alt=media)

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

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

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

* 很难做到高可用，有单点故障
* 性能较低，扩展性较差
* 预插方式需要维护程序，并且每个服务的ID生成策略可能都不同
* 有多种数据库产品，每个数据库产品的相关操作可能不同，不方便程序扩展

### 使用Zookeeper的临时节点

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

* 有序，使用临时序号节点
* 使用节点的数据版本号
* 高并发下性能较差

### 使用Redis的incr

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

* 高性能
* 数字ID，有序，分页较为方便
* 局部有序，全局无法保证有序
