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

前言

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

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

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将被考虑在租约到期后重新投递。