大厂分布式ID方案之美团Leaf

出来看星星吗？不看星星出来也行。 / 2024-08-30 / 原文

分布式ID必须保证以下特性：

全局唯一
有序性：便于索引
高并发可用
不依赖中心认证
安全性

目前大厂的分布式ID方案基本都是基于号段式，号段模式可以理解成从数据库批量获取 ID，然后将 ID 缓存在本地，以此来提高业务获取 ID 的效率。例如，每次从数据库获取 ID 时，获取一个号段，如(1,1000]，这个范围表示 1000 个 ID，业务应用在请求获取 ID 时，只需要在本地从 1 开始自增并返回，而不用每次去请求数据库，一直到本地自增到 1000 时，才去数据库重新获取新的号段，后续流程循环往复。

美团-Leaf-基于数据库自增ID的优化

Leaf-V1.0

在DB之上挂N个Server，每个Server启动时，都会去DB拿固定长度的ID List。这样就做到了完全基于分布式的架构，同时因为ID是由内存分发，所以也可以做到很高效。接下来是数据持久化问题，Leaf每次去DB拿固定长度的ID List，然后把最大的ID持久化下来，也就是并非每个ID都做持久化，仅仅持久化一批ID中最大的那一个。

上线之后发现的问题：

耗时尖刺，发现系统最大耗时取决于更新号段的时间，造成性能波动
更新号段时DB宕机造成整个服务不可用
可以估计发号数量，估计订单数量，数据细腻系泄漏

Leaf-V2.0-异步更新双Buffer

整体思路其实就是不等消费完毕就去更新号段，预更新的思路。使用缓存解决了耗时尖刺和DB宕机的问题，DB宕机时也预留了一段的重启时间。

每个biz-tag都有消费速度监控，通常推荐segment长度设置为服务高峰期发号QPS的600倍（10分钟），这样即使DB宕机，Leaf仍能持续发号10-20分钟不受影响。
每次请求来临时都会判断下个号段的状态，从而更新此号段，所以偶尔的网络抖动不会影响下个号段的更新。

上线之后发现的问题：号段长度Step不好控制，短了流量激增频繁获取，长了ID跨度很大。

号段长度始终是固定的，假如Leaf本来能在DB不可用的情况下，维持10分钟正常工作，那么如果流量增加10倍就只能维持1分钟正常工作了。
号段长度设置的过长，导致缓存中的号段迟迟消耗不完，进而导致更新DB的新号段与前一次下发的号段ID跨度过大。

Leaf-V2.5-动态调整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。Leaf采用一主二从半同步复制的方案，在极端情况下会超时退化成异步复制，造成ID重复。但是概率非常小

异步复制：性能最高，延迟最低，但数据一致性较弱，适合对延迟敏感且容忍一定数据不一致的场景。
半同步复制：在性能和一致性之间取得平衡，适合希望提高数据安全性但又不能承受完全同步带来的性能损失的场景。
同步复制：提供最强的数据一致性，但对性能有较大影响，通常只在对数据一致性要求极高的情况下使用，但在 MySQL 中不常用。

Leaf-snowflake方案

在之前版本中，可以通过在0点下单和24点下单的ID号推算出美团一天的订单量，这是不能忍受的，于是每天结合雪花算法做出了Leaf-snowflake方案。

Leaf-snowflake方案完全沿用snowflake方案的bit位设计，即是“1+41+10+12”的方式组装ID号。对于workerID的分配，当服务集群数量较小的情况下，完全可以手动配置。Leaf服务规模较大，动手配置成本太高。所以使用Zookeeper持久顺序节点的特性自动对snowflake节点配置wokerID。

也就是说：美团的Leaf-snowflake方案在雪花算法的基础上使用zookeeper解决了自动配置workerID的问题，同时在本地缓存workerID，使之成为弱依赖zookeeper。

在时钟回拨问题上，Leaf-snowflake会上报当前生成ID的最大时间戳到zookeeper（间隔周期3秒），上报时，如果发现当前时间戳少于最后一次上报的时间戳，那么会放弃上报。之所以这么做的原因是，防止在leaf实例重启过程中，由于时钟回拨导致可能产生重复ID的问题。本质就是用zookeeper判断是否发生时钟回拨，所以运行期间还是依赖zookeeper的，zookeeper可以短时间宕机，但是长时间宕机会导致时钟回拨问题无法检测。

Leaf并不是全局有序，因为是并发获取，只是单节点有序。

时钟回拨解决的代码：

    //发生了回拨，此刻时间小于上次发号时间
    if (timestamp < lastTimestamp) {
    long offset = lastTimestamp - timestamp;
    if (offset &lt;= 5) {
        try {
            //时间偏差大小小于5ms，则等待两倍时间
            wait(offset &lt;&lt; 1);//wait
            timestamp = timeGen();
            if (timestamp &lt; lastTimestamp) {
               //还是小于，抛异常并上报
                throwClockBackwardsEx(timestamp);
              }    
        } catch (InterruptedException e) {  
           throw  e;
        }
    } else {
        //throw
        throwClockBackwardsEx(timestamp);
    }
}
//分配ID</code></pre>