前言

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

FOQS在Facebook上支持?jǐn)?shù)百個(gè)服務(wù)，包括:

facebook engineering^[1]

構(gòu)建分布式優(yōu)先隊(duì)列

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

• Enqueue
• Dequeue
• Ack
• Nack
• GetActiveTopics

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

Item

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

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

「FOQS中的每個(gè)Item對應(yīng)于MySQL表中的一行。在進(jìn)入隊(duì)列時(shí)，會給一個(gè)Item分配一個(gè)ID。」

topic

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

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

namespace

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

Enqueue

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

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

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

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

Dequeue

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

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

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

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

預(yù)取緩沖區(qū)(Prefetch Buffer)通過存儲每個(gè)topic的客戶端請求(出隊(duì)率)來補(bǔ)充自身。預(yù)取緩沖區(qū)(Prefetch Buffer)將以與客戶端請求成比例的速率請求item。快速出隊(duì)的topic將獲得更多的item放入預(yù)取緩沖區(qū)。

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

Ack/Nack

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

nack表示一個(gè)item應(yīng)該被重新投遞，因?yàn)榭蛻舳诵枰俅翁幚怼．?dāng)一個(gè)項(xiàng)被NACK時(shí)，是可以延遲處理的，允許客戶端在處理失敗的item時(shí)利用指數(shù)后退。此外，客戶端可以在nack上更新該item的元數(shù)據(jù)，以便在該item中存儲部分結(jié)果。

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

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