[[263398]]

概覽

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

之前簡單翻譯了 Facebook 的前驅(qū)之作 —— Haystack，隨著業(yè)務(wù)量發(fā)展，數(shù)據(jù)量進一步增大，過去玩法又不轉(zhuǎn)了，如果所有 BLOG 都用 Haystack 存，由于其三備份的實現(xiàn)，在這個量級下，性價比很低。但是完全用網(wǎng)絡(luò)掛載+傳統(tǒng)磁盤+Unix-like(POSIX)文件系統(tǒng)等冷存儲，讀取跟不上。于是計算機科學(xué)中最常用的分而治之的思想登場了。

他們首先統(tǒng)計了 BLOBs 的訪問頻次與創(chuàng)建時間的關(guān)系，然后提出了隨著時間推移 BLOB 訪問出現(xiàn)的冷熱分布概念(和長尾效應(yīng)差不多)。并據(jù)此提出了熱、溫分開的訪問策略：用 HayStack 當(dāng)做熱存儲去應(yīng)對那些頻繁訪問的流量，然后用 F4 去響應(yīng)剩下的不那么頻繁訪問的 BLOB流量，在此假設(shè)(F4只存儲那些基本不怎么變動，訪問量相對不大的數(shù)據(jù))前提下，可以大大簡化 F4 的設(shè)計。當(dāng)然有個專門的路由層于兩者之上進行了屏蔽，并進行決策和路由。

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

對于 F4 來說，主要設(shè)計目的在于保證容錯的前提下盡可能的減小有效冗余倍數(shù)(effective-replication-factor)，以應(yīng)對日益增長的溫數(shù)據(jù) 存取需求。此外更加模塊化，可擴展性更好，即能以加機器方式平滑擴展應(yīng)對數(shù)據(jù)的不斷增長。

我總結(jié)一下，本論文主要高光點就是溫?zé)岱珠_，冗余編碼，異地取或。

數(shù)據(jù)量級

到2014年，F(xiàn)acebook 大概有超 4000 億張圖片。

訪問頻度的熱力圖

論文的結(jié)論是，訪問頻度的熱力圖是存在的，創(chuàng)建時間是影響其變化關(guān)鍵因子，而且溫部數(shù)據(jù)是持續(xù)增長的。

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

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

熱數(shù)據(jù)總是那些頭部數(shù)據(jù)，相對來說增長較慢。但是歷史數(shù)據(jù)，也就是溫數(shù)據(jù)是隨著時間推移而尾巴越來越長，這勢必要求存儲架構(gòu)進行相應(yīng)的調(diào)整。

存儲系統(tǒng)總體架構(gòu)

設(shè)計原則是讓每個組件盡可能簡單、內(nèi)聚并且高度契合其要承擔(dān)的工作。這是從 UNIX 以來就一直在強調(diào)的一個原則。下圖是總體架構(gòu)圖，包括創(chuàng)建(C1-C2，由 Haystack 負責(zé))，刪除(D1-D2，大部分是 Haystack 負責(zé)，少部分是 f4 負責(zé))和讀取(R1-R4 由 Haystack 和 f4 共同負責(zé))。

如前述論文 Haystack 所述，我們將一批 BLOG 集結(jié)為邏輯卷，盡可能減少 meta 信息，從而減少IO次數(shù)。每個邏輯卷我們設(shè)計了 100G 左右的容量，在滿之前是為 未鎖定 (unlocked) 的狀態(tài)，一旦達到容量，就變?yōu)殒i定(locked)狀態(tài)，只允許讀取和刪除。

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

控制模塊(Controller)

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

路由層(Route Tier)

路由層負責(zé)BLOB 存儲系統(tǒng)向?qū)ν馓峁┙涌冢帘瘟讼到y(tǒng)底層的實現(xiàn)，使得可以方便添加如 f4 一樣的子系統(tǒng)。所有的路由層的機器角色都是一樣的，因為該層將所有狀態(tài)(如邏輯卷到物理卷的映射)都存在了另外的數(shù)據(jù)庫里(將所有相關(guān)狀態(tài)收集起來額外存儲，使得剩下的部分無狀態(tài)可以平滑擴展，這也是系統(tǒng)設(shè)計常用的原則)。這使得路由層的可以不依賴其他模塊來平滑擴展。

對于讀取請求，路由模塊會從 BLOB id 中解析出 邏輯卷 id，然后根據(jù)數(shù)據(jù)庫中讀出的映射關(guān)系來找到對應(yīng)的所有物理卷信息。一般來說會從最近一個主機取數(shù)據(jù)，如果失敗的話，會產(chǎn)生一個超時事件，去下一個物理卷所在的主機進行嘗試。

對于創(chuàng)建請求，路由模塊會選取一個有空閑空間的邏輯卷，然后將 BLOB 發(fā)送到該邏輯卷對應(yīng)的所有物理卷進行寫入(是并行發(fā)，還是鏈?zhǔn)桨l(fā)還是串行發(fā)?)如果遇到任何問題，就會中斷寫，并且已經(jīng)寫入的數(shù)據(jù)會被廢棄，且戶重新挑選一個可用邏輯卷，重復(fù)上述過程。(看起來像并行寫，容錯策略也超級粗暴)

對于刪除請求，路由模塊會將其發(fā)送到所有對應(yīng)的物理卷(然后就快速返回)，然后對應(yīng)物理主機程序會異步的進行刪除，遇到錯誤就一直重試，直到成功刪除所有對應(yīng)物理卷上的對應(yīng) BLOB。(倒也簡單，但不知道實現(xiàn)的時候是會寫入 journal file 后返回，還是只是在內(nèi)存中標(biāo)記下就返回。對應(yīng)的數(shù)據(jù)文件上的 BLOB 肯定是在 compact 的時候才會刪掉)。

路由層通過將實現(xiàn)細節(jié)隱藏，使得(對用戶)無感知地構(gòu)建溫存儲成為可能，當(dāng)一個卷被從熱存儲移到溫存儲的時候，會在兩者上同時存在一段時間，直到有效(邏輯卷到物理卷)的映射被更新后，客戶端的請求將被無感知的地導(dǎo)向溫存儲。

轉(zhuǎn)換層(Transformer Tier)

轉(zhuǎn)換層負責(zé)處理對檢索到的 BLOB 數(shù)據(jù)的變換操作，比如圖片的縮放和裁剪。在 Facebook 的老版本的系統(tǒng)中，這些計算密集型的操作會在存儲節(jié)點上完成。

增加轉(zhuǎn)換層可以解放存儲節(jié)點，使其專注于提供存儲服務(wù)。將計算任務(wù)分離出來也有利于將存儲層和轉(zhuǎn)換層進行獨立的擴展。然后，它也可以讓我們精確地控制存儲節(jié)點的容量以恰好滿足需求。更進一步，也可以使我們針對不同任務(wù)類型進行更優(yōu)的硬件選型。比如說我們可以將存儲節(jié)點設(shè)計為具有大量硬盤，但只有一個CPU和少量內(nèi)存。

緩存棧(Caching Stack)

一開始是為了處理熱點 BLOB 數(shù)據(jù)的請求，緩解后端存儲系統(tǒng)的壓力。對于溫存儲來說，它也可以減小其請求壓力。這里說的應(yīng)該是 CDN 以及類似 akamai 內(nèi)容分發(fā)商提供的緩存。

Haystack 熱存儲(Hot Storage with Haystack)

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

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

讀請求過來后，會在內(nèi)存中拿到請求的 BLOB 的元信息，并且看其是否被刪除，然后通過物理文件位置+ offset + size ，僅進行一次 IO 拿到對應(yīng) BLOB 數(shù)據(jù)。

當(dāng)主機收到創(chuàng)建請求后，會同步的將 BLOB 數(shù)據(jù)追加到數(shù)據(jù)文件上，然后更新內(nèi)存中的元信息并將更改寫入索引文件和備忘文件中(備忘文件不是只記錄刪除操作嗎?)。

當(dāng)主機收到刪除請求時，會更新索引文件和備忘文件。但是對應(yīng)數(shù)據(jù)仍然存在于數(shù)據(jù)文件中，定期地我們會進行緊縮操作，才會真正的刪除數(shù)據(jù)，并回收相應(yīng)空間。

容錯(Fault tolerance)

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

暫存內(nèi)容驅(qū)動(Expiry-Driven Content)

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

f4 設(shè)計

設(shè)計目標(biāo)是在容錯的基礎(chǔ)上盡可能高效。也就是在能夠容忍硬盤錯誤，主機故障，機架問題，數(shù)據(jù)中心災(zāi)難的前提下，把有效冗余倍數(shù)降一降。

f4 概覽(f4 Overview)

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

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

單個 f4 cell(Individual f4 Cell)

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

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

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

下圖是架構(gòu)圖，接下來逐一介紹下各個模塊。

名字節(jié)點(Name Node)

name node 維護了數(shù)據(jù)塊、奇偶校驗塊 到實際存儲這些塊的存儲節(jié)點(也就是下一節(jié)的存儲節(jié)點)之間的映射;這些映射(利用標(biāo)準(zhǔn)技術(shù)?還說參考了GFS，這沒大看懂，留個坑回頭讀 GFS 填上)分配到存儲節(jié)點中。名字節(jié)點使用主從備份策略進行容錯。

存儲節(jié)點(Storage Nodes)

存儲節(jié)點是 Cell 的主要組件，處理所有常規(guī)的讀取和刪除請求。對外暴露兩個 API：Index API 負責(zé)提供 Volume 的有無檢查和位置信息;File API 提供實際的數(shù)據(jù)訪問。(File API 與 Data API 的區(qū)別估計在于，前者是提供上層抽象 BLOB 的操作接口，而后者會暴露底層數(shù)據(jù)塊 Block 的訪問的接口)

存儲節(jié)點將 index file (包括BLOB到 volume 的映射，偏移量和長度)存在硬盤上，并且加載到自定義存儲結(jié)構(gòu)的內(nèi)存中。此外還維持了volume 偏移量到物理數(shù)據(jù)塊的映射(由于一個 volume 被整齊的切成了好多 block， 因此定位一個數(shù)據(jù)塊的邏輯位置，需要記下他的所在volume+offset)。上述兩個信息都被存在內(nèi)存里，以避免硬盤 IO(似乎后面也有變化，index 也不小隨著ssd更便宜，存ssd也可以)。

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

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

在進行實際數(shù)據(jù)讀取(無論是 R1-R3 的正常流程還是 R1，R4，R5的出錯回退流程)的同時，路由層(route tier)會并行的從外部數(shù)據(jù)庫讀取該 BLOB 對應(yīng)的秘鑰，然后在路由層進行解密操作，這是一個計算密集型任務(wù)，放在這里可以讓數(shù)據(jù)層專注于存儲，并且兩層可以獨立的擴展。

回退節(jié)點(Backoff Nodes)

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

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

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

當(dāng)然了，回了照顧讀取延遲，每次進行在線回退讀糾錯的時候，都只恢復(fù)對應(yīng)BLOB的數(shù)據(jù)而不是其所在的整個數(shù)據(jù)塊 Block 的信息。整個數(shù)據(jù)塊的恢復(fù)會交給重建節(jié)點(Rebuilder Nodes)離線的去做。

重建節(jié)點(Rebuilder Nodes)

在民用物理機數(shù)目達到一定量級的情況下，硬盤和節(jié)點的故障是不可避免的。存儲在損壞模塊上的數(shù)據(jù)塊就需要進行重建。重建節(jié)點是存儲稀疏而計算密集型的，負責(zé)在后臺默默地進行重建工作。每個重建節(jié)點通過探針(定期掃描其負責(zé)的范圍內(nèi)的數(shù)據(jù)?還是在每個數(shù)據(jù)節(jié)點上安裝探針?)檢測數(shù)據(jù)塊錯誤，并且將其匯報到協(xié)調(diào)節(jié)點(Coordinator Nodes)，然后通過取出同一條帶(Stripe)上兄弟塊和奇偶校驗塊中的沒有損壞過的n塊，對損壞節(jié)點進行重建(如果n+k中有其他模塊壞了估計也一并重建吧)。這是一個很重的處理過程，并且會給存儲節(jié)點帶來極大的網(wǎng)絡(luò)和 IO 負載。因此重建節(jié)點會對其吞吐量進行限流，以防對正常的用戶請求造成不利影響。而統(tǒng)籌調(diào)度重建工作，以盡量減小數(shù)據(jù)丟失的風(fēng)險，則是協(xié)調(diào)節(jié)點的工作。

協(xié)調(diào)節(jié)點(Coordinator Nodes)

一個數(shù)據(jù)單元(cell)需要很多日常的運維任務(wù)，比如安排(大概就是確定一個重建順序，并且在不同的重建節(jié)點間進行分配吧)損壞的數(shù)據(jù)塊重建，調(diào)整當(dāng)前的數(shù)據(jù)分布以盡可能減小數(shù)據(jù)的不可用概率。協(xié)調(diào)節(jié)點也是存儲稀疏計算密集型的，用來執(zhí)行數(shù)據(jù)單元范圍的任務(wù)。

如之前提到的，一個數(shù)據(jù)條帶上的不同數(shù)據(jù)塊需要被分散放置于不同的數(shù)據(jù)容錯區(qū)域內(nèi)以***化可靠性。然而，在經(jīng)過故障，重建和替換后，肯定會有一些不符合上述原則的情況，比如兩個同條帶上的數(shù)據(jù)塊被放在了同一個數(shù)據(jù)容錯區(qū)域中。協(xié)調(diào)節(jié)點會運行一個平衡擺放位置的進程去檢查一個數(shù)據(jù)單元中的數(shù)據(jù)塊分布。和重建操作一樣，也會給存儲節(jié)點帶來相當(dāng)大的額外硬盤和網(wǎng)絡(luò)負載，因此協(xié)調(diào)節(jié)點也會進行自我限流以減小對正常請求的影響。

地理備份

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

考慮到數(shù)據(jù)中心級別的故障還是很***的，我們找到了一種可以進一步減小有效冗余因子的方案——當(dāng)然，也減小了吞吐率。不過，現(xiàn)在XOR方案可以將有效冗余因子進一步做到 2.1。

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

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

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

簡單總結(jié)

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

一個數(shù)據(jù)單元(cell)存在一個數(shù)據(jù)中心中，包含 14 個機架。一個邏輯上的卷 (Volume)，大約 100G，被分為 100 個 1G 的數(shù)據(jù)塊(Block);然后每 10 個數(shù)據(jù)塊作為一組(Companion Block)進行數(shù)據(jù)冗余編碼(RS編碼)后，產(chǎn)生 4 個新的奇偶校驗塊(Parity Block)，這 14 個數(shù)據(jù)塊+奇偶校驗塊稱為一個條帶(stripe)，被分別放置在不同機架上以進行容錯。其中哪些數(shù)據(jù)塊屬于一組的映射關(guān)系在名字節(jié)點( Name Node) 中維持著。

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

此外，協(xié)調(diào)節(jié)點(Coordinator Nodes)會根據(jù)探針的心跳信息，得到全局?jǐn)?shù)據(jù)分布和狀態(tài)信息。協(xié)調(diào)節(jié)點據(jù)此將損壞的模塊交給重建節(jié)點(Rebuilder Nodes)進行數(shù)據(jù)重建;并且平衡、維持條帶上的所有塊被放在不同的數(shù)據(jù)容錯閾。

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

術(shù)語解釋：

數(shù)據(jù)文件(data file)：存儲一堆 BLOB 和其元信息的的文件

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

備忘文件(journal file)：在 Haystack 中，用于記錄所有的刪除請求。

有效備份因子，有效冗余倍數(shù)(effective-replica-factor)：實際占用的物理空間和要存的邏輯數(shù)據(jù)大小之間的比值。

兄弟模塊，伙伴模塊(companion block)：用于編碼的 n+k 個數(shù)據(jù)塊中那 n 個模塊的稱呼。

奇偶校驗塊(parity block)：用于編碼 n+k 個數(shù)據(jù)塊中那 k 個模塊的稱呼

溫存儲(warm storage)：相對于熱存儲，指那些專門針對訪問頻次不怎么高的數(shù)據(jù)所構(gòu)建的存儲。

存儲節(jié)點，存儲機器(storage nodes，storage machines)：都是指的負責(zé)存儲最終數(shù)據(jù)的的物理機。

緊縮(compact)：Haystack 中會定期地檢查數(shù)據(jù)文件，將其復(fù)制一遍，但是略過所有重復(fù)和已經(jīng)標(biāo)記刪除的數(shù)據(jù)，從而回收對應(yīng)空間。

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

秘鑰(encryption key)：用來給 BLOB 進行加密的鍵

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

數(shù)據(jù)單元(cell)：由14個機架，每個機架上有15臺機器組成的一個數(shù)據(jù)部署和回滾的的單元。

數(shù)據(jù)卷(volume)：分邏輯卷和物理卷，包含多個數(shù)據(jù)條帶。

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

數(shù)據(jù)塊(block)：一般是1G左右，被分散在不同容錯單元中。

本文轉(zhuǎn)載自微信公眾號「分布式點滴」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系分布式點滴公眾號。