14. Design Unique ID Generator In Distributed Systems

info

在实际业务建模过程中，大多数情况下我们需要通过一个唯一 ID 来标记一条数据例如用户信息等，而这些唯一 ID 需要在插入数据库之前在程序中生成，如果存在多个不同的后端 pod 同时接受请求，则需要使用一个分布式的 ID 生成器来解耦 ID 生成与后端 Pod 的依赖。

Your first thought might be to use a primary key with the auto_increment attribute in a traditional database. However, auto_increment does not work in a distributed environment because a single database server is not large enough and generating unique IDs across multiple databases with minimal delay is challenging.

然而，auto_increment 不适用于分布式环境，因为单个数据库服务器不够大，并且以最小的延迟跨多个数据库生成唯一 ID 具有挑战性。

Step 1 - Understand the problem and Requirements

• IDs must be unique.
• IDs are numerical values only. 数值型
• IDs fit into 64-bit. 64 位
• IDs are ordered by date. 按日期排序
• Ability to generate over 10,000 unique IDs per second. 每秒能够生成超过 10,000 个唯一 ID

Step 2 - Propose high-level design and get buy-in

The common options we considered are:

• Universally unique identifier (UUID)
• Twitter Snowflake approach
• Range-based Allocation 号段模式

UUID

A UUID is another easy way to obtain unique IDs. UUID is a 128-bit number used to identify information in computer systems

Here is an example of UUID: 09c93e62-50b4-468d-bf8a-c07e1040bfb2. UUIDs can be generated independently without coordination between servers. UUID 可以独立生成，无需服务器之间协调。

In this design, each web server contains an ID generator, and a web server is responsible for generating IDs independently. 每个 Web 服务器都包含一个 ID 生成器，并且 Web 服务器负责独立生成 ID。

Pros:

• Generating UUID is simple. No coordination between servers is needed so there will not be any synchronization issues. 服务器之间不需要协调，因此不会出现任何同步问题。
• The system is easy to scale because each web server is responsible for generating IDs they consume. ID generator can easily scale with web servers. 易于扩展。

Cons:

• IDs are 128 bits long, but our requirement is 64 bits. IDs 的常见过长, If the primary key is long, the secondary indexes use more space, so it is advantageous to have a short primary key. -- MySQL - 14.6.2.1 Clustered and Secondary Indexes
• IDs do not go up with time. 无序，随机字符串，不具备自增的趋势。
• IDs could be non-numeric. 为字符串，非数字。
• 如果以 uuid 为主键，则主键索引分页的概率较大，数据页越多，磁盘 IO 的次数也会越多，查询速度也会越慢
  • 自增主键记录会顺序添加到当前索引节点的后续位置，当 16kb 的一页写满时，会自动新建一页。
  • 而非自增主键的插入顺序类似于随机，插入容易导致 B+树数据的频繁的移动和分页操作；

Twitter snowflake approach

Twitter’s unique ID generation system called “snowflake” [3] is inspiring and can satisfy our requirements. 雪花算法（Snowflake）是 twitter 公司内部分布式项目采用的 ID 生成算法。Snowflake 生成的是 Long 类型的 ID

Instead of generating an ID directly, we divide an ID into different sections. Figure 5 shows the layout of a 64-bit ID.

理论上 snowflake 方案的 QPS 约为 4 million/s，这种分配方式可以保证在任何一个 IDC 的任何一台机器在任意毫秒内生成的 ID 都是不同的。

Each section is explained below.

• Sign bit 符号位: 1 bit. It will always be 0. This is reserved for future uses. It can potentially be used to distinguish between signed and unsigned numbers.
• Timestamp 时间戳: 41 bits. Milliseconds since the epoch or custom epoch. We use Twitter snowflake default epoch 1288834974657, equivalent to Nov 04, 2010, 01:42:54 UTC.
• Datacenter ID: 5 bits, which gives us 2 ^ 5 = 32 datacenters.
• Machine ID: 5 bits, which gives us 2 ^ 5 = 32 machines per datacenter.
• Sequence number 自增序列号: 12 bits. For every ID generated on that machine/process, the sequence number is incremented by 1. The number is reset to 0 every millisecond. 对于该机器/进程上生成的每个 ID，序列号都会增加 1。该数字每毫秒重置为 0。

Pros:

• 毫秒数在高位，自增序列在低位，整个 ID 都是趋势递增的。
• 不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成 ID 的性能也是非常高的。
• 可以根据自身业务特性分配 bit 位，非常灵活。

Cons:

• Clock synchronization 时钟同步问题
• Strong Dependence on Machine Clock. If the system clock is set back to a past time (due to some issues), it may lead to duplicate IDs or temporary unavailability of the service. 强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。

info

强依赖机器时钟 在 Snowflake 算法中，生成的 ID 的一部分是基于时间戳的。这意味着算法需要访问当前时间来生成 ID。因此，如果系统的时钟不准确，那么生成的 ID 也可能不准确。这种对系统时钟的依赖被称为“强依赖机器时钟”。

时钟回拨问题 时钟回拨是指系统时钟由于某种原因（如手动更改、软件错误或同步问题）而被设置成过去的时间。在 Snowflake 算法中，这会导致两个主要问题:

• 发号重复: 因为时间戳是 ID 的一部分，如果时钟回拨到过去的某个时间点，那么生成的 ID 可能与之前在那个时间点生成的 ID 相同。在分布式系统中，ID 的唯一性是非常重要的，重复的 ID 可能会导致数据冲突和一系列的问题。
• 服务不可用: 为了避免重复 ID 的问题，Snowflake 算法可能会在检测到时钟回拨时停止生成新的 ID，直到系统时钟赶上之前的时间点。这意味着，在这段时间里，系统无法生成新的 ID，从而导致服务不可用。

Range-based Allocation 号段模式

在数据库自增 ID 中，使用的时数据库提供的自增 ID 的多业务可扩展性不强，可以通过号段模式来优化

号段模式为: 业务每次使用事务的方式来数据库取一个号段存储到内存中，然后每次生成 ID 的时候从内存中取数据。

CREATE TABLE ids (
  id int(10) NOT NULL auto_increment,
  max_id bigint(20) NOT NULL COMMENT '当前最大id',
  step int(20) NOT NULL COMMENT '号段的步长',
  biz_type	varchar(64) NOT NULL COMMENT '业务类型',
  update_timestamp TIMESTAMP DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  PRIMARY KEY (`id`),
  UNIQUE KEY `biz_type` (`biz_type`)
)

通过 biz_type 来区分不同的业务，每次业务取号时，新建一个事务，然后锁定对于的 biz_type 的行，更新 max_id，写表，提交事务，然后就可以获取到一个完整的 ID；

Pros:

• 便于扩展
• ID 为 64 位且有递增趋势
• 服务内有缓存，DB 暂时性宕机对业务基本无影响
• max_id 可以自定义，便于迁移

Cons:

• ID 不随机
• 号段用完的时候需要取号段，此时会对业务产生一定的影响，如果取号段的时候 DB 挂掉，则业务不可用
• DB 宕机时间过长会导致整个系统不可用

为了解决上述问题，可以通过采用下面的架构: 内存中存储了多个号段，当号段消耗超过一定比例的时候，启动一个异步任务取更新号段，此时即使 DB 宕机，服务也会缓存一定的号段（可以为峰值 QPS 的倍数）维持业务的运行。

美团分布式 ID 生成系统

01 Requirements

数据日渐增长，对数据分库分表后需要有一个唯一 ID 来标识一条数据或消息，数据库的自增 ID 显然不能满足需求；特别一点的如订单、骑手、优惠券也都需要有唯一 ID 做标识。此时一个能够生成全局唯一 ID 的系统是非常必要的。概括下来，那业务系统对 ID 号的要求有哪些呢？

• 全局唯一性: 不能出现重复的 ID 号，既然是唯一标识，这是最基本的要求。
• 趋势递增: 在 MySQL InnoDB 引擎中使用的是聚集索引，由于多数 RDBMS 使用 B-tree 的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
• 单调递增: 保证下一个 ID 一定大于上一个 ID，例如事务版本号、IM 增量消息、排序等特殊需求。
• 信息安全: 如果 ID 是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定 URL 即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要 ID 无规则、不规则。

上述 123 对应三类不同的场景，3 和 4 需求还是互斥的，无法使用同一个方案满足。

同时除了对 ID 号码自身的要求，业务还对 ID 号生成系统的可用性要求极高，想象一下，如果 ID 生成系统瘫痪，整个美团点评支付、优惠券发券、骑手派单等关键动作都无法执行，这就会带来一场灾难。

由此总结下一个 ID 生成系统应该做到如下几点:

• Both Average Latency and TP999 Latency should be as low as possible. 平均延迟和 TP999 延迟都要尽可能低
• 可用性 Five Nines
• High QPS

info

平均延迟在英文中通常称为 "Average Latency"。这是衡量系统响应时间的一个重要指标，表示在一段时间内所有请求的响应时间的平均值。

TP999 延迟在英文中被称为 "Tail Latency at 99.9th Percentile" 或 "TP999 Latency"。这个指标表示在所有请求中，有 99.9%的请求其响应时间都低于这个值。它用于衡量系统在极端情况下的性能表现，反映了系统的稳定性和可靠性。

02 Range-based Allocation 号段数据库方案

• 利用 proxy server 批量获取，每次获取一个 segment (step 决定大小) 号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。
• 各个业务不同的发号需求用 biz_tag 字段来区分，每个 biz_tag 的 ID 获取相互隔离，互不影响。
• 如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对 biz_tag 分库分表就行。

CREATE TABLE ids (
  id int(10) NOT NULL auto_increment,
  max_id bigint(20) NOT NULL COMMENT '当前最大id',
  step int(20) NOT NULL COMMENT '号段的步长',
  biz_type	varchar(64) NOT NULL COMMENT '业务类型',
  update_timestamp TIMESTAMP DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  PRIMARY KEY (`id`),
  UNIQUE KEY `biz_type` (`biz_type`)
)

• biz_tag 用来区分业务，
• max_id 表示该 biz_tag 目前所被分配的 ID 号段的最大值，
• step 表示每次分配的号段长度。
• 原来获取 ID 每次都需要写数据库，现在只需要把 step 设置得足够大，比如 1000。那么只有当 1000 个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从 1 减小到了 1/step

test_tag 在第一台 Leaf 机器上是 1-1000 的号段，当这个号段用完时，会去加载另一个长度为 step=1000 的号段，假设另外两台号段都没有更新，这个时候第一台机器新加载的号段就应该是 3001-4000。同时数据库对应的 biz_tag 这条数据的 max_id 会从 3000 被更新成 4000，更新号段的 SQL 语句如下

Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx
SELECT tag, max_id, step FROM table WHERE biz_tag=xxx
Commit

Pros

• Leaf 服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景。
• ID 号码是趋势递增的 8byte 的 64 位数字，满足上述数据库存储的主键要求。
• 容灾性高: Leaf 服务内部有号段缓存，即使 DB 宕机，短时间内 Leaf 仍能正常对外提供服务。
• 可以自定义 max_id 的大小，非常方便业务从原有的 ID 方式上迁移过来。

Cons

• ID 号码不够随机，能够泄露发号数量的信息，不太安全。
• TP999 数据波动大，当号段使用完之后还是会 hang 在更新数据库的 I/O 上，tg999 数据会出现偶尔的尖刺。
• DB 宕机会造成整个系统不可用。

尽管这种 ID 生成系统在大多数时间内性能稳定，但在需要与数据库交互以获取新号段时，可能会出现性能瓶颈，导致偶尔的高延迟现象。

2.1 双 Buffer 优化

取号段的时机是在号段消耗完的时候进行的，也就意味着号段临界点的 ID 下发时间取决于下一次从 DB 取回号段的时间，并且在这期间进来的请求也会因为 DB 号段没有取回来，导致线程阻塞。如果请求 DB 的网络和 DB 的性能稳定，这种情况对系统的影响是不大的，但是假如取 DB 的时候网络发生抖动，或者 DB 发生慢查询就会导致整个系统的响应时间变慢。

我们希望 DB 取号段的过程能够做到无阻塞，不需要在 DB 取号段的时候阻塞请求线程，即当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。这样做就可以很大程度上的降低系统的 TP999 指标。

Solution

采用双 buffer 的方式，Leaf 服务内部有两个号段缓存区 segment。当前号段已下发 10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前 segment 接着下发，循环往复。

• 每个 biz_tag 都有消费速度监控，通常推荐 segment 长度设置为服务高峰期发号 QPS 的 600 倍 (10 分钟)，这样即使 DB 宕机，Leaf 仍能持续发号 10-20 分钟不受影响。
• 每次请求来临时都会判断下个号段的状态，从而更新此号段，所以偶尔的网络抖动不会影响下个号段的更新。

03 Snowflake 方案

Leaf-segment 方案可以生成趋势递增的 ID，同时 ID 号是可计算的，不适用于订单 ID 生成场景，比如竞对在两天中午 12 点分别下单，通过订单 id 号相减就能大致计算出公司一天的订单量，这个是不能忍受的。面对这一问题，我们提供了 Leaf-snowflake 方案。

弱依赖 ZooKeeper

除了每次会去 ZK 拿数据以外，也会在本机文件系统上缓存一个 workerID 文件。当 ZooKeeper 出现问题，恰好机器出现问题需要重启时，能保证服务能够正常启动。

对于 workerID 的分配，使用 Zookeeper 持久顺序节点的特性自动对 snowflake 节点配置 wokerID。Leaf-snowflake 是按照下面几个步骤启动的:

• 启动 Leaf-snowflake 服务，连接 Zookeeper，检查自己是否已经注册过（是否有该顺序子节点）。
• 如果有注册过直接取回自己的 workerID (zk 顺序节点生成的 int 类型 ID 号)，启动服务。
• 如果没有注册过，就在该父节点下面创建一个持久顺序节点，创建成功后取回顺序号当做自己的 workerID 号，启动服务。

解决时钟问题

• 检查是否已经注册
  • 如果这个服务之前在 Zookeeper 注册过，它会检查自己的系统时间。如果系统时间比 Zookeeper 记录的旧，就意味着时钟有问题，服务启动失败，并会发送一个警报。
• 对于新服务的处理
  • 如果是第一次启动，服务就在 Zookeeper 创建一个新记录，并写下当前时间。
  • 然后，服务会检查它的时间是否准确，通过 RPC 请求所有节点的系统时间，计算出所有节点时间的平均值。
  • IfAbs(systemTime - sum(time)/nodeSize) < Threshold, 认为当前系统时间准确，正常启动服务。
  • 否则认为本机系统时间发生大步长偏移，启动失败并报警。
• 定期更新时间信息
  • 每隔一段时间 (3 秒) 更新它在 Zookeeper 节点的时间信息。

由于强依赖时钟，对时间的要求比较敏感。在时钟回拨的时候直接不提供服务直接返回 ERROR_CODE，等时钟追上即可。或者做一层重试，然后上报报警系统，更或者是发现有时钟回拨之后自动摘除本身节点并报警。

 //发生了回拨，此刻时间小于上次发号时间
 if (timestamp < lastTimestamp) {

            long offset = lastTimestamp - timestamp;
            if (offset <= 5) {
                try {
                	//时间偏差大小小于5ms，则等待两倍时间
                    wait(offset << 1);//wait
                    timestamp = timeGen();
                    if (timestamp < lastTimestamp) {
                       //还是小于，抛异常并上报
                        throwClockBackwardsEx(timestamp);
                      }
                } catch (InterruptedException e) {
                   throw  e;
                }
            } else {
                //throw
                throwClockBackwardsEx(timestamp);
            }
        }
 //分配ID

Reference

• Leaf——美团点评分布式 ID 生成系统
• 分布式 ID 生成算法