唯一 ID 的组成

每个唯一 ID 由三部分组成：

• 时间戳

• 自增 ID

• 段 ID

即其结构如下所示：

+-------------------------+
| 时间戳 | 自增 ID | 段 ID |
+-------------------------+

唯一 ID 具有如下特性：

• 唯一 ID 的整体趋势是递增的
• 可以从其中提取出时间戳，进而可以估算出与唯一 ID 相关联的资源的创建时间

时间戳

这里的时间戳不是相对于 epoch（纪元，即 1970-01-01 00:00:00） 的时间戳，而是相对于某个自定义时刻的，比如系统正式上线的那刻。

这样做的好处是可以使用更少的空间表示更长的时间。假如当前时刻的时间戳是 1600848185，并且用 32 个 bit 保存时间戳，那么：

• 当使用相对于纪元的时间戳时，系统最长支持到 2³² - 1600848185 秒前
• 当使用相对于当前时刻的时间戳时，系统最长支持到 2³² 秒前

需要注意：

• 如果想要获得 ID 是何时分配的，只需要把从 ID 中提取出的时间戳加上自定义的时刻即可
• 用多少个 bit 保存时间戳决定了系统的生命周期

可将这个自定义的时刻称为系统的纪元。

自增 ID 和段 ID

对于每个 ID 分配服务而言，其每秒可以分配多个具有相同时间戳的 ID，这些 ID 之间通过自增 ID 和 段 ID 加以区分。

段 ID 由两部分组成：

• 段标识（一个自增的非负整数）
• 段服务 ID

整体架构

NOTE：

架构设计的目标是无状态、share nothing、易于水平扩展

唯一 ID 由分配服务分配；段 ID 由段服务分配。

1，段服务说明：

如果系统使用 N 个 bit 保存段服务 ID，那么最多可以部署 2^N 个段服务。每个段服务拥有唯一的段服务 ID，段 ID 中包含段服务 ID，这样做是为了保证不同的段服务分配的段 ID 不同。段服务之间互相独立，无法感知彼此的存在。当某个段服务不可用时，段服务的使用方可以去其它段服务上尝试获取段 ID。

每个段服务需要持久化已经分配出去的最大段标识，以便重启时，在原来的基础上继续分配，从而避免重复。但是如果每分配一个段标识持久化一次，会使系统性能下降。因此段服务启动时，先在持久化存储中给最大段标识 max_seg 增加一个步长 STEP，然后分配区间 (max_seg, max_seg + STEP] 里的段标识，在这个区间内的段标识被消费完成之前无需进行持久化操作，当该区间内的段标识被消费完时，按照前面的流程，获取新的段标识区间。

获取和持久化 max_seg 的伪代码如下：

-- 开启事务

select max_seg from tb_allocated_seg where svr_id = <段服务 ID> for update;
update tb_allocated_seg set max_seg = max_seg + <STEP> where svr_id = <段服务 ID>;

-- 提交事务

重启服务会导致区间内尚未被分配出去的段标识“丢失”，因此为了避免浪费，需要设置合适的步长。

2，分配服务说明：

分配服务启动时，需要先从段服务申请段 ID，为了减少与段服务的交互，可以预申请多个段 ID，然后缓存在内存中。分配服务生成唯一 ID 的策略是：

• 获取当前时间戳
• 查询在当前时间戳内已经分配出去的 ID 数量
  • 如果已分配出去的 ID 数量达到了自增 ID 的上限，则将当前的段 ID 丢弃，切换到新的段 ID，并将自增 ID 置为0
  • 切换到新的段 ID 时，如果本地没有缓存的段 ID，需要请求段服务
  • 否则，将自增 ID 增加 1
• 利用时间戳、自增 ID、段 ID 生成唯一 ID，并进行编码（将一个长整数编码成类似 base64 的字符串）

每个段服务可以是单点的，也可以是主从的，分配服务可以通过注册中心、域名解析等方式查找段服务的地址。

如何解决时钟回退的问题

如果分配服务运行过程中，时钟发生了回滚，可能导致唯一 ID 重复。解决方式是：设置游标 last_cur，它表示分配服务最后一次分配 ID 的时刻。分配服务每次获取时间戳（记为 ts）时，将其与 last_cur 比较：

• 如果 ts 等于 last_cur 说明分配服务在 1 秒内收到了多个分配请求，属于正常现象
• 如果 ts 大于 last_cur 说明当前请求的时间与上次请求的时间不在同一秒内，属于正常现象，同时需要将 last_cur 设置为 ts
• 如果 ts 小于 last_cur 说明时钟发生了回退，一个解决方案是：
  • 查询在 last_cur 时已经分配出去的 ID 数量
    • 如果已分配出去的 ID 数量达到了自增 ID 的上限，则将 last_cur 增加 1，并将 last_cur 当作时间戳，将自增 ID 置为 0
    • 否则，将自增 ID 增加 1
  • 利用时间戳、自增 ID、段 ID 生成唯一 ID，并进行编码

使用上面的解决方案时，last_cur 会被请求“推着”前进，当时钟恢复时，last_cur 可能大于真实时间，但是随着请求低谷的到来，last_cur 的前进速度将小于时间的前进速度，最终时间会追上 last_cur，last_cur 将等于真实的时间。

需要注意的是：last_cur 无需持久化，因为分配服务每次启动时，会使用新的、未被使用过的段 ID，所以哪怕时钟发生回滚，也不会产生重复的 ID。