分布式ID

在分布式系统中，譬如数据库拆分的场景下，我们往往需要分布式节点各自独立生成全局唯一的ID，其需要满足唯一、趋势递增(减少落库时的索引开销)、高性能、高可用等特性：

• 全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。

• 趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。

• 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。

• 不可枚举：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；在很多应用场景下，会需要ID无规则、不规则。

常见的分布式ID算法往往基于节点本身的唯一标识，或者单点的唯一性：

• 节点本身有一个唯一标识，依赖节点自身标识实现生成ID的全局唯一性。比如zookeeper，每个zookeeper节点有一个预先设定好的nodeId，nodeId必须是一个正整数，zookeeper节点生成的ID都是本节点nodeId的同余类(比如集群数量是5，当前节点的nodeId=1时，生成的ID=5*n + 1)，由于本节点生成的ID递增，不同节点生成的ID集合互不相交，因此保证了ID的全局唯一。但是这种场景下节点需要持久化当前偏移量，在崩溃恢复后保证ID的唯一性，此外如果集群数量发生变化，可能导致ID重复，需要额外的代价做到集群数量增加。

• 节点本身无状态，由中心节点生成ID，这种方式对高可用和性能的挑战很高，但是可以生成全区唯一并且有序的序列，客户端不需要记录任何信息，每次需要ID就向中心申请即可。微信的序列号就是这么做的，生成的ID严格有序，并且做到高可用和高吞吐。

目前，有Twitter的Snowflake机制、Zookeeper机制、微信的序列号方式以及基于MySQL的sequence机制，不同的算法适应不同的场景。另外，美团开源了的 Leaf，是用于生成分布式ID的，可以用作第三方服务。

Links

• https://zhuanlan.zhihu.com/p/59289093