導讀:Facebook在OSDI 2014上發表論文f4: Facebook’s Warm BLOB Storage System,這個系統主要目的就是降低儲存成本,在容忍磁碟,主機,機架等故障的同時,保證一定的可用性。該系統用於儲存介於冷熱資料之間的溫資料,國內對於溫資料的儲存研究較少,Facebook實現該系統的思路十分值得深入研究。
概覽
首先說下 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)和垃圾回收。
路由層(Route Tier)
路由層負責BLOB 儲存系統向對外提供介面,它遮蔽了系統底層的實現,使得可以方便新增如 f4 一樣的子系統。所有的路由層的機器角色都是一樣的,因為該層將所有狀態(如邏輯捲到物理捲的對映)都存在了另外的資料庫裡(將所有相關狀態收集起來額外儲存,使得剩下的部分無狀態可以平滑擴充套件,這也是系統設計常用的原則)。這使得路由層的可以不依賴其他模組來平滑擴充套件。
對於讀取請求,路由模組會從 BLOB id 中解析出 邏輯捲 id,然後根據資料庫中讀出的對映關係來找到對應的所有物理捲資訊。一般來說會從最近一個主機取資料,如果失敗的話,會產生一個超時事件,去下一個物理捲所在的主機進行嘗試。
對於建立請求,路由模組會選取一個有空閑空間的邏輯捲,然後將 BLOB 傳送到該邏輯捲對應的所有物理捲進行寫入(是並行發,還是鏈式發還是序列發?)如果遇到任何問題,就會中斷寫,並且已經寫入的資料會被廢棄,且戶重新挑選一個可用邏輯捲,重覆上述過程。(看起來像並行寫,容錯策略也超級粗暴)
對於刪除請求,路由模組會將其傳送到所有對應的物理捲(然後就快速傳回),然後對應物理主機程式會非同步的進行刪除,遇到錯誤就一直重試,直到成功刪除所有對應物理捲上的對應 BLOB。(倒也簡單,但不知道實現的時候是會寫入 journal file 後傳回,還是隻是在記憶體中標記下就傳回。對應的資料檔案上的 BLOB 肯定是在 compact 的時候才會刪掉)。
路由層透過將實現細節隱藏,使得(對使用者)無感知地構建溫儲存成為可能,當一個捲被從熱儲存移到溫儲存的時候,會在兩者上同時存在一段時間,直到有效(邏輯捲到物理捲)的對映被更新後,客戶端的請求將被無感知的地導向溫儲存。
轉換層(Transformer Tier)
轉換層負責處理對檢索到的 BLOB 資料的變換操作,比如圖片的縮放和裁剪。在 Facebook 的老版本的系統中,這些計算密集型的操作會在儲存節點上完成。
增加轉換層可以解放儲存節點,使其專註於提供儲存服務。將計算任務分離出來也有利於將儲存層和轉換層進行獨立的擴充套件。然後,它也可以讓我們精確地控制儲存節點的容量以恰好滿足需求。更進一步,也可以使我們針對不同任務型別進行更優的硬體選型。比如說我們可以將儲存節點設計為具有大量硬碟,但只有一個CPU和少量記憶體。
快取棧(Caching Stack)
一開始是為了處理熱點 BLOB 資料的請求,緩解後端儲存系統的壓力。對於溫儲存來說,它也可以減小其請求壓力。這裡說的應該是 CDN 以及類似 akamai 內容分發商提供的快取。
Haystack 熱儲存(Hot Storage with Haystack)
Haystack 開始是被設計來盡可能的提高 IOPS 的,透過攬下所有建立請求,大部分的刪除請求和高頻讀請求,使得溫儲存的設計可以大大簡化。
如相關 paper 提到的,Haystack 透過合併 BLOB 和簡化元資訊使得 IOPS 大大提高。具體來說,包括將邏輯捲設計為集合了一批 BLOB 的單個檔案,利用三個物理捲對同一個邏輯捲進行冗餘備份等等。
讀請求過來後,會在記憶體中拿到請求的 BLOB 的元資訊,並且看其是否被刪除,然後透過物理檔案位置+ offset + size ,僅進行一次 IO 拿到對應 BLOB 資料。
當主機收到建立請求後,會同步的將 BLOB 資料追加到資料檔案上,然後更新記憶體中的元資訊並將更改寫入索引檔案和備忘檔案中(備忘檔案不是隻記錄刪除操作嗎?)。
當主機收到刪除請求時,會更新索引檔案和備忘檔案。但是對應資料仍然存在於資料檔案中,定期地我們會進行緊縮操作,才會真正的刪除資料,並回收相應空間。
容錯(Fault tolerance)
Haystack 透過在一個資料中心的不同機架上各放一個副本,然後再不同資料中心再放一個副本的三副本策略獲得了對硬碟,主機,機架甚至資料中心的容錯能力。然後透過 RAID-6(1.2倍冗餘資料編碼,能夠小範圍的糾正錯誤,可以讀讀糾錯碼之類的文章)進行額外的硬碟容錯,更上一層保險。但是付出的代價是 3*1.2 = 3.6 倍的有效冗餘因子,這也是 Haystack 的侷限之處,雖然最大化了 IOPS,但是在儲存使用上卻並不高效,造成了很多 BLOB 的資料冗餘。
暫存內容驅動(Expiry-Driven Content)
有些型別的 BLOB 具有一定的過期時間,比如說使用者上傳的影片,會從原始格式轉化為我們的儲存格式。在此之後原始影片需要刪掉。我們會避免將此類具有過期時間的資料移動到 F4 上,從而讓 Haystack 負責這些頻繁的刪除請求,並透過頻繁緊縮來回收空間。
f4 設計
設計標的是在容錯的基礎上盡可能高效。也就是在能夠容忍硬碟錯誤,主機故障,機架問題,資料中心災難的前提下,把有效冗餘倍數降一降。
f4 概覽(f4 Overview)
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(Individual f4 Cell)
每個 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)
name node 維護了資料塊、奇偶校驗塊 到實際儲存這些塊的儲存節點(也就是下一節的儲存節點)之間的對映;這些對映(利用標準技術?還說參考了GFS,這沒大看懂,留個坑回頭讀 GFS 填上)分配到儲存節點中。名位元組點使用主從備份策略進行容錯。
儲存節點(Storage Nodes)
儲存節點是 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)離線的去做。
重建節點(Rebuilder Nodes)
在民用物理機數目達到一定量級的情況下,硬碟和節點的故障是不可避免的。儲存在損壞模組上的資料塊就需要進行重建。重建節點是儲存稀疏而計算密集型的,負責在後臺默默地進行重建工作。每個重建節點透過探針(定期掃描其負責的範圍內的資料?還是在每個資料節點上安裝探針?)檢測資料塊錯誤,並且將其彙報到協調節點(Coordinator Nodes),然後透過取出同一條帶(Stripe)上兄弟塊和奇偶校驗塊中的沒有損壞過的n塊,對損壞節點進行重建(如果n+k中有其他模組壞了估計也一併重建吧)。這是一個很重的處理過程,並且會給儲存節點帶來極大的網路和 IO 負載。因此重建節點會對其吞吐量進行限流,以防對正常的使用者請求造成不利影響。而統籌排程重建工作,以儘量減小資料丟失的風險,則是協調節點的工作。
協調節點(Coordinator Nodes)
一個資料單元(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左右,被分散在不同容錯單元中。
本文作者穆尼奧,授權高可用架構發表,點選閱讀原文瞭解更多詳情。
朋友會在“發現-看一看”看到你“在看”的內容