分布式容錯存儲系統(tǒng)中陣列碼的研究綜述

李秋萍 趙軍霞 李康滿

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

關(guān)鍵詞：分布式;容錯存儲系統(tǒng);陣列碼;數(shù)據(jù)編解碼;數(shù)據(jù)修復(fù);數(shù)據(jù)更新

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

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

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

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

1 問題與挑戰(zhàn)

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

1.1 數(shù)據(jù)編解碼

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

1.2 數(shù)據(jù)修復(fù)

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

1.3 數(shù)據(jù)更新

基于糾刪碼的數(shù)據(jù)存儲系統(tǒng)中，一個數(shù)據(jù)塊往往關(guān)聯(lián)著許多數(shù)據(jù)塊，這導(dǎo)致更新一塊數(shù)據(jù)將要面臨更新許多塊數(shù)據(jù)的傳輸和更新，這導(dǎo)致了與數(shù)據(jù)修復(fù)面臨相同的問題，即需要提高數(shù)據(jù)的更新效率。

2 研究現(xiàn)狀分析

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

2.1 水平碼

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

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

2.2 垂直碼

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

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

2.3 水平一垂直碼

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

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

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

可見針對陣列碼容錯性的研究一直在進行，不斷地在優(yōu)化，但隨著數(shù)據(jù)量的不斷增長，這一研究仍然需要持續(xù)的關(guān)注。

3 研究展望

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

3.1 數(shù)據(jù)編解碼

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

3.2 數(shù)據(jù)修復(fù)

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

3.3 數(shù)據(jù)更新

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

4 總結(jié)

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

[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擴散層研究與實現(xiàn)》，衡陽師范學(xué)院科研基金項目（No.18D23）;《一種低資源的輕量級分組密碼的研究與實現(xiàn)》，湖南省教育廳科學(xué)研究一般項目（NO.18C0678）

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