草庐IT

深入理解美团 Leaf 发号器开源方案

陈树义 2023-03-28 原文
大家好,我是树哥。

之前我们有聊过「如何设计一个分布式 ID 发号器」,其中有讲过 4 种解决方案,分别是:

  • UUID
  • 类雪花算法
  • 数据库自增主键
  • Redis 原子自增
美团以第 2、3 种解决方案为基础,开发出了分布式 ID 生成方案 Leaf,并将其开源。我们可以在 GitHub 上获取到该项目的源码,以及相关的文档说明,项目地址:Meituan-Dianping/Leaf: Distributed ID Generate Service。

今天我们就来学习一下 Leaf 的设计思路,看看大厂是如何设计大型中间件的,这有利于进一步提升我们自己的系统设计能力。

数据库自增主键

在「如何设计一个分布式 ID 发号器?」文章里,我们说到可以基于数据库自增主键设计发号器。但我们也提到其存在如下两个问题:

  • 只能依赖堆机器提高性能。当请求再次增多时,我们只能无限堆机器,这貌似是一种物理防御一样。
  • 水平扩展困难。当我们需要增加一台机器时,其处理过程非常麻烦。首先,我们需要先把新增的服务器部署好,设置新的步长,起始值要设置一个不可能达到的值。当把新增的服务器部署好之后,再一台台处理旧的服务器,这个过程真的非常痛苦,可以说是人肉运维了。
简单地说,就是基于数据库主键自增的方式,其发号效率受限于单台物理机器。在低 QPS 的情况下还可以支持,但在高 QPS 的时候就支持不了了。即使可以通过设计步长的方式来堆机器,但是其运维成本也非常高。

在这样的业务背景下,美团开源的 Leaf 做了进一步优化,在数据库与业务服务之间加入了中间层。之前业务系统直接去请求数据库,现在业务系统不直接请求数据库,而是去请求 Leaf 中间层,之后由 Leaf 中间层去数据库取数据。

Leaf 中间层每次去数据库获取 ID 的时候,一次性获取一批 ID 号码段,而不是只获取一个 ID。 整个服务的具体处理流程如下所示。

Leaf Segment 处理流程 - 图片来自美团技术团队博客

如上图所示,绿色的业务系统请求 Leaf 发号服务的时候,带上业务编码标记。随后 Leaf 发号服务根据业务编号类型返回下一个唯一 ID。Leaf 发号服务每次向数据库获取 1000 个 ID,数据库往表中插入一条数据,表示这 1000 个 ID 分给了某个业务。

通过这种方式,原本业务系统获取 1000 个 ID 需要进行 1000 次数据请求,现在可能只需要 1 次就够了,极大地提高了运行效率。 此外,业务系统获取 ID 的时候都是从内存获取,不需要请求第三方,极大的提高了响应速度。

上述方式虽然解决了数据库层的压力问题,但也存在一些问题,例如:在 ID 号码段发完时,这时候需要去进行数据库请求,这次请求的耗时就会突增,系统监控上就会出现耗时尖刺。

为了解决这个问题,美团 Leaf 采用了「双 Buffer + 预加载」的策略,即在内存中维护两个 ID 段,并在上一个 ID 段使用达到 10% 的时候去预加载。这其实有点像我们 App 上加载瀑布流的预加载,思路是一样的。其设计思路如下图所示。

双 Buffer + 预加载 - 图片来自美团技术团队博客

通过预加载的方式,Leaf 解决了尖刺的问题,并且提供了一定程度的数据库宕机高可用。 如果数据库宕机,Leaf 服务还可以提供一段时间的服务,只要其在短时间内可以恢复。

按照官方博客种的说法,这套方案再上线半年之后又遇到了问题 —— 发号 ID 段是固定的,但流量不是固定的,如果流量增加 10 倍,就会发现维持的时间很短,这样仍然有可能导致数据库压力较大。

为了解决这个问题,其采用了动态号码段的思路,即:根据上次号码段的长度及分发耗时,计算出下次应发的号码段长度。对于号码长度的计算规则如下:

  • T < 15min,nextStep = step * 2
  • 15min < T < 30min,nextStep = step
  • T > 30min,nextStep = step / 2
简单地说,如果耗时低于 15 分钟,那么下次应发的号码段长度变为原有的 2 倍。如果在 15 - 30 分钟之间,那么就保持应发号码段长度不变。如果耗时大于 30 分钟, 那么下次应发号码段长度减半。

这种设计思路,其实有点像 Hotspot 虚拟机获取锁时的自适应自旋,或许我们可以称它为:自适应长度。

即使 Leaf 做了如此多的优化,但在更恶劣的环境下,仍然可能发生系统不可以的情况,例如:

  • 数据库主库突然宕机,短时间内无法恢复,此时系统不可用。
  • 业务流量突增几十倍,即使有批量分发,但数据库单机无法支撑如此高的写请求。
  • 等等。
在上面这些场景下,系统仍然无法保证高可用。究其根本,这是因为 Leaf 对数据库是强依赖的,因此需要从数据库层面去做高可用保障。

按照 Leaf 官方博客的思路,Leaf 目前使用了半同步的方式同步数据,并且实现了主从切换。 这就解决了主库宕机的问题,进一步提升了高可用程度。

MySQL 半同步有点类似于 Kafka 的副本同步,需要有一个 slave 收到 binlog 之后,才能提交事务,从而保证了一定程度上的一致性,降低了号码段重发的风险。

但由于半同步方式,并无法保证数据强一致性,因此极端情况下还是可能会有号码段重发的风险,只是较低罢了。如果需要保证完全的强一致性,那么需要考虑使用 MySQL 的 Group Replication 特性。但由于美团内部的数据库强一致性特性还在迭代中,因此 Leaf 也未实现数据强一致性。

类雪花算法

在「如何设计一个分布式 ID 发号器?」文章里,我们说到雪花算法是一个非常好的分布式 ID 生成算法。但其存在一个缺陷 —— 存在时钟回拨的问题。美团开源的 Leaf 也实现了基于雪花算法的分布式 ID 生成功能,并且解决了时钟回拨的问题。

美团 Leaf 引入了 zookeeper 来解决时钟回拨问题,其大致思路为:每个 Leaf 运行时定时向 zk 上报时间戳。每次 Leaf 服务启动时,先校验本机时间与上次发 ID 的时间,再校验与 zk 上所有节点的平均时间戳。如果任何一个阶段有异常,那么就启动失败报警。

这个解决方案还是比较好理解的,就是对比上次发 ID 的时间,还有其他机器的平均时间。除了时间回拨的问题,当机器数量变多的时候,雪花算法中的 workerId 也不是很好维护。

因此,Leaf 也用 zookeeper 作为中间件,以每个服务器的 IP + Port 作为 key 去注册一个节点,获取一个 int 类型的节点作为 workerId。

总结

美团开源的 Leaf 提供了两种 ID 生成方式:

  • 号码段模式。基于数据库自增组件,ID 从低位趋势增长,能够忍受 MySQL 短时间不可用。
  • 类雪花算法模式。基于雪花算法,解决了时间回拨以及海量机器的 workId 维护问题。
对于号码段模式而言,其在传统的自增 ID 基础上,增加了 Proxy 模式,提出号码段模式。接着,又采用「双 Buffer + 预加载」的方式解决尖刺的问题。再之,为了解决流量暴增的问题,采用了自适应号码段长度的优化思路。最后,在数据库高可用上,使用 MySQL 半同步复制 + 主从切换,从一定程度上保障了高可用。

对于类雪花算法模式而言,其引入了 zookeeper 作为海量机器的 workerId 生成方法。其次,还通过「本地存储时间戳 + 定时上报时间戳」的方式,解决了时间戳的问题。

好了,这就是今天分享的全部内容了。

有关深入理解美团 Leaf 发号器开源方案的更多相关文章

  1. ruby - 在 jRuby 中使用 'fork' 生成进程的替代方案? - 2

    在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',

  2. CAN协议的学习与理解 - 2

    最近在学习CAN,记录一下,也供大家参考交流。推荐几个我觉得很好的CAN学习,本文也是在看了他们的好文之后做的笔记首先是瑞萨的CAN入门,真的通透;秀!靠这篇我竟然2天理解了CAN协议!实战STM32F4CAN!原文链接:https://blog.csdn.net/XiaoXiaoPengBo/article/details/116206252CAN详解(小白教程)原文链接:https://blog.csdn.net/xwwwj/article/details/105372234一篇易懂的CAN通讯协议指南1一篇易懂的CAN通讯协议指南1-知乎(zhihu.com)视频推荐CAN总线个人知识总

  3. TimeSformer:抛弃CNN的Transformer视频理解框架 - 2

    Transformers开始在视频识别领域的“猪突猛进”,各种改进和魔改层出不穷。由此作者将开启VideoTransformer系列的讲解,本篇主要介绍了FBAI团队的TimeSformer,这也是第一篇使用纯Transformer结构在视频识别上的文章。如果觉得有用,就请点赞、收藏、关注!paper:https://arxiv.org/abs/2102.05095code(offical):https://github.com/facebookresearch/TimeSformeraccept:ICML2021author:FacebookAI一、前言Transformers(VIT)在图

  4. ruby - 易于初学者理解的 Ruby 库 - 2

    关闭。这个问题不符合StackOverflowguidelines.它目前不接受答案。我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题,以便用事实和引用来回答。关闭3年前。Improvethisquestion我正处于学习Ruby的阶段,我想查看一些小型库的源代码以了解它们是如何构建的。我不知道什么是小型图书馆,但希望SO能推荐一些易于理解的图书馆来学习。因此,如果有人知道一两个非常小的库,这是新手Rubyists学习的好例子,请推荐!我想使用Manveru'sInnatelib,因为它试图保持在2000LOC以下,但我还不熟悉其中经常使用的Ruby速记。也许大约100-5

  5. ruby - 无法理解 `puts{}.class` 和 `puts({}.class)` 之间的区别 - 2

    由于匿名block和散列block看起来大致相同。我正在玩它。我做了一些严肃的观察,如下所示:{}.class#=>Hash好的,这很酷。空block被视为Hash。print{}.class#=>NilClassputs{}.class#=>NilClass为什么上面的代码和NilClass一样,下面的代码又显示了Hash?puts({}.class)#Hash#=>nilprint({}.class)#Hash=>nil谁能帮我理解上面发生了什么?我完全不同意@Lindydancer的观点你如何解释下面几行:print{}.class#NilClassprint[].class#A

  6. Ruby 守护进程和 JRuby - 备选方案 - 2

    我有一个应用程序正在从Ruby迁移到JRuby(由于需要通过Java提供更好的Web服务安全支持)。我使用的gem之一是daemons创建后台作业。问题在于它使用fork+exec来创建后台进程,但这对JRuby来说是禁忌。那么-是否有用于创建后台作业的替代gem/wrapper?我目前的想法是只从shell脚本调用rake并让rake任务永远运行......提前致谢,克里斯。更新我们目前正在使用几个与Java线程相关的包装器,即https://github.com/jmettraux/rufus-scheduler和https://github.com/philostler/acts

  7. ruby - 如何理解 Ruby 中的发送者和接收者? - 2

    我很难理解Ruby中sender和receiver的实际含义。它们一般是什么意思?到目前为止,我只是将它们理解为方法调用和获取其返回值的调用。但是,我知道我的理解还远远不够。谁能给我一个Ruby中发送者和接收者的具体解释? 最佳答案 面向对象中的一个核心概念是消息传递和早期概念化,这在很大程度上借鉴了计算的Actor模型。艾伦·凯(AlanKay)创造了面向对象一词并发明了最早的OO语言之一SmallTalk,他拥有voicedregretatusingatermwhichputthefocusonobjectsinsteadofo

  8. ruby-on-rails - Rails - 理解 application.js 和 application.css - 2

    rails新手。只是想了解\assests目录中的这两个文件。例如,application.js文件有如下行://=requirejquery//=requirejquery_ujs//=require_tree.我理解require_tree。只是将所有JS文件添加到当前目录中。根据上下文,我可以看出requirejquery添加了jQuery库。但是它从哪里得到这些jQuery库呢?我没有在我的Assets文件夹中看到任何jquery.js文件——或者直接在我的整个应用程序中没有看到任何jquery.js文件?同样,我正在按照一些说明安装TwitterBootstrap(http:

  9. ruby-on-rails - 能够处理 rar/tar/zip/7z 的 Ruby/rubyzip 替代方案? - 2

    关闭。这个问题不符合StackOverflowguidelines.它目前不接受答案。要求我们推荐或查找工具、库或最喜欢的场外资源的问题对于StackOverflow来说是偏离主题的,因为它们往往会吸引自以为是的答案和垃圾邮件。相反,describetheproblem以及迄今为止为解决该问题所做的工作。关闭9年前。Improvethisquestion我想知道是否有人知道Ruby的ruby​​zip替代品,它可以处理各种格式,特别是zip/rar/7z?我知道libarchive,但它对我的目的来说并不完整(它是一个很好的gem)。(澄清一下,libarchive-对我不起作用-因为

  10. ruby-on-rails - 对于 Ruby 应用程序,是否有比 Sanitize 更好的替代方案? - 2

    我爱Sanitize.这是一个了不起的实用程序。我遇到的唯一问题是,它需要永远准备一个开发环境,因为它使用Nokogiri,这对编译时间来说是一种痛苦。是否有任何程序可以在不使用Nokogiri的情况下执行Sanitize的操作(如果没有别的,只是温和地执行它的操作)?这将以指数方式提供帮助! 最佳答案 Rails有自己的SanitizeHelper。根据http://api.rubyonrails.org/classes/ActionView/Helpers/SanitizeHelper.html,它将Thissanitizehe

随机推荐