分布式环境下全局唯一发号器的设计

思路：

---

UUID ~ 独立（水平扩展 ~ 预缓存）~ 内置
自增 ID ~ 独立（分段 ~ 等步长 ~ 号段 ~ 混合）~ 内置（雪花）

时间回拨问题 ~ 多时钟 ~ 历史时间 ~ 定时校验 ~ 错误重试
机器 ID 问题

1.1. 基本实现

全局唯一可以有两种实现方式：UUID 或者自增 ID

1. UUID 只需要使用 UUID 的生成算法就能实现了

   UUID 没有自增的概念，适合于只要求 ID 唯一的情景。
   可以是独立的发号器发放 ID，也能内置到各个节点各自发放 ID

   1. 独立式需要考虑性能问题，由于每个 ID 的获取之间没有联系，是无状态的，所以这个发号器可以进行水平扩展来提升性能。但如果使用的 UUID 版本是基于时间戳的，还要求各个发号器之间统一好时钟。

      如果水平扩展成本太高或者还达不到要求，可以选择预先缓存一批 UUID，请求的时候直接返回即可

   2. 将 ID 发放分摊到各个结点，就不需要一个固定的发号器了，每个结点自己获取即可。同样如果是基 UUID 版本是基于时间戳的，也要统一好时钟。

   UUID 的优缺点：

   优点：
   ① 性能高，可以不需要网络传输直接在本地生成

   缺点：
   ① 长字符串不易存储占空间，作为主键导致索引树太大
   ② 如果采用 B+ 树存储会导致频繁的树形调整，效率低下
   ③ 信息不安全，如果是基于 MAC 地址生成的话可能导致 MAC 地址泄露
   

2. 自增 ID 的实现也可以分为独立或者内置的

   1. 独立的发号器可以使用 Redis 或者数据库实现

      Redis 就是采用 incrby，实现每次访问 Redis 令其值自增即可
      MySQL 则是利用自增 ID 实现

      单一的发号器可能会导致高并发下竞争激烈
      可以采用：分段 ID、等步长 ID或者号段 ID 来解决

      1. 分段 ID 的实现方式是，部署 N 个发号器，每个发号器维护一个范围内的 ID 的发放，使得多个请求可以均摊到不同的发号器上，减少竞争。

         缺点：
         ① 只能保证全局 ID 唯一，不能保证全局自增
         ② 每个发号器维护的范围难以确定，如果有最大值且设置为等范围，那么在进行水平扩展时，后加入的服务器需要与前一个服务器划分范围，不均匀

         ① 如果系统整体对自增没有要求的话，可以使用。
         ② 如果只是每个请求方对 ID 的自增有要求，那么也可以使用。只要做到每一个请求方只去访问特定的一个变量获取值，就一定是自增的但不一定连续，适合于对连续没有要求的业务。这个功能可以使用一致性哈希算法来实现，具体可以使用哈希环或者哈希槽。

      2. 等步长 ID 的实现方式是，部署 N 个发号器，起始值分别是 1~N，每一次 ID 值的自增都是 N，这样多个发号器的 ID 就不会冲突了

         缺点：
         ① 水平扩展比较困难，一旦 N 值确定后，再增加机器就非常困难了。如果采用这种方法，需要在一开始设置初始值的时候，预留一定的空位供以后扩展使用，如每个初始值都相差很大，但这样也会退化成分段 ID 的情况而且更加复杂
         ② ID 同样不是全局自增的，只是局部自增。可以通过一致性哈希保证每个请求方获取的 ID 是自增的

      3. 号段 ID 的实现方式是，每个请求获取 ID 时，不只取 1 个 ID 而是取 N 个

         号段 ID 有两种实现方式，发号器计算所有的 ID 返回，或者只返回起始值让请求方自己自增 N 次获取接下来的 ID

         第二种方式效率会高一些，但需要每个请求方都知道发号器的自增规则，如是自增 1 还是自增 N

         优点：
         ① 具备 ID 号缓存，即使发号器宕机，业务在短时间内也能使用已缓存的 ID 正常提供服务
         

         缺点：
         ① 这种方法同样不能做到全局自增，只是对于每个请求方来说是自增的

      4. 还可以将两种方法合起来用，分段 + 号段 或者 等步长 + 号段，能确保 ID 全局唯一且每个请求方的 ID 自增

   2. 可以使用雪花算法实现，不需要专门的节点做发号器

      雪花算法使用时间戳、机器ID、序列号组成，同时灵活度也是最高的，可以将某些特定的位改成业务相关的值，这样通过 ID 还可以获取到额外的信息

      但是雪花算法非常依赖机器时钟，需要各机器做好发生时间回拨时的处理，否则可能出现 ID 回拨或重复的情况，可能导致服务不可用

      雪花算法 / 基于雪花算法 的优缺点：

      优点：
      ① 可以本地生成，没有网络开销
      ② 可以根据业务分配 ID 的各个位，灵活

      缺点：
      ① 非常依赖机器时钟

1.2. 时间回拨问题解决

在解决闰秒问题、手动调整时间和各节点时间同步的时候，就可能会出现时间回拨。由于雪花算法的时间是处在高位的，一旦时间回拨就很可能导致 ID 倒退甚至出现重复的问题

解决的思路大致分为两种：检测 + 回避或者解决
一般优先采用回避的方法，知道无法回避才真正去进行解决

1. 检测方法：本地/zk等保存上一次的时间

   每隔一段时间去检查已保存的时间，如果当前时间比保存的时间更靠后，则说明没问题更新这个时间，否则判断为出现时间回拨，需要进行回避或者解决

2. 回避 1：使用时钟 ID，多时钟的方法

   具体的做法是，选出 ID 中某些为作为时间 ID 位，一旦时间发生回拨，就将时间 ID 自增 1，这样即时时间回拨了，由于时间 ID 自增了 1，也依旧能保证 ID 是递增的

   极端情况下，如果机器重启和时间回拨同时发生，可以选择将时钟 ID 保存到磁盘中，在每次发号器重启时时钟 ID 都自增 1，即不使用重启之前的时钟了

   高并发情况下，如果当前时钟的序号已经全部用完，可以将时钟 ID 自增 1 切换到下一个时钟，继续生成

   优点：实现简单，由于时间回拨不会频繁出现，所以预留 2~3 个时钟 ID 位就足够使用很久了。即使所有时钟 ID 位用完，也能退化为时间同步然后重新使用时钟 ID

   缺点：
   ① 序列位被时钟 ID 位占用了，如果一直没有发生回拨，就相当于能生成的序列个数变成了原来的 2^-N

3. 回避 2：使用历史时间

   具体的做法是，不再使用系统真实的时间，而是只使用一个初始的时间，等到这个时间的序号全部发放完毕，才将时间戳自增 1

   不同机器的历史时间可能有差异，也会导致时间回退问题？不太理解

   

4. 解决 1：同步等待时间

   这种方法在时间回拨时，不进行 ID 生成，而是等到回拨的时间全部花完，或者和其他机器同步的时间大于已经记录的时间，才继续发放 ID

   适用于时间回拨比较小的，否则将导致长实践的服务不可用

5. 保底：直接抛出异常

   当时间回拨处理成本太大时，可以采用直接抛出异常，让请求方到别的发号器进行请求