谈谈常用的分布式ID的设计方案？

典型回答

首先，我们需要明确通常的分布式ID定义，基本的要求包括：

全局唯一，区别于单点系统的唯一，全局是要求分布式系统内唯一。
有序性，通常都需要保证生成的ID是有序递增的。例如，在数据库存储等场景中，有序ID便于确定数据位置，往往更加高效。

目前业界的方案很多，典型方案包括：

基于数据库自增序列的实现。这种方式优缺点都非常明显，好处是简单易用，但是在扩展性和可靠性等方面存在局限性。
基于Twitter早期开源的Snowflake的实现，以及相关改动方案。这是目前应用相对比较广泛的一种方式，其结构定义你可以参考下面的示意图。
整体长度通常是64 （1 + 41 + 10+ 12 = 64）位，适合使用Java语言中的long类型来存储。

头部是1位的正负标识位。

紧跟着的高位部分包含41位时间戳，通常使用System.currentTimeMillis()。

后面是10位的WorkerID，标准定义是5位数据中心 + 5位机器ID，组成了机器编号，以区分不同的集群节点。

最后的12位就是单位毫秒内可生成的序列号数目的理论极限。
Snowflake的官方版本是基于Scala语言，Java等其他语言的参考实现有很多，是一种非常简单实用的方式，具体位数的定义是可以根据分布式系统的真实场景进行修改的，并不一定要严格按照示意图中的设计。

Redis、ZooKeeper、MongoDB等中间件，也都有各种唯一ID解决方案。其中一些设计也可以算作是Snowflake方案的变种。例如，MongoDB的ObjectId提供了一个12 byte（96位）的ID定义，其中32位用于记录以秒为单位的时间，机器ID则为24位，16位用作进程ID，24位随机起始的计数序列。
国内的一些大厂开源了其自身的部分分布式ID实现，InfoQ就曾经介绍过微信的seqsvr，它采取了相对复杂的两层架构，并根据社交应用的数据特点进行了针对性设计，具体请参考相关代码实现。另外，百度、美团等也都有开源或者分享了不同的分布式ID实现，都可以进行参考。

考点分析

涉及分布式，很多单机模式下的简单问题突然就变得复杂了，这是分布式天然的复杂性，需要从不同角度去理解适用场景、架构和细节算法，我会从下面的角度进行适当解读：

我们的业务到底需要什么样的分布式ID，除了唯一和有序，还有哪些必须要考虑的要素？
在实际场景中，针对典型的方案，有哪些可能的局限性或者问题，可以采取什么办法解决呢？

知识扩展

如果试图深入回答这个问题，首先需要明确业务场景的需求要点，我们到底需要一个什么样的分布式ID？

需求要点

除了唯一和有序，考虑到分布式系统的功能需要，通常还会额外希望分布式ID保证：

有意义，或者说包含更多信息，例如时间、业务等信息。这一点和有序性要求存在一定关联，如果ID中包含时间，本身就能保证一定程度的有序，虽然并不能绝对保证。ID中包含额外信息，在分布式数据存储等场合中，有助于进一步优化数据访问的效率。
高可用性，这是分布式系统的必然要求。前面谈到的方案中，有的是真正意义上的分布式，有得还是传统主从的思路，这一点没有绝对的对错，取决于我们业务对扩展性、性能等方面的要求。
紧凑性，ID的大小可能受到实际应用的制约，例如数据库存储往往对长ID不友好，太长的ID会降低MySQL等数据库索引的性能；编程语言在处理时也可能受数据类型长度限制。

在具体的生产环境中，还有可能提出对QPS等方面的具体要求，尤其是在国内一线互联网公司的业务规模下，更是需要考虑峰值业务场景的数量级层次需求。

主流方案的优缺点分析

对于数据库自增方案，除了实现简单，它生成的ID还能够保证固定步长的递增，使用很方便。

但是，因为每获取一个ID就会触发数据库的写请求，是一个代价高昂的操作，构建高扩展性、高性能解决方案比较复杂，性能上限明显，更不要谈扩容等场景的难度了。与此同时，保证数据库方案的高可用性也存在挑战，数据库可能发生宕机，即使采取主从热备等各种措施，也可能出现ID重复等问题。

实际大厂商往往是构建了多层的复合架构，例如美团公开的数据库方案Leaf-Segment，引入了起到缓存等作用的Leaf层，对数据库操作则是通过数据库中间件提供的批量操作，这样既能保证性能、扩展性，也能保证高可用。但是，这种方案对基础架构层面的要求很多，未必适合普通业务规模的需求。

与其相比，Snowflake方案的好处是算法简单，依赖也非常少，生成的序列可预测，性能也非常好，比如Twitter的峰值超过10万/s。

但是，它也存在一定的不足，例如：

时钟偏斜问题（Clock Skew）。我们知道普通的计算机系统时钟并不能保证长久的一致性，可能发生时钟回拨等问题，这就会导致时间戳不准确，进而产生重复ID。
针对这一点，Twitter曾经在文档中建议开启NTP，毕竟Snowflake对时间存在依赖，但是也有人提议关闭NTP。我个人认为还是应该开启NTP，只是可以考虑将stepback设置为0，以禁止回调。
从设计和具体编码的角度，还有一个很有效的措施就是缓存历史时间戳，然后在序列生成之前进行检验，如果出现当前时间落后于历史时间的不合理情况，可以采取相应的动作，要么重试、等待时钟重新一致，或者就直接提示服务不可用。
另外，序列号的可预测性是把双刃剑，虽然简化了一些工程问题，但很多业务场景并不适合可预测的ID。如果你用它作为安全令牌之类，则是非常危险的，很容易被黑客猜测并利用。
ID设计阶段需要谨慎考虑暴露出的信息。例如，Erlang版本的flake实现基于MAC地址计算WorkerID，在安全敏感的领域往往是不可以这样使用的
从理论上来说，类似Snowflake的方案由于时间数据位数的限制，存在与2038年问题相似的理论极限。虽然目前的系统设计考虑数十年后的问题还太早，但是理解这些可能的极限是有必要的，也许会成为面试的过程中的考察点

如果更加深入到时钟和分布式系统时序的问题，还有与分布式ID相关但又有所区别的问题，比如在分布式系统中，不同机器的时间很可能是不一致的，如何保证事件的有序性？Lamport在1978年的论文（Time, Clocks, and the Ording of Events in a Distributed System）中就有很深入的阐述，有兴趣的同学可以去查找相应的翻译和解读。

最后，再补充一些当前分布式领域的面试热点，例如：

分布式事务，包括其产生原因、业务背景、主流的解决方案等。

理解CAP、BASE等理论，懂得从最终一致性等角度来思考问题，理解Paxos、Raft等一致性算法。

理解典型的分布式锁实现，例如最常见的Redis分布式锁。

负载均衡等分布式领域的典型算法，至少要了解主要方案的原理。