专栏首页Coder的技术之路Facebook有序队列服务设计原理和高性能浅析

Facebook有序队列服务设计原理和高性能浅析

前言

Facebook生态系统是由成千上万的分布式系统和微服务驱动构成的,其中许多服务都得益于异步作业,特别是在在线流量的高峰时期。异步化提供了诸多好处:更有效地利用资源、提高系统可靠性、允许计划执行,以及微服务彼此间可靠通信。实现这些优势都需要一个队列——一个存储作业的地方,允许其异步发生,或者从一个服务传递到另一个服务。facebook有序队列服务FOQS应运而生。

FOQS在Facebook上支持数百个服务,包括:

- Async (Facebook的异步计算平台),是Facebook上广泛使用的通用异步计算平台。它提供了各种功能,从通知到完整性检查,再到为任务计划执行,利用FOQS的能力来存储大量作业的积压,推迟作业运行,从而达到削峰填谷。

- 视频编码服务,支持异步视频编码服务。当视频被上传时,它们被分解成多个组件,每个组件存储在FOQS中,然后进行处理。

- 语言翻译技术,为语言间的帖子翻译提供了支持。这种工作在计算上可能非常昂贵,通过将其分解为多个作业,存储在FOQS中,并由workers并行运行而从并行化中获益。等

facebook engineering[1]

构建分布式优先队列

FOQS的主要能力是存储位于namespace中的topic中的item。它公开了一个Thrift API,包含以下操作:

  • Enqueue
  • Dequeue
  • Ack
  • Nack
  • GetActiveTopics

FOQS通过内部服务Shard Manager来管理对主机的分片分配。每个分片分配给一台主机。为了更容易地与其他后端服务通信,FOQS实现了Thrift接口。下面来分别介绍各部分的原理和设计:

Item

item是FOQS中优先队列的消息,其中包含用户指定的数据。一般来说,它由以下字段组成:

  • Namespace FOQS的多租户单元
  • Topic 即一个优先队列; 一个 namespace可以包含许多(数千个) topics.
  • Priority (用户指定的32位整数), 数值越小优先级越高。
  • Payload 不可变二进制大对象,大小可以到10kb。开发人员可以自由地在这里放置他们想要的任何东西。
  • Metadata 可变二进制对象。开发人员可以自由地在这里放置他们想要的任何东西。通常,元数据应该只有几百字节。
  • Dequeue delay — Item应该从队列中退出的时间戳。这也称为deliver_after.
  • Lease duration 一个Item需要被消费者ACK或者NACK而出队列的持续时间,如果消费者什么都没有做,则FOQS可以根据客户指定的重试策略(至少一次、最多一次和最大重试计数)重新投递Item。
  • FOQS-assigned unique ID 用于通过API标识一个Item.
  • TTL 限制Item在队列中的驻留时间。一旦一个Item的生存时间(TTL)被命中,它将被删除。

「FOQS中的每个Item对应于MySQL表中的一行。在进入队列时,会给一个Item分配一个ID。」

topic

一个topic就是一个逻辑优先队列,一般是一个字符串,由用户指定。它包含item,并按它们的优先级和deliver_after值对它们进行排序。主题是廉价且而且是动态变动的,只需将item排队并指定topic标识就可以创建topic。

由于topic是动态的,FOQS为开发人员提供了一个API,通过查询活动topic(至少包含一个item)来发现topic。当一个topic没有更多的item时,它就不再存在。

namespace

一个namespace和一个队列用例相匹配。它是FOQS的多租户单位。每个namespace都有一定的容量保证,以每分钟的队列数量衡量。命名空间可以共享同一列(一列是FOQS主机和MySQL分片的集合,为一组命名空间提供服务),且不相互影响。命名空间只映射到一个列。

Enqueue

Enqueues是item进入FOQS的入口。如果成功进入队列,则会执行持久化,最终出队列。

当一个入队请求到达FOQS主机时,请求被缓冲下来并返回一个promise。每个MySQL分片都有一个对应的worker,它从缓冲区中读取item并将它们插入到MySQL中。一个数据库行对应一个item。一旦插入完成(成功或失败),promise就会完成实现,并将队列响应发送回客户机。如下图所示:

FOQS使用熔断设计模式来标记不健康的分片。其健康状况由慢查询(滚动窗口上平均毫秒数大于 x ms)或错误率(滚动窗口上平均错误数大于x%)定义。如果分片被判定为不健康,worker将停止工作,直到分片健康。这样,FOQS就不会继续向已经不健康的分片添加新item了。

如果插入成功,enqueue API返回一个项目的唯一ID。该ID是一个字符串,包含分片 ID和分片中的64位主键。这种组合唯一地标识了FOQS中的每一项。

Dequeue

dequeue API的入参是(topic, count)的参数对的集合。对于每个topic,FOQS最多会返回对该topic的count个item。这些item是按优先级和deliver_after排序的,因此优先级较低的物品将首先被交付。如果多个item的优先级最低,较低的deliver_after(即较老的)item将首先交付。

队列API允许指定项目的过期期限。当一个item出队列时,它的过期判定也会开始。如果item没有在期限内被ack或被nack,它可以被重投。这是为了避免下游消费者在ack或nack item之前崩溃时丢失item。FOQS支持至少一次和最多一次的投递。如果一个item最多投递一次,则在过期时间到期后将其删除;如果至少一次,将尝试重新投递。

由于FOQS支持优先级,每台主机需要在它关联的分片上做一个reduce操作,以找到优先级最高的item。为了优化,FOQS维护了一个叫做预取缓冲区(Prefetch Buffer)的数据结构,它在后台运行,从所有分片中取优先级最高的item,然后进行缓存,以便客户端从队列中取出。

每个分片维护一个按优先级排序的,准备投递的item主键的 内存索引。该索引被所有可能标记一个item已经准备好投递的操作(如enqueues)进行更新。并允许预取缓冲区通过k-way merge和select查询来高效地找到优先级最高的主键。这些item的状态在数据库中也被更新为“已投递”,避免重复投递。

预取缓冲区(Prefetch Buffer)通过存储每个topic的客户端请求(出队率)来补充自身。预取缓冲区(Prefetch Buffer)将以与客户端请求成比例的速率请求item。快速出队的topic将获得更多的item放入预取缓冲区。

dequeue API只是从预取缓冲区读取项目并将它们返回给客户机:

Ack/Nack

ack表示该item已退出队列并已成功处理,不需要再次发送。

nack表示一个item应该被重新投递,因为客户端需要再次处理。当一个项被NACK时,是可以延迟处理的,允许客户端在处理失败的item时利用指数后退。此外,客户端可以在nack上更新该item的元数据,以便在该item中存储部分结果。

因为每个MySQL分片最多属于一个FOQS主机,一个ack/nack请求需要落在分片对应的主机上。由于shard ID编码在每个item ID中,FOQS客户端使用shard来定位主机。这个映射通过Shard Manager查找。

一旦ack/nack被路由到正确的主机,它就会被发送到特定分片的内存缓冲区。worker从ack缓冲区中取出item,然后从MySQL分片中删除这些行; 类似地,worker从nack缓冲区中提取item。但不是删除,而是使用新的deliver_after时间和元数据(如果客户端更新了它)更新item。如果ack或nack操作因为任何原因丢失,例如MySQL不可用或FOQS节点崩溃,这些item将被考虑在租约到期后重新投递。

Push vs. Pull

FOQS提供了一个基于拉的接口,消费者使用dequeue API来获取可用数据。为了理解在FOQS API中提供拉模型背后的动机,我们看看使用FOQS的作业的多样性。它包括以下特征:

  • 端到端延迟处理的需要:端到端处理延迟,是指item从准备好到被消费者从队列中拉取消费所经历的时间。快速消费和缓慢消费的作业混在一起。有的可以被毫秒级消费,而有的会延迟好几天。
  • 处理速率 : topic对于item的消费速率可能是不同的(每分钟10个item到每分钟1000多个item)。但是,根据下游资源在特定时间的可用性,可能有别于它们日常的处理速度。
  • 优先级: topic级别或topic内单个item级别的处理优先级不同。
  • 处理的位置 : 某些topic和item需要在特定的区域进行处理,以确保它们与正在处理的数据的关联性。

FOQS的大规模实践

FOQS在过去几年中经历了指数级的增长,现在每天处理近一万亿件产品。而处理的积压订单已经达到数千亿项,反映了系统处理能力普遍欠缺。为了处理这种规模,我们必须实现一些优化。

检查点 CheckPointing

FOQS专门设置有后台线程,来运行比如延迟的item准备投递、租约过期和清除过期的item,这些操作依赖于记录行中的时间戳字段。

比如,如果我们想更新所有准备交付的item的状态,来标识它们已经准备好投递,则需要一个查询:

where timestamp_column <= UNIX_TIMESTAMP() for update

对所有行进行更新。

这种查询的问题是MySQL需要用时间戳≲now 锁定对所有行更新(不仅仅是符合条件的那些记录)。、历史越长,读取查询就越慢。

通过checkpoinging,FOQS在查询上维护了一个下界(最后处理的已知时间戳),它限定了where子句。where子句变成:

WHERE <checkpoint> <= timestamp_column AND timestamp_column <= UNIX_TIMESTAMP()

通过在两边绑定查询,表示历史记录的行数就会更少,从而使读取(和更新)的总体性能更好。

灾备

Facebook的基础设施需要能够承受一整个数据中心发生异常。所以,每个FOQS MySQL分片被复制到两个冗余的灾备集群。跨区复制是异步的,但是MySQL binlog以同步的方式持久化到同一区域的另一个灾备集群中。

如果数据中心需要被清空(或者MySQL数据库正在进行维护),MySQL主数据库将暂时处于只读模式,直到副本能够和主节点同步。

这通常需要几毫秒。一旦副本和主节点数据达到一致,副本就被提升为主节点。

而这时会变成MySQL的主节点在另一个区域,而分区被分配给该区域的FOQS主机。这将最大限度地减少跨区域的网络流量,但相对来说比较昂贵。推动MySQL副本成为主节点的事件会导致跨地区的流量不平衡(一般来说,FOQS不能假设哪里有多少流量)。为了处理这些场景,FOQS不得不改进它的路由,使入队列路由到有足够容量的主机,而出队列路由到具有高优先级item的主机。

FOQS本身使用的一些灾难可靠性优化:

  • 入队转发: 如果入队请求落在一个负载过重的主机上,FOQS将它转发给另一个有处理能力的主机。
  • 全局速率限制: 由于namespace是foqs的多租户单元,所以每个namespace都有一个速率限制(计算为每分钟排队数)。FOQS在全局(所有地区)强制执行这个速率限制。在一个特定的区域内保证速率限制是不可能的,但是FOQS确实使用流量模式来尝试将处理能力与流量配置在一起,以减少跨区域的流量。

Reference

[1]facebook engineering: facebook工程师技术博客

本文分享自微信公众号 - Coder的技术之路(gh_1b3189982966),作者:Coder的技术之路

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 几个大型网站的Feeds(Timeline)设计简单对比

    Facebook起源的NewsFeed,以及Twitter起源的Timeline,核心问题都是如何处理巨大的消息(活动,activity)分发。“推Push”和...

    芋道源码
  • 今日推荐:awesome-architecture

    但是这条路还是有很多人走,而且也留下了相应的封神之法,今天推荐的就是一个相当详细的架构师框架学习图。内容很充实,看目录的时候,滚动条滚了很多次!学习起来肯定也不...

    仇诺伊
  • 阿里&百度&腾讯&facebook&Microsoft&Google开源项目汇总

    BAT && YMFT Tencent GitHub地址:https://github.com/Tencent/tinker Tinker是Android的...

    shaonbean
  • Facebook、亚马逊是如何构建超集群数据库的

    我们建立了Keen IO,是为了以让大多数软件工程团队无需从头架设所有内容,就可以利用最新的大型事件数据技术。但是,如果您对如何成为巨头公司感到...

    BestSDK
  • Fail at Scale

    Fail at Scale 是 Facebook 2015 年在 acm queue 上发表的一篇文章。主要写了常见的线上故障和应对方法,内容还是比较实在的。

    梦醒人间
  • 「冰河技术」部分精华文章目录汇总

    个人研发的在高并发场景下,提供的简单、稳定、可扩展的延迟消息队列框架,具有精准的定时任务和延迟队列处理功能。自开源半年多以来,已成功为十几家中小型企业提供了精准...

    冰河
  • 大数据利器2018版

    一见
  • 560万Facebook人际关系数据,揭秘家庭职业传承“真相”

    当你走出校门迈向职场,择业时也许很难完全避免来自父母的影响。而这种影响甚至还不是一时,而是打你一出生就已经开始了。“龙生龙凤生凤”,父母的职业在多大程度上会影响...

    DT数据侠
  • Facebook:如何让应用适合所有系统、带宽以及屏幕

    如果你的移动应用程序只能在某个地区(比如US)运行良好,那么该如何改善?在@scale conference上,Facebook多次谈及了这个问题。那么如何才能...

    CSDN技术头条
  • React的时间简史

    首先,失踪人口正式回归,近来遇到些事情导致原定的系列计划搁置,深表抱歉,后续会正常迭代。

    Cookieboty
  • 从客户端的角度来谈谈移动端IM的消息可靠性和送达机制

    IM App 是我做过 App 类型里复杂度最高的一类,里面可供深究探讨的技术难点非常之多。这篇文章和大家聊下从移动端客户端的角度所关注的IM消息可靠性和送达机...

    JackJiang
  • 深入Facebook机器学习部门:服务、模型、框架和硬件(贾扬清等HPCA论文)

    来源:research.fb.com 作者:Kim Hazelwood et al. 编译:刘小芹 【新智元导读】近日 Facebook 研究团队公开一篇 HP...

    新智元
  • Facebook万字长文:AI模型全部迁移至PyTorch框架

    PyTorch自2017年推出以来,就迅速占领GitHub热度榜榜首,一度有赶超Tensorflow的趋势。

    代码医生工作室
  • 2017 我的技术之路:不忘初心,夯实基础

    又一年春去冬来,到了年末盘点的时候,感觉自己今年相较于前两年沉稳了些,也愈能明晰自身的不足;所以本年的主题就定为了不忘初心,夯实基础。今年年初的时候领证结婚,未...

    王下邀月熊
  • 大数据学习资源最全版本(收藏)

    Apache Hadoop:分布式处理架构,结合了 MapReduce(并行处理)、YARN(作业调度)和HDFS(分布式文件系统);

    风火数据
  • SOA、ESB、NServiceBus、云计算 总结

    SOA SOA 是通过功能组件化、服务化,来实现系统集成、解决信息孤岛,这是其主要目标。而更进一步则是实现更快响应业务的变化、更快推出新的应用系统。与此同时,S...

    用户1172223
  • 想了解大数据的鼻祖Hadoop技术栈,这里有一份优质书单推荐!

    如何用形象的比喻描述大数据的技术生态?Hadoop、Hive、Spark 之间是什么关系?对于大部分人来说都是傻傻分不清楚。

    黄小斜学Java
  • 想了解大数据的鼻祖Hadoop技术栈,这里有一份优质书单推荐!

    如何用形象的比喻描述大数据的技术生态?Hadoop、Hive、Spark 之间是什么关系?对于大部分人来说都是傻傻分不清楚。

    Java技术江湖
  • Netty干货分享:京东京麦的生产级TCP网关技术实践总结

    京东的京麦商家后台2014年构建网关,从HTTP网关发展到TCP网关。在2016年重构完成基于Netty4.x+Protobuf3.x实现对接PC和App上下行...

    JackJiang

扫码关注云+社区

领取腾讯云代金券