深入理解美团 Leaf 发号器开源方案
大家好，我是树哥。
之前我们有聊过「如何设计一个分布式 ID 发号器」，其中有讲过 4 种解决方案，分别是：
UUID 类雪花算法 数据库自增主键 Redis 原子自增
美团以第 2、3 种解决方案为基础，开发出了分布式 ID 生成方案 Leaf，并将其开源。我们可以在 GitHub 上获取到该项目的源码，以及相关的文档说明，项目地址：Meituan-Dianping/Leaf: Distributed ID Generate Service。
今天我们就来学习一下 Leaf 的设计思路，看看大厂是如何设计大型中间件的，这有利于进一步提升我们自己的系统设计能力。
数据库自增主键
在「如何设计一个分布式 ID 发号器？」文章里，我们说到可以基于数据库自增主键设计发号器。但我们也提到其存在如下两个问题：
只能依赖堆机器提高性能。 当请求再次增多时，我们只能无限堆机器，这貌似是一种物理防御一样。 水平扩展困难。 当我们需要增加一台机器时，其处理过程非常麻烦。首先，我们需要先把新增的服务器部署好，设置新的步长，起始值要设置一个不可能达到的值。当把新增的服务器部署好之后，再一台台处理旧的服务器，这个过程真的非常痛苦，可以说是人肉运维了。
简单地说，就是基于数据库主键自增的方式，其发号效率受限于单台物理机器。在低 QPS 的情况下还可以支持，但在高 QPS 的时候就支持不了了。即使可以通过设计步长的方式来堆机器，但是其运维成本也非常高。
在这样的业务背景下，美团开源的 Leaf 做了进一步优化，在数据库与业务服务之间加入了中间层。之前业务系统直接去请求数据库，现在业务系统不直接请求数据库，而是去请求 Leaf 中间层，之后由 Leaf 中间层去数据库取数据。
Leaf 中间层每次去数据库获取 ID 的时候，一次性获取一批 ID 号码段，而不是只获取一个 ID。 整个服务的具体处理流程如下所示。
如上图所示，绿色的业务系统请求 Leaf 发号服务的时候，带上业务编码标记。随后 Leaf 发号服务根据业务编号类型返回下一个 ID。Leaf 发号服务每次向数据库获取 1000 个 ID，数据库往表中插入一条数据，表示这 1000 个 ID 分给了某个业务。
通过这种方式，原本业务系统获取 1000 个 ID 需要进行 1000 次数据请求，现在可能只需要 1 次就够了，极大地提高了运行效率。 此外，业务系统获取 ID 的时候都是从内存获取，不需要请求第三方，极大的提高了响应速度。
上述方式虽然解决了数据库层的压力问题，但也存在一些问题，例如：在 ID 号码段发完时，这时候需要去进行数据库请求，这次请求的耗时就会突增，系统监控上就会出现耗时尖刺。
为了解决这个问题，美团 Leaf 采用了「双 Buffer + 预加载」的策略，即在内存中维护两个 ID 段，并在上一个 ID 段使用达到 10% 的时候去预加载。这其实有点像我们 App 上加载瀑布流的预加载，思路是一样的。其设计思路如下图所示。
通过预加载的方式，Leaf 解决了尖刺的问题，并且提供了一定程度的数据库宕机高可用。 如果数据库宕机，Leaf 服务还可以提供一段时间的服务，只要其在短时间内可以恢复。
按照官方博客种的说法，这套方案再上线半年之后又遇到了问题 —— 发号 ID 段是固定的，但流量不是固定的，如果流量增加 10 倍，就会发现维持的时间很短，这样仍然有可能导致数据库压力较大。
为了解决这个问题，其采用了动态号码段的思路，即：根据上次号码段的长度及分发耗时，计算出下次应发的号码段长度。对于号码长度的计算规则如下：
T < 15min，nextStep = step * 2 15min < T < 30min，nextStep = step T > 30min，nextStep = step / 2
简单地说，如果耗时低于 15 分钟，那么下次应发的号码段长度变为原有的 2 倍。如果在 15 - 30 分钟之间，那么就保持应发号码段长度不变。如果耗时大于 30 分钟， 那么下次应发号码段长度减半。
这种设计思路，其实有点像 Hotspot 虚拟机获取锁时的自适应自旋，或许我们可以称它为：自适应长度。
即使 Leaf 做了如此多的优化，但在更恶劣的环境下，仍然可能发生系统不可以的情况，例如：
数据库主库突然宕机，短时间内无法恢复，此时系统不可用。 业务流量突增几十倍，即使有批量分发，但数据库单机无法支撑如此高的写请求。 等等
在上面这些场景下，系统仍然无法保证高可用。究其根本，这是因为 Leaf 对数据库是强依赖的，因此需要从数据库层面去做高可用保障。
按照 Leaf 官方博客的思路，Leaf 目前使用了半同步的方式同步数据，并且实现了主从切换。 这就解决了主库宕机的问题，进一步提升了高可用程度。
MySQL 半同步有点类似于 Kafka 的副本同步，需要有一个 slave 收到 binlog 之后，才能提交事务，从而保证了一定程度上的一致性，降低了号码段重发的风险。
但由于半同步方式，并无法保证数据强一致性，因此极端情况下还是可能会有号码段重发的风险，只是较低罢了。如果需要保证完全的强一致性，那么需要考虑使用 MySQL 的 Group Replication 特性。但由于美团内部的数据库强一致性特性还在迭代中，因此 Leaf 也未实现数据强一致性。
类雪花算法
在「如何设计一个分布式 ID 发号器？」文章里，我们说到雪花算法是一个非常好的分布式 ID 生成算法。但其存在一个缺陷 —— 存在时钟回拨的问题。美团开源的 Leaf 也实现了基于雪花算法的分布式 ID 生成功能，并且解决了时钟回拨的问题。
美团 Leaf 引入了 zookeeper 来解决时钟回拨问题，其大致思路为：每个 Leaf 运行时定时向 zk 上报时间戳。每次 Leaf 服务启动时，先校验本机时间与上次发 ID 的时间，再校验与 zk 上所有节点的平均时间戳。如果任何一个阶段有异常，那么就启动失败报警。
这个解决方案还是比较好理解的，就是对比上次发 ID 的时间，还有其他机器的平均时间。除了时间回拨的问题，当机器数量变多的时候，雪花算法中的 workerId 也不是很好维护。
因此，Leaf 也用 zookeeper 作为中间件，以每个服务器的 IP + Port 作为 key 去注册一个节点，获取一个 int 类型的节点作为 workerId。
总结
美团开源的 Leaf 提供了两种 ID 生成方式：
号码段模式。 基于数据库自增组件，ID 从低位趋势增长，能够忍受 MySQL 短时间不可用。 类雪花算法模式。 基于雪花算法，解决了时间回拨以及海量机器的 workId 维护问题。
对于号码段模式而言，其在传统的自增 ID 基础上，增加了 Proxy 模式，提出号码段模式。接着，又采用「双 Buffer + 预加载」的方式解决尖刺的问题。再之，为了解决流量暴增的问题，采用了自适应号码段长度的优化思路。后，在数据库高可用上，使用 MySQL 半同步复制 + 主从切换，从一定程度上保障了高可用。
对于类雪花算法模式而言，其引入了 zookeeper 作为海量机器的 workerId 生成方法。其次，还通过「本地存储时间戳 + 定时上报时间戳」的方式，解决了时间戳的问题。
好了，这就是今天分享的全部内容了。
如果你喜欢今天的分享，记得一键三连支持我！你的鼓励，是我写文章大的动力！
参考资料
Meituan-Dianping/Leaf: Distributed ID Generate Service
Leaf：美团分布式 ID 生成服务开源 - 美团技术团队
Leaf—— 美团点评分布式 ID 生成系统 - 美团技术团队
美团分布式 ID 生成框架 Leaf 源码分析及优化改进 - SegmentFault 思否
Leaf：美团的分布式 ID 方案深入剖析 - 简书
UidGenerator：百度开源的分布式 ID 服务（解决了时钟回拨问题）
相关文章