Leaf 美团点评分布式ID生成系统

背景

分布式ID的要求

• 全局维一性
• 趋势递增
• 单调递增
• 信息安全

分布式系统的要求

• 平均延迟和TP9999延迟都要尽可能低
• 可用性5个9
• 高QPS

常见方法

UUID

uuid的标准型包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字段，示例：550e8400-e29b-41d4-a716-446655440000
缺点

• 不易存储
• 信息不安全，基于mac地址生成可能会造成mac地址泄露
• 在DB主键的场景下，超级不适用

类snowflake算法

一种以划分命令空间来生成ID的一种算法，把64-bit分别划分成多段，分别来标志机器、时间等

41-bit的时间可以表明69年的时间，10-bit机器可以分别表明1024台机器
优势

• 毫秒数在高位，自增序列在低位，整个ID是趋势递增的
• 不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能超级高
• 可以根据自身业务特性分配bit位，超级灵活
  缺点
• 强依赖机器时钟，如果机器上回拨时钟，会导致拨号重复或者服务会处于不可用的状态

Leaf 发布干方案实现

There are not two identical leaves in the world
“世界上没有两片一样的树叶”

综合比对上诉几种方案，在上述第二种和第三种方案上做了相应的优化，实现了Leaf-segment和Leaf-snowflake方案

Leaf-segment数据库方案

• 原方案每次获取ID都是读写一次数据库，造成数据库压力大，改为利用proxy server批量获取，每次获取一个segment号段的值，用完之后再去数据库获取，大大减轻数据库压力
• 各个业务的不同发号需求用biz_tag字段来区分，每个biz_tag的ID获取相互隔离，互不影响。如果后来性能需要对数据库扩容，只需要对biz_tag分区分表

Leaf-snowflake方案

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

• 先检查自己是否写过zk的leaf_forever节点
• 有写过，则比较自身系统时间与leaf_forever/${self}的系统时间，如果小于则认为系统做了大步长回拨，服务启动失败并告警
• 如果没有写过，则新增一个持久化节点，并上报自身的系统时间，综合比对其余节点的系统时间来判断自身系统时间的准确性，获取leaf_temporary下所有临时节点的ip:port，通过RPC来获取每个节点系统时间，并计算sum(time)/nodesize
• 如果计算结果<阈值，则认为当前系统时间准确，系统启动正常，同事写临时节点leaf_temporary/${self}持续租约
• 否则则认为本机系统发生大步长时间回拨，启动失败并告警
• 每隔一段时间(3s)上报自身系统时间到leaf_forever/${self}