Leaf:美团分布式ID生成服务开源

Stella981
• 阅读 677

Leaf是美团基础研发平台推出的一个分布式ID生成服务,名字取自德国哲学家、数学家莱布尼茨的一句话:“There are no two identical leaves in the world.”Leaf具备高可靠、低延迟、全局唯一等特点。目前已经广泛应用于美团金融、美团外卖、美团酒旅等多个部门。具体的技术细节,可参考此前美团技术博客的一篇文章:《Leaf美团分布式ID生成服务》。近日,Leaf项目已经在Github上开源:https://github.com/Meituan-Dianping/Leaf,希望能和更多的技术同行一起交流、共建。

Leaf特性

Leaf在设计之初就秉承着几点要求:

  1. 全局唯一,绝对不会出现重复的ID,且ID整体趋势递增。
  2. 高可用,服务完全基于分布式架构,即使MySQL宕机,也能容忍一段时间的数据库不可用。
  3. 高并发低延时,在CentOS 4C8G的虚拟机上,远程调用QPS可达5W+,TP99在1ms内。
  4. 接入简单,直接通过公司RPC服务或者HTTP调用即可接入。

Leaf诞生

Leaf第一个版本采用了预分发的方式生成ID,即可以在DB之上挂N个Server,每个Server启动时,都会去DB拿固定长度的ID List。这样就做到了完全基于分布式的架构,同时因为ID是由内存分发,所以也可以做到很高效。接下来是数据持久化问题,Leaf每次去DB拿固定长度的ID List,然后把最大的ID持久化下来,也就是并非每个ID都做持久化,仅仅持久化一批ID中最大的那一个。这个方式有点像游戏里的定期存档功能,只不过存档的是未来某个时间下发给用户的ID,这样极大地减轻了DB持久化的压力。

整个服务的具体处理过程如下:

Leaf:美团分布式ID生成服务开源

  • 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压力的问题,而快速迭代出的一个版本。因而在生产环境中,也发现了些问题。比如:

  1. 在更新DB的时候会出现耗时尖刺,系统最大耗时取决于更新DB号段的时间。
  2. 当更新DB号段的时候,如果DB宕机或者发生主从切换,会导致一段时间的服务不可用。

Leaf双Buffer优化

为了解决这两个问题,Leaf采用了异步更新的策略,同时通过双Buffer的方式,保证无论何时DB出现问题,都能有一个Buffer的号段可以正常对外提供服务,只要DB在一个Buffer的下发的周期内恢复,就不会影响整个Leaf的可用性。

Leaf:美团分布式ID生成服务开源

这个版本代码在线上稳定运行了半年左右,Leaf又遇到了新的问题:

  1. 号段长度始终是固定的,假如Leaf本来能在DB不可用的情况下,维持10分钟正常工作,那么如果流量增加10倍就只能维持1分钟正常工作了。
  2. 号段长度设置的过长,导致缓存中的号段迟迟消耗不完,进而导致更新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:美团分布式ID生成服务开源

Leaf Snowflake

Snowflake,Twitter开源的一种分布式ID生成算法。基于64位数实现,下图为Snowflake算法的ID构成图。

Leaf:美团分布式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

Leaf:美团分布式ID生成服务开源

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
捉虫大师 捉虫大师
3年前
如何设计一款“高可用高性能”的发号器
本文已收录https://github.com/lkxiaolou/lkxiaolou欢迎star。背景在分布式场景中,很多地方需要生成全局唯一的id,如数据库分库分表后需要用唯一id代替单机版本的自增id。发号器的基本要求是全局唯一,无论如何都不能重复某些场景下还要求单调递增,如排序需求等。网上有很多介绍发号器的文章,比如美团的《Leaf——美团点
Stella981 Stella981
3年前
Nginx + lua +[memcached,redis]
精品案例1、Nginxluamemcached,redis实现网站灰度发布2、分库分表/基于Leaf组件实现的全球唯一ID(非UUID)3、Redis独立数据监控,实现订单超时操作/MQ死信操作SelectPollEpollReactor模型4、分布式任务调试Quartz应用
Stella981 Stella981
3年前
Flink 助力美团数仓增量生产
简介:本文由美团研究员、实时计算负责人鞠大升分享,主要介绍Flink助力美团数仓增量生产的应用实践。内容包括:1、数仓增量生产;2、流式数据集成;3、流式数据处理;4、流式OLAP应用;5、未来规划。一、数仓增量生产1.美团数仓架构先介绍一下美团数仓的架构以及增量生产。如下图所示,这是美团数仓的简单架构,我
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Easter79 Easter79
3年前
Storm VS Flink ——性能对比
!(https://oscimg.oschina.net/oscnet/2cec00eb2dccf5fdec8def77207da253a86.jpg)1.背景ApacheFlink和ApacheStorm是当前业界广泛使用的两个分布式实时计算框架。其中ApacheStorm(以下简称“Storm”)在美团点评实时
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_