[[263398]]

概覽

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

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

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

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

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

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

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

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

訪問頻度的熱力圖

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

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

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

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

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

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

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

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

控制模塊(Controller)

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

路由層(Route Tier)

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

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

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

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

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

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

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

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

緩存棧(Caching Stack)

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

Haystack 熱存儲(chǔ)(Hot Storage with Haystack)

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

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

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

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

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

容錯(cuò)(Fault tolerance)

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

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

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

f4 設(shè)計(jì)

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

f4 概覽(f4 Overview)

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

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

單個(gè) f4 cell(Individual f4 Cell)

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

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

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

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

名字節(jié)點(diǎn)(Name Node)

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

存儲(chǔ)節(jié)點(diǎn)(Storage Nodes)

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

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

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

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

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

回退節(jié)點(diǎn)(Backoff Nodes)

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

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

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

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

重建節(jié)點(diǎn)(Rebuilder Nodes)

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

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

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

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

地理備份

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

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

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

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

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

簡(jiǎn)單總結(jié)

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

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

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

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

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

術(shù)語解釋：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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