Darktea Home

本文主要介绍在一个分布式系统中, 怎么样生成全局唯一的 ID

一, 问题描述

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

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

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

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

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

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

在要满足前面 6 点要求的场景中, 怎么来生成全局 unique ID 呢?

Twitter 的 Snowflake 是一种比较好的做法. 下面主要介绍 Twitter Snowflake, 以及它的变种

二, Twitter Snowflake

https://github.com/twitter/snowflake

Snowflake 生成的 unique ID 的组成 (由高位到低位):

一共 63 bits (最高位是 0)

unique ID 生成过程:

整个过程中, 只是在 Worker 启动的时候会对外部有依赖 (需要从 Zookeeper 获取 Worker 号), 之后就可以独立工作了, 做到了去中心化.

异常情况讨论:

从这个异常情况可以看出, 如果 Snowflake 所运行的那些机器时钟有大的偏差时, 整个 Snowflake 系统不能正常工作 (偏差得越多, 分配新 ID 时等待的时间越久)

从 Snowflake 的官方文档 (https://github.com/twitter/snowflake/#system-clock-dependency) 中也可以看到, 它明确要求 "You should use NTP to keep your system clock accurate". 而且最好把 NTP 配置成不会向后调整的模式. 也就是说, NTP 纠正时间时, 不会向后回拨机器时钟.

三, Snowflake 的其他变种

Snowflake 有一些变种, 各个应用结合自己的实际场景对 Snowflake 做了一些改动. 这里主要介绍 3 种.

1. Boundary flake

http://boundary.com/blog/2012/01/12/flake-a-decentralized-k-ordered-unique-id-generator-in-erlang/

变化:

它这样做的目的是用更多的 bits 实现更小的冲突概率, 这样就支持更多的 Worker 同时工作. 同时, 每毫秒能分配出更多的 ID

2. Simpleflake

http://engineering.custommade.com/simpleflake-distributed-id-generation-for-the-lazy/

Simpleflake 的思路是取消 Worker 号, 保留 41 bits 的 Timestamp, 同时把 sequence number 扩展到 22 bits;

Simpleflake 的特点:

Simpleflake 的问题就是 sequence number 完全随机生成, 会导致生成的 ID 重复的可能. 这个生成 ID 重复的概率随着每秒生成的 ID 数的增长而增长.

所以, Simpleflake 的限制就是每秒生成的 ID 不能太多 (最好小于 100次/秒, 如果大于 100次/秒的场景, Simpleflake 就不适用了, 建议切换回 Snowflake).

3. instagram 的做法

先简单介绍一下 instagram 的分布式存储方案:

instagram unique ID 的组成:

生成 unique ID 时, 41 bits 的 Timestamp 和 Snowflake 类似, 这里就不细说了.

主要介绍一下 13 bits 的 logic Shard 代号 和 10 bits 的 sequence number 怎么生成.

logic Shard 代号:

sequence number 利用 PostgreSQL 每个 Table 上的 auto-increment sequence 来生成:

instagram 这个方案的优势在于:

同时, 今后做数据迁移的时候, 也是按 logic Shard 为单位做数据迁移的, 所以这种做法也不会影响到今后的数据迁移