前言Facebook生态系统由数以千计的分布式系统和微服务驱动，其中许多受益于异步作业，尤其是在在线流量高峰期。异步提供了许多好处：更有效地利用资源、提高系统可靠性、允许计划执行以及微服务之间的可靠通信。实现这些好处需要一个队列——一个存储作业的地方，允许它们异步发生，或者从一个服务传递到另一个服务。Facebook的有序队列服务FOQS应运而生。FOQS支持Facebook上的数百种服务，其中包括：-Async（Facebook的异步计算平台），是一种在Facebook上广泛使用的通用异步计算平台。它提供了多种功能，从通知到完整性检查，再到调度任务执行，利用FOQS的能力存储大量积压的作业，并推迟作业的运行，从而实现调峰和山谷填充。-视频编码服务，支持异步视频编码服务。上传视频时，它们会被分解成组件，每个组件都存储在FOQS中，然后进行处理。-语言翻译技术，支持不同语言之间的帖子翻译。这类工作的计算成本可能很高，通过将其分解为多个作业、存储在FOQS中并由工作人员并行运行，可以从并行化中获益。facebook工程[1]构建分布式优先级队列FOQS的主要能力是将项目存储在位于命名空间的主题中。它公开了一个ThriftAPI，包括以下操作：EnqueueDequeueAckNackGetActiveTopicsFOQS通过内部服务ShardManager管理分片到主机的分配。每个分片都分配给一个主机。为了更轻松地与其他后端服务通信，FOQS实现了Thrift接口。下面分别介绍各部分的原理和设计：Itemitem是FOQS中优先级队列的消息，包含用户指定的数据。一般来说，它由以下字段组成：NamespaceFOQS的多租户单元Topic是一个优先级队列；命名空间可以包含许多（数千个）主题。Priority（用户指定的32位整数），数值越小，优先级越高。Payload不可变二进制大对象，最大可达10kb。开发人员可以在这里随意放置他们想要的任何东西。元数据可变二进制对象。开发人员可以在这里随意放置他们想要的任何东西。通常，元数据应该只有几百个字节。出列延迟—项目应出列的时间戳。这也称为deliver_after。Leaseduration一个项目需要被消费者ACK或NACK的持续时间。如果消费者什么都不做，FOQS可以根据客户端指定的策略（至少一次、最多一次和最大重试次数）重试以重新发布Item。FOQS分配的唯一ID用于通过API识别项目。TTL限制了Item在队列中的停留时间。一旦达到项目的生存时间(TTL)，它将被删除。“FOQS中的每个Item对应MySQL表中的一行，进入队列时，会为一个Item分配一个ID。”topic主题是一个逻辑优先级队列，通常是一个字符串，由用户指定。它包含项目并按它们的优先级和deliver_after值对它们进行排序。主题便宜且充满活力。您只需要将项目排队并指定主题标识符即可创建主题。由于主题是动态的，FOQS为开发人员提供了一个API，可以通过查询活动主题（至少包含一个项目）来发现主题。当一个主题没有更多的项目时，它就不复存在了。命名空间命名空间匹配队列实例。它是FOQS的多租户单元。每个命名空间都有一定的容量保证，以每分钟的队列数来衡量。命名空间可以共享同一列（列是FOQS主机和服务于一组命名空间的MySQL分片的集合）而不会相互影响。命名空间仅映射到一列。EnqueueEnqueues是项目进入FOQS的条目。如果成功入队，则执行持久化，最后出队。当排队的请求到达FOQS主机时，请求被缓冲并返回承诺。每个MySQL分片都有一个对应的worker，它从缓冲区中读取项目并将它们插入到MySQL中。数据库行对应于一个项目。一旦插入完成（成功或失败），承诺就会履行，排队的响应将被发送回客户端。如下图所示：FOQS使用断路器设计模式来标记不健康的分片。它的健康状况由慢速查询（滚动窗口内的平均毫秒数>xms）或错误率（滚动窗口内的平均错误数>x%）定义。如果分片被判断为不健康，worker将停止工作，直到分片健康。这样，FOQS就不会继续向已经不健康的分片中添加新的项目。如果插入成功，入队API会返回项目的唯一ID。ID是一个字符串，包含分片ID和分片中的64位主键。这种组合唯一地标识了FOQS中的每个项目。DequeuedequeueAPI的输入参数是（topic，count）参数对的集合。对于每个主题，FOQS最多返回该主题的count个项目。这些项目按优先级和deliver_after排序，因此优先级较低的项目将首先交付。如果多个项目具有最低优先级，则较低的deliver_after（即较旧的）项目将首先交付。QueueAPI允许为项目指定有效期。当一个项目出队时，它的过期检查也将开始。如果该项目在截止日期内未被确认或被取消，则可以重新滚动。这是为了避免下游消费者在acking或nacking物品之前崩溃而丢失物品。FOQS支持至少一次和至多一次交付。如果一个物品最多被传送过一次，则在过期时间到期后将被删除；如果至少一次，将尝试重新交付。由于FOQS支持优先级，每个主机都需要对其关联的分片执行归约操作以找到具有最高优先级的项目。为了优化，FOQS维护了一个名为预取缓冲区（PrefetchBuffer）的数据结构，它在后台运行，从所有分片中取出优先级最高的项目，然后缓存起来，以便客户端可以从队列中取出。每个分片都维护一个优先的内存索引，该索引是准备交付的项目的主键。索引由所有可能将项目标记为已准备好交付的操作（例如入队）更新。并允许预取缓冲区通过k路合并和选择查询高效地找到最高优先级的主键。这些项目的状态也在数据库中更新为“已交付”，以避免重复交付。预取缓冲区通过存储每个主题的客户端请求（出队率）来补充自身。预取缓冲区将以与客户端请求成比例的速率请求项目。快速出列的主题会将更多项目放入预取缓冲区。dequeueAPI只是简单的从prefetchbuffer中读取item返回给客户端：Ack/Nackack表示item已经dequeued并且处理成功，不需要再次发送。nack表示应该重新交付一个项目，因为客户端需要再次处理它。当一个项目被NACKed时，可以延迟处理，允许客户端在处理失败的项目时利用指数退避。此外，客户端可以在nack上更新项目的元数据以将部分结果存储在项目中。因为每个MySQL分片最多属于一个FOQS主机，所以一个ack/nack请求需要落在该分片对应的主机上。由于分片ID编码在每个项目ID中，因此FOQS客户端使用分片来定位主机。此映射由分片管理器查找。一旦ack/nack被路由到正确的主机，它就会被发送到特定于分片的内存缓冲区。工作人员从确认缓冲区中获取项目，然后从MySQL分片中删除行；类似地，工作人员从nack缓冲区中获取项目。但不是删除，而是使用新的deliver_after时间和元数据更新该项目（如果客户端更新了它）。如果ack或nack操作由于任何原因丢失，例如MySQL不可用或FOQS节点崩溃，这些项目将在租约到期后考虑重新交付。推与拉FOQS提供了一个基于拉的接口，消费者可以在其中使用出队API来获取可用数据。要了解在FOQSAPI中提供拉模型背后的动机，让我们看一下使用FOQS的工作的多样性。它包括以下特点：端到端延迟处理的需要：端到端处理延迟是指从物品准备好到被消费者从队列中拉出的时间。存在快速消耗和缓慢消耗的工作的混合。有些可以在几毫秒内消耗完，而另一些可能会延迟数天。处理速率：主题可能以不同的速率消耗项目（每分钟10个项目到每分钟超过1000个项目）。但是，根据特定时间下游资源的可用性，它们的处理方式可能与日常不同。优先级：主题级别或主题内单个项目级别的处理优先级不同。处理位置：一些主题和项目需要在特定区域进行处理，以确保它们与正在处理的数据相关。FOQS在实践中的规模化FOQS在过去几年经历了指数级增长，现在每天处理近万亿产品。处理订单积压已达数千亿件，反映出系统处理能力普遍不足。为了处理这种规模，我们必须实施一些优化。CheckpointingCheckPointingFOQS专门设置有后台线程来运行诸如延迟项目交付准备、租约到期和清除过期项目等操作。这些操作依赖于记录行中的时间戳字段。例如，如果我们要更新所有准备交付的项目的状态以指示它们已准备好交付，我们需要一个查询：wheretimestamp_column<=UNIX_TIMESTAMP()forupdate来更新所有行。这种查询的问题是MySQL需要用时间戳?now锁定所有行更新（不仅仅是那些符合条件的行），历史越长，读查询越慢。通过检查点，FOQS维护查询的下限（最后处理的已知时间戳），它限制了where子句。where子句变为：WHERE
