一、简介

当您将图像上传到 Instagram 或在您最喜欢的经纪应用程序上进行交易时，后端系统会为新创建的对象分配一个唯一 ID (UID)。此 ID 通常用作某些数据库表中的主键，可用于高效地检索对象。我猜你知道我要去哪里——我们如何生成 UID？

嗯，你肯定知道 SQL 中的自增主键。依赖这个特性的问题很明显——它只适用于单机数据库，因为它涉及锁定，因此不可扩展。如果我每秒需要数百万个 UID 用于 Slack、AWS、Youtube 等应用程序怎么办？在本文中，我想与大家分享我的大型 UID 生成器的设计。

1.1 要求

在生成 UID 时，必须区分两种类型的 UID。首先是没有明显语义的随机UID。其次，有顺序 UID，带有排序等固有信息。

图 1. 两种类型的 UID，作者图

随机 UID 不会泄漏任何有意义的信息，因此将其提供给人类更安全（客户端和人类不同！客户端是代码，它会尝试猜测其他人的 URL）。给定一个随机 UID，很难猜测其他对象的 ID，从而提供一些隐私。Youtube 上的视频或 TinyUrl 上的链接都是以这种方式编码的。例如，如果我创建了一个 tinyUrl 并获得了tinyurl.com/2p8u9m2d，我很难猜测其他新创建的 URL（事实上，tinyurl.com/2p8u9m3d 或 tinyurl.com/2p8u9m2c 并不存在）。

顺序 UID 有其自身的优点。它的内在含义帮助应用程序组织数据。例如，在 Instagram 的 Slack/images 中为聊天消息提供连续的 UID 是有意义的，因为我们想保留项目顺序。此外，如果 UID 不暴露给人类，即使不使用固有顺序，也可以使用顺序 UID。

在本文中，我将重点关注顺序 UID，因为大多数百万 WPS 级别的应用程序不会向人类提供 UID。以下是系统的核心功能需求：

• 能够每秒生成一千万个顺序 UID
• UID 必须保留一定程度的排序信息
• 能够根据消耗调整发电率

不用说，系统应该是可扩展的和高度可用的。

2. 高层设计

通常在系统设计面试中，我会从访问模式和数据库模式开始。但是，我们的系统不需要任何数据库支持，稍后我会向您展示。整个系统几乎是无状态的；如果一台发电机崩溃了，可以重新启动另一台发电机并重新开始。

2.1 API设计

我们的 UID 生成器只有一个目的——为任何需要它们的人提供新的 UID。因此，它只需要以下面向客户端的 RPC 接口：

get_uid_batch(batch_size: int) -> 列表[int64]

为了最小化通信开销，客户端每约 100 毫秒获取一批 UID，并将 UID 缓存在内存中。如果客户端崩溃，本地 UID 就会丢失，这很好，因为我们有很多东西可以浪费。

2.2 高层架构

1. 由于应用程序的任务是每秒生成数百万个 UID，因此我们需要多台计算机同时工作才能满足需求。
2. 我们需要某种集群管理器来监控节点健康状况和工作负载。如果供不应求，经理将增加更多工人。

图 2. 架构，作者图

2.3 控制逻辑

1. 启动 ZooKeeper 服务和集群主管。在实践中，监督者可以被自动扩展容器的 Kubernetes 等软件的内置功能所取代。
2. 集群主管默认创建 N 个 worker。
3. 当一个 worker 被创建时，它向 ZooKeeper 注册并获得一个唯一的 worker ID（简单的整数，例如，从 0 到 256）。
4. 每个 worker 对应于 ZooKeeper 上的一个临时 znode。当一个 worker 死亡时，它的 znode 将被删除，ZooKeeper 会通知 supervisor。
5. 所有工作人员定期将他们的 CPU 负载发送到集群管理器。经理删除/添加工人以最好地满足消耗率。

三、细节

3.1 UID分解

到目前为止，我们的讨论都集中在 API 和架构等高级功能上。在本节中，我们需要最终确定 UID 格式。应该多长时间？它捕获什么信息？

UID 长度

UID 长度由应用程序及其存储需求决定。我们假设外部服务每秒最多消耗 1000 万个 UID。让我们检查耗尽不同长度的 UID 需要多长时间：

图 3. UID 耗尽日期，作者图

显然，我们至少需要 56 位，以便应用程序在其生命周期内永远不会用完新的 UID。

UID 时间戳

我们希望 UID 是可排序的，所以它的一部分必须是某种时间戳。对于我们的应用程序，将时间戳保持在毫秒粒度就足够了。一个好的起点是 UNIX 时间戳。但是，它有 64 位，对我们的应用程序来说太长了。为了解决这个问题，我们可以建立一个自定义纪元（而不是 UNIX 时间戳使用的纪元 1970/1/1 0:0:0）并计算经过的毫秒数。

图 4. 如何使用 epoch，作者图

那么，应该用多少位来存储时间戳呢？图 5 显示了不同时间戳大小的溢出时间：

图 5. 不同时间戳大小的溢出时间，作者图

假设项目寿命为 20 年，我们使用 40 位是安全的。

UID 附加信息

很想在这里停下来完成我们的 UID 设计。但是，无论时间戳多么精确，都无法防止 UID 冲突。两台计算机可能会生成两个具有相同时间戳的 UID。为了区分同时生成的 UID，我们必须投入新的信息。以下是我的建议，基于实践中使用的流行设计（Twitter Snowflake）：

图 6. UID 分解，作者图

1. Worker ID：我们可以使用分配给每台计算机的唯一Worker ID来区分。位数由集群中的最大工人数决定。
2. 线程 ID：为了最大化吞吐量，多线程用于利用现代多核 CPU 机器提供的并行性。为什么不是进程ID？进程间通信更昂贵，我们希望将所有生成的 ID 放入一个共享的内存缓冲区中，以供 RPC 线程访问。
3. 本地计数器：即使在20年的老电脑上，一个线程也能在一毫秒内产生两个时间戳。因此，我们需要一个本地计数器来进一步区分两个 UID。当计数器满时，线程在当前毫秒内进入休眠状态。

我在我的笔记本电脑上做了一个简单的实验，这是一台 2019 款六核 MacBook pro。这是我实现的吞吐量（此处为代码）：

图 7. 单机吞吐量，作者图

在不运行 RPC 服务器和其他繁重的东西的情况下，我的笔记本电脑可以达到每百万秒约 40K 个 UID。理想沙箱中的吞吐量高得惊人，我认为性能只会在实践中下降。根据有根据的猜测，假设计算机可以生成 5K UID/ms。要达到 1000 万个 UID/s，我们需要两台计算机。当然，在实践中，我们可能需要更多。

现在，将所有东西放在一起，峰值性能（对于我的笔记本电脑）是通过 13 个线程（4 位）实现的，每个线程都有 12 位的本地计数器。不包括工人 ID，我们的 UID 至少需要 56 位。因此，最好使用 64 位 UID。

图 8. UID 细分，作者图

3.2 为什么不用队列

你们中的一些人可能想知道使用专用队列将外部服务与此 ID 生成系统分离是否是个好主意。一个可能的架构如下所示：

图 9. 具有队列接口的替代架构，由作者绘制

像 Kafka 这样的中间件服务提供了很好的特性，例如解耦、缓冲、重试和简单的接口。但是，此应用程序不需要这些功能。我们不需要缓冲多余的 UID，因为它们可以被丢弃。该系统具有我能想象到的最简单的 RPC 接口，这使得 Kafka 的接口看起来像火箭科学。使用 Kafka，消费者的数量受分区数量的限制，这很不方便。

在所有反对队列的理由中，这是让我相信 RPC 更好的最重要的理由。一些队列不会透露缓冲的消息数量，这使得我们的服务无法在需求上升/下降时增加/减少容量。使用 RPC，集群主管可以更轻松地监控整体工作负载。如果没有人使用 UID，一些工人将被解雇以节省资金。

4.总结

在这篇文章中，我们设计了一个具有疯狂吞吐量的分布式顺序 UID 生成器。我们深入研究了各种方法之间的技术权衡。在面试中，没有最佳答案。所有解决方案都有优点和缺点；我们的工作是评估他们中的每一个，并根据面试官给出的限制做出最合理的权衡。