leaf：美团开源的分布式ID生成系统剖析

见贤思齐

说明，本文基于谢照东的《Leaf：美团点评分布式ID生成系统》，之所以有这样文章，是因为笔者发现谢照东的这篇文章和美团开源的leaf（GitHub地址：https://github.com/Meituan-Dianping/Leaf）是有一些非常重要的出入的，尤其在涉及时钟回拨等问题。所以，笔者根据美团开源的leaf源码，写下了这篇文章。为什么叫leaf？因为天底下没有两片完全一样的树叶（德国哲学家、数学家莱布尼茨：There are no two identical leaves in the world），意味着每次通过leaf获取的ID肯定是唯一的。首先，简单介绍一下如何使用leaf。配置leaf是基于springboot、以HTTP协议的方式提供获取分布式唯一ID的服务。总计有两种模式：Snowflake和Segment。我们通过它的核心配置文件leaf.properties可知：leaf.name=afei#?segment模式开关，这种模式依赖数据库leaf.segment.enable=trueleaf.jdbc.url=jdbc:mysql://localhost:3306/leafleaf.jdbc.username=afeileaf.jdbc.password=afei#?snowflake模式，这种模式依赖zookeeperleaf.snowflake.enable=trueleaf.snowflake.zk.address=127.0.0.1:2181leaf.snowflake.port=8686DML首先创建表leaf_alloc（DDL语句在GitHub首页可以找到）：CREATE?DATABASE?leafCREATE?TABLE?`leaf_alloc`?(??`id`?int(11)?NOT?NULL?AUTO_INCREMENT,??`biz_tag`?varchar(128)??NOT?NULL?DEFAULT?'',??`max_id`?bigint(20)?NOT?NULL?DEFAULT?'1',??`step`?int(11)?NOT?NULL,??`description`?varchar(256)??DEFAULT?NULL,??`update_time`?timestamp?NOT?NULL?DEFAULT?CURRENT_TIMESTAMP?ON?UPDATE?CURRENT_TIMESTAMP,??PRIMARY?KEY?(`id`),??UNIQUE?KEY?(`biz_tag`))?ENGINE=InnoDB;然后需要插入几条初始化数据，假设支付服务和账户服务需要调用leaf获取唯一ID，那么初始化数据的SQL如下：insert?into?leaf_alloc(biz_tag,?max_id,?step,?description)?values('pay',?1,?2000,?'leaf'),('account',?1,?2000,?'leaf');启动由于leaf基于springboot开发，所以启动它非常简单，运行com.sankuai.inf.leaf.server.LeafServerApplication即可。访问Snowflake和Segment两种获取唯一ID的模式的访问方式如下：#?Segment模式获取唯一IDhttp://localhost:8080/api/segment/get/payhttp://localhost:8080/api/segment/get/account#?Snowflake模式获取唯一IDhttp://localhost:8080/api/snowflake/get/payhttp://localhost:8080/api/snowflake/get/account监控leaf提供了非常简单的监控页面，能够让用户看到Segment模式下有哪些服务，以及这些服务当前获取唯一ID的位置。这个监控页面事实上就是可视化本地内存中的数据，所以一定要在leaf启动后获取过至少一次唯一ID，其对应的数据才能正常展示，否则都是0。访问地址是 http://localhost:8080/cache，访问结果如下：leaf-cache监控接下来分别对leaf提供的两种模式进行深入剖析。Segment模式前面已经提到，Segment模式依赖数据库。认识leaf的Segment模式之前，我们假设在不考虑并发能力的情况下如何通过数据库获取唯一ID：利用MySQL的自增主键，而且MyBatis可以获取每次insert的逐渐ID。这种方案的优点如下：非常简单，利用现有数据库系统的功能实现，成本小，有DBA专业维护。ID号单调自增，可以实现一些对ID有特殊要求的业务。缺点如下：强依赖DB，当DB异常时整个系统不可用，属于致命问题。配置主从复制可以尽可能的增加可用性，但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能会导致重复发号。ID发号性能瓶颈限制在单台MySQL的读写性能。Segment有“段”的意思，leaf这种模式意味着并不是每次获取唯一ID都需要操作数据库。所以，Segment模式就是在前面提到的数据库方案基础之上进行了优化：既然每次操作数据库性能有问题，那么我就每过N次才操作一次数据库。在这N次以内的访问，都只需要通过操作本地缓存获取。如此一来，性能就很高了。这个N值表示的范围就是Segment的意思。不过还是有点瑕疵，因为每过N次都要操作一次数据库。如果恰好在这个时候并发较高，那么数据库操作就会阻塞，甚至出现超时，从而形成性能毛刺甚至降低SLA。怎么办？leaf的做法是将这个步骤提前并异步化，leaf的Segment模式用一张图表示如下：leaf segment如图所示：设置step为1000（可通过DML配置）；当发号期已经分发到100的时候（即取了步长step的10%），就会触发一个异步操作去初始化下一个号段；当1～1000用尽并且分配到1100的时候，又会触发异步操作去初始化又1个号段（2001～3000），以此类推；通过这种方案设计，每次获取唯一ID都只需要操作内存即可。至于对数据库的操作，完全异步完成。一些疑问点这种方案是如何避免重启后分配重复的ID呢？我们假设已经分配到1122，这个1122又没有持久化到任何一个地方，数据库中只保存了（max_id=2001, step=1000），如果这时候leaf宕机。leaf的做法是在第一次获取唯一ID的时候，会首先更新数据库跳到下一个号段（max_id=3001, step=1000），那么这时候获取的唯一ID就是2001，至于1123～2000之前的ID全部被抛弃，不会被分配了。Segment模式有时钟回拨问题吗？很明显没有，因为通过这种模式获取的ID没有任何时间属性，所以不存在时钟回拨问题。新增服务需要多久生效？假设我们通过SQL语句插入一个订单服务，那么要过多久订单服务才能通过请求地址http://localhost:8080/api/segment/get/order向leaf获取唯一ID呢？insert?into?afei.leaf_alloc?values('order',?1,?1000,?'leaf',?now());答案是最多60s，因为leaf有一个schedule任务，间隔60s刷新本地缓存中的服务信息，假设刷新前只有[pay，account]两个服务，那么刷新后就有[pay，account，order]三个服务。核心源码如下：private?void?updateCacheFromDbAtEveryMinute()?{????ScheduledExecutorService?service?=?Executors.newSingleThreadScheduledExecutor(new?ThreadFactory()?{????????@Override????????public?Thread?newThread(Runnable?r)?{????????????Thread?t?=?new?Thread(r);????????????t.setName("check-idCache-thread");????????????t.setDaemon(true);????????????return?t;????????}????});????service.scheduleWithFixedDelay(new?Runnable()?{????????@Override????????public?void?run()?{????????????updateCacheFromDb();????????}????},?60,?60,?TimeUnit.SECONDS);}private?void?updateCacheFromDb()?{????logger.info("update?cache?from?db");????try?{????????List?dbTags?=?dao.getAllTags();????????//?这里就会更新本地缓存中的接入服务列表信息（即leaf_alloc表中的biz_tag字段）????????...????}????...}Snowflake模式leaf的Snowflake模式，顾名思义，源自于twitter的Snowflake算法，其64位构成如下，leaf的Snowflake模式与原生Snowflake模式完全一致，都是采用1+41+10+12的模式，且不可配置，除非修改源码：snowflake modeleaf的Snowflake模式核心源码在com.sankuai.inf.leaf.snowflake.SnowflakeIDGenImpl中。接下来，我们看看该模式下，获取唯一id时调用的方法get(String)的核心源码（部分省略）：//?synchronized保证线程安全问题public?synchronized?Result?get(String?key)?{????long?timestamp?=?System.currentTimeMillis();????//?如果时钟发生了回拨????if?(timestamp?