Skip to content

系统设计:在分布式系统中设计唯一 ID 生成器(07)

Published: at 11:35:23

在本章中,要求在分布式系统中设计一个唯一 ID 生成器。 你的第一个想法可能是在传统数据库中使用具有 auto_increment 属性的主键。 但是,auto_increment 在分布式环境中不起作用,因为 单个数据库服务器不够大,跨多个数据库以最小延迟生成唯一 ID 具有挑战性。 以下是唯一 ID 的一些示例:

第1步:了解问题并确定设计范围

了解清楚问题是解决任何系统设计面试问题的第一步。下面是一个候选人与面试官互动的例子:

候选人:唯一ID有什么特点?

面试官:ID 必须是唯一的,并且是可排序的。

候选人:每增加一条记录,ID 是否加 1?

面试官:ID是按时间递增的,不一定只递增1,当天晚上创建的ID比早上创建的ID大。

候选人:ID 是否只包含数值?

面试官:是的,这很正确。

候选人:ID长度要求是多少?

面试官:ID 应该适合 64 位。

候选人:系统的规模是多少?

面试官:系统应该可以每秒生成10000个ID。

以上是可以向面试官提出的一些示例问题。了解需求并澄清歧义很重要。

本次面试题,要求如下:

第2步:提出高层次的设计方案并获得认同

可以使用多个选项在分布式系统中生成唯一ID。

我们考虑的选项有:

让我们看看它们是如何工作的,以及每个选项的优缺点。

多主复制

如图7-2所示,第一种方式是多主复制。

这种方法使用数据库的 auto_increment 特性。我们不是将下一个 ID 增加 1,而是将其增加 k,其中 k 是正在使用的数据库服务器的数量。如图 7-2 所示,下一个要生成的 ID 等于同一服务器中的前一个 ID 加 2。这解决了一些可扩展性问题,因为 ID 可以随着数据库服务器的数量而扩展。

然而,这种策略有一些主要的缺点:

UUID

UUID 是另一种获取唯一 ID 的简单方法。 UUID 是一个 128 位数字,用于识别计算机系统中的信息。UUID获得串通的概率非常低。引自维基百科,“在每秒产生10亿个UUIDs,大约100年后,创造一个重复的概率会达到50%” [1] 。

以下是 UUID 的示例:09c93e62-50b4-468d-bf8a-c07e1040bfb2。 UUID 可以独立生成,无需服务器之间的协调。图 7-3 展示了 UUID 的设计。

在这个设计中,每个Web服务器都包含一个ID生成器,并且Web服务器负责独立生成ID。

优点:

缺点:

Ticket 服务器

票据服务器是产生唯一ID的另一种有趣的方式。Flicker开发了票据服务器来生成分布式主键[2]。值得一提的是,该系统是如何工作的。

这个想法是在一个单一的数据库服务器(Ticket Server)中使用一个集中的自动增量功能。要了解更多这方面的信息,请参考flicker的工程博客文章[2] 。

优点:

缺点:

推特雪花算法

上面提到的方法给了我们一些关于不同的ID生成系统如何工作的想法。然而,它们都不符合我们的具体要求;因此,我们需要另一种方法。Twitter 独特的 ID 生成系统“snowflake”[3] 很有启发性,可以满足我们的要求。

分而治之是我们的朋友。我们不是直接生成一个ID,而是将一个ID分成不同的部分。图7-5显示了一个64位ID的布局。

下面对每个部分进行解释:

第3步:深入设计

在高层设计中,我们讨论了在分布式系统中设计唯一ID生成器的各种方案。我们确定了一种基于Twitter雪花ID生成器的方法。让我们深入了解一下这个设计。为了恢复我们的记忆,设计图被重新列在下面。

数据中心ID和机器ID是在启动时选择的,一般在系统运行后就固定下来。数据中心ID和机器ID的任何变化都需要仔细审查,因为这些数值的意外变化会导致ID冲突。时间戳和序列号是在ID生成器运行时生成的。

时间戳

最重要的41位组成了时间戳部分。由于时间戳随时间增长,ID可按时间排序。

图 7-7 显示了二进制表示如何转换为 UTC 的示例。您还可以使用类似的方法将 UTC 转换回二进制表示。

可以用 41 位表示的最大时间戳是: 2 ^ 41 - 1 = 2199023255551毫秒(ms),这样我们就可以得到。~ 69年=2199023255551毫秒/1000秒/365天/24小时/3600秒。

这意味着 ID 生成器将工作 69 年,并且自定义纪元时间接近今天的日期会延迟溢出时间。 69年后,我们将需要一个新的纪元时间或采用其他技术来迁移ID。

序列号

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

第4步:总结

在本章中,我们讨论了设计唯一 ID 生成器的不同方法:多主复制、UUID、票务服务器和类似 Twitter 雪花的唯一 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-the-cheap

[3] Announcing Snowflake: https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake.html

[4] Network time protocol: https://en.wikipedia.org/wiki/Network_Time_Protocol