第七章：设计一个分布式系统中的唯一 ID 生成器 (Design A Unique ID Generator In Distributed Systems)
在这一章中，我们将设计一个分布式系统中的唯一 ID 生成器。你可能会首先想到在传统数据库中使用具有 auto_increment 属性的主键。然而，在分布式环境中，auto_increment 并不起作用，因为单个数据库服务器的容量有限，而在多个数据库中生成唯一 ID 并保持最小延迟是具有挑战性的。
以下是一些唯一 ID 的示例：
第 1 步 - 理解问题并确定设计范围
提出澄清性问题是应对任何系统设计面试问题的第一步。以下是候选人与面试官的对话示例：
候选人：唯一 ID 的特性是什么？
面试官：ID 必须是唯一的，并且是可排序的。
候选人：对于每条新记录，ID 是否递增 1？
面试官：ID 按时间递增，但不一定每次递增 1。同一天晚上创建的 ID 要大于早上创建的 ID。
候选人：ID 只包含数值吗？
面试官：是的，正确。
候选人：ID 的长度要求是什么？
面试官：ID 应该适合 64 位。
候选人：系统的规模有多大？
面试官：系统应该能够每秒生成 10,000 个 ID。
上述对话展示了一些可以向面试官提出的样例问题。理解需求并澄清模糊点非常重要。对于这个面试问题，需求总结如下：
- ID 必须唯一。
- ID 只包含数值。
- ID 适合 64 位。
- ID 按日期排序。
- 系统需要能够每秒生成超过 10,000 个唯一 ID。
第 2 步 - 提出高层设计并获得认同
在分布式系统中有多种方案可以用来生成唯一 ID。我们考虑的选项有：
- 多主复制（Multi-master replication）
- 全球唯一标识符（UUID）
- 票据服务器（Ticket server）
- Twitter 雪花算法（Snowflake）
接下来，我们将逐一分析每种方法，了解它们的工作原理以及每种方案的优缺点。
多主复制 (Multi-master replication)
如图 7-2 所示，第一种方法是多主复制。
该方法利用了数据库的 auto_increment（自动递增）功能。与每次递增 1 的传统方式不同，我们将每次递增的步长设置为 k，其中 k 是使用的数据库服务器数量。如图 7-2 所示，每个服务器生成的下一个 ID 等于同一服务器中前一个 ID 加上 2。这种方式解决了一些可扩展性问题，因为 ID 可以随着数据库服务器数量的增加而扩展。
然而，这种策略存在一些主要的缺点：
- 难以在多个数据中心之间扩展。
- 在多个服务器之间，ID 不能随时间递增。
- 当添加或移除服务器时，扩展性较差。
UUID（全球唯一标识符）
UUID 是另一种简单的生成唯一 ID 的方法。UUID 是一个 128 位的数字，用于在计算机系统中标识信息。UUID 发生冲突的概率非常低。
引用自维基百科：“在每秒生成 10 亿个 UUID 持续大约 100 年后，生成重复 UUID 的概率才会达到 50%。” [1]。
以下是一个 UUID 示例：09c93e62-50b4-468d-bf8a-c07e1040bfb2。UUID 可以在不需要服务器间协调的情况下独立生成。图 7-3 展示了 UUID 的设计。
在这个设计中，每个 Web 服务器都包含一个 ID 生成器，并且每个 Web 服务器独立负责生成 ID。
优点：
- 生成 UUID 非常简单。不需要服务器之间的协调，因此不会出现同步问题。
- 系统易于扩展，因为每个 Web 服务器负责生成它们使用的 ID。ID 生成器可以随着 Web 服务器轻松扩展。
缺点：
- UUID 是 128 位长的，但我们的需求是 64 位。
- UUID 不会随时间递增。
- UUID 可能不是纯数值。
票据服务器 (Ticket Server)
票据服务器 是生成唯一 ID 的另一种有趣方法。Flickr 开发了票据服务器来生成分布式的主键 [2]。值得一提的是它的工作机制。
该方法的核心思想是利用一个单独数据库服务器（票据服务器）中的集中式 auto_increment（自动递增）功能。更多详情可以参考 Flickr 的工程博客文章 [2]。
优点：
- 生成的是数值型 ID。
- 实现简单，适用于中小规模的应用。
缺点：
- 单点故障。单一的票据服务器意味着如果该服务器宕机，所有依赖它的系统都会遇到问题。为避免单点故障，可以设置多个票据服务器，但这会引入新的挑战，比如数据同步问题。
Twitter 雪花算法 (Twitter Snowflake Approach)
上述提到的方法为我们提供了不同 ID 生成系统如何工作的思路。然而，这些方法都无法满足我们的具体需求，因此我们需要另一种方法。Twitter 的独特 ID 生成系统称为“雪花”（Snowflake）[3] 是非常有启发性的，可以满足我们的需求。
分而治之 是我们的好朋友。我们不是直接生成一个 ID，而是将 ID 分成不同的部分。图 7-5 展示了一个 64 位 ID 的布局。
每个部分的解释如下：
- 符号位：1 位。始终为 0。此位保留供将来使用，可能用于区分有符号和无符号数字。
- 时间戳：41 位。从纪元（epoch）或自定义纪元以来的毫秒数。我们使用 Twitter 雪花算法的默认纪元
1288834974657，相当于 2010 年 11 月 04 日 01:42:54 UTC。 - 数据中心 ID：5 位，可以表示
2^5 = 32个数据中心。 - 机器 ID：5 位，可以表示
2^5 = 32台每个数据中心的机器。 - 序列号：12 位。对于在该机器/进程上生成的每个 ID，序列号递增 1。该数字每毫秒重置为 0。
第 3 步 - 深入设计
在高层设计中，我们讨论了各种在分布式系统中设计唯一 ID 生成器的选项。我们最终选择了一种基于 Twitter 雪花 ID 生成器的方法。让我们深入探讨这个设计。为了回忆设计图，下面重新列出设计图。
数据中心 ID 和机器 ID 在系统启动时选择，一般在系统运行后固定不变。对数据中心 ID 和机器 ID 的任何更改都需要仔细审查，因为这些值的意外更改可能会导致 ID 冲突。时间戳和序列号在 ID 生成器运行时生成。
时间戳 (Timestamp)
最重要的 41 位组成了时间戳部分。随着时间的推移，时间戳的增长使得 ID 按时间可排序。图 7-7 展示了如何将二进制表示转换为 UTC 的示例。你也可以使用类似的方法将 UTC 转换回二进制表示。
41 位的最大时间戳可以表示为 2^41 - 1 = 2199023255551 毫秒（ms），这大约等于 69 年：2199023255551 ms / 1000 seconds / 365 days / 24 hours/ 3600 seconds ~ 69 year. 这意味着 ID 生成器将在 69 年内正常工作，并且将自定义的纪元时间设置为接近当前日期可以延迟溢出时间。在 69 年后，我们需要一个新的纪元时间或采用其他技术来迁移 ID。
序列号 (Sequence number)
序列号为 12 位，这意味着可以生成 2^12 = 4096 种组合。该字段默认为 0，除非在同一毫秒内在同一服务器上生成超过一个 ID。理论上，一台机器可以支持每毫秒最多生成 4096 个新 ID。
第 4 步 - 总结
在本章中，我们讨论了设计唯一 ID 生成器的不同方法：多主复制、UUID、票据服务器，以及类似于 Twitter 雪花算法的唯一 ID 生成器。我们最终选择了雪花算法，因为它支持我们所有的用例，并且在分布式环境中具有可扩展性。
如果在面试结束时还有额外时间，以下是一些额外的讨论要点：
- 时钟同步。在我们的设计中，我们假设 ID 生成服务器的时钟是相同的。然而，这一假设在服务器运行于多个核心时可能不成立。在多机器场景中也存在同样的挑战。时钟同步的解决方案超出了本书的范围；但了解这一问题的存在非常重要。网络时间协议（Network Time Protocol，NTP）是解决这一问题的最常用方案。对感兴趣的读者，可以参考相关资料 [4]。
- 部分长度调整。例如，对于低并发和长期应用，减少序列号位数而增加时间戳位数是有效的。
- 高可用性。由于 ID 生成器是一个关键任务系统，因此必须具备高可用性。
恭喜你读到这里！给自己一个赞，做得很好！
参考文献
[1] Universally unique identifier: https://en.wikipedia.org/wiki/Universally_unique_identifier
[2] Ticket Servers: Distributed Unique Primary Keys on the Cheap: https://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-thecheap/
[3] Announcing Snowflake: https://blog.twitter.com/engineering/en_us/a/2010/announcingsnowflake.html
[4] Network time protocol: https://en.wikipedia.org/wiki/Network_Time_Protocol