Facebook F4架構解讀：千億級圖片存儲Haystack的演進

首先說下 BLOB 的意思， 英文全稱是 Binary Large OBjects，可以理解為任意二進位格式的大對象；在 Facebook 的語境下，也就是用戶在賬戶里上傳的的圖片，視頻以及文檔等數據，這些數據具有一次創建，多次讀取，不會修改，偶爾刪除 的特點。

之前簡單翻譯了 Facebook 的前驅之作 —— Haystack，隨著業務量發展，數據量進一步增大，過去玩法又不轉了，如果所有 BLOG 都用 Haystack 存，由於其三備份的實現，在這個量級下，性價比很低。但是完全用網路掛載+傳統磁碟+Unix-like（POSIX）文件系統等冷存儲，讀取跟不上。於是計算機科學中最常用的分而治之的思想登場了。

他們首先統計了 BLOBs 的訪問頻次與創建時間的關係，然後提出了隨著時間推移 BLOB 訪問出現的冷熱分布概念（和長尾效應差不多）。並據此提出了熱、溫分開的訪問策略：用 HayStack 當做熱存儲去應對那些頻繁訪問的流量，然後用 F4 去響應剩下的不那麼頻繁訪問的 BLOB流量，在此假設（F4隻存儲那些基本不怎麼變動，訪問量相對不大的數據）前提下，可以大大簡化 F4 的設計。當然有個專門的路由層於兩者之上進行了屏蔽，並進行決策和路由。

對於 Haystack 來說，從其論文出來時，已經過去了七年（07~14）。相對於當時，做了少許更新，比如說去掉了 Flag 位，在 data file，Index file 之外，增加了 journal file，專門用來記錄被刪除的 BLOB 條目。

對於 F4 來說，主要設計目的在於保證容錯的前提下儘可能的減小有效冗餘倍數（effective-replication-factor），以應對日益增長的溫數據 存取需求。此外更加模塊化，可擴展性更好，即能以加機器方式平滑擴展應對數據的不斷增長。

我總結一下，本論文主要高光點就是溫熱分開，冗餘編碼，異地取或。

到2014年，Facebook 大概有超 4000 億張圖片。

論文的結論是，訪問頻度的熱力圖是存在的，創建時間是影響其變化關鍵因子，而且溫部數據是持續增長的。

論文的度量方法也很簡單，就是追蹤其網站上不同類型的 BLOB 數據的訪問頻次隨著創建時間變化曲線，創建時間小於一天的數據的訪問頻次大概是創建時間一年的數據的100多倍。具體數據就不列了，可以去 paper 里看。

然後論文探討了區分熱數據和溫數據的一個界限，通過對訪問頻次和刪除頻次隨著創建時間的變化的分析，對於大部分 BLOG，得到了一個的大概值：一個月。但是有兩個例外，一個是用戶頭像，一直是熱數據；另外一個普通圖片，使用三個月作為閾值。

熱數據總是那些頭部數據，相對來說增長較慢。但是歷史數據，也就是溫數據是隨著時間推移而尾巴越來越長，這勢必要求存儲架構進行相應的調整。

設計原則是讓每個組件儘可能簡單、內聚並且高度契合其要承擔的工作。這是從 UNIX 以來就一直在強調的一個原則。下圖是總體架構圖，包括創建（C1-C2，由 Haystack 負責），刪除（D1-D2，大部分是 Haystack 負責，少部分是 f4 負責）和讀取（R1-R4 由 Haystack 和 f4 共同負責）。

如前述論文 Haystack 所述，我們將一批 BLOG 集結為邏輯卷，儘可能減少 meta 信息，從而減少IO次數。每個邏輯卷我們設計了 100G 左右的容量，在滿之前是為 未鎖定 （unlocked） 的狀態，一旦達到容量，就變為鎖定（locked）狀態，只允許讀取和刪除。

每個卷包含三個文件，一個數據文件，一個索引文件和一個備忘文件（journal file）。和 Haystack 論文提到的一樣，數據文件就是記錄 BLOG 本身和其原信息，索引文件就是內存中的查找結構的快照。備忘文件是新增的，它通過記錄所有被刪除的 BLOG 的記錄來進行刪除操作。而原 Haystack 論文中，刪除文件是通過直接修改索引文件和數據文件來實現的。在未鎖定階段，三個文件均可讀寫，在鎖定階段，只有備忘文件可以讀寫，其他兩個文件都會變成只讀的。

控制模塊（Controller）

統籌整個系統，比如提供新的存儲機器；維持一個未鎖定卷（unlocked volumes ）的池子；確保所有邏輯卷有足夠的物理捲來備份；根據需求適時創建物理卷；進行周期性的維護任務，比如說數據緊縮（compaction）和垃圾回收。

路由層負責BLOB 存儲系統向對外提供介面，它屏蔽了系統底層的實現，使得可以方便添加如 f4 一樣的子系統。所有的路由層的機器角色都是一樣的，因為該層將所有狀態（如邏輯卷到物理卷的映射）都存在了另外的資料庫里（將所有相關狀態收集起來額外存儲，使得剩下的部分無狀態可以平滑擴展，這也是系統設計常用的原則）。這使得路由層的可以不依賴其他模塊來平滑擴展。

對於讀取請求，路由模塊會從 BLOB id 中解析出 邏輯卷 id，然後根據資料庫中讀出的映射關係來找到對應的所有物理卷信息。一般來說會從最近一個主機取數據，如果失敗的話，會產生一個超時事件，去下一個物理卷所在的主機進行嘗試。

對於創建請求，路由模塊會選取一個有空閑空間的邏輯卷，然後將 BLOB 發送到該邏輯卷對應的所有物理卷進行寫入（是並行發，還是鏈式發還是串列發？）如果遇到任何問題，就會中斷寫，並且已經寫入的數據會被廢棄，且戶重新挑選一個可用邏輯卷，重複上述過程。（看起來像並行寫，容錯策略也超級粗暴）

對於刪除請求，路由模塊會將其發送到所有對應的物理卷（然後就快速返回），然後對應物理主機程序會非同步的進行刪除，遇到錯誤就一直重試，直到成功刪除所有對應物理卷上的對應 BLOB。（倒也簡單，但不知道實現的時候是會寫入 journal file 後返回，還是只是在內存中標記下就返回。對應的數據文件上的 BLOB 肯定是在 compact 的時候才會刪掉）。

路由層通過將實現細節隱藏，使得（對用戶）無感知地構建溫存儲成為可能，當一個卷被從熱存儲移到溫存儲的時候，會在兩者上同時存在一段時間，直到有效（邏輯卷到物理卷）的映射被更新後，客戶端的請求將被無感知的地導向溫存儲。

轉換層負責處理對檢索到的 BLOB 數據的變換操作，比如圖片的縮放和裁剪。在 Facebook 的老版本的系統中，這些計算密集型的操作會在存儲節點上完成。

增加轉換層可以解放存儲節點，使其專註於提供存儲服務。將計算任務分離出來也有利於將存儲層和轉換層進行獨立的擴展。然後，它也可以讓我們精確地控制存儲節點的容量以恰好滿足需求。更進一步，也可以使我們針對不同任務類型進行更優的硬體選型。比如說我們可以將存儲節點設計為具有大量硬碟，但只有一個CPU和少量內存。

一開始是為了處理熱點 BLOB 數據的請求，緩解後端存儲系統的壓力。對於溫存儲來說，它也可以減小其請求壓力。這裡說的應該是 CDN 以及類似 akamai 內容分發商提供的緩存。

Haystack 開始是被設計來儘可能的提高 IOPS 的，通過攬下所有創建請求，大部分的刪除請求和高頻讀請求，使得溫存儲的設計可以大大簡化。

如相關 paper 提到的，Haystack 通過合併 BLOB 和簡化元信息使得 IOPS 大大提高。具體來說，包括將邏輯卷設計為集合了一批 BLOB 的單個文件，利用三個物理卷對同一個邏輯卷進行冗餘備份等等。

讀請求過來後，會在內存中拿到請求的 BLOB 的元信息，並且看其是否被刪除，然後通過物理文件位置+ offset + size ，僅進行一次 IO 拿到對應 BLOB 數據。

當主機收到創建請求後，會同步的將 BLOB 數據追加到數據文件上，然後更新內存中的元信息並將更改寫入索引文件和備忘文件中（備忘文件不是只記錄刪除操作嗎？）。

當主機收到刪除請求時，會更新索引文件和備忘文件。但是對應數據仍然存在於數據文件中，定期地我們會進行緊縮操作，才會真正的刪除數據，並回收相應空間。

Haystack 通過在一個數據中心的不同機架上各放一個副本，然後再不同數據中心再放一個副本的三副本策略獲得了對硬碟，主機，機架甚至數據中心的容錯能力。然後通過 RAID-6（1.2倍冗餘數據編碼，能夠小範圍的糾正錯誤，可以讀讀糾錯碼之類的文章）進行額外的硬碟容錯，更上一層保險。但是付出的代價是 3*1.2 = 3.6 倍的有效冗餘因子，這也是 Haystack 的局限之處，雖然最大化了 IOPS，但是在存儲使用上卻並不高效，造成了很多 BLOB 的數據冗餘。

有些類型的 BLOB 具有一定的過期時間，比如說用戶上傳的視頻，會從原始格式轉化為我們的存儲格式。在此之後原始視頻需要刪掉。我們會避免將此類具有過期時間的數據移動到 F4 上，從而讓 Haystack 負責這些頻繁的刪除請求，並通過頻繁緊縮來回收空間。

設計目標是在容錯的基礎上儘可能高效。也就是在能夠容忍硬碟錯誤，主機故障，機架問題，數據中心災難的前提下，把有效冗餘倍數降一降。

f4 是溫數據存儲架構的子系統。包含一系列 數據單元（cell），每個 cell 都在同一個數據中心（機房，datacenter）里。當前（2014）的 cell 包含 14 個機架，每個機架有15個主機，每個主機有三十塊 4T 容量的硬碟。cell 負責存儲邏輯卷，每個邏輯卷實際存儲時，會將數據利用里所碼（Reed-Solomon coding，簡稱RS，這是前面提到的RAID-6 標準的重要成員）進行冗餘編碼，比如 RS(n, k) 就是每存 n 個比特，就要編入額外的 k 個比特，以此來容忍最多 k 個比特的出錯。通過這種編碼方式可以解決硬碟，主機和機架出錯問題。

此外利用異或編碼（XOR coding）來解決跨數據中心或者地理位置的出錯問題。我們選取兩個不同機房的對等數量 volume/stripe/block 結成對子，然後將每一對的異或值存在第三個機房。

每個 f4 數據單元（cell） 只處理鎖定的卷（Volume），也就是只用支持讀取和刪除操作。數據文件和索引文件都是只讀的，Haystack 中的備忘文件在 f4 中是不存在的。我們用了另一種方式來達到「刪除」的效用，將每個 BLOB 進行加密後存儲，將用於加密的秘鑰（key）存在一個外部資料庫中。響應刪除請求時，只需要將 BLOB 對應的秘鑰刪掉就行（有點絕，對用戶提供了隱私保證，而且將刪除操作的延時降到很低）。

索引文件由於比較小，直接用了三副本存儲來保證可靠性，可以省去編解碼帶來的額外複雜度。數據文件用 n=10, k = 4 的里所碼進行編碼。具體來說，將每個數據文件切分為 n 個連續的數據塊（block），每個具有固定尺寸 b（最後一個塊不滿，而又寫不進去一個新 BLOB 的情況下，在結尾補零，類似這種打 padding 也是數據對齊常用的手法）；對於每 n 個這樣的塊，生成 k 個同樣尺寸的奇偶校驗塊（parity block），這樣 n+k 個數據塊構成一個邏輯上的 條帶（stripe）。同一條帶上的任意兩個塊互稱為兄弟塊（companion block）。正常讀取時，可以直接從數據塊中讀（我猜是那n個塊，不用額外進行計算還原，有待考證，還得看里所碼原理以及具體實現）。如果某些塊不可用了，就會在同一條帶上任取 n 塊，解碼後還原；此外還有個性質，就是讀取 n 個 block 上對應的 n 截數據（比如某個 BLOB），也可以進行解碼（這兩個性質都是編碼決定的，類似於 n 元線性方程組，有 k 個冗餘方程）。

通常 b 為 1G，即每個數據塊（Block）選取 1G 大小（這有個疑問，看起來每個Block仍在Volume中，而不是單獨拿出來，那麼定位一個物理block是不是就得通過 volume 文件打開句柄 + offset + length），選這麼大有兩方面的考慮，一個是盡量減小 BLOB 的跨塊概率，以減少讀取一個 BLOB 還得多次 IO 的頻率；另一個是降低 block 所需要維護的總元信息數量。不選更大的是因為重建起來會付出更大代價（但為什麼就是 1G 呢？）。

下圖是架構圖，接下來逐一介紹下各個模塊。

name node 維護了數據塊、奇偶校驗塊 到實際存儲這些塊的存儲節點（也就是下一節的存儲節點）之間的映射；這些映射（利用標準技術？還說參考了GFS，這沒大看懂，留個坑回頭讀 GFS 填上）分配到存儲節點中。名位元組點使用主從備份策略進行容錯。

存儲節點是 Cell 的主要組件，處理所有常規的讀取和刪除請求。對外暴露兩個 API：Index API 負責提供 Volume 的有無檢查和位置信息；File API 提供實際的數據訪問。（File API 與 Data API 的區別估計在於，前者是提供上層抽象 BLOB 的操作介面，而後者會暴露底層數據塊 Block 的訪問的介面）

存儲節點將 index file （包括BLOB到 volume 的映射，偏移量和長度）存在硬碟上，並且載入到自定義存儲結構的內存中。此外還維持了volume 偏移量到物理數據塊的映射（由於一個 volume 被整齊的切成了好多 block， 因此定位一個數據塊的邏輯位置，需要記下他的所在volume+offset）。上述兩個信息都被存在內存里，以避免硬碟 IO（似乎後面也有變化，index 也不小隨著ssd更便宜，存ssd也可以）。

由於每個 BLOB 都是加密過的，其秘鑰放在額外的存儲，通常是資料庫中。通過刪除其秘鑰就可以達到事實上的 BLOB 的刪除，這樣就避免了數據緊縮（為什麼可以不回收那些刪除空間呢，畢竟對於文存儲，刪除量只有很小一部分，之前的溫存儲的假設就用在這裡）；同時也省去了用備忘文件（journal file）來追蹤刪除信息。

下面說下讀取流程。首先通過 Index API 來檢查文件是否存在（R1過程），然後將請求轉到該 BLOB 所在的數據塊所在的存儲節點上。Data API 提供了對數據塊和奇偶校驗塊（parity block）的訪問。正常情況下的讀請求會被導向合適的存儲節點（R2流程），然後直接從該 BLOB 所在塊讀取它（R3）。在失敗的情況下，會通過 Data API 讀取損壞模塊中的所有 n+k 個兄弟模塊中完好的 n 個塊，送到回退節點（back-off node）進行重建。

在進行實際數據讀取（無論是 R1-R3 的正常流程還是 R1，R4，R5的出錯回退流程）的同時，路由層（route tier）會並行的從外部資料庫讀取該 BLOB 對應的秘鑰，然後在路由層進行解密操作，這是一個計算密集型任務，放在這裡可以讓數據層專註於存儲，並且兩層可以獨立的擴展。

回退節點（Backoff Nodes）

就是負責給出正常讀取流程出錯時的一種回退方案。

當 cell 中出現故障時，會有些塊變得不可用，就需要從其兄弟塊和奇偶校驗塊中進行在線恢復。回退模塊都是IO稀疏而計算密集型節點，來處理這些計算密集型的在線恢復操作。

回退模塊對外暴露 File API，以處理正常讀取失敗情況下的回退重試（R4）。在此時，讀取請求已經被一個主卷伺服器（primary volume-server，不過這是個什麼節點？）解析成了數據文件，偏移量和長度的元組，回退節點會向除損壞數據塊之外的 n-1 個兄弟塊和 k 個奇偶校驗塊中對應偏移量，讀取對應長度的信息。只要收到n個回應（估計是並行發？然後為了節省時間，收到任意n個回應就開始幹活，進行差錯糾正？）

當然了，回了照顧讀取延遲，每次進行在線回退讀糾錯的時候，都只恢復對應BLOB的數據而不是其所在的整個數據塊 Block 的信息。整個數據塊的恢復會交給重建節點（Rebuilder Nodes）離線的去做。

在民用物理機數目達到一定量級的情況下，硬碟和節點的故障是不可避免的。存儲在損壞模塊上的數據塊就需要進行重建。重建節點是存儲稀疏而計算密集型的，負責在後台默默地進行重建工作。每個重建節點通過探針（定期掃描其負責的範圍內的數據？還是在每個數據節點上安裝探針？）檢測數據塊錯誤，並且將其彙報到協調節點（Coordinator Nodes），然後通過取出同一條帶（Stripe）上兄弟塊和奇偶校驗塊中的沒有損壞過的n塊，對損壞節點進行重建（如果n+k中有其他模塊壞了估計也一併重建吧）。這是一個很重的處理過程，並且會給存儲節點帶來極大的網路和 IO 負載。因此重建節點會對其吞吐量進行限流，以防對正常的用戶請求造成不利影響。而統籌調度重建工作，以盡量減小數據丟失的風險，則是協調節點的工作。

一個數據單元（cell）需要很多日常的運維任務，比如安排（大概就是確定一個重建順序，並且在不同的重建節點間進行分配吧）損壞的數據塊重建，調整當前的數據分布以儘可能減小數據的不可用概率。協調節點也是存儲稀疏計算密集型的，用來執行數據單元範圍的任務。

如之前提到的，一個數據條帶上的不同數據塊需要被分散放置於不同的數據容錯區域內以最大化可靠性。然而，在經過故障，重建和替換後，肯定會有一些不符合上述原則的情況，比如兩個同條帶上的數據塊被放在了同一個數據容錯區域中。協調節點會運行一個平衡擺放位置的進程去檢查一個數據單元中的數據塊分布。和重建操作一樣，也會給存儲節點帶來相當大的額外硬碟和網路負載，因此協調節點也會進行自我限流以減小對正常請求的影響。

單個 f4 的數據單元都存在一個數據中心中，因此難以抵禦數據中心的故障。於是在開始的時候，我們將兩份同樣的數據單元放在不同的數據中心中，這樣一個損壞仍然可以利用另一個對請求進行響應。這樣將有效冗餘因子從 Haystack 的 3.6 降低到了 2.8 。

考慮到數據中心級別的故障還是很稀少的，我們找到了一種可以進一步減小有效冗餘因子的方案——當然，也減小了吞吐率。不過，現在XOR方案可以將有效冗餘因子進一步做到 2.1。

地理備份異或編碼（XOR coding）方案通過將兩個不同的卷（Volume，大小一樣）做異或後的結果放在第三個數據中心的方式，提供了數據中心級別的容錯。如圖9一樣，每個數據卷中的數據塊和奇偶校驗塊被與等量的其他數據塊或者奇偶校驗塊（稱為哥們塊，buddy block）被拿來做異或運算，得到其異或塊（XOR block）。這些異或模塊的索引也是簡單的三備份存儲。

一旦某個 datacenter出現問題導致整個 volume 不可用，讀取請求會被路由到一個叫做 geo-bakoff node ，然後會從兩個 buddy node 和 XOR node 所在數據中心去取對應 BLOB 數據，進行損壞 BLOB的重建。選擇XOR編碼，當然是簡單又能滿足需求。

負載因子的計算，(1.4 * 3) / 2 = 2.1

基本思想大概就這些，剩下的不翻了。但是論文說的有點啰嗦，同一個點在不同地方說了好幾遍，但同時一個模塊有時又分散在不同模塊中，不好連成一個整體，在這裡，我簡單總結一下。

一個數據單元（cell）存在一個數據中心中，包含 14 個機架。一個邏輯上的卷 （Volume），大約 100G，被分為 100 個 1G 的數據塊（Block）；然後每 10 個數據塊作為一組（Companion Block）進行數據冗餘編碼（RS編碼）後，產生 4 個新的奇偶校驗塊（Parity Block），這 14 個數據塊+奇偶校驗塊稱為一個條帶（stripe），被分別放置在不同機架上以進行容錯。其中哪些數據塊屬於一組的映射關係在名位元組點（ Name Node） 中維持著。

在存儲節點上，內存中需要維護兩個映射作為 index 信息，一個是 BLOB id 到 volume，偏移量和大小的映射，一個是 volume 偏移量到 Block 實際物理位置的映射。當讀請求失敗的時候，讀取請求連同一些元信息（比如所在數據塊 id，以及在其上的偏移量）被導向回退節點（Backoff Node）。回退節點會根據 BLOB id 所在的 Block id 在 Name Node 拿到條帶上其他數據塊位置信息，以及偏移量，只對該 BLOB 的所有對等數據進行解碼，還原出該 BLOB 後返回。

此外，協調節點（Coordinator Nodes）會根據探針的心跳信息，得到全局數據分布和狀態信息。協調節點據此將損壞的模塊交給重建節點（Rebuilder Nodes）進行數據重建；並且平衡、維持條帶上的所有塊被放在不同的數據容錯閾。

最後，在兩個不同數據中心的將所有數據塊配對後，進行異或（XOR）操作，得到一個異或結果，放在第三個數據中心。這樣，這三個數據中心的任何數據條帶損壞到 RS 碼都無法拯救的情況下（比如有四個以上機架出問題了），就可以通過其他兩個數據中心數據進行 XOR 操作來搶救一下。

術語解釋：

數據文件（data file）：存儲一堆 BLOB 和其元信息的的文件

索引文件（index file）：記錄 BLOB 在數據文件偏移量，長度和簡單信息的文件，用來快速 seek 取出 BLOB。

備忘文件（journal file）：在 Haystack 中，用於記錄所有的刪除請求。

有效備份因子，有效冗餘倍數（effective-replica-factor）：實際佔用的物理空間和要存的邏輯數據大小之間的比值。

兄弟模塊，夥伴模塊（companion block）：用於編碼的 n+k 個數據塊中那 n 個模塊的稱呼。

奇偶校驗塊（parity block）：用於編碼 n+k 個數據塊中那 k 個模塊的稱呼

溫存儲（warm storage）：相對於熱存儲，指那些專門針對訪問頻次不怎麼高的數據所構建的存儲。

存儲節點，存儲機器（storage nodes，storage machines）：都是指的負責存儲最終數據的的物理機。

緊縮（compact）：Haystack 中會定期地檢查數據文件，將其複製一遍，但是略過所有重複和已經標記刪除的數據，從而回收對應空間。

副本，備份（replica）：一種冗餘策略，廉價通用型機器上免不了出錯，為了留有後手進行恢復，最常用策略就是多存幾份了，這幾份同樣的數據成為多副本或者多備份。

秘鑰（encryption key）：用來給 BLOB 進行加密的鍵

回退模塊（backoff node）：其實我覺得翻譯成兜底模塊也挺好哈哈，就是應對出錯，取 n 個兄弟塊來進行恢復的。

數據單元（cell）：由14個機架，每個機架上有15台機器組成的一個數據部署和回滾的的單元。

數據卷（volume）：分邏輯卷和物理卷，包含多個數據條帶。

數據條帶（stripe）：原始n個數據塊和生成的k個奇偶校驗塊所組成的集合，稱為條帶。

數據塊（block）：一般是1G左右，被分散在不同容錯單元中。

本文作者穆尼奧，授權高可用架構發表，點擊閱讀原文了解更多詳情。

參考閱讀：

• 10行代碼理解Java鎖消除

• 未來架構| 雲原生時代的分散式事務

• 5分鐘了解Java 12 八大新特性

• 主流微服務註冊中心淺析和對比

• 一圖了解Google工具棧

活動預告：

隨著Cloud-Native、IoT、人工智慧等前沿技術、數據及商業智能、工程文化及管理、大中台、經典架構等熱門技術的突飛猛進，互聯網系統架構又有了更廣闊的發展空間。6月21-23日，由msup和高可用架構技術社區聯合舉辦的第五屆GIAC將在深圳舉辦！

GIAC是長期關注互聯網技術與架構的高可用架構技術社區，面向架構師、技術負責人及高端技術從業人員的年度技術架構大會，累計超過4500位技術團隊帶頭人參與，是中國規模最大的技術會議之一。

參加 GIAC，盤點2019年最新技術，目前購買7.5折優惠，多人購買有更多優惠。識別二維碼了解大會更多詳情。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！