分布式 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