前言

Facebook生態(tài)系統(tǒng)是由成千上萬的分布式系統(tǒng)和微服務驅動構成的，其中許多服務都得益于異步作業(yè)，特別是在在線流量的高峰時期。異步化提供了諸多好處：更有效地利用資源、提高系統(tǒng)可靠性、允許計劃執(zhí)行，以及微服務彼此間可靠通信。實現(xiàn)這些優(yōu)勢都需要一個隊列——一個存儲作業(yè)的地方，允許其異步發(fā)生，或者從一個服務傳遞到另一個服務。facebook有序隊列服務FOQS應運而生。

FOQS在Facebook上支持數(shù)百個服務，包括:

facebook engineering^[1]

構建分布式優(yōu)先隊列

FOQS的主要能力是存儲位于namespace中的topic中的item。它公開了一個Thrift API，包含以下操作:

• Enqueue
• Dequeue
• Ack
• Nack
• GetActiveTopics

FOQS通過內部服務Shard Manager來管理對主機的分片分配。每個分片分配給一臺主機。為了更容易地與其他后端服務通信，F(xiàn)OQS實現(xiàn)了Thrift接口。下面來分別介紹各部分的原理和設計：

Item

item是FOQS中優(yōu)先隊列的消息，其中包含用戶指定的數(shù)據(jù)。一般來說，它由以下字段組成:

• Namespace  FOQS的多租戶單元
• Topic 即一個優(yōu)先隊列;  一個 namespace可以包含許多(數(shù)千個) topics.
• Priority (用戶指定的32位整數(shù))， 數(shù)值越小優(yōu)先級越高。
• Payload 不可變二進制大對象，大小可以到10kb。開發(fā)人員可以自由地在這里放置他們想要的任何東西。
• Metadata 可變二進制對象。開發(fā)人員可以自由地在這里放置他們想要的任何東西。通常，元數(shù)據(jù)應該只有幾百字節(jié)。
• Dequeue delay — Item應該從隊列中退出的時間戳。這也稱為deliver_after.
• Lease duration 一個Item需要被消費者ACK或者NACK而出隊列的持續(xù)時間，如果消費者什么都沒有做，則FOQS可以根據(jù)客戶指定的重試策略(至少一次、最多一次和最大重試計數(shù))重新投遞Item。
• FOQS-assigned unique ID 用于通過API標識一個Item.
• TTL 限制Item在隊列中的駐留時間。一旦一個Item的生存時間(TTL)被命中，它將被刪除。

「FOQS中的每個Item對應于MySQL表中的一行。在進入隊列時，會給一個Item分配一個ID。」

topic

一個topic就是一個邏輯優(yōu)先隊列，一般是一個字符串，由用戶指定。它包含item，并按它們的優(yōu)先級和deliver_after值對它們進行排序。主題是廉價且而且是動態(tài)變動的，只需將item排隊并指定topic標識就可以創(chuàng)建topic。

由于topic是動態(tài)的，F(xiàn)OQS為開發(fā)人員提供了一個API，通過查詢活動topic(至少包含一個item)來發(fā)現(xiàn)topic。當一個topic沒有更多的item時，它就不再存在。

namespace

一個namespace和一個隊列用例相匹配。它是FOQS的多租戶單位。每個namespace都有一定的容量保證，以每分鐘的隊列數(shù)量衡量。命名空間可以共享同一列(一列是FOQS主機和MySQL分片的集合，為一組命名空間提供服務)，且不相互影響。命名空間只映射到一個列。

Enqueue

Enqueues是item進入FOQS的入口。如果成功進入隊列，則會執(zhí)行持久化，最終出隊列。

當一個入隊請求到達FOQS主機時，請求被緩沖下來并返回一個promise。每個MySQL分片都有一個對應的worker，它從緩沖區(qū)中讀取item并將它們插入到MySQL中。一個數(shù)據(jù)庫行對應一個item。一旦插入完成(成功或失敗)，promise就會完成實現(xiàn)，并將隊列響應發(fā)送回客戶機。如下圖所示:

FOQS使用熔斷設計模式來標記不健康的分片。其健康狀況由慢查詢(滾動窗口上平均毫秒數(shù)大于 x ms)或錯誤率(滾動窗口上平均錯誤數(shù)大于x%)定義。如果分片被判定為不健康，worker將停止工作，直到分片健康。這樣，F(xiàn)OQS就不會繼續(xù)向已經不健康的分片添加新item了。

如果插入成功，enqueue API返回一個項目的唯一ID。該ID是一個字符串，包含分片 ID和分片中的64位主鍵。這種組合唯一地標識了FOQS中的每一項。

Dequeue

dequeue API的入參是(topic, count)的參數(shù)對的集合。對于每個topic，F(xiàn)OQS最多會返回對該topic的count個item。這些item是按優(yōu)先級和deliver_after排序的，因此優(yōu)先級較低的物品將首先被交付。如果多個item的優(yōu)先級最低，較低的deliver_after(即較老的)item將首先交付。

隊列API允許指定項目的過期期限。當一個item出隊列時，它的過期判定也會開始。如果item沒有在期限內被ack或被nack，它可以被重投。這是為了避免下游消費者在ack或nack item之前崩潰時丟失item。FOQS支持至少一次和最多一次的投遞。如果一個item最多投遞一次，則在過期時間到期后將其刪除;如果至少一次，將嘗試重新投遞。

由于FOQS支持優(yōu)先級，每臺主機需要在它關聯(lián)的分片上做一個reduce操作，以找到優(yōu)先級最高的item。為了優(yōu)化，F(xiàn)OQS維護了一個叫做預取緩沖區(qū)(Prefetch Buffer)的數(shù)據(jù)結構，它在后臺運行，從所有分片中取優(yōu)先級最高的item，然后進行緩存，以便客戶端從隊列中取出。

每個分片維護一個按優(yōu)先級排序的，準備投遞的item主鍵的 內存索引。該索引被所有可能標記一個item已經準備好投遞的操作(如enqueues)進行更新。并允許預取緩沖區(qū)通過k-way merge和select查詢來高效地找到優(yōu)先級最高的主鍵。這些item的狀態(tài)在數(shù)據(jù)庫中也被更新為“已投遞”，避免重復投遞。

預取緩沖區(qū)(Prefetch Buffer)通過存儲每個topic的客戶端請求(出隊率)來補充自身。預取緩沖區(qū)(Prefetch Buffer)將以與客戶端請求成比例的速率請求item?？焖俪鲫牭膖opic將獲得更多的item放入預取緩沖區(qū)。

dequeue API只是從預取緩沖區(qū)讀取項目并將它們返回給客戶機：  

Ack/Nack

ack表示該item已退出隊列并已成功處理，不需要再次發(fā)送。

nack表示一個item應該被重新投遞，因為客戶端需要再次處理。當一個項被NACK時，是可以延遲處理的，允許客戶端在處理失敗的item時利用指數(shù)后退。此外，客戶端可以在nack上更新該item的元數(shù)據(jù)，以便在該item中存儲部分結果。

因為每個MySQL分片最多屬于一個FOQS主機，一個ack/nack請求需要落在分片對應的主機上。由于shard ID編碼在每個item ID中，F(xiàn)OQS客戶端使用shard來定位主機。這個映射通過Shard Manager查找。

一旦ack/nack被路由到正確的主機，它就會被發(fā)送到特定分片的內存緩沖區(qū)。worker從ack緩沖區(qū)中取出item，然后從MySQL分片中刪除這些行; 類似地，worker從nack緩沖區(qū)中提取item。但不是刪除，而是使用新的deliver_after時間和元數(shù)據(jù)(如果客戶端更新了它)更新item。如果ack或nack操作因為任何原因丟失，例如MySQL不可用或FOQS節(jié)點崩潰，這些item將被考慮在租約到期后重新投遞。