CHAPTER 7: DESIGN A UNIQUE ID GENERATOR IN DISTRIBUTED SYSTEMS

In this chapter, you are asked to design a unique ID generator in distributed systems. Your
first thought might be to use a primary key with the auto_increment attribute in a traditional
database. However, auto_increment does not work in a distributed environment because a
single database server is not large enough and generating unique IDs across multiple
databases with minimal delay is challenging.
Here are a few examples of unique IDs:

在本章中，您将被要求在分布式系统中设计一个唯一的 ID 生成器。

你首先想到的可能是在传统数据库中使用具有 auto_increment 属性的主键。但是，auto_increment在分布式环境中不起作用，因为单个数据库服务器不够大，并且跨多个数据库服务器生成唯一 ID

延迟最小的数据库具有挑战性。
以下是唯一 ID 的几个示例：

Step 1 - Understand the problem and establish design scope 第 1 步 - 了解问题并建立设计范围

Asking clarification questions is the first step to tackle any system design interview question.
Here is an example of candidate-interviewer interaction:
Candidate: What are the characteristics of unique IDs?
Interviewer: IDs must be unique and sortable.
Candidate: For each new record, does ID increment by 1?
Interviewer: The ID increments by time but not necessarily only increments by 1. IDs
created in the evening are larger than those created in the morning on the same day.
Candidate: Do IDs only contain numerical values?
Interviewer: Yes, that is correct.
Candidate: What is the ID length requirement?
Interviewer: IDs should fit into 64-bit.
Candidate: What is the scale of the system?
Interviewer: The system should be able to generate 10,000 IDs per second.

提出澄清问题是解决任何系统设计面试问题的第一步。
以下是候选人与面试官互动的示例：

应聘者：唯一 ID 有哪些特征？
面试官：ID 必须唯一且可排序。
应聘者：对于每条新记录，ID 是否递增 1？
面试官：ID 按时间递增，但不一定只递增 1。id晚上创建的比同一天早上创建的要大。
应聘者：ID 是否仅包含数值？
采访者：是的，没错。
应聘者：id长度要求是什么？
采访者：ID 应适合 64 位。
应聘者：系统的规模有多大？
采访者：系统应该每秒能够生成 10，000 个 ID。

Above are some of the sample questions that you can ask your interviewer. It is important to
understand the requirements and clarify ambiguities. For this interview question, the
requirements are listed as follows:
• IDs must be unique.
• IDs are numerical values only.
• IDs fit into 64-bit.
• IDs are ordered by date.
• Ability to generate over 10,000 unique IDs per second.

以上是您可以向面试官提出的一些示例问题。重要的是
了解要求并澄清歧义。对于这个面试问题，
要求如下：
• ID 必须是唯一的。
• ID 仅为数值。
• ID 适合 64 位。
• ID 按日期排序。
• 每秒能够生成超过10，000个唯一ID。

Step 2 - Propose high-level design and get buy-in 第 2 步 - 提出高级设计并获得支持

Multiple options can be used to generate unique IDs in distributed systems. The options we
considered are:
• Multi-master replication
• Universally unique identifier (UUID)
• Ticket server
• Twitter snowflake approach
Let us look at each of them, how they work, and the pros/cons of each option.

可以使用多个选项在分布式系统中生成唯一 ID。我们的选项
考虑的是：
• 多主复制
• 通用唯一标识符 （UUID）
• 票务服务器
• 推特雪花方法
让我们看看它们中的每一个，它们是如何工作的，以及每个选项的优缺点。

Multi-master replication 多主机复制

As shown in Figure 7-2, the first approach is multi-master replication

This approach uses the databases’ auto_increment feature. Instead of increasing the next ID
by 1, we increase it by k, where k is the number of database servers in use. As illustrated in
Figure 7-2, next ID to be generated is equal to the previous ID in the same server plus 2. This
solves some scalability issues because IDs can scale with the number of database servers.
However, this strategy has some major drawbacks:
• Hard to scale with multiple data centers
• IDs do not go up with time across multiple servers.
• It does not scale well when a server is added or removed.

此方法使用数据库的auto_increment功能。而不是增加下一个 ID
乘以 1，我们将其增加 k，其中 k 是正在使用的数据库服务器数。如
图 7-2，要生成的下一个 ID 等于同一服务器中的前一个 ID 加 2。这
解决了某些可伸缩性问题，因为 ID 可以随数据库服务器的数量而扩展。
但是，这种策略有一些主要缺点：
• 难以通过多个数据中心进行扩展
• ID 不会随着多个服务器的时间而增加。
• 添加或删除服务器时，它不能很好地扩展。

UUID

A UUID is another easy way to obtain unique IDs. UUID is a 128-bit number used to identify
information in computer systems. UUID has a very low probability of getting collusion.
Quoted from Wikipedia, “after generating 1 billion UUIDs every second for approximately
100 years would the probability of creating a single duplicate reach 50%” [1].
Here is an example of UUID: 09c93e62-50b4-468d-bf8a-c07e1040bfb2. UUIDs can be
generated independently without coordination between servers. Figure 7-3 presents the
UUIDs design.

UUID 是获取唯一 ID 的另一种简单方法。UUID 是一个 128 位数字，用于识别
计算机系统中的信息。UUID获得勾结的可能性非常低。
引自维基百科，“在每秒生成 10 亿个 UUID 大约
100年后，创建单个副本的概率将达到50%“ [1]。
下面是 UUID 的示例：09c93e62-50b4-468d-bf8a-c07e1040bfb2。UUID 可以是
独立生成，无需服务器之间的协调。图 7-3 显示了
UUID 设计。

In this design, each web server contains an ID generator, and a web server is responsible for
generating IDs independently.
Pros:
• Generating UUID is simple. No coordination between servers is needed so there will not
be any synchronization issues.
• The system is easy to scale because each web server is responsible for generating IDs
they consume. ID generator can easily scale with web servers.
Cons:
• IDs are 128 bits long, but our requirement is 64 bits.
• IDs do not go up with time.
• IDs could be non-numeric.


在此设计中，每个 Web 服务器都包含一个 ID 生成器，Web 服务器负责
独立生成 ID。
优点：
• 生成 UUID 非常简单。服务器之间不需要协调，因此不会
是任何同步问题。
• 系统易于扩展，因为每个 Web 服务器负责生成 ID
他们消费。ID生成器可以轻松地与Web服务器一起扩展。
缺点：
• ID 长度为 128 位，但我们的要求是 64 位。
• ID 不会随时间而增加。
• ID 可以是非数字。

Ticket Server

Ticket servers are another interesting way to generate unique IDs. Flicker developed ticket
servers to generate distributed primary keys [2]. It is worth mentioning how the system
works.

票务服务器是生成唯一ID的另一种有趣方式。闪烁开发票
用于生成分布式主键 [2] 的服务器。值得一提的是系统如何
工程。

The idea is to use a centralized auto_increment feature in a single database server (Ticket
Server). To learn more about this, refer to flicker’s engineering blog article [2].
Pros:
• Numeric IDs.
• It is easy to implement, and it works for small to medium-scale applications.
Cons:
• Single point of failure. Single ticket server means if the ticket server goes down, all
systems that depend on it will face issues. To avoid a single point of failure, we can set up
multiple ticket servers. However, this will introduce new challenges such as data
synchronization.


这个想法是在单个数据库服务器中使用集中式auto_increment功能（票证服务器）。要了解更多信息，请参阅 flinker 的工程博客文章 [2]。
优点：
• 数字 ID。
• 它易于实施，适用于中小型应用。
缺点：
• 单点故障。单个票证服务器意味着如果票务服务器出现故障，则所有
依赖它的系统将面临问题。为了避免单点故障，我们可以设置
多个票务服务器。但是，这将带来新的挑战，例如数据同步。

Twitter snowflake approach

Approaches mentioned above give us some ideas about how different ID generation systems
work. However, none of them meet our specific requirements; thus, we need another
approach. Twitter’s unique ID generation system called “snowflake” [3] is inspiring and can
satisfy our requirements.
Divide and conquer is our friend. Instead of generating an ID directly, we divide an ID into
different sections. Figure 7-5 shows the layout of a 64-bit ID.

上面提到的方法为我们提供了一些关于不同ID生成系统如何工作的想法。
但是，它们都不符合我们的特定要求;因此，我们需要另一个
方法。Twitter独特的ID生成系统称为“雪花”[3]，令人鼓舞，可以
满足我们的要求。
分而治之是我们的朋友。我们不是直接生成 ID，而是将 ID 划分为
不同的部分。图 7-5 显示了 64 位 ID 的布局。

Each section is explained below.
• Sign bit: 1 bit. It will always be 0. This is reserved for future uses. It can potentially be
used to distinguish between signed and unsigned numbers.
• Timestamp: 41 bits. Milliseconds since the epoch or custom epoch. We use Twitter
snowflake default epoch 1288834974657, equivalent to Nov 04, 2010, 01:42:54 UTC.
• Datacenter ID: 5 bits, which gives us 2 ^ 5 = 32 datacenters.
• Machine ID: 5 bits, which gives us 2 ^ 5 = 32 machines per datacenter.
• Sequence number: 12 bits. For every ID generated on that machine/process, the sequence
number is incremented by 1. The number is reset to 0 every millisecond.

下面对每个部分进行说明。
• 符号位：1 位。它将始终为 0。这是保留供将来使用的。它可能是用于区分有符号和无符号数字。
• 时间戳：41 位。自纪元或自定义纪元以来的毫秒数。我们使用推特
雪花默认纪元1288834974657，相当于 2010 年 11 月 4 日 01：42：54 UTC。
• 数据中心 ID：5 位，这给了我们 2 ^ 5 = 32 个数据中心。
• 计算机 ID：5 位，每个数据中心有 2 ^ 5 = 32 台计算机。
• 序列号：12 位。对于在该计算机/进程上生成的每个 ID，序列
数字递增 1。该数字每毫秒重置为 0。

Step 3 - Design deep dive

In the high-level design, we discussed various options to design a unique ID generator in
distributed systems. We settle on an approach that is based on the Twitter snowflake ID
generator. Let us dive deep into the design. To refresh our memory, the design diagram is
relisted below.






在高级设计中，我们讨论了在
分布式系统。我们确定了一种基于Twitter雪花ID的方法
发电机。让我们深入了解设计。为了刷新我们的记忆，设计图是
下面重新列出。

Datacenter IDs and machine IDs are chosen at the startup time, generally fixed once the
system is up running. Any changes in datacenter IDs and machine IDs require careful review
since an accidental change in those values can lead to ID conflicts. Timestamp and sequence
numbers are generated when the ID generator is running.

数据中心 ID 和计算机 ID 在启动时选择，通常在
系统已启动运行。数据中心 ID 和计算机 ID 中的任何更改都需要仔细检查
因为这些值的意外更改可能会导致 ID 冲突。时间戳和顺序
数字是在 ID 生成器运行时生成的。

Timestamp

The most important 41 bits make up the timestamp section. As timestamps grow with time,
IDs are sortable by time. Figure 7-7 shows an example of how binary representation is
converted to UTC. You can also convert UTC back to binary representation using a similar
method.

最重要的 41 位构成了时间戳部分。随着时间戳随着时间的推移而增长，
ID 可按时间排序。图 7-7 显示了二进制表示方式的示例
转换为 UTC。您还可以使用类似的方法将 UTC 转换回二进制表示形式
方法。

The maximum timestamp that can be represented in 41 bits is
2 ^ 41 - 1 = 2199023255551 milliseconds (ms), which gives us: ~ 69 years =
2199023255551 ms / 1000 seconds / 365 days / 24 hours/ 3600 seconds. This means the ID
generator will work for 69 years and having a custom epoch time close to today’s date delays
the overflow time. After 69 years, we will need a new epoch time or adopt other techniques
to migrate IDs.

可以用 41 位表示的最大时间戳为
2 ^ 41 - 1 = 2199023255551毫秒 （ms），它给我们：~ 69 年 =
2199023255551 毫秒 / 1000 秒 / 365 天 / 24 小时/ 3600 秒。这意味着 ID
生成器将工作 69 年，并具有接近今天的日期延迟的自定义纪元时间
溢出时间。69年后，我们将需要一个新的时代或采用其他技术
以迁移 ID。

Sequence number

Sequence number is 12 bits, which give us 2 ^ 12 = 4096 combinations. This field is 0 unless
more than one ID is generated in a millisecond on the same server. In theory, a machine can
support a maximum of 4096 new IDs per millisecond.

序列号为 12 位，这给了我们 2 ^ 12 = 4096 种组合。此字段为 0，除非
在同一服务器上，一毫秒内生成多个 ID。从理论上讲，机器可以
每毫秒最多支持 4096 个新 ID。

Step 4 - Wrap up

In this chapter, we discussed different approaches to design a unique ID generator: multimaster replication, UUID, ticket server, and Twitter snowflake-like unique ID generator. We
settle on snowflake as it supports all our use cases and is scalable in a distributed
environment.
If there is extra time at the end of the interview, here are a few additional talking points:
• Clock synchronization. In our design, we assume ID generation servers have the same
clock. This assumption might not be true when a server is running on multiple cores. The
same challenge exists in multi-machine scenarios. Solutions to clock synchronization are
out of the scope of this book; however, it is important to understand the problem exists.
Network Time Protocol is the most popular solution to this problem. For interested
readers, refer to the reference material [4].
• Section length tuning. For example, fewer sequence numbers but more timestamp bits
are effective for low concurrency and long-term applications.
• High availability. Since an ID generator is a mission-critical system, it must be highly
available.
Congratulations on getting this far! Now give yourself a pat on the back. Good job!

在本章中，我们讨论了设计唯一 ID 生成器的不同方法：多主复制、UUID、票务服务器和类似 Twitter 雪花的唯一 ID 生成器。我们
选择雪花，因为它支持我们所有的用例，并且可以在分布式中扩展
环境。
如果在面试结束时有额外的时间，这里有一些额外的谈话要点：
• 时钟同步。在我们的设计中，我们假设 ID 生成服务器具有相同的
时钟。当服务器在多个内核上运行时，此假设可能不正确。这
在多计算机方案中也存在相同的挑战。时钟同步的解决方案是
超出本书的范围;但是，了解问题存在很重要。
网络时间协议是此问题的最流行的解决方案。对于感兴趣的
读者请参考参考资料[4]。
• 节长调整。例如，更少的序列号，但更多的时间戳位
对低并发和长期应用程序有效。
• 高可用性。由于 ID 生成器是关键任务系统，因此它必须高度
可用。
恭喜你走到了这一步！现在拍拍自己的背。干得好！

Reference materials

• [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