前言

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將被考慮在租約到期后重新投遞。