我看 ID 生成器

什么是 ID 生成器

全局唯一 ID 作为一种唯一标识来区分数据,它可以用作订单号、用户 ID 等。在一个大的系统中或者基础服务里,提供一种全局唯一 ID 十分重要。ID 生成器的作用就是生成全局唯一 ID 的工具,甚至它能作为一种基础服务为其他业务提供服务。

构建 ID

怎样去构建一个全局唯一的 ID ?获得唯一 ID 的方式有:带时间戳和不带时间戳两种。时间戳能很好的表达ID的唯一性。考虑到一秒或更小的时间单位内可能并发生成大量 ID,可以再添加序列号增加区分粒度。而不带时间戳的全局唯一 ID 主要是通过生成时的序列号来辨识了。

Snowflake

Snowflake 算法就是带有时间戳的全局唯一 ID 生成算法。它有一套固定的ID格式,如下:

41位的时间序列(精确到毫秒,41位的长度可以使用69年)
10位的机器标识(10位的长度最多支持部署1024个节点)
12位的计数顺序号(12位的计数顺序号支持每个节点每毫秒产生4096个ID序号)

Ticket servers

MySQL 本身支持 auto_increment 操作,可以借助这个特性来构建ID。Flicker 的 Ticket servers 就利用了 MySQL 自增长特性。

构建 ID 生成器

除了使用带时间戳的 snowflake 算法,数据库自增特性来生成全局唯一 ID,还可以不带时间戳,不依靠数据库自增来生成。你可以自己构建一个 ID 生成器来实现它。没有时间戳的区分粒度,那么它只能靠生成 ID 时的序列号来唯一标识。

原型

一个简单的ID生成器原型构成部分有:保存 ID 数据的数据库和分配 ID 的 worker 组成。worker 分配 ID 后存到数据库,下次再需要分配 ID 时,从数据库中查询到已分配的最大 ID,然后加1,作为新的ID分配出去。
原型
这只是一个简单的生成器,可以为它添加一个对外服务的接口。其它程序调用这个接口就能发出申请ID的请求,worker接收到请求后分配ID。
原型2

改进

频繁地读取数据库带来的后果是整个程序的响应速度慢。同时,当有大量的请求过来时,会给数据库带来巨大压力。

减少访问数据库次数

其实,分配 ID 时可以不用每次都读写数据库。在服务器上用一段内存来保存最近一次分配的 ID。而且,已经被分配出去的 ID 也可以不用每次到保存到数据库,而是先存放在内存里面,然后一段一段的存到数据库。这两种方式有效地减少了数据库存取频率。
如果业务不需要保存已经分配出去的每个 ID,那么存到数据库中的数据可以不是 ID,而是 ID 段。ID 段指由多个 ID 组成的一个序列。假设某 ID 段[minID, maxID],当前被分配的ID为curID,(maxID - minID = 500,ID 段容量),即有 500 个可供分配的 ID。当 curID 分配到 maxID 时,就将 minID, maxID 保存到数据库。然后 worker 继续分配下一个ID段中的ID。
ID Range
如果 worker 因崩溃而停止服务,再次提供生成 ID 服务时,先访问内存获取已分配的最大 ID;如果 worker 所在主机宕机,导致保存在内存中的数据清空,那么再次提供生成 ID 服务时先读取数据库中最近保存的 ID 段信息,在 maxID 加上一定的余量(如:500)。加上余量的目的是避免分配出重复的 ID,会造成一部分 ID 浪费,一般余量为 ID 段容量的倍数。
如果 ID 段容量远大于 500,那么 maxID 加上余量会浪费很多的可用 ID 资源。假设 ID 段容量为 100000,每次 worker 宕机之后至少加上 100000,使 ID 资源利用率极低。为了使worker宕机重启后能提供正常服务且 ID 资源利用率高,可以引入一个检查点(checkpoint)。当 curID % 500 == 0 时,此 ID 被认为是检查点,将 curID,minID,maxID 一起保存到数据库。curID 每成为一个检查点,便插入或更新数据。

调整架构

在原型中,worker 既担负了分配 ID 的服务,也负责管理 ID 段。可以进一步调整,分拆 worker,架构图如下:
原型3
将 worker 拆分为 worker 和 manager。worker 专职分配 ID,manager 专职管理 ID 段。拆分的好处有:

  1. 各部分独立;
  2. 方便后期扩展。

架构调整后,ID 生成的整个流程为:

  1. proxy 发出申请 ID 请求;
  2. worker 接收到请求后开始处理。如果已经 ID 段中有可用资源,则返回 ID 给 proxy,ID 为检查点时保存数据到数据库;否则,worker 向 manager 申请新的 ID 段;
  3. manager 接收到申请后,分配新的 ID 段返回给 worker,并保存 ID 段信息到数据库。

每申请一个 ID,proxy 与 worker 通信一次,而 worker 与 manager,worker 与 DB 和 manager 与 DB 只会在满足条件是进行通信,数据库的访问压力减小。
作为一种基础服务,它的可用性必须高。为了提高 ID 生成器的可用性,可以将 worker,manager 设计成分布式架构。
原型4

如上图,增加了 worker 与 manager。多个 worker 与 manager 可以部署在不同的主机上,可以避免其中一台 worker 或 manager 暂停工作而导致ID生成器无法提供服务。增加 worker 后,它的职责不变,都是从内存中读取已分配到的 ID,然后加一或者去 manager 申请新的 ID 段;而增加 manager 后,确保 ID 唯一性,则需要保证多台 manager 上分配的 ID 段不相同。这个问题最简单的办法是:有两台 manager,以 maxID / (maxID - minID) 值的奇偶性来将不同的 ID 段分配到不同的 manager 中。
这种方法抽象出来就是设置步长的问题。先假设 ID 段容量为 10000,如果按照奇偶性来解决,那么 manager1 上管理的 ID 段将是 [1,10000],[20001, 30000]…,manager2 上管理的 ID 段将是 [10001, 20000],[30001, 40000]…。manager1 上的第一个 ID 段和 manager1 上的第二个 ID 段的对应 ID 相差 20000,可以认为此时 ID 段的步长为 20000,把它们分到两台机器上,即每台机器上的 ID 段容量为 10000。
如果想要不止 2 台 manager(暂假设为 N 台),且每台 manager 上的 ID 段容量依旧为 10000,那么可以将 ID 段的步长设置为 N*10000。这样一来,manager1 上的 ID 段会是 [1, 10000],[30001, 40000]…,manager2 上的 ID 段会是 [10001, 20000],[40001, 50000]…,manager3 上的 ID 段会是 [20001, 30000],[50001, 60000]…。managerN 上的 ID 段依此类推。
添加多个 manager 之后,worker 就可能向不同的 manager 申请 ID 段。提高了 manager 的可用性,也需要有备用的 worker 来确保 worker 的高可用性。这种架构虽然可用性提高了,但还有一些缺陷:

  1. 如果 worker 一直向同一个 manager 申请 ID 段,那么 worker 返回给 proxy 的 ID 将呈现跳跃性,不利于 ID 资源的充分利用;
  2. 如果 proxy 一直将申请 ID 的请求发送至同一台 worker,那么也会导致不用 worker 间的负载不均衡。

这部分是一个自建 ID 生成器的大概方案,它还有很多可以完善的地方,比如:负载均衡,自动探测可用 worker,manager 等等。

参考

  1. Twitter-Snowflake,64位自增ID算法详解
  2. MySQL分库分表环境下全局ID生成方案
  3. 细聊分布式ID生成方法
  4. 腾讯文学内容中心id生成器的设计与实现
  5. 业务系统需要什么样的ID生成器