Facebook 有序隊列服務設計原理和高性能淺析

【CSDN 編者按】作爲全球最領先的社交網絡，Facebook 的高性能集羣系統承擔了海量數據的處理，它的服務器架構一直爲業界人所關注。

作者 | Coder 的技術之路

責編 | 歐陽姝黎

出品 | CSDN（ID：CSDNnews）

前言

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

FOQS 在 Facebook 上支持數百個服務，包括:

Async (Facebook 的異步計算平臺)，是 Facebook 上廣泛使用的通用異步計算平臺。它提供了各種功能，從通知到完整性檢查，再到爲任務計劃執行，利用 FOQS 的能力來存儲大量作業的積壓，推遲作業運行，從而達到削峯填谷。
視頻編碼服務，支持異步視頻編碼服務。當視頻被上傳時，它們被分解成多個組件，每個組件存儲在 FOQS 中，然後進行處理。
語言翻譯技術，爲語言間的帖子翻譯提供了支持。這種工作在計算上可能非常昂貴，通過將其分解爲多個作業，存儲在 FOQS 中，並由 workers 並行運行而從並行化中獲益等。

facebook engineering[1]

構建分佈式優先隊列

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

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

Push vs. Pull

FOQS 提供了一個基於拉的接口，消費者使用 dequeue API 來獲取可用數據。爲了理解在 FOQS API 中提供拉模型背後的動機，我們看看使用 FOQS 的作業的多樣性。它包括以下特徵:

FOQS 的大規模實踐

FOQS 在過去幾年中經歷了指數級的增長，現在每天處理近一萬億件產品。而處理的積壓訂單已經達到數千億項，反映了系統處理能力普遍欠缺。爲了處理這種規模，我們必須實現一些優化。檢查點 CheckPointing

FOQS 專門設置有後臺線程，來運行比如延遲的 item 準備投遞、租約過期和清除過期的 item，這些操作依賴於記錄行中的時間戳字段。

比如，如果我們想更新所有準備交付的 item 的狀態，來標識它們已經準備好投遞，則需要一個查詢:

where timestamp_column <= UNIX_TIMESTAMP() for update

對所有行進行更新。

這種查詢的問題是 MySQL 需要用時間戳≲now 鎖定對所有行更新 (不僅僅是符合條件的那些記錄)。、歷史越長，讀取查詢就越慢。

通過 checkpoinging，FOQS 在查詢上維護了一個下界 (最後處理的已知時間戳)，它限定了 where 子句。where 子句變成:

WHERE <checkpoint> <= timestamp_column AND timestamp_column <= UNIX_TIMESTAMP()

通過在兩邊綁定查詢，表示歷史記錄的行數就會更少，從而使讀取 (和更新) 的總體性能更好。

災備

Facebook 的基礎設施需要能夠承受一整個數據中心發生異常。所以，每個 FOQS MySQL 分片被複制到兩個冗餘的災備集羣。跨區複製是異步的，但是 MySQL binlog 以同步的方式持久化到同一區域的另一個災備集羣中。

如果數據中心需要被清空 (或者 MySQL 數據庫正在進行維護)，MySQL 主數據庫將暫時處於只讀模式，直到副本能夠和主節點同步。

這通常需要幾毫秒。一旦副本和主節點數據達到一致，副本就被提升爲主節點。

而這時會變成 MySQL 的主節點在另一個區域，而分區被分配給該區域的 FOQS 主機。這將最大限度地減少跨區域的網絡流量，但相對來說比較昂貴。推動 MySQL 副本成爲主節點的事件會導致跨地區的流量不平衡 (一般來說，FOQS 不能假設哪裏有多少流量)。爲了處理這些場景，FOQS 不得不改進它的路由，使入隊列路由到有足夠容量的主機，而出隊列路由到具有高優先級 item 的主機。

FOQS 本身使用的一些災難可靠性優化:

入隊轉發: 如果入隊請求落在一個負載過重的主機上，FOQS 將它轉發給另一個有處理能力的主機。
全局速率限制: 由於 namespace 是 foqs 的多租戶單元，所以每個 namespace 都有一個速率限制 (計算爲每分鐘排隊數)。FOQS 在全局(所有地區) 強制執行這個速率限制。在一個特定的區域內保證速率限制是不可能的，但是 FOQS 確實使用流量模式來嘗試將處理能力與流量配置在一起，以減少跨區域的流量。

Reference

[1]facebook engineering: facebook 工程師技術博客

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/F3mfoJHID1JKoh7rN-yQGw

前言