Facebook的有序隊列服務(wù)設(shè)計原理和高性能淺析
Facebook生態(tài)系統(tǒng)是由成千上萬的分布式系統(tǒng)和微服務(wù)驅(qū)動構(gòu)成的，其中許多服務(wù)都得益于異步作業(yè)，特別是在在線流量的高峰時期。異步化提供了諸多好處：更有效地利用資源、提高系統(tǒng)可靠性、允許計劃執(zhí)行，以及微服務(wù)彼此間可靠通信。實(shí)現(xiàn)這些優(yōu)勢都需要一個隊列——一個存儲作業(yè)的地方，允許其異步發(fā)生，或者從一個服務(wù)傳遞到另一個服務(wù)。facebook有序隊列服務(wù)FOQS應(yīng)運(yùn)而生。 FOQS在Facebook上支持?jǐn)?shù)百個服務(wù)，包括: facebook engineering[1] FOQS的主要能力是存儲位于namespace中的topic中的item。它公開了一個Thrift API，包含以下操作: FOQS通過內(nèi)部服務(wù)Shard Manager來管理對主機(jī)的分片分配。每個分片分配給一臺主機(jī)。為了更容易地與其他后端服務(wù)通信，F(xiàn)OQS實(shí)現(xiàn)了Thrift接口。下面來分別介紹各部分的原理和設(shè)計： item是FOQS中優(yōu)先隊列的消息，其中包含用戶指定的數(shù)據(jù)。一般來說，它由以下字段組成: 「FOQS中的每個Item對應(yīng)于MySQL表中的一行。在進(jìn)入隊列時，會給一個Item分配一個ID?！?/strong> 一個topic就是一個邏輯優(yōu)先隊列，一般是一個字符串，由用戶指定。它包含item，并按它們的優(yōu)先級和deliver_after值對它們進(jìn)行排序。主題是廉價且而且是動態(tài)變動的，只需將item排隊并指定topic標(biāo)識就可以創(chuàng)建topic。 由于topic是動態(tài)的，F(xiàn)OQS為開發(fā)人員提供了一個API，通過查詢活動topic(至少包含一個item)來發(fā)現(xiàn)topic。當(dāng)一個topic沒有更多的item時，它就不再存在。 一個namespace和一個隊列用例相匹配。它是FOQS的多租戶單位。每個namespace都有一定的容量保證，以每分鐘的隊列數(shù)量衡量。命名空間可以共享同一列(一列是FOQS主機(jī)和MySQL分片的集合，為一組命名空間提供服務(wù))，且不相互影響。命名空間只映射到一個列。 Enqueues是item進(jìn)入FOQS的入口。如果成功進(jìn)入隊列，則會執(zhí)行持久化，最終出隊列。 當(dāng)一個入隊請求到達(dá)FOQS主機(jī)時，請求被緩沖下來并返回一個promise。每個MySQL分片都有一個對應(yīng)的worker，它從緩沖區(qū)中讀取item并將它們插入到MySQL中。一個數(shù)據(jù)庫行對應(yīng)一個item。一旦插入完成(成功或失敗)，promise就會完成實(shí)現(xiàn)，并將隊列響應(yīng)發(fā)送回客戶機(jī)。如下圖所示: FOQS使用熔斷設(shè)計模式來標(biāo)記不健康的分片。其健康狀況由慢查詢(滾動窗口上平均毫秒數(shù)大于 x ms)或錯誤率(滾動窗口上平均錯誤數(shù)大于x%)定義。如果分片被判定為不健康，worker將停止工作，直到分片健康。這樣，F(xiàn)OQS就不會繼續(xù)向已經(jīng)不健康的分片添加新item了。 如果插入成功，enqueue API返回一個項目的唯一ID。該ID是一個字符串，包含分片 ID和分片中的64位主鍵。這種組合唯一地標(biāo)識了FOQS中的每一項。 dequeue API的入?yún)⑹?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允許指定項目的過期期限。當(dāng)一個item出隊列時，它的過期判定也會開始。如果item沒有在期限內(nèi)被ack或被nack，它可以被重投。這是為了避免下游消費(fèi)者在ack或nack item之前崩潰時丟失item。FOQS支持至少一次和最多一次的投遞。如果一個item最多投遞一次，則在過期時間到期后將其刪除;如果至少一次，將嘗試重新投遞。 由于FOQS支持優(yōu)先級，每臺主機(jī)需要在它關(guān)聯(lián)的分片上做一個reduce操作，以找到優(yōu)先級最高的item。為了優(yōu)化，F(xiàn)OQS維護(hù)了一個叫做預(yù)取緩沖區(qū)(Prefetch Buffer)的數(shù)據(jù)結(jié)構(gòu)，它在后臺運(yùn)行，從所有分片中取優(yōu)先級最高的item，然后進(jìn)行緩存，以便客戶端從隊列中取出。 每個分片維護(hù)一個按優(yōu)先級排序的，準(zhǔn)備投遞的item主鍵的 內(nèi)存索引。該索引被所有可能標(biāo)記一個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)通過存儲每個topic的客戶端請求(出隊率)來補(bǔ)充自身。預(yù)取緩沖區(qū)(Prefetch Buffer)將以與客戶端請求成比例的速率請求item。快速出隊的topic將獲得更多的item放入預(yù)取緩沖區(qū)。 dequeue API只是從預(yù)取緩沖區(qū)讀取項目并將它們返回給客戶機(jī)： 前言
構(gòu)建分布式優(yōu)先隊列
Item
topic
namespace
Enqueue
Dequeue
ack表示該item已退出隊列并已成功處理，不需要再次發(fā)送。 nack表示一個item應(yīng)該被重新投遞，因?yàn)榭蛻舳诵枰俅翁幚怼．?dāng)一個項被NACK時，是可以延遲處理的，允許客戶端在處理失敗的item時利用指數(shù)后退。此外，客戶端可以在nack上更新該item的元數(shù)據(jù)，以便在該item中存儲部分結(jié)果。 因?yàn)槊總€MySQL分片最多屬于一個FOQS主機(jī)，一個ack/nack請求需要落在分片對應(yīng)的主機(jī)上。由于shard ID編碼在每個item ID中，F(xiàn)OQS客戶端使用shard來定位主機(jī)。這個映射通過Shard Manager查找。 一旦ack/nack被路由到正確的主機(jī)，它就會被發(fā)送到特定分片的內(nèi)存緩沖區(qū)。worker從ack緩沖區(qū)中取出item，然后從MySQL分片中刪除這些行; 類似地，worker從nack緩沖區(qū)中提取item。但不是刪除，而是使用新的deliver_after時間和元數(shù)據(jù)(如果客戶端更新了它)更新item。如果ack或nack操作因?yàn)槿魏卧騺G失，例如MySQL不可用或FOQS節(jié)點(diǎn)崩潰，這些item將被考慮在租約到期后重新投遞。 Ack/Nack
Push vs. Pull
FOQS提供了一個基于拉的接口，消費(fèi)者使用dequeue API來獲取可用數(shù)據(jù)。為了理解在FOQS API中提供拉模型背后的動機(jī)，我們看看使用FOQS的作業(yè)的多樣性。它包括以下特征:
端到端延遲處理的需要：端到端處理延遲，是指item從準(zhǔn)備好到被消費(fèi)者從隊列中拉取消費(fèi)所經(jīng)歷的時間。快速消費(fèi)和緩慢消費(fèi)的作業(yè)混在一起。有的可以被毫秒級消費(fèi)，而有的會延遲好幾天。 處理速率 : topic對于item的消費(fèi)速率可能是不同的(每分鐘10個item到每分鐘1000多個item)。但是，根據(jù)下游資源在特定時間的可用性，可能有別于它們?nèi)粘５奶幚硭俣取?/span> 優(yōu)先級: topic級別或topic內(nèi)單個item級別的處理優(yōu)先級不同。 處理的位置 : 某些topic和item需要在特定的區(qū)域進(jìn)行處理，以確保它們與正在處理的數(shù)據(jù)的關(guān)聯(lián)性。
FOQS的大規(guī)模實(shí)踐
FOQS在過去幾年中經(jīng)歷了指數(shù)級的增長，現(xiàn)在每天處理近一萬億件產(chǎn)品。而處理的積壓訂單已經(jīng)達(dá)到數(shù)千億項，反映了系統(tǒng)處理能力普遍欠缺。為了處理這種規(guī)模，我們必須實(shí)現(xiàn)一些優(yōu)化。
檢查點(diǎn) CheckPointing
FOQS專門設(shè)置有后臺線程，來運(yùn)行比如延遲的item準(zhǔn)備投遞、租約過期和清除過期的item，這些操作依賴于記錄行中的時間戳字段。
比如，如果我們想更新所有準(zhǔn)備交付的item的狀態(tài)，來標(biāo)識它們已經(jīng)準(zhǔn)備好投遞，則需要一個查詢:
- where timestamp_column <= UNIX_TIMESTAMP() for update
對所有行進(jìn)行更新。
這種查詢的問題是MySQL需要用時間戳≲now 鎖定對所有行更新(不僅僅是符合條件的那些記錄)。、歷史越長，讀取查詢就越慢。
通過checkpoinging，F(xiàn)OQS在查詢上維護(hù)了一個下界(最后處理的已知時間戳)，它限定了where子句。where子句變成:
- WHERE <checkpoint> <= timestamp_column AND timestamp_column <= UNIX_TIMESTAMP()
通過在兩邊綁定查詢，表示歷史記錄的行數(shù)就會更少，從而使讀取(和更新)的總體性能更好。
災(zāi)備
Facebook的基礎(chǔ)設(shè)施需要能夠承受一整個數(shù)據(jù)中心發(fā)生異常。所以，每個FOQS MySQL分片被復(fù)制到兩個冗余的災(zāi)備集群?？鐓^(qū)復(fù)制是異步的，但是MySQL binlog以同步的方式持久化到同一區(qū)域的另一個災(zāi)備集群中。
如果數(shù)據(jù)中心需要被清空(或者M(jìn)ySQL數(shù)據(jù)庫正在進(jìn)行維護(hù))，MySQL主數(shù)據(jù)庫將暫時處于只讀模式，直到副本能夠和主節(jié)點(diǎn)同步。
這通常需要幾毫秒。一旦副本和主節(jié)點(diǎn)數(shù)據(jù)達(dá)到一致，副本就被提升為主節(jié)點(diǎn)。
而這時會變成MySQL的主節(jié)點(diǎn)在另一個區(qū)域，而分區(qū)被分配給該區(qū)域的FOQS主機(jī)。這將最大限度地減少跨區(qū)域的網(wǎng)絡(luò)流量，但相對來說比較昂貴。推動MySQL副本成為主節(jié)點(diǎn)的事件會導(dǎo)致跨地區(qū)的流量不平衡(一般來說，F(xiàn)OQS不能假設(shè)哪里有多少流量)。為了處理這些場景，F(xiàn)OQS不得不改進(jìn)它的路由，使入隊列路由到有足夠容量的主機(jī)，而出隊列路由到具有高優(yōu)先級item的主機(jī)。
FOQS本身使用的一些災(zāi)難可靠性優(yōu)化:
入隊轉(zhuǎn)發(fā): 如果入隊請求落在一個負(fù)載過重的主機(jī)上，F(xiàn)OQS將它轉(zhuǎn)發(fā)給另一個有處理能力的主機(jī)。 全局速率限制: 由于namespace是foqs的多租戶單元，所以每個namespace都有一個速率限制(計算為每分鐘排隊數(shù))。FOQS在全局(所有地區(qū))強(qiáng)制執(zhí)行這個速率限制。在一個特定的區(qū)域內(nèi)保證速率限制是不可能的，但是FOQS確實(shí)使用流量模式來嘗試將處理能力與流量配置在一起，以減少跨區(qū)域的流量。
Reference
facebook engineering: facebook工程師技術(shù)博客
