大數據環境下的可靠存儲技術思考

李揮+張宇蒙+陳俊

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

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

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

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

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

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

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

1 基于復制的容錯技術

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

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

1.1 副本數量設置

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

1.2 副本放置策略

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

1.3 副本修復策略

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

2 基于糾刪碼的容錯技術

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

2.1 糾刪碼基本原理

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

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

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

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

2.3糾刪碼技術的缺陷

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

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

3 基于再生碼的容錯技術

3.1再生碼的基本原理

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

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

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

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

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

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

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

技術

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

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

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

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

5 結束語

介紹了大數據環境下的可靠存儲技術，并針對分布式存儲系統，介紹多種容錯策略及相關技術。基于復制的容錯技術冗余度大，性能提升艱難，很多研究者將目光聚集于基于糾刪碼的容錯技術。而再生碼和局部可修復碼通過適量增加存儲開銷，有效降低了糾刪碼的修復帶寬。

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

致謝：

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