美团点评开源分布式ID方案：Leaf

引出建议读者先阅读我的另一篇文章作为前提条件分布式ID的演进Leaf是美团点评公司基础研发公司提出的一个唯一ID生成器服务具有高可靠性、低延迟、全局唯一等特点Leaf根据不同业务的需求分别实现了Leaf-segment 和 Leaf-snowflake两种方案前者基于数据库的自增主键后者基于Snowflake算法。接下来分别介绍两种方案的技术原理一、Leaf-segment方案二、Leaf-snowflake方案一、Leaf-segment方案Leaf-segment方案与批量缓存架构方案类似不同业务方的唯一ID需求用biz_tag字段区分每个biz-tag的ID相互隔离。当某业务请求携带biz_tag访问Leaf服务时数据库会通过执行如下语句生成唯一IDBEGINUPDATEtableSETmax_idmax_idstepWHEREbiz_tagxxxSELECTtag,max_id,stepFROMtableWHEREbiz_tagxxxCOMMIT重要字段说明biz_tag用来区分业务max_id表示该biz_tag目前所被分配的ID号段的最大值step表示每次分配的号段长度。然后将生成的ID缓存到本地缓存这样获取ID就不用每次都写数据库现在只需要把step设置得足够大比如1000。那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从1减小到了1/step大致架构如下图所示优点因为是趋势递增所以唯一ID生成服务可以有多个Leaf服务具有高可扩展性数据库可以根据业务来分库分表提升性能数据库有对应的本地缓存访问数据库的次数减少可以灵活地修改不同业务方的step当请求量大时step就设置大一点缺点ID号码不够随机能够泄露发号数量的信息不太安全容灾性低当数据库宕机时倘若正好某个Leaf的ID用完了需要更新会造成阻塞高依赖数据库可用性对缺点的解决二级缓存解决缺点2上述说的本地缓存即第一级缓存第二级缓存就是为了让在数据库宕机的情况下Leaf服务能提供更长时间的服务两级缓存比一级缓存的数据量更大具体做法是当第一级缓存的数据已经用了10%时就用一个线程异步更新下一个缓存这样即使ID在请求到200时数据库宕机Leaf服务仍然还能提供200-2000缺点3采用一主两从的方式同时分机房部署Master和Slave之间采用半同步方式同步数据。同时使用美团公司Atlas数据库中间件已开源改名为DBProxy做主从切换。当然这种方案在一些情况会退化成异步模式甚至在非常极端情况下仍然会造成数据不一致的情况但是出现的概率非常小如果你的系统要保证100%的数据强一致可以选择使用“类Paxos算法”实现的强一致MySQL方案如MySQL Group Replication。但是运维成本和精力都会相应的增加根据实际情况选型即可对于缺点1是不可避免的若对此缺点敏感则使用Leaf-snowflake方案二、Leaf-snowflake方案基于雪花算法我们只需要考虑服务ID和时钟回拨问题使用zookeeper和其leaf-forever来解决服务ID的问题当一个Leaf-snowflake服务启动时可能是第一次启动也可能是重启首先根据IP和端口号去Zookeeper的持久节点中找如果有则直接拿对应的服务ID如果没有则以IP端口号递增的数字作为持久节点同时为了防止zookeeper宕机时Leaf服务此时又重启造成的找不到服务ID问题Leaf服务在获得到 worker ID 后会将其缓存在本地文件使用zookeeper和leaf-forever和leaf-temporary来解决时钟回拨问题首先说明leaf-forever和leaf-temporary中的节点是啥leaf-forever中 - IP端口号递增的数字 当前服务的雪花算法中的时间戳会不断修改leaf-temporary中 - 所有服务的雪花算法中的时间戳不会修改下面我们来走一遍流程当Leaf服务第一次启动Leaf服务启动在leaf-forever中注册并写入此时的时间戳拿到leaf-temporary中的所有信息然后计算出一个平均时间值表示Leaf服务集群的系统时间若该Leaf服务的时间值与 平均值 的差值小于某个阈值则返回leaf-forever中的服务ID否则失败写入该Leaf的时间到 leaf-temporary每隔3s更新leaf-forever该Leaf的时间当Leaf服务重启Leaf服务重启找到对应的leaf-forever取出时间戳若自身的系统时间比取出的该时间戳小则认为发生了时钟回拨重启失败拿到leaf-temporary中的所有信息然后计算出一个平均时间值表示Leaf服务集群的系统时间若该Leaf服务的时间值与 平均值 的差值小于某个阈值则返回leaf-forever中的服务ID否则失败写入该Leaf的时间到 leaf-temporary每隔3s更新leaf-forever该Leaf的时间另外此方案建议关闭NTP时钟同步功能