1.场景需求需求界定

•ID必须是唯一的。

•ID只包含数字。

•ID长为64位。

•ID按日期排序。

•可以每秒生成超过10，000个唯一ID。

2.高层级的设计

在分布式系统中，有多个方法可以用来生成唯一ID。我们考虑的方法有：

•多主复制(Multi-master Replication)。

•通用唯一标识符(Universally Unique Identifier，UUID)。

•工单服务器(Ticket Server)。

•推特的雪花(Snowflake)系统。

我们来看看它们的工作原理以及优缺点。

2.1.多主复制

图-1

这个方法利用了数据库的自增特性。我们并不是把下一个ID加1，而是加k，这里k是正在使用的服务器数量。在图-1中，生成的下一个ID等于同一个服务器上的前一个ID加2。这种方法解决了一些可扩展性问题，因为ID可以随着服务器数量的增加而同步扩展。但是这个方法也有一些重大缺点。

•很难与多个数据中心一起扩展，需要进行额外的同步和协调操作。

•在分布式环境下，多个服务器同时生成ID，可能导致ID并不连续，也即ID并不随时间递增。

•当服务器被添加或者移除时，ID不能很好地随之变化。

2.2 UUID

UUID是另一种获取唯一ID的简单方法。UUID是一个128位的数字，用来标识计算机系统中的信息。UUID重复的概率非常低。这里引用维基百科的说法，“每秒产生10亿个UUID且持续约100年，产生一个重复UUID的概率才达到50%。”。下面是一个UUID的例子：09c93e62-50b4-468d-bf8a-c07e1040bfb2。UUID可以独立地生成而不需要在服务器之间做任何协调。图-2展示了采用UUID的设计。在这个设计中，每个Web服务器都含有一个ID生成器且负责独立地生成ID。

图-2

UUID方法的优点是：

•生成ID很简单。服务器之间不需要任何协调，所以不会有任何同步问题。

•系统易于扩展，因为每个Web服务器只负责生成它们自己使用的ID。ID生成器可以很容易地随Web服务器一起扩展。

其缺点是：

•ID长128位，但是我们要求的是64位。

•ID并不随时间增加。

•ID可能是非数字的。

2.3 工单服务器

工单服务器也是生成唯一ID的重要方法。Flicker研发了工单服务器来生成分布式主键。值得一提的是这个方法的工作原理。这个方法的思想是利用中心化的单数据库服务器（工单服务器）的自增特性（参见图-3）。

图-3

工单服务器方法的优点是：

•ID为数字。

•容易实现，适用于中小型应用。

其缺点是存在单点故障。单个工单服务器意味着，如果这个服务器发生故障，所有依赖于它的系统就都会面临问题。为了避免单点故障，我们可以设置多个工单服务器。但是这会引入新的挑战，比如数据同步问题。

2.4雪花系统

前面介绍了几个ID生成方法的原理，但是这些方法中没有一个满足我们的特定需求，因此我们需要另一种方法。推特的唯一ID生成系统叫作“Snowflake”（雪花），它很有启发性，而且能满足我们的需求。分布解决是个好办法。我们不直接生成一个ID，而是把一个ID分成不同的部分。图-4展示了一个64位ID的构成。

图-4

每个部分的含义如下所述。

•符号位（1位）：它始终为数字0，留作未来使用。它有可能被用来区分有符号数和无符号数。

•时间戳（41位）：它是从纪元或者自定义纪元开始以来的毫秒数。我们使用Snowflake默认纪元(epoch)1，288，834，974，657，相当于UTC时间2010年11月4日01:42:54。

•数据中心ID（5位）：最多可以有32个(25)数据中心。

•机器ID（5位）：每个数据中心最多可以有32台(25)机器。

•序列号（12位）：对于某个机器/进程，每生成一个ID，序列号就加1。这个数字每毫秒开始时都会被重置为0。

3.深入设计

我们讨论了在分布式系统中设计唯一ID生成器的各种方法，最后选择了基于推特Snowflake ID生成器的方法。接下来，我们进行深入的设计。

图-5

数据中心ID和机器ID通常在起始阶段就选好了，一旦系统运行起来，这两个部分就是固定的。对数据中心ID和机器ID所做的任何更改都需要仔细审查，因为对这些值的意外改动可能会导致ID冲突。时间戳和序列号是在ID生成器运行后才生成的。

3.1时间戳

41位的时间戳是ID中最重要的部分。随着时间的推移，时间戳不断增长，因此ID可以按时间排序。图-6展示了一个例子，将二进制表示的时间戳转换成UTC时间。你也可以用类似的方法把UTC时间转换成二进制表示。

41位能表示的最大时间戳是241-1，即2，199，023，255，551毫秒(ms)，约等于69年（计算方法为2，199，023，255，551÷1000÷365÷24÷3600）。这意味着ID生成器可以工作约69年。如果我们把纪元开始时间定制得离今天的日期足够近，就可以延迟溢出时间。69年后，我们需要一个新的纪元时间或者采用别的技术来迁移ID。

图-6

3.2序列号

序列号有12位，相当于4096种组合(212)。这个部分一般是0，除非在1毫秒内同一个服务器生成了多个ID。理论上，一个服务器每毫秒最多生成4096个新ID。

4.总结

在本文中，我们讨论了设计一个唯一ID生成器的不同方法：多主复制、UUID、工单服务器和类似推特Snowflake的唯一ID生成器。我们最后选择了Snowflake，因为它支持我们的所有用例，并且可以在分布式环境中扩展。如果在面试的最后还有一些时间，你可以讨论下面这些议题。

•时钟同步。在我们的设计里，我们假设生成ID的服务器都有同样的时钟。但是，当服务器运行在多核上时，这个假设可能并不成立。在多机器的场景中也存在同样的挑战。时钟同步的解决方案不在本文的讨论范围内；但是，知道这个问题的存在是很重要的。网络时间协议(NTP)是这个问题最流行的解决方案，感兴趣的读者可以参阅维基百科中的“Network Time Protocol”词条。

•调整ID各部分的长度。比如，对于低并发且长时间持续运行的应用，减少序列号部分的长度，增加时间戳部分的长度，生成的ID会更高效。

•高可用性。因为ID生成器是一个非常关键的系统，所以它必须是高可用的。