李揮+張宇蒙+陳俊

中圖分類號：TN929.1 文獻標志碼：A 文章編號：1009-6868 （2015） 05-0027-005

摘要：針對分布式容錯技術的研究，提出了兩點關鍵要求：降低冗余開銷、提高節(jié)點修復效率。分析目前主流的容錯策略： 復制、糾刪碼、再生碼、基于局部可修復碼，并認為這些容錯策略存在不同程度的缺陷，因此設計出容錯能力、計算效率及存儲利用率更高的容錯策略，仍是未來很長一段時間內(nèi)值得深入研究的問題。

關鍵詞： 大數(shù)據(jù)；可靠性；分布式存儲；容錯技術

Abstract： Two key requirements of fault tolerance technology are proposed in this paper： minimal storage overhead and maximum node recovery performance. Four main strategies for fault tolerance are analyzed： replication， erasure codes， regenerating codes and locally repairable codes. It is considered that these fault tolerance strategies have different defects. Designing a fault tolerance strategy with higher fault tolerance， better computational efficiency and memory utilization will still be a problem needs to be solved in the future.

Key words： big data； reliability； distributed storage； fault tolerance technolog

隨著經(jīng)濟全球化的發(fā)展和科技改革的推進，網(wǎng)絡覆蓋面積不斷加大，信息交互隨之增強，全球數(shù)據(jù)正在以爆炸式的速度增長。國際數(shù)據(jù)公司（IDC）報告指出，從2010—2020年全球數(shù)據(jù)量將有50倍的增長，預測達到40 ZB數(shù)量級[1]。同時海量數(shù)據(jù)對存儲系統(tǒng)提出了巨大的挑戰(zhàn)，根據(jù)統(tǒng)計，數(shù)據(jù)存儲的需求每年的增速在50%～62%之間。大規(guī)模分布式存儲系統(tǒng)以其海量存儲能力、高吞吐量、高可用性和低成本的突出優(yōu)勢成為存儲海量數(shù)據(jù)的有效系統(tǒng)并被廣泛使用。當前最主流的分布式系統(tǒng)是開源的Hadoop分布式文件系統(tǒng)（HDFS）[2]，作為GFS[3]的一個開源實現(xiàn)，它被應用于眾多大型企業(yè)，如Yahoo、Amazon、Facebook、eBay等。

隨著分布式存儲系統(tǒng)的規(guī)模越來越大，為節(jié)省成本，存儲節(jié)點大多采用廉價、可靠性差的設備，這直接導致節(jié)點故障越來越頻繁。圖1給出了Facebook部署的Hadoop集群的日節(jié)點失效數(shù)。集群共3 000個節(jié)點，涉及45 PB數(shù)據(jù)，平均每天有22個節(jié)點失效，最高的日節(jié)點失效超過100個[4]。如何有效保障數(shù)據(jù)可靠性成為了當前分布式存儲系統(tǒng)首要關注的問題。

為了提供可靠的存儲服務，分布式存儲系統(tǒng)通過引入冗余信息來提高系統(tǒng)的容錯能力。這種冗余存儲的方式能夠使系統(tǒng)容忍一定數(shù)量的節(jié)點故障[5-6]，同時系統(tǒng)還需要一個良好的節(jié)點修復機制，在發(fā)生故障時能快速有效地修復失效數(shù)據(jù)，維持系統(tǒng)冗余度。

1 基于復制的容錯技術

復制策略是引入冗余最簡單的方法，其基本思想是為系統(tǒng)中的每一個數(shù)據(jù)對象都建立若干個相同的副本，并把這些副本分散存儲在不同的節(jié)點上，當遇到某個數(shù)據(jù)損壞或失效而無法正常使用時，可通過訪問最近的存儲節(jié)點來獲取與原件完全一致的數(shù)據(jù)備份，這樣只要數(shù)據(jù)對象還有一個存活副本，分布式存儲系統(tǒng)就可以一直正常運行。修復過程也十分簡單高效，只要向所有存儲副本的節(jié)點中最近的節(jié)點發(fā)出請求、下載并重新存儲，即可恢復系統(tǒng)冗余度。復制策略存儲方式簡單，易于實現(xiàn)，故障修復容易，并且便于擴展。此外，存儲的多個副本也可以均攤讀文件時的負載，如通過為熱點文件配置更高的副本數(shù)來支持高效的并發(fā)讀操作。

但是在節(jié)點數(shù)量龐大，存儲結構復雜的大規(guī)模分布式系統(tǒng)中，要實現(xiàn)快速高效的容錯技術，必須解決3個問題：副本數(shù)量的設置、副本的放置方式和副本的修復策略。

1.1 副本數(shù)量設置

設置副本數(shù)量一般有兩種方式： 一是靜態(tài)設置，主流的分布式文件系統(tǒng)如HDFS[2]和GFS[3]都是采用3副本固定機制，這種方法操作簡單，但靈活性差；二是動態(tài)設置副本數(shù)量，亞馬遜分布式存儲系統(tǒng)S3提供用戶可以自行設定副本數(shù)的功能。另外，文獻[7]提出一種動態(tài)的容錯機制，系統(tǒng)根據(jù)數(shù)據(jù)的訪問頻率、出錯概率、網(wǎng)絡狀況以及存儲時間等動態(tài)因素決定副本數(shù)，同時動態(tài)地刪除或添加副本，這種動態(tài)機制能大大增加存儲空間的利用率、提高數(shù)據(jù)的獲取性能，但動態(tài)決策方式會加大系統(tǒng)的處理開銷。

1.2 副本放置策略

副本的放置策略不但影響分布式存儲系統(tǒng)的容錯性能，還關系到副本的存儲效率和訪問效率。HDFS采用的3副本放置策略，如圖2所示[2]。3副本放置策略為：本地放一份，同機架內(nèi)其他任一節(jié)點放一份，不同機架的任一節(jié)點放一份。同機架內(nèi)存放兩個副本，可減少機架間的數(shù)據(jù)傳輸，方便本地節(jié)點對于數(shù)據(jù)需求時的讀取。若本地數(shù)據(jù)損壞，節(jié)點可以從同一機架內(nèi)的相鄰節(jié)點獲取數(shù)據(jù)，讀取速率快。而數(shù)據(jù)塊存放在兩個不同的機架中能避免機架故障導致的數(shù)據(jù)不可用。同時，為了降低整體的帶寬消耗和讀取延時，HDFS會盡量讓讀取程序讀取離它最近的副本。如果在讀取程序的同一個機架上有一個副本，那么就讀取該副本。如果一個HDFS集群跨越多個數(shù)據(jù)中心，那么客戶端也將首先讀本地數(shù)據(jù)中心的副本。

1.3 副本修復策略

容錯技術的修復過程事實上就是恢復系統(tǒng)的冗余度，保證其在一定的可接受范圍內(nèi)。實際的存儲系統(tǒng)采用的修復策略有兩種：一種是“主動”修復策略[8]，一旦檢測到一個副本失效立刻創(chuàng)建一個新副本；另一種是基于閾值的“惰性”修復策略，這種策略只有當備份數(shù)量小于某個閾值才進行修復，如Total Recall[9]。根據(jù)資源的訪問頻率，可以分為熱門資源和冷門資源，熱門資源一般采用主動修復，而訪問量小的冷門資源則可以采用惰性修復策略，減少修復臨時失效等不必要的開銷。

2 基于糾刪碼的容錯技術

糾刪碼起源于通信傳輸領域，由于其數(shù)學特性，被逐漸應用于大規(guī)模存儲系統(tǒng)中，特別是分布式存儲環(huán)境，實現(xiàn)數(shù)據(jù)的冗余保護。相較于復制策略，糾刪碼技術在相同可靠性條件下可以最小化冗余存儲，學術界和工業(yè)界已將糾刪碼廣泛應用于分布式文件系統(tǒng)。例如卡耐基梅隆大學研究的DiskReduce[10]、Facebook的HDFS-RAID[11]、谷歌的Colossus[12]、微軟的Azure[13]存儲系統(tǒng)均采用了糾刪碼并實現(xiàn)了更經(jīng)濟的可靠性。

2.1 糾刪碼基本原理

糾刪碼的基本原理如圖3所示，存儲原始文件O，首先將其切分成k個數(shù)據(jù)塊，記為O1， O2， …， Ok，然后編碼生成n個編碼塊，記為B1， B2， …， Bn，n>k，最后將這n個編碼塊按照一定的放置規(guī)則分別存儲在不同的節(jié)點上。編碼過程中生成了冗余數(shù)據(jù)，當系統(tǒng)中有存儲節(jié)點失效時，只要留下足夠的編碼塊就可以利用這些剩余的編碼塊恢復出丟失的數(shù)據(jù)，維持系統(tǒng)的冗余度。若n個編碼塊中任意k個塊即可重構原始文件O，則這種糾刪碼滿足最大距離可分特性（MDS）[14]，在可靠性和冗余的權衡上達到最優(yōu)，最常用的編碼方法是RS碼[15]。

2.2基于糾刪碼的分布式存儲模型

在分布式存儲系統(tǒng)中，數(shù)據(jù)分布在多個相互關聯(lián)的存儲節(jié)點上，通常情況下，映射生成的編碼塊需要存儲在不同的節(jié)點上。圖4給出了一種基于糾刪碼的分布式存儲模型[16]，假設系統(tǒng)中含有n個存儲節(jié)點，其中k個是數(shù)據(jù)節(jié)點，m個是編碼節(jié)點，即滿足n = k + m。k個數(shù)據(jù)節(jié)點存儲原始數(shù)據(jù)塊，標記為D0， D1，…， Dk-1；m個編碼節(jié)點存儲編碼數(shù)據(jù)塊，標記為C0， C1， …， Cm-1。糾刪碼算法需要將原始文件切割成k等份后依次存儲在k個數(shù)據(jù)節(jié)點中，并將編碼生成的m份放入m個編碼節(jié)點。當存儲大文件時，需要對原始文件進行二次切割，即每次從文件中讀取指定大小的數(shù)據(jù)量進行編碼，我們將一次編碼過程中涉及的原始數(shù)據(jù)和編碼數(shù)據(jù)稱為一個stripe[16]。一個stripe獨立地構成一個編碼的信息集合，不同stripe之間相互無關。但是，邏輯上的stripe與實際物理節(jié)點的對應關系并不是恒定不變的，可以通過stripe的輪轉實現(xiàn)數(shù)據(jù)存儲負載均衡。

與復制策略相比，糾刪碼策略可以有效地降低維持可靠性所需的存儲開銷，提供令人滿意的存儲效率[5]。

2.3糾刪碼技術的缺陷

然而，基于糾刪碼的容錯技術未能在實際的大規(guī)模分布式存儲系統(tǒng)中真正應用，除了其結構較復制策略復雜外，糾刪碼本身在數(shù)據(jù)恢復時存在致命的缺陷。在基于糾刪碼的分布式存儲系統(tǒng)中，當一個節(jié)點失效時，為維持系統(tǒng)冗余度，新節(jié)點需要首先從k個節(jié)點中下載全部數(shù)據(jù)恢復出原始文件，再重新編碼生成失效的數(shù)據(jù)，這個過程中傳輸?shù)臄?shù)據(jù)量是失效數(shù)據(jù)的k倍。當節(jié)點在網(wǎng)絡中分布較分散時，節(jié)點的修復需要消耗大量的網(wǎng)絡帶寬。這一缺陷在普通分布式系統(tǒng)中已有制約，在大數(shù)據(jù)環(huán)境下，數(shù)據(jù)量和存儲節(jié)點在成倍甚至幾何級增長時更為明顯。同時，需要的下載量太大勢必會導致節(jié)點修復過程變慢，對于不斷發(fā)生故障的分布式存儲系統(tǒng)來說，節(jié)點的修復速率直接影響到系統(tǒng)可靠性。如果修復速率過慢，甚至趕不上節(jié)點發(fā)生故障的速度，那么系統(tǒng)將無法維持其可靠性。據(jù)Facebook在HotStorage13上發(fā)布的論文指出，糾刪碼的低效修復已經(jīng)成為限制其廣泛應用的瓶頸所在[4]。

針對糾刪碼的修復問題，Rodrigues提出了一種混合策略[5]：采用糾刪碼的同時維護一個副本，從而有效減少修復帶寬。然而，這種混合策略節(jié)省帶寬有限，但存儲開銷大，同時使得系統(tǒng)設計復雜化。Dimakis創(chuàng)造性地將網(wǎng)絡編碼應用于分布式存儲，提出再生碼的概念[17]，顯著降低了修復帶寬。

3 基于再生碼的容錯技術

3.1再生碼的基本原理

再生碼的描述如下：將原始文件編碼后存儲到n個節(jié)點中，每個節(jié)點存儲大小為α。當一個節(jié)點失效時，新節(jié)點連接剩余n-1個節(jié)點中的d個節(jié)點（k≤d≤n-1），從每個節(jié)點下載大小為β（β≤α） 的數(shù)據(jù)進行修復，即修復帶寬為γ=d×β。再生碼的參數(shù)集可表示為{n， k， d， α， β， B}，其平均修復帶寬γ小于文件大小B。再生碼的編碼、再生及重構過程如圖5所示。

隨著每個節(jié)點的存儲量的提高，節(jié)點修復時需要下載的數(shù)據(jù)量將降低，通過在信息流圖上求最小割界的方法，給出了節(jié)點修復帶寬消耗的下界曲線，而再生碼正是在存儲開銷α和修復帶寬γ的最優(yōu)曲線上。如圖6所示，最優(yōu)曲線上存在兩個極值點，分別代表最優(yōu)存儲效應和最小修復帶寬效應，達到這兩個極值點的編碼稱為最小存儲再生碼（MSR）和最小帶寬再生碼（MBR），已有一些明確的編碼實現(xiàn)[18]。理論上，當d=n-1時，再生碼的修復帶寬達到最小值。

3.2再生碼技術的瓶頸及前景

雖然理論上再生碼可以達到最優(yōu)的存儲開銷和修復帶寬，但由于它依賴于復雜的參數(shù)和晦澀難懂的數(shù)學理論，其實現(xiàn)方式非常復雜?，F(xiàn)有的再生碼大多在有限域GF（2w）上進行域元素的多項式運算[18]。計算機處理中，加法較為簡單，但乘法和除法卻非常復雜，甚至需要借助離散對數(shù)運算和查表才能實現(xiàn)。這使得再生碼的編解碼計算開銷大，無法適應存儲系統(tǒng)對計算效率的要求。很多研究都表明，設計一種結構簡單、計算復雜度低的策略至關重要。文獻[19]中分析了3種再生碼：隨機線性網(wǎng)絡碼（RL）[20]、精確線性碼（EL）[21]和生成矩陣碼（PM）[22]。其中，PM碼利用一種緊湊的表示方式和高效的編解碼算法大大提高了編解碼速率，然而與糾刪碼相比，PM碼仍需要更長的計算時間。

再生碼作為對糾刪碼的改進，具有很好的理論支撐。但目前提出的大多數(shù)再生碼、編解碼復雜度較高且碼率較底。如何提出碼率較高并且復雜度低的編碼策略就很有意義。深圳市融合網(wǎng)絡技術實驗室在該領域進行了深入研究，并取得了一定的研究成果：1）提出BASIC[23]編碼框架，利用一種新穎的卷積形式來表示編碼運算過程，可以將有限域運算轉化為GF（2）內(nèi)簡單的移位和異或操作；2）提出一種改進的Zig-Zag編碼[24]，采用移位和異或的Zig-Zag解碼算法，避免解碼時所需要的復雜計算，達到了最低的編解碼復雜度。這些編碼都可以應用在再生碼的構造上，以更好地實現(xiàn)碼率較高并且復雜度低的編碼。

對于再生碼編碼策略的未來研究方向，應結合安全問題、網(wǎng)絡拓撲和磁盤輸入輸出（I/O）復雜度進行設計，從而使再生碼更為實用。

4 基于局部可修復碼的容錯

技術

除再生碼外，局部可修復碼技術（LRC）[25]可以通過增加本地數(shù)據(jù)實現(xiàn)修復帶寬的降低。文獻[25]給出了修復局部性r、編碼距離d、每個節(jié)點的存儲大小α以及存儲編碼長度n之間的權衡。Facebook在HDFS中實現(xiàn)了LRC技術[4]，微軟也在Azure上添加了LRC技術[26]。

文獻[4]給出了LRC技術的一種實現(xiàn)：如圖7，原始文件被等分成10個數(shù)據(jù)塊，通過RS編碼生成4個冗余塊，圖中顯示為4個綠色方框。為降低修復帶寬，在RS碼基礎上進行二次編碼產(chǎn)生3個額外的冗余塊，標記為S1，S2和S3，圖中顯示為3個橙色的方框。S1是由前5個數(shù)據(jù)塊編碼產(chǎn)生，S2是由后5個數(shù)據(jù)塊編碼產(chǎn)生，這兩個由局部原始數(shù)據(jù)塊編碼產(chǎn)生的冗余塊稱為本地校驗塊。而S3則是由4個冗余校驗塊編碼產(chǎn)生，稱為隱式校驗塊。實際存儲中，我們將10個原始數(shù)據(jù)塊標記為c1，c2，...，c10，將7個冗余塊標記為c1，c2，...，c7，存放在7個不同的節(jié)點。當1個數(shù)據(jù)塊丟失時，只需要1個額外的冗余塊和4個數(shù)據(jù)塊即可修復失效數(shù)據(jù)，與傳統(tǒng)糾刪碼相比，修復帶寬降低了大概一半。

從圖7可以看出LRC技術以額外的14%存儲開銷為代價，降低RS碼的修復帶寬。但其編碼方式仍是RS碼，因此編碼效率沒有提高。另外，LRC編碼不滿足MDS特性，系統(tǒng)還需要增加額外信息標示二次編碼數(shù)據(jù)。當修復一個節(jié)點故障時，LRC具有很好的修復局部性，但修復兩個或兩個以上的節(jié)點故障時就需要連接k個節(jié)點，修復帶寬與糾刪碼相同，仍是失效數(shù)據(jù)的k倍。隨著存儲系統(tǒng)規(guī)模變得越來越大，出現(xiàn)兩個或者多個故障的幾率也隨之增大。

除此之外，針對大數(shù)據(jù)存儲系統(tǒng)中的容錯修復問題，我們不斷對存儲編碼的構造方式進行改進[27-28]，以獲得更低的冗余開銷和更高效的修復性能。

5 結束語

介紹了大數(shù)據(jù)環(huán)境下的可靠存儲技術，并針對分布式存儲系統(tǒng)，介紹多種容錯策略及相關技術?；趶椭频娜蒎e技術冗余度大，性能提升艱難，很多研究者將目光聚集于基于糾刪碼的容錯技術。而再生碼和局部可修復碼通過適量增加存儲開銷，有效降低了糾刪碼的修復帶寬。

這些容錯策略在容錯能力、計算效率、存儲利用率等方面都存在不同程度的缺陷，如何平衡這些影響系統(tǒng)可靠性的因素，設計出容錯能力、計算效率及存儲利用率更高的容錯策略，仍是未來很長一段時間內(nèi)值得不斷深入研究的問題。

致謝：

感謝北京大學先進網(wǎng)絡技術實驗室博士研究生侯韓旭對于研究的理論支持。