共计 3709 个字符，预计需要花费 10 分钟才能阅读完成。
Leaf 是美团基础研发平台推出的一个分布式 ID 生成服务，名字取自德国哲学家、数学家莱布尼茨的一句话：“There are no two identical leaves in the world.”Leaf 具备高可靠、低延迟、全局唯一等特点。目前已经广泛应用于美团金融、美团外卖、美团酒旅等多个部门。具体的技术细节，可参考此前美团技术博客的一篇文章：《Leaf 美团分布式 ID 生成服务》。近日，Leaf 项目已经在 Github 上开源：https://github.com/Meituan-Dianping/Leaf，希望能和更多的技术同行一起交流、共建。
Leaf 特性
Leaf 在设计之初就秉承着几点要求：
全局唯一，绝对不会出现重复的 ID，且 ID 整体趋势递增。
高可用，服务完全基于分布式架构，即使 MySQL 宕机，也能容忍一段时间的数据库不可用。
高并发低延时，在 CentOS 4C8G 的虚拟机上，远程调用 QPS 可达 5W+，TP99 在 1ms 内。
接入简单，直接通过公司 RPC 服务或者 HTTP 调用即可接入。
Leaf 诞生
Leaf 第一个版本采用了预分发的方式生成 ID，即可以在 DB 之上挂 N 个 Server，每个 Server 启动时，都会去 DB 拿固定长度的 ID List。这样就做到了完全基于分布式的架构，同时因为 ID 是由内存分发，所以也可以做到很高效。接下来是数据持久化问题，Leaf 每次去 DB 拿固定长度的 ID List，然后把最大的 ID 持久化下来，也就是并非每个 ID 都做持久化，仅仅持久化一批 ID 中最大的那一个。这个方式有点像游戏里的定期存档功能，只不过存档的是未来某个时间下发给用户的 ID，这样极大地减轻了 DB 持久化的压力。
整个服务的具体处理过程如下：
Leaf Server 1：从 DB 加载号段 [1，1000]。
Leaf Server 2：从 DB 加载号段 [1001，2000]。
Leaf Server 3：从 DB 加载号段 [2001，3000]。
用户通过 Round-robin 的方式调用 Leaf Server 的各个服务，所以某一个 Client 获取到的 ID 序列可能是：1，1001，2001，2，1002，2002…… 也可能是：1，2，1001，2001，2002，2003，3，4…… 当某个 Leaf Server 号段用完之后，下一次请求就会从 DB 中加载新的号段，这样保证了每次加载的号段是递增的。
Leaf 数据库中的号段表格式如下：
+————-+————–+——+—–+——————-+—————————–+
| Field | Type | Null | Key | Default | Extra |
+————-+————–+——+—–+——————-+—————————–+
| biz_tag | varchar(128) | NO | PRI | | |
| max_id | bigint(20) | NO | | 1 | |
| step | int(11) | NO | | NULL | |
| desc | varchar(256) | YES | | NULL | |
| update_time | timestamp | NO | | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+————-+————–+——+—–+——————-+—————————–+
Leaf Server 加载号段的 SQL 语句如下：
Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx
SELECT tag, max_id, step FROM table WHERE biz_tag=xxx
Commit
整体上，V1 版本实现比较简单，主要是为了尽快解决业务层 DB 压力的问题，而快速迭代出的一个版本。因而在生产环境中，也发现了些问题。比如：
在更新 DB 的时候会出现耗时尖刺，系统最大耗时取决于更新 DB 号段的时间。
当更新 DB 号段的时候，如果 DB 宕机或者发生主从切换，会导致一段时间的服务不可用。
Leaf 双 Buffer 优化
为了解决这两个问题，Leaf 采用了异步更新的策略，同时通过双 Buffer 的方式，保证无论何时 DB 出现问题，都能有一个 Buffer 的号段可以正常对外提供服务，只要 DB 在一个 Buffer 的下发的周期内恢复，就不会影响整个 Leaf 的可用性。
这个版本代码在线上稳定运行了半年左右，Leaf 又遇到了新的问题：
号段长度始终是固定的，假如 Leaf 本来能在 DB 不可用的情况下，维持 10 分钟正常工作，那么如果流量增加 10 倍就只能维持 1 分钟正常工作了。
号段长度设置的过长，导致缓存中的号段迟迟消耗不完，进而导致更新 DB 的新号段与前一次下发的号段 ID 跨度过大。
Leaf 动态调整 Step
假设服务 QPS 为 Q，号段长度为 L，号段更新周期为 T，那么 Q * T = L。最开始 L 长度是固定的，导致随着 Q 的增长，T 会越来越小。但是 Leaf 本质的需求是希望 T 是固定的。那么如果 L 可以和 Q 正相关的话，T 就可以趋近一个定值了。所以 Leaf 每次更新号段的时候，根据上一次更新号段的周期 T 和号段长度 step，来决定下一次的号段长度 nextStep：
T < 15min，nextStep = step * 2
15min < T < 30min，nextStep = step
T > 30min，nextStep = step / 2
至此，满足了号段消耗稳定趋于某个时间区间的需求。当然，面对瞬时流量几十、几百倍的暴增，该种方案仍不能满足可以容忍数据库在一段时间不可用、系统仍能稳定运行的需求。因为本质上来讲，Leaf 虽然在 DB 层做了些容错方案，但是号段方式的 ID 下发，最终还是需要强依赖 DB。
MySQL 高可用
在 MySQL 这一层，Leaf 目前采取了半同步的方式同步数据，通过公司 DB 中间件 Zebra 加 MHA 做的主从切换。未来追求完全的强一致，会考虑切换到 MySQL Group Replication。
现阶段由于公司数据库强一致的特性还在演进中，Leaf 采用了一个临时方案来保证机房断网场景下的数据一致性：
多机房部署数据库，每个机房一个实例，保证都是跨机房同步数据。
半同步超时时间设置到无限大，防止半同步方式退化为异步复制。
Leaf 监控
针对服务自身的监控，Leaf 提供了 Web 层的内存数据映射界面，可以实时看到所有号段的下发状态。比如每个号段双 buffer 的使用情况，当前 ID 下发到了哪个位置等信息都可以在 Web 界面上查看。
Leaf Snowflake
Snowflake，Twitter 开源的一种分布式 ID 生成算法。基于 64 位数实现，下图为 Snowflake 算法的 ID 构成图。
第 1 位置为 0。
第 2 -42 位是相对时间戳，通过当前时间戳减去一个固定的历史时间戳生成。
第 43-52 位是机器号 workerID，每个 Server 的机器 ID 不同。
第 53-64 位是自增 ID。
这样通过时间 + 机器号 + 自增 ID 的组合来实现了完全分布式的 ID 下发。
在这里，Leaf 提供了 Java 版本的实现，同时对 Zookeeper 生成机器号做了弱依赖处理，即使 Zookeeper 有问题，也不会影响服务。Leaf 在第一次从 Zookeeper 拿取 workerID 后，会在本机文件系统上缓存一个 workerID 文件。即使 ZooKeeper 出现问题，同时恰好机器也在重启，也能保证服务的正常运行。这样做到了对第三方组件的弱依赖，一定程度上提高了 SLA。
未来规划
号段加载优化：Leaf 目前重启后的第一次请求还是会同步加载 MySQL，之所以这么做而非服务初始化加载号段的原因，主要是 MySQL 中的 Leaf Key 并非一定都被这个 Leaf 服务节点所加载，如果每个 Leaf 节点都在初始化加载所有的 Leaf Key 会导致号段的大量浪费。因此，未来会在 Leaf 服务 Shutdown 时，备份这个服务节点近一天使用过的 Leaf Key 列表，这样重启后会预先从 MySQL 加载 Key List 中的号段。
单调递增：简易的方式，是只要保证同一时间、同一个 Leaf Key 都从一个 Leaf 服务节点获取 ID，即可保证递增。需要注意的问题是 Leaf 服务节点切换时，旧 Leaf 服务用过的号段需要废弃。路由逻辑，可采用主备的模型或者每个 Leaf Key 配置路由表的方式来实现。
关于开源
分布式 ID 生成的方案有很多种，Leaf 开源版本提供了两种 ID 的生成方式：
号段模式：低位趋势增长，较少的 ID 号段浪费，能够容忍 MySQL 的短时间不可用。
Snowflake 模式：完全分布式，ID 有语义。
读者可以按需选择适合自身业务场景的 ID 下发方式。希望美团的方案能给予大家一些帮助，同时也希望各位能够一起交流、共建。
Leaf 项目 Github 地址：https://github.com/Meituan-Dianping/Leaf。
如有任何疑问和问题，欢迎提交至 Github issues。
