分布式容錯存儲系統中陣列碼的研究綜述

李秋萍 趙軍霞 李康滿

摘要：計算機和網絡技術的飛速發展，使得人們快速地步入了數據大爆炸的時代。數據的存儲技術也得到了快速發展，從單機存儲系統發展為廉價且存儲擴展能力強的分布式存儲。但隨著存儲數據量的增大，數據失效成為一種每天都會發生的事件，所以分布式系統的容錯能力的研究，成為迫切需要解決的問題。陣列碼因其可以用最少的冗余來容錯，而且編解碼容易實現，被廣大學者所研究。該文首先介紹了陣列碼容錯技術研究生存在的挑戰。然后根據陣列碼的結構特點，分為水平碼，垂直碼和水平一垂直碼對其研究現狀進行了分析。最后，我們分別從數據編解碼，數據修復和數據更新三個方面，對未來的研究方向進行了展望。

關鍵詞：分布式;容錯存儲系統;陣列碼;數據編解碼;數據修復;數據更新

中圖分類號：TP311 文獻標識碼：A

文章編號：1009-3044（2020）08-0250-02

隨著計算機存儲和壓縮技術的發展，大容量存儲設備、智能手機的廣泛應用以及多媒體應用與社交網絡的流行，互聯網上的各種數據（文本、圖像以及視頻等）呈現出爆炸式的增長趨勢，大量數據的產生己經成為必然趨勢，隨著數據存儲規模的不斷增長，傳統的單機系統已經無法滿足高速增加的數據存儲需求，存儲這些海量數據成了亟待解決的問題。分布式存儲系統使用大量廉價商用服務器通過網絡互聯，可以提供極強的服務能力和擴展能力，但這些組件的數量和質量導致了該類存儲系統的節點失效成為常態事件，而數據本身的價值往往是無法估量的，因此，相比于存儲系統的存儲容量、存取帶寬、I＼0處理能力等指標，容錯能力是其中最重要的一項。

多副本技術和糾刪碼技術是兩種常用的容錯技術。多副本技術的基本思想是為數據對象包含的數據塊創建多個副本，并將多個副本放置在不同的節點中以最大化數據的可用性。多副本技術最大的優點是維護多個副本只需要額外的通信和存儲開銷，不需要任何計算，不占用服務器的CPU資源。但多副本技術的數據冗余度較大，存儲效率低。糾刪碼技術的基本原理是將數據對象包含的多個數據塊通過編碼方式生成多個編碼塊，并將數據塊與編碼塊分別存儲在不同的節點中以最大化數據可用性。糾刪碼技術能夠通過調節數據分塊和冗余塊的取值使系統在節約存儲空間的同時，提供容忍更多失效節點的容錯能力，這也使得基于糾刪碼的容錯技術成為當前分布式存儲領域一個重要的研究熱點。陣列碼是一類在存儲系統中常用的糾刪碼，這類碼可以使用最少的冗余來提供容錯能力，并且其編解碼過程只需要用到簡單的異或和循環移位運算，因此近幾年來受到了越來越廣泛的關注。

1 問題與挑戰

隨著信息時代數據規模的快速增長，容錯能力強且存儲成本低的陣列碼技術受到了越來越多的關注。但現有的陣列碼在數據編解碼，數據修復，數據更新三個方面仍可以進一步優化。

1.1 數據編解碼

數據的編解碼技術大概可以分成兩個方向，一個是提高數據編解碼計算效率，一個是提高陣列碼容錯能力。在基于糾刪碼的容錯存儲系統中，在數據寫入系統時首先要對其進行編碼，讀出數據時需要對其進行解碼，如果編解碼效率不高，則會影響整個系統的讀寫效率，極大地制約了糾刪碼在存儲系統中的應用。提高糾刪碼的容錯能力可以提高數據的可靠性，可用性，節約存儲空間。但是優化編解碼效率與提高容錯能力之間往往相互矛盾，現有的一些糾刪碼經常在二者之間進行權衡。

1.2 數據修復

基于糾刪碼的存儲系統中，修復一個失效塊前需要先對未失效固定個數的數據塊進行下載，然后再對數據進行修復，這導致一旦一個數據塊失效會有固定倍數的數據傳輸產生，這極大地降低了數據的傳輸效率和整個系統的傳輸效率。因此提高糾刪碼的修復效率是基于糾刪碼的容錯系統急需解決的一個問題。

1.3 數據更新

基于糾刪碼的數據存儲系統中，一個數據塊往往關聯著許多數據塊，這導致更新一塊數據將要面臨更新許多塊數據的傳輸和更新，這導致了與數據修復面臨相同的問題，即需要提高數據的更新效率。

2 研究現狀分析

陣列碼是一種將數據以二維形式排列的線性分組碼，其具有實現容易，編解碼以及更新計算開銷較低的優點。陣列碼無論是在編解碼的復雜度，還是在冗余開銷，更新復雜度等方面較其他糾刪碼都有明顯的優勢。根據陣列碼的結構特點，陣列碼分為水平碼，垂直碼，水平一垂直碼，本小節我們將這三個方面對國內外的研究進展進行分析。

2.1 水平碼

水平碼是把原數據和校驗數據分別存儲在不同的數據塊中的陣列碼。目前已知最具代表性的水平碼主要包括EVENODD[2]碼，RDP[3]碼，Liberation碼等及它們的推廣碼。

EVENODD碼和RDP碼都是可以容忍任意兩個磁盤同時出錯的陣列碼，并且都滿足MDS性質。EVENODD碼是最早應用于RAID-6的陣列碼，但隨著硬盤容量的增加，對系統的容錯能力要求也越來越高，為解決這些問題，許多學者對這兩種編碼方式進行了一定的改進，如總體解碼效率得到提高的可以容忍任意三個磁盤同時出錯的STAIR陣列碼及一些二進制MDS陣列碼。RDP碼是與EVENODD碼十分相似的陣列碼，它的特點是編碼過程中首先計算第一個校驗列的值，然后將其作為數據列參與對角線校驗列的計算，值得一提的是它的編解碼效率最優。RDP碼提出后，EVENODD碼的作者Mario Blaum提出了一種廣義的RDP碼，這種碼在滿足一定條件時肯定是MDS碼。同時RDP的原作者受到STAR碼的啟發，提出了RTP碼[5]，使得其總體解碼性能優于原RDP碼。Liberation碼的奇偶校驗矩陣的密度達到了水平碼的下界，這使得其更新復雜度是所有水平陣列碼中最低的，但是其解碼復雜度要比以上兩種陣列碼的高許多。除此之外，也有學者提出了可以有效降低數據修復成本的LRC碼和LRCs碼這兩組碼可以在修復開銷與存儲空間開銷之間靈活地進行權衡。

2.2 垂直碼

垂直碼是將數據分組后按照一定的計算方式得到校驗塊，并將得到的校驗塊與數據塊交叉放置在磁盤的陣列碼。具有代表性的垂直碼包括X-code碼和WEAVER碼，B-碼等。

X-code碼是一種非常易于實現的垂直碼，它最大的優點是編解碼復雜度和更新復雜度均能達到最低。它的缺陷是對碼長的限制太過嚴格，雖然文獻中根據水平碼碼長的擴展方法對其進行了擴展，但擴展過程比水平碼復雜。WEAVER碼是限定了數據塊和校驗塊的個數后，通過搜索找出最優的放置方法，使其容錯能力達到最高。WEAVER碼的不足是冗余度較高以及空間利用率較低。B-碼的優點是其碼長限制最少，同時編解碼復雜度和更新復雜度同時達到了最低，值得一提的是B-碼的作者將完全圖的PIF（Perfect One Factorization）問題與最低密度MDS碼的構造結合，證明了只要給定的一個完全圖PIF，就可以構造出一個與之相對應的B-碼。

2.3 水平一垂直碼

水平一垂直碼是指數據塊和校驗塊兼有水平碼和垂直碼的特征，部分數據塊和校驗塊單獨放置，部分交叉放置。具有代表性的水平垂直碼包括HVPC碼，GRID碼和HoVer碼和SHEC碼等。

HVPC碼是很早提出的一種編碼，它的容錯能力為3，同時也能夠被擴展成多維的情況，以便有更高的容錯能力，但是它的存儲空間利用率較低。在HVPC的基礎上，GPID碼使用了一些其他的編碼來替代HVPC碼中的保護碼，提高了容錯能力，同時也有較高的存儲空間利用率，但是它要求構造它的兩類編碼必須相互匹配，這導致適用于它的編碼對較少。另外一類水平一垂直碼是HoVer碼，它的存儲利用率較高，容錯能力最多能達到4，可以很方便的調節存儲利用率和計算效率間的均衡。

除了上述三種結構，陣列碼還有許多其他形式的編碼。如2014年Tosato和Sandell提出的一種適用于存儲系統中各節點容量不同的場合的不規則MDS陣列碼，清華大學的Fu[4]等人提出的對RAID-6在正常模式和降級模式下的讀性能進行優化的一種由最低密度MDS陣列碼。數據修復時只傳輸數據而不需要進行任何數學運算的MBR碼。以及可以將數據修復時所需下載的數據量降低45%的Hichhiker碼。帶扇區容錯的SD碼，PMDS碼[1]等。

可見針對陣列碼容錯性的研究一直在進行，不斷地在優化，但隨著數據量的不斷增長，這一研究仍然需要持續的關注。

3 研究展望

從陣列碼研究遇到的問題和研究現狀可以看出，陣列碼在以下幾個方面仍然需要進一步的研究。

3.1 數據編解碼

陣列碼在相同的容錯能力的前提下，能夠極大的節約存儲空間。數據的編解碼效率直接與陣列碼本身相關，何種方法構造的陣列碼可以提高編解碼效率同時節約硬件存儲資源，是我們需要研究的問題。因此，研究在保證容錯能力的條件下，如何提高編解碼效率，降低計算復雜度是值得研究的方向。

3.2 數據修復

陣列碼由于碼字本身的特殊性，可以通過增加一些額外的冗余數據來減少修復時下載的數據量，通過構造一些低復雜度的碼來優化修復能力，以達到提高數據修復效率的目標。因此，數據修復效率與陣列碼生成矩陣的元素計算效率息息相關，如何選擇矩陣來提高計算效率仍然是我們要解決的問題。

3.3 數據更新

陣列碼中的計算可以通過簡單的異或運算和循環移位來實現，所以我們可以通過一些稀疏矩陣的迭代來簡化數據的計算與更新，以達到提高數據更新效率的目標。而數據更新效率與數據修復效率相同，主要是數據傳輸量和計算量大的問題，因此如何構造矩陣使其有較低的計算量是我們可以研究的方向。

4 總結

近年來人類社會所產生的數據急劇膨脹，分布式存儲系統由于其在成本、性能、可擴展性及存儲容量等方面的優勢，被廣泛應用于商業和科學計算等大數據的存儲之中。而分布式存儲系統中的節點故障已經成為系統運行中一個常態化的行為，因此容錯能力已經成為區分分布式存儲系統好壞的一個重要指標。本文首先指出了陣列碼在分布式容錯存儲系統中的優勢和面臨的主要問題。隨后，對分布式存儲系統中陣列碼容錯技術的國內外研究現狀進行了分析。最后，本文基于面臨的問題和研究現狀對未來的研究進行了展望。

[1] Blaum M，Hafner J L，Hetzler S.Partial-MDS codes and theirapplication to RAID type of architectures[J].lEEE Transactionson Information Theory， 2013，59（7）：4510-45 19.

[2] Blaum M， Brady J， Bruck J， et al. EVENODD： An efficientscheme for tolerating double diskfailures in RAID architec-tures [J]. Computers. IEEE Transactions on. 1995， 44 （2）：192-202.

[3] Corbett P， English B， Goel A， et al. Row-diagonal parity fordouble disk failure correction. in：Proceedings of the 3rd USE-NIX Conference on File and Storage Technologies （FAST' 04），2004，1-14.

[4] Fu Y X，Shu J W.D-code：an efficient RAID-6 code to opti-mize l/0 loads and read performance[Cy/2015 lEEE Intema-tional Parallel and Distributed Processing Symposium，May 25-29， 2015. Hyderabad， India. IEEE. 2015.

[5] Coel A，Corbett P.RAID triple parity[J].ACM SIGOPS Operat-ing Systems Review， 2012，46（3）：41.

收稿日期：2019-12-25

基金項目：《輕量級MDS擴散層研究與實現》，衡陽師范學院科研基金項目（No.18D23）;《一種低資源的輕量級分組密碼的研究與實現》，湖南省教育廳科學研究一般項目（NO.18C0678）

作者簡介：李秋萍（1989-），女，遼寧沈陽人，博士研究生，講師，主要研究方向為密碼編碼學。