分布式 ID

在分布式系统存在多个 Shard 的场景中 , 同时在各个 Shard 插入数据时 , 怎么给这些数据生成全局的 unique ID?

在单机系统中 (例如一个 MySQL 实例), unique ID 的生成是非常简单的 , 如直接利用 MySQL 自带的自增 ID 功能就可以实现。

但在一个存在多个 Shards 的分布式系统 (例如多个 MySQL 实例组成一个集群 , 在这个集群中插入数据), 这个问题会变得复杂 , 所生成的全局的 unique ID 要满足以下需求 :

• 保证生成的 ID 全局唯一。
• 今后数据在多个 Shards 之间迁移不会受到 ID 生成方式的限制。
• 生成的 ID 中最好能带上时间信息 , 例如 ID 的前 k 位是 Timestamp, 这样能够直接通过对 ID 的前 k 位的排序来对数据按时间排序。
• 生成的 ID 最好不大于 64 bits。
• 生成 ID 的速度有要求 。例如 , 在一个高吞吐量的场景中 , 需要每秒生成几万个 ID (Twitter 最新的峰值到达了 143,199 Tweets/s, 也就是 10 万+/ 秒)
• 整个服务最好没有单点。

如果没有上面这些限制, 问题会相对简单, 例如：

• 直接利用 UUID.randomUUID() 接口来生成 unique ID (http://www.ietf.org/rfc/rfc4122.txt). 但这个方案生成的 ID 有 128 bits, 另外 , 生成的 ID 中也没有带 Timestamp。
• 利用一个中心服务器来统一生成 unique ID. 但这种方案可能存在单点问题 ; 另外 , 要支持高吞吐率的系统 , 这个方案还要做很多改进工作 (例如 , 每次从中心服务器批量获取一批 IDs, 提升 ID 产生的吞吐率)。
• Flickr 的做法 (http://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/). 但他这个方案 ID 中没有带 Timestamp, 生成的 ID 不能按时间排序。