把来自传统数据库的自增主键用作 ID，实现分布式的话性能不佳， 而且容易处于被预测、被分析的被动局面，这是我们不希望看到的。
最近我写了一个程序 awesome-github， 借此来挖掘一下 GitHub 上有什么流行的分布式 ID 方案。 现在，就让我们一起来看看当今流行的 6 个方案： UUID，Nano ID，ULID，KSUID，和两个常见的 ID 算法： Mongdb objectID 和 Snowflake ID (雪花算法)。
它们采取了不同的技术实现，在它们的项目主页上，通常罗列着很多特性。 什么是不可预测性 (unpredictability)？单调性 (monotonic)？排序性 (K-ordered)？ URL-safe？…… 如此多的特性，会为我们带来什么？ 不仅如此，在本文中我们还将着重探究它们的局限性。
注意：为什么我在本文里只介绍 6 种呢？其实我在这里介绍的分布式 ID 方案， 可以做到严格意义上的多个节点独立产生 ID，节点之间是不需要相互感知的， 从而保证真正的分布式。
可以看到，一些营销号的文章总爱吹嘘有多少种，自己是最全面的， 它们除了把 Redis 拉进讨论中，还喜欢把滴滴的 TinyID、美团的 Leaf、 百度的 UidGenerator 等项目也算作好几种来理解。其实在本文的框架下， 国内大厂提出的几个方案大同小异， 都来源自 Snowflake 算法，不会给我们带来多少新鲜感， 所以应该归类到 Snowflake 算法中，请见后文。
ID 方案总览
设计一个分布式 ID 的生成方案，可以分成两个步骤来看
- 生成二进制的 ID，通常从伪随机数、时间、节点 ID 中选取
- 将该二进制的 ID 转成人类可读、易于传输的字符串文本
第一步生成的二进制 ID 已经可以被使用了，但由于很多时候还需要以文本的形式被使用， 所以 ID 方案还要实现第二步中的编码方式。
第一步：生成二进制
上面提到的方案，我们先把它们划分成三类：
- 基于「伪随机数」：UUID v4 和 Nano ID
- 基于「时间 + 伪随机数」：ULID 和 KSUID
- 基于「时间 + 节点 ID」：Snowflake ID 和 Mongdb objectID
基于「伪随机数」的方案
完全由伪随机数保证唯一性。
| 方案 | 伪随机数(bit) | 二进制(bit) |
|---|---|---|
| UUID v4 | 122 | (122+6) 128 |
| Nano ID | 126 | 126 |
可以注意到 UUID v4 的二进制位数被表示成了 (122+6)，这是因为 UUID v4 使用了 122 位的伪随机数，然后另外有 4 位表示版本号为 4； 以及 2 位表示变体种类。但由于一旦采用了确定的方案，这个值是不会 再发生改变的，所以虽然总长 128 位，但实际保证唯一性的位数为 122 位。
由于 UUID 是个相当通用的方案，所以具体内容将在后文 UUID 一节中详细说明。
其实 Nano ID 是个灵活的规范，表格中的数据是它的默认值，可以被修改成其他值。
基于「时间 + 伪随机数」的方案
高位由时间组成，低位由伪随机数组成。 在同一时间下，用伪随机数保证唯一性。
因为时间在高位，所以无论是二进制还是字符串表示，都可以按照时间进行排序。
| 方案 | 时间(bit) | 伪随机数(bit) | 二进制(bit) |
|---|---|---|---|
| ULID | 48 | 80 | 128 |
| KSUID | 32 | 128 | 160 |
注意，ULID 使用的伪随机数并非是完全随机的，它号称实现了 同一时间内单调自增；但这是有争议的，具体在 单调性 一节 中讨论这个问题。
基于「时间 + 节点 ID + 递增计数」的方案
高位由时间组成，低位由节点 ID 和递增计数组成，取代了上面方案中的伪随机数。 在同一时间下的某个节点上，用递增计数保证唯一性。
在这里，把节点所在的环境中，固有的一些 ID 都统一称作节点 ID， 它可能是 MAC 地址，或者是主机名的 hash 值，又或者是由分布式协调器分配给 节点的 ID，只要该 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 算法 是比较热门的选择。
小结
完全由伪随机数构成的 ID，位数要足够长，以保证碰撞的概率极低。
在引入时间后，碰撞概率降低了些，所以随机数的位数可以减少些。
基于「时间」的方案和 基于「时间 + 节点 ID」的方案， 保证了在只有一个节点的情况下也可以保证有足够的 ID。 而在分布式环境中往往有多个节点，所以可以引入节点 ID， 使用基于「时间 + 节点 ID」的方案。该方案可以减少对伪随机数 的依赖，用一个序号进行替代。
简单思考一下，为什么没有「时间 + 递增计数」的方案呢？ 这个问题也可以改成：分布式环境中多个节点同时 生成 ID，它能做到彼此生成的 ID 全局唯一吗？
第二步：将二进制编码成文本
在上一步中，我们已经得到了二进制形式的 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] |
从 128、126、128 到 256、168、208，原始二进制大小相差无几， 转成文本后大小却相差好几个字节。 为什么不同方案，从二进制转成文本后的长度差距这么大呢？ 这完全是因为他们采用的编码方式不同， 但是这个步骤留到文章下一节再讲，我们先看看二进制的 ID 是怎么生成的。
生成方式和特性
伪随机数
UUID v4 和 Nano ID，就是完全由伪随机数组成的。随机数的位数越多，碰撞概率越低。 使用伪随机数的方案，相比不使用伪随机数的方案，能额外提供不可预测性。
生成伪随机数依赖系统的伪随机数发生器，有两个 API 可供调用：
Math.random和Crypto API。
一般认为 Crypto API 生成的伪随机数更加不可预测，而 Math.random 生成的随机数
更有规律，相比而言容易被预测。
所以 Math.random 用在一些对安全要求不高的场景，
最常见的例子就是游戏中的随机数。而在生成 ID 的过程中，
没有特殊需求，一律使用 Crypto API。
通常，Crypto API 从系统上的/dev/urandom那儿获取随机数。
Nano ID 在其 README 上强调算法是不可预测的
Unpredictability. Instead of using the unsafe Math.random(), Nano ID uses the crypto module in Node.js and the Web Crypto API in browsers. These modules use unpredictable hardware random generator.
这不神秘，因为它是在调用 Crypto API。所有使用伪随机数的 ID 生成方案， 都应该默认调用 Crypto API 生成伪随机数。
时间
时间能提供唯一性自不必说。引入时间能有效降低 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 中使用时间有以下好处：
- 可排序
- 优化数据库的聚集索引
所有带有时间的 ID 方案都在宣称自己是可排序的 (lexicographically sortable)。 但要注意它们是粗略的 (roughly/loosely) 排序，在相同时间下不能区分先后。
为此，时间一定会放在 ID 的最高位，并且使用大端字节序 (big-endian)。
必须注意，ID 中的时间不代表它就是现实时间！ 它应该使用时间戳，而且是 单调时间 (monotonic clock)。 想直接从 ID 中获取时间信息的想法是脱离实际的， 因为单调时间不是 墙上时间 (wall clock)。 该时间是用来保证唯一性和可排序性的， 而不是为了将时间信息嵌入到 ID 中。不能依赖它来获知 ID 的创建时间！
所以，需要注意时钟回拨问题：即使发生墙上时钟回拨，单调时钟依旧在增加。 单调时间依赖进程保持运行，只有进程存在，才能记录运行时间。 在进程重启后，丢失了之前进程记录的单调时间，这时单调时钟也不可避免 地遭遇时钟回拨。在 时钟偏移问题 一节中再继续讨论这个问题。
节点 ID
可以从一个节点环境中获取各种 ID，再汇入到最终结果的节点 ID 中。 可以获取 MAC 地址，或者主机名，或者 dmi product_uuid， 还可以再包含 PID，UID，GID。 只要是节点所在环境中能被利用的 ID，统统都可以纳入节点 ID 中。 还有一个本文尚未提及的方案 cuid，它甚至使用浏览器指纹！
正如引入时间可以减少伪随机数的位数一样，节点 ID 可以进一步减少对 伪随机数的依赖，snowflake 完全放弃了伪随机数，使用一个从 0 开始递增 的序号。
snowflake 和 mongodb objectid 都采用节点 ID，但它们使用了完全不同的思路。
首先我们要明确，多个分布式节点可以在不同主机上，也可以在同一主机上。 节点 ID 必须要有效区分它们。
snowflake 需要自己分配节点 ID，由于多个节点是可以运行在同一主机上的， 每个节点可以分配 1、2、3…… 通常手动分配比较繁琐和不可靠，所以 snowflake 的实际应用时会 借助 ZooKeeper 等服务来管理对节点 ID 的分配。
再比如说 xid 方案，它实现了 mongodb objectid，首先获取 dmi product_uuid， 但该文件需要特权，如果获取失败，它退而使用主机名的 hash 值。 但如果同一主机上的多个实例怎么办呢？所以它还要用到进程 PID 来减少碰撞概率。 这意味着 mongodb objectid 方案需要在分布式环境中正确配置主机名！
至此，三种成分就已经说明完毕了，接下来再看看它们会带来怎样的特性。
不可预测性
上面所有方案，都能保证 ID 的全局唯一性。但是对于不可预测性 (unpredictability) 来说， 需要每次生成 ID 时使用伪随机数。注意是每次都使用一个新的伪随机数。 所以比如 xid 这种实现方式，它只在初始化时生成一个 伪随机数，然后每次生成新 ID 时在该伪随机数上递增，不具备不可预测性。
美团团队在 Leaf——美团点评分布式ID生成系统 一文中谈到无法忍受使用递增 ID 会被人估计一天的订单量，所以转而采用了 Snowflake 算法。 我个人认为这是有失偏颇的做法，因为从 Snowflake 算法中估计 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 的库时还请多加留意。
编码方式
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 等编码，它们不需要使用除字母和数字之外的字符，在此刻发挥了价值。
UUID
除了最流行的版本
- UUID v4 使用伪随机数
还有其他版本
- UUID v1 使用时间、MAC 地址
- UUID v2 使用用户 ID (或者组 ID)、时间、MAC 地址
- UUID v3 对 namespace 和 name 的组合进行 md5
- UUID v5 对 namespace 和 name 的组合进行 sha1
我们可以参考 UUID 的一个 golang 实现 satori/go.uuid， 从它的源码中，我们可以知道它使用了这些值：
uuid.NewV1: timeNow, clockSeq, hardwareAddr
uuid.NewV2: posixUID/posixGID, timeNow, clockSeq, hardwareAddr
uuid.NewV3: namespace, name
uuid.NewV5: namespace, name
UUID v1/v2 的唯一性主要来自时间。因为虽然在不同主机上， 系统的用户 ID、组 ID、MAC 地址不同；但在同一台主机上， 这些值通常是保持不变的。所以需要靠时间标记进行区分。 但是时间也相同怎么办呢？ 为了保证即使在相同时间下生成的两个 UUID 不同，实际上时间中还包含了 一个自增的时钟序，后生成的 UUID 的时钟序比前一个大。
UUID v3/v5 使用命名空间和名称。在这个组合相同的请况下， 是可以反复生成相同 ID 的，所以需要使用者自行保证命令空间 和名称的组合唯一。
该用哪个版本呢？
UUID v1/v2 泄漏了主机的 MAC 地址，因为它是未经加密的。 而且 MAC 地址也不可靠，因为它容易被篡改。 v3/v5 徒增了复杂度，因为它把保持唯一性的要求交还给了使用者。 所以 UUID 的版本 1235 很不常用。一般需要一个伪随机数就可以了， 那么就使用 UUID v4 吧。
自己实现
怎么样，看完之后有没有找到自己心仪的 ID 生成方案呢？ 又或者，跃跃欲试想要设计一个更优秀的方案呢？ 这很正常，我们已经知道了各个方案的特性和原理实现，以及它们的局限性和缺陷。 它们的源码其实并不复杂，你完全有能力实现自己的方案。
当然啦，一个好的方案，不仅要在保证正确性的前提下， 还需要得到多种编程语言的支持，需要不遗余力地推广。 也许下一个优秀的方案就由你来提供。
推荐
在线网页计算碰撞率：可以自定义 alphabet 和长度
