系统设计-Ch7-设计一个分布式ID生成器

设计一个分布式ID生成器

Step1：Understand the problem and establish design scope

对于”设计一个分布式ID生成器“这个系统设计话题，我们可以向面试官提出以下问题：

  • Q：生成的ID是要保证是唯一的吗？

    A：ID必须是唯一的

  • Q：生成的ID必须要是数值吗？ 要求可排序吗？

    A：是的，要求是数值，要求晚创建的ID比早创建的ID大（即按日期排序）

  • Q：对于每个新的记录，ID是否递增1？

    A：不一定只递增1，随创建时间而定

  • Q：ID的长度有没有要求？

    A：64位

  • Q：系统最多支持每秒钟生成多少个ID？

    A：随使用场景可调节的，你可以假设每秒生成1000个ID

根据以上提问和回答，对于设计分布式ID生成器这个问题，我们可以总结要求如下：

  • ID必须是唯一的
  • ID仅为数值
  • ID适合64位
  • ID按生成日期排序
  • 系统具备每秒生成1000个唯一ID的能力，并且可调节

Step2：Propose high-level design and get buy-in

UUID

UUID（Universally Unique Identifier，通用唯一标识码），看名字就知道，是一类通用的唯一标识码算法。

UUID 的标准形式为，以连字号分为五段，形式为8-4-4-4-12的 32 个十六进制数（128位）组成的字符串，例如：
467e8542-2275-4163-95d6-7adc205580a9。

为什么说UUID是一类算法呢，因为其基于使用场景的不同，有不同的版本，到目前为止业界一共有5种方式生成UUID（详情请见A Universally Unique IDentifier (UUID) URN Namespace]），这里只简单介绍最常见的：
基于时间的 UUID：主要依赖当前的时间戳和机器 mac 地址生成UUID，基本可以保证全球唯一性。

优点：

  • 生成性能高，由于是本地生成，没有网络消耗（无中心认证网络交互）。

  • 自主性：在分布式环境下，UUID可以不依赖中心认证即可自动生成全局唯一ID

缺点：

  • 不易存储：16字节128位过长，不适合作为DB主键（效率）
  • 不安全：基于时间的 UUID 可能会暴露机器的mac 地址和ID的生成时间
  • 不适用于实际的业务需求：如果用作订单号的UID生成，UUID这样的字符串看不出和订单相关的有用信息

auto_increment

常见的关系型数据库一般都带有数据库字段自增的特性，如：

  • MySQL，AUTO_INCREMENT 特性
  • PostgresSQL，SEQUENCE 特性
  • Oracle，SEQUENCE 特性

这些数据库自增ID的方案，都支持设置初始值以及自增步长

例如，flicker的这篇文章所介绍的，他仅使用了两台MySQL服务器，就实现了分布式自增，原理如下：

TicketServer1:
auto-increment-increment = 2   # 自增步长 2
auto-increment-offset = 1      # 初始值 1

TicketServer2:
auto-increment-increment = 2   # 自增步长 2
auto-increment-offset = 2      # 初始值 2

# TicketServer1只会生成UID： 1 3 5 7 9.....
# TicketServer2只会生成UID： 2 4 6 8 10.....

不难发现只要保证SQL服务器集群的数量 == 自增步长，就能够保证数据库中的ID是全局唯一的。

虽然这种方案不是非常优雅，但是简单有效work well。

优点：

  • 生成性能高，具有全局唯一性，不依赖中心认证
  • ID单调递增，数值类型查询速度快

缺点：

  • 不利于扩展：如果后续需要增加新的SQL服务器，需要修改所有其它SQL服务器实例的初始值和步长配置
    而且需要扩容的数量或次数越多，配置方案越复杂，后期维护的噩梦

Twitter Snowflake

snowflake是一种以划分命名空间（UUID也算，由于比较常见，所以单独分析）来生成ID的一种算法，这种方案把64-bit分别划分成多段，分开来标示机器、时间等，比如在snowflake中的64-bit分别表示如下图所示：

最高位不用，永远为0，其余三组bit占位均可浮动，看具体的业务需求而定。
默认情况下：

  • 41-bit的时间戳可以表示(1L<<41)/(1000L∗3600∗24∗365)(1L<<41)/(1000L*3600*24*365)=69年的时间范围。
  • 5-bit的数据中心id可以支持32个数据中心。
  • 5-bit的工作机器id可以支持32台服务器（因此总共32 * 32 = 1024个服务器）。
  • 12-bit序列号支持1毫秒（一个时间戳）产生4096个自增序列id。

优点：

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

Step3：Design deep dive

最优的方案是基于Snowflake算法，即雪花算法。优缺点都总结在上面，这里就不再赘述

Step4：Warm up

下面介绍一些Snowflake算法的拓展，供读者参考：

美团Leaf

Leaf-segment

号段模式是对直接用数据库自增 ID 充当分布式 ID 的一种优化，减少对数据库的访问频率。
相当于新增了一片缓存用于存放ID，每次从数据库批量的获取自增 ID，每次获取一个seg(step大小)号段的值。

+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field       | Type         | Null | Key | Default           | Extra                       |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag     | varchar(128) | NO   | PRI |                   |                             |
| max_id      | bigint(20)   | NO   |     | 1                 |                             |
| step        | int(11)      | NO   |     | NULL              |                             |
| desc        | varchar(256) | YES  |     | NULL              |                             |
| update_time | timestamp    | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+

字段说明：

  • biz_tag：用来区分业务
  • max_id：表示该biz_tag目前所被分配的ID号段的最大值
  • step：表示每次分配的Segment号段长度

Leaf-server 中缓存的号段耗尽之后再去数据库获取新的号段，可以大大地减轻数据库的压力。
获取新段号：对 max_id 字段做一次 update 操作，update max_id = max_id + step，update 成功则说明新号段获取成功，新的号段范围为(max_id, max_id + step]。

双buffer优化

Leaf-server 中采用了异步更新的策略，通过双 buffer 的方式存储号段，如下图所示：

当前号段消费到一定程度时，会开启一个新的线程从db中获取新的号段放到另一个segment buffer;
当前号段消费完成后，进行切换操作：修改pos指向另一个号段并继续消费，并当前号段写入到数据库中。

通过这样双buffer的机制可以保证DB取号段的过程做到无阻塞.可以很大程度上的降低系统的TP999指标

优点：

  • Leaf服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景。

  • ID号码是趋势递增的8byte的64位数字，满足上述数据库存储的主键要求

  • 数据库压力小：读写数据库的频率从1减小到了1/step

  • 容灾性高：Leaf服务内部有号段缓存，即使DB宕机，短时间内Leaf仍能正常对外提供服务。

缺点：

  • ID号码不够随机，能够泄露发号数量的信息，不太安全。
Leaf-Snowflake

Leaf-snowflake方案完全沿用snowflake方案的bit位设计，即使用“1+41+10+12”的方式组装ID号。

但是对于10-bit的WorkID的配置，由于Leaf服务规模较大，使用Zookeeper持久顺序节点的特性自动对snowflake节点配置wokerID。

Leaf-snowflake 方案在处理时钟回拨问题的策略如下所示：

1）服务启动时

  • 在服务启动时，首先检查自己是否写过 zookeeper leaf_forever 节点；
  • 如果写过，则用自身系统时间与 leaf_forever/${self}节点记录时间做比较，若小于则认为机器时间发生了大步长回拨，服务启动失败并告警；
  • 如果没有写过，直接创建持久节点 leaf_forever/${self}，并写入自身系统时间；
  • 然后取 leaf_temporary 下的所有临时节点(所有运行中的 Leaf-snowflake 节点)的服务 IP：Port，然后通过 RPC 请求得到所有节点的系统时间，计算 sum(time)/nodeSize；
  • 如果若 abs( 系统时间-sum(time)/nodeSize ) < 阈值，认为当前系统时间准确，正常启动服务，同时写临时节点 leaf_temporary/${self} 维持租约；否则认为本机系统时间发生大步长偏移，启动失败并报警；
  • 每隔一段时间(3s)上报自身系统时间写入 leaf_forever/${self}。

2）服务运行时

  • 会检查时钟回拨时间是否小于 5ms，若时钟回拨时间小于等于 5ms，等待时钟回拨时间后，重新产生新的 ID；若时钟回拨时间大于 5ms，直接抛异常给到业务侧。

基于多时间线改进的雪花算法

基于多时间线改进的雪花算法在 snowflake 基础上增加了时间线部分（1~2 位），可同时支持 2~4 条时间线并行。其对雪花算法的 bit 位的分配做了微调，如下图所示：

基于多时间线改进的雪花算法生成 ID 过程如下所示：

  • 初始时，所有时间线进度均为基准时间，随机选定一条时间线作为当前时间线；
  • 在当前时间线上生成 ID，同时推进当前时间线进度；
  • 一旦发生时钟回退，且回退距离小于一定阈值，等待时间推进直到回退前的时间，会到步骤 2 继续生成 ID；
  • 如果回退距离大于阈值，暂停当前时间线进度，选择一条合适的时间线（进度<当前时间）并切换到该时间线，回到步骤 2 继续生成 ID。如果找不到合适的时间线，报错返回。

总体而言，现在主流的分布式UID生成主要分为以下两种方案：

  1. 基于数据库字段自增的号段模式
  2. 基于NameSpace的Snowflake算法

针对其各自衍生出的问题，上述一些企业提出了自己的改进策略：
号段模式（提高数据库读写效率）+双buffer异步更新（实现取号段无阻塞）
ZooKeeper持久化或多时间线标志位解决Snowflake的时钟回拨问题

Ref

【1】https://soulmachine.gitbooks.io/system-design/content/cn/distributed-id-generator.html

【2】https://zhuanlan.zhihu.com/p/534893180

【3】https://zhuanlan.zhihu.com/p/152179727