分布式环境下的核心挑战：

  • 多节点间同时请求获取的 ID，不可重复；
  • 唯一 ID 生成器需要承载极高的并发量，而不会影响 生成ID 的速度，并且需要保证服务的高可用性；
  • 可能需要递增且不连续的 ID，递增是为了顺序性（如使用 b+Tree 作为存储索引结构时，避免随机读写造成性能下降，LSM 没有这个问题），不连续是为了安全性，避免被预测 ID；
  • 如果使用时间戳作为 唯一ID 生成的基础，需要解决不同节点间时钟不一致的问题；

UUID

  本地生成，8个16进制数 + 一个连字符 + 4个16进制数 + 一个连字符 + 4个16进制数 + 1个连字符 + 12个16进制数；

优点：

  • 本地生成，性能高；

缺点：

  • 太长；
  • 无序性，如在 mysql 写入场景下，追加写（如原本的自增主键）变成随机的 io，性能大幅下降；

Snowflake

  按照最高位锁0（防负）+ 时间 + 机器码 + 递增序列号，可保证任何机器生成的 id 均唯一；

优点：

  • 递增趋势；
  • 仅依赖于时钟； 缺点：
  • 因为强依赖于时钟，但是服务器的时钟可能会发生飘逸（包括人工误操作，即 clock drift，可考虑使用 NTP 服务平滑调整时钟）（也许可以考虑逻辑时钟如 lamport？但它在高并发环境下重复问题，需要引入全序关系广播类策略解决，也麻烦）

Leaf

1、Leaf-segment；

  基于数据库，通过 biz 区分业务场景，max_id 为当前的发号上限，做了一个优化：快到上限值时，会起异步线程提前更新上限值（降低 TP999），后面设计个人目前看下来类似于 seqsvr，不赘述了（见下文 seqsvr 分析）；

2、Leaf-snowflake：

  看下来，核心是两步：1、使用一个分布式的 KV 存储保持各服务的时钟（心跳维护）；2、服务会通过 KV 的时钟和当前时钟进行对比，防止出现大步长回拨，新服务启动时，也会和 KV 中所有时钟对比，防止多个节点的时钟偏差过大；

seqsvr

策略设计

  唯一 ID 视为一个序列号，是唯一和递增的 int64，且每个用户都有自己独立的 64位 ID 的空间；

  即每个用户都独占 8bytes 空间，空间内存放已经分配出去的最后一个 序列号 K；

  最简单的方法就是，用户申请一个序列号 K+1，服务持久化并返回；

  但很明显在高并发场景下不可能做到如此频繁的持久化，第一个服务的优化策略：

  1. 非连续递增的序列号持久化：
  2.   业务场景并不会要求 ID 严格递增，只需要保持递增趋势，用于分辨 ID 顺序即可；

初始化状态：当前最后一个被分配的 ID：K，递增上限步长：N，分配 ID 的上限值：M=K+N；

核心逻辑：用户请求 ID 时，执行 K+1，并将其与上限值对比，如果大于，则需要持久化上限值到磁盘，并执行 M += N，再返回当前 ID：K+1；

  由此可见，当 ID 生成器服务宕机时，此时磁盘中存储的上限值，一定大于当前最后一个被分配的 ID，将其赋值到 K 中，重新初始化，依然能保证 ID 唯一性、递增性；

  总结：抽象点就是 聚合一批数据，一次持久化，本处聚合的数据集 就是在一个 N 中，被分配出去的多个不同时刻的 K；

  解决了用户请求的并发问题（频繁磁盘IO），新问题接踵而至，单用户使用 8 字节的空间，所有用户总占用的空间也相当庞大，故障恢复的时间会被拖长，故第二个服务优化策略：

  1. 分 Section 合并持久化：

  再次聚合 上限值，相邻 uid 组成一个 section，共用一个 上限值；（唯一缺点貌似是一个 section 中有一个用户发送消息的频繁远高于其他用户，导致一个累积，只要发生一次宕机，那么其他用户的 ID 值会暴涨）

  优点显而易见，合并多少 uid 到一个 section 中，就能减少多少次磁盘 IO；

工程设计

设计原则：保持自身架构简单、避免对外部服务的强依赖；

  1. 分为存储层和缓存中间层，StoreSvr 为存储层 通过 NRW 保证数据持久化后不丢失、AllocSvr（分布式） 负责一组 section 的序列号分配；
  2. 整个发号器根据 uid 进行分组，每个组有单独的 StoreSvr 和 AllocSvr，主要为了限制故障的范围；

（这里为个人思考，可能有误区，原文的图5感觉有点问题，既然是同一个 uid 的序列号，不同 AllocSvr 上最后一个被分配的序列号也不应该会相差到 一个上限步长，否则正常分配序列号肯定会重复，最新的上限值会被持久化，问题应该是：不同 AllocSvr 本地缓存的 序列号可能会有冲突，因为同步序列号明显不适合，解决方案为加分布式锁等，但也明显性能下降，所以此处的设计应该是 AllocSvr 的管理 uid 的集合不应该有交集）

  1. AllocSvr 明显存在单点故障的问题，故引入一个仲裁服务，负责 AllockSvr 的探活，故障转移通过 仲裁服务更新 故障范围内 section 的 迁移位置 到 Store 并将其持久化，AllocSvr 会定期访问 StoreSvr 获取最新的配置信息；
  2. 为防止多个 AllocSvr 操作 序列号，引入租约概念，当一个 AllocSvr 与 StoreSvr 发生网络分区时，无法进行续约，当前 AllocSvr 将会在剩余有效期内停止服务，被分配到当前 section 的 AllocSvr 则会在更新配置信息后一个完整租期后才开始提供服务；
    1. 隐藏条件：
      1. 所有 AllocSvr 从 StoreSvr 同步配置信息的时间必须尽可能相等，或者说租约的有效期必须远长于 StoreSvr 的同步周期；
      2. 还需要避免 AllocSvr 和 仲裁服务 在同一网络分区内，否则当发生网络分区时，仲裁服务也无法更新 StoreSvr 的配置信息；也不能出现：AllocSvr 与 StoreSvr 断链，但是没有和仲裁服务断链的情况；

多机 NRW 策略：Non-delay Right-shift、Weighted，用于多机调度问题的优化策略；

  • 无延迟调度：即所有节点均等分配任务，即每个节点的权重值相同（非异构机器）；
  • 右移调整：为减少任务间冲突、平衡负载，向右移动任务的开始时间优化调度计划；
  • 加权优化：对任务加权；
容灾策略

  个人感觉没什么特别值得聊的，原文提到的嵌入式路由表本质上就是在请求和响应的过程中 实时更新路由表，即更新 uid 对应的 AllocSvr 的地址（他这里只讨论数据迁移后如何寻找的问题）；

  至于区分路由表的新旧，也是常规版本号可以轻易解决；

参考资料

微信序列号生成器架构设计及演变 Leaf——美团点评分布式ID生成系统