随机 ID 生成器

原文：Random ID Generator

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

让我们继续讨论我们的系统设计面试问题。如果你刚刚看到这个系列，你可以查看我们以前的文章。基本上，我们每个星期都会选择一些有趣的面试问题，并提供深入的分析。

值得注意的是，这篇文章并不是要给你一些标准答案。相反，我们更注重分析问题，以及如何提出合理的方法。系统设计面试更是如此，因为这个问题可能是非常开放的。

本周，我们将讨论如何设计随机 ID 生成器。我们将介绍一些主题，包括扩展 ID 生成器和每种方法的优缺点。

如果你不知道ID生成器是什么，请让我在这里简要解释一下。假设你正在构建 Twitter 这样的社交网络产品，则需要将每个用户存储在数据库中，并使用唯一的用户标识来确定系统中的每个用户。

在某些系统中，你可以从1, 2, 3 ... N持续增加 ID 。在其他系统中，我们可能需要生成一个随机字符串的 ID。通常，ID 生成器的要求很少：

他们不能任意长。比方说，我们保持在 64 位。
ID 按日期递增。这给系统提供了很大的灵活性，例如你可以通过 ID 排序用户，这与登记日期排序相同。

还有一些其他的要求，尤其是当你想扩展系统来支持数百万甚至数十亿用户时。

单机

我们以前的建议是，从简单的事情开始并继续优化就很好，当问题很宽泛时更是如此。如果我在系统设计面试中遇到这个问题，很可能我会从一台机器设计开始。这不仅容易设计，而且在大多数情况下都足够了。

在最简单的情况下，我们可以从1, 2, 3 ... N递增 ID，这实际上是许多真实项目中最常用的生成 ID 的方法之一。如果用户 A 的 ID 比用户 B 大，那么我们知道 A 是稍后注册的。

但是，这种方法难以扩展。比方说一年之后，每天都有太多的用户，需要将数据库扩展到多个实例。你会看到这种方法无效，因为它可能会为不同的用户生成重复的 ID。

为了将 ID 生成器扩展到多台机器，一种自然的解决方案是维护一个单独的服务器，只负责生成 ID。更具体地说，当用户注册产品时，无论哪个服务器处理这个请求，它都会连接到第三方服务器来请求一个随机 ID。由于所有 ID 的生成都是在一台服务器上处理的，因此不会产生重复的 ID。

然而，这个解决方案的缺点是显而易见的。假设产品如此受欢迎，以至于一秒钟内就可能有大量的注册用户，第三方服务器很快就会成为瓶颈。服务器可能会阻止注册或只是崩溃。

因此，我们必须将 ID 生成扩展到多个服务器。如果我们不想和 ID 生成服务器通信，则每个服务器应该自己能够生成随时间增加的唯一 ID。考虑使用时间戳来生成 ID 应该是很自然的。

由于在一个时间戳内也可能有多个用户，我们可以用两种方法解决这个问题。

我们为每个 ID 生成服务器分配一个服务器 ID，最终的 ID 是时间戳和服务器 ID 的组合。
我们还可以在单个服务器上的单个时间戳内允许多个请求。我们可以在每个服务器上保留一个计数器，它表示在当前时间戳里已经生成了多少个 ID。所以最终的 ID 是时间戳，serverID 和计数器的组合。

如前所述，ID 不能是任意长的，例如计数器可能只有 8 位。在这种情况下，服务器最多可以在单个时间戳内处理 256 个请求。如果频繁超过这个限制，我们需要添加更多的实例。

事实上，这个解决方案就是 Twitter 解决问题的方法。他们开放了他们的 ID 生成器，叫 Snowflake。

我们忽略了上述分析中的一个关键问题。事实上，有一个隐藏的假设，即所有 ID 生成服务器都有相同的时钟来生成时间戳，在分布式系统中可能不是这样。

实际上，在分布式系统中的系统时钟可能会发生严重偏斜，这可能会导致我们的 ID 生成器提供重复的 ID，或顺序不正确的 ID。时钟同步不在本次讨论的范围内，但是，了解这个系统中的这个问题对你来说很重要。有很多方法可以解决这个问题，如果你想了解更多的信息，请查看 NTP。

随机 ID 生成器在许多真实项目中是一个非常实际的问题。与许多其他系统类似，乍看起来似乎很容易，但在扩展到多台机器时存在相当多的问题。如果你想了解此主题的更多信息，还可以查看 Flickr 的票务服务器，这是除了“Snowflake”之外的另一种方法。