應(yīng)用于海量存儲中高度容錯的新編碼方案

于XOR的糾刪編碼的一種新方法，解決了傳統(tǒng)RAID系統(tǒng)不能解決的高容錯性問題，且比ReedSolomon等算法有更好的時間效率。Ningxy編碼方法對于解決高容錯性問題有著最佳的效果，該編碼更適用于動態(tài)增減磁盤數(shù)量的網(wǎng)絡(luò)存儲的數(shù)據(jù)修復(fù)；與此同時提出了新概念步長，步長對解決高度容錯起到了關(guān)鍵性作用；通過線性變換、高斯消元，迅速地恢復(fù)丟失的磁盤數(shù)據(jù)。更值得一提的是從整體性能和效率上來說，該編碼比其他的編碼更具有靈活性。

隨著當(dāng)前信息數(shù)據(jù)的爆炸式增長，如何確切地保護和妥善管理用戶的重要數(shù)據(jù)成為一個亟待解決的問題。目前擁有很多種方案來解決數(shù)據(jù)的安全性問題。例如當(dāng)數(shù)據(jù)丟失后，仍可以讓其恢復(fù)或再生。在解決這個問題中，需要提及一個概念RAID。它是由美國的D.A.Patterson在1988年提出的。RAID將離散的磁盤變成了RAID子系統(tǒng)。RAID具有較高的性能，這是因為不同磁盤上的數(shù)據(jù)可以同時讀取，從而提高磁盤的帶寬；所有磁盤可以并行地進行尋道工作，減少了尋道的時間，提高整體性能。在性能提高的同時，還可以保證一定程度的容錯性。通過相應(yīng)的冗余磁盤容錯機制，可以保證在不丟失保存在失效磁盤上的數(shù)據(jù)的前提下允許磁盤的失效。Gibson等人對磁盤驅(qū)動器失效的規(guī)律進行了研究。他們廣泛地收集實驗數(shù)據(jù)并分析了磁盤失效模型，認為負指數(shù)分布很好地表述了磁盤驅(qū)動器的失效規(guī)律。這種研究可以提供一種思維方式，如因為自然災(zāi)害（地震、火災(zāi)）、戰(zhàn)爭等情況下，多個磁盤驅(qū)動器同時發(fā)生故障、系統(tǒng)癱瘓，也能對機密資料進行快速恢復(fù)或修復(fù)，給把數(shù)據(jù)視為生命的機構(gòu)和單位提供保障。

大多數(shù)情況，在目前單點失效模式下，磁盤陣列系統(tǒng)主要依靠RAID 5容錯來為用戶數(shù)據(jù)提供可靠性。在比特錯誤提高很少的情況下，磁盤容量的持續(xù)增長把RAID 5和RAID 6系統(tǒng)可靠性削弱到了無法令人接受的境地。本文提出了在磁盤陣列和其他可靠的存儲系統(tǒng)中基于XOR的糾刪編碼的一個新方法。這個新編碼的一個關(guān)鍵優(yōu)勢是其并不是非MDS（在編碼理論中，MDS代表最大距離分離）。

1相關(guān)的概念術(shù)語

a)單元（element）是一個基本的數(shù)據(jù)或者校驗單元。

b)條帶（stripe）是一個完整的數(shù)據(jù)和校驗單元的集合。這些單元由于校驗關(guān)系而有著依賴相關(guān)性。實際上它相當(dāng)于一個碼字，既有原始信息又有冗余信息，并且原始數(shù)據(jù)和冗余數(shù)據(jù)間必須有校驗關(guān)系。

c)條塊（strip）是所有連續(xù)的在同一磁盤和條帶上的存儲單元。它上面存放的是數(shù)據(jù)或者校驗數(shù)據(jù)或者兩者都有。值得說明的是，這些strip大小相同（包含同樣數(shù)量的elements）。

d)陣列（array）是存在一個或者多個條帶的數(shù)個磁盤的組合。磁盤陣列中的劃分如圖1所示。

e)堆棧（stack）是一個陣列中數(shù)個條帶的集合，這些條帶中的條塊數(shù)目是相同的。

f)水平碼（horizontal code）不同于數(shù)據(jù)，它單獨地存儲校驗數(shù)據(jù)。

g)步長(step)是一個數(shù)據(jù)條塊到另一個數(shù)據(jù)條塊之間的跨度（本文引入的新概念）。步長示意圖如圖2所示。圖中步長用S表示。

按照誤碼控制的不同功能可分為檢錯碼、糾錯碼和糾刪碼等。檢錯碼僅具備識別錯碼功能而無糾正錯碼功能；糾錯碼不僅具備識別錯碼功能，同時具備糾正錯碼功能；糾刪碼則不僅具備識別錯碼和糾正錯碼的功能，而且當(dāng)錯碼超過糾正范圍時可把無法糾錯的信息刪除。

按照誤碼產(chǎn)生的原因不同，可分為糾正隨機錯誤的碼與糾正突發(fā)性錯誤的碼。前者主要用于產(chǎn)生獨立的局部誤碼；后者主要用于產(chǎn)生大面積連續(xù)誤碼的情況，如磁帶數(shù)碼記錄中磁粉脫落而發(fā)生的信息丟失。按照信息碼元與附加的監(jiān)督碼元之間的檢驗關(guān)系可分為線性碼與非線性碼。如果兩者呈線性關(guān)系，即滿足一組線性方程式，稱為線性碼；否則，兩者關(guān)系不能用線性方程式來描述，稱為非線性碼。

6進一步工作

本文闡述了容錯度為t且根據(jù)決定空間效率的參數(shù)r/v來進行磁盤整列的設(shè)計、分析時間復(fù)雜度的情況。這種編碼算法對于在RAID或者DRAID結(jié)構(gòu)中的磁盤損壞有很好的恢復(fù)效果。就存儲效率和性能來說，也比其他很多編碼有更強的優(yōu)勢，如比Weaver、ReedSolomon等算法空間復(fù)雜性與時間復(fù)雜性都好。同時也引進了一個新的概念，即步長。這個概念的引入對解決高容錯性磁盤陣列問題或者更大的網(wǎng)絡(luò)存儲數(shù)據(jù)修復(fù)問題起著非常重要的作用。進一步工作是如何用解決高容錯度的思路去得出v、r、t和n的關(guān)系，求出最佳的公式表達。主要的工作就是探討存儲效率更高、容錯更大，使得空間效率和時間效率在某一應(yīng)用中能達到最佳狀態(tài)，對這個DRAID或者RAID系統(tǒng)的影響，并提出一些新的觀點，以求解決在高容錯情況下高容錯度問題。

致謝：筆者向?qū)Ρ疚牡墓ぷ鹘o予支持和建議的同行，特別是蘭州理工大學(xué)電通院的董建設(shè)、徐維濤以及江南大學(xué)的劉英戈表示感謝。

參考文獻：

[1]PLANK J S. A tutorial on ReedSolomon coding for faulttolerance in RAIDlike systems [J].Software Practice Experience, 1997, 27(9):995-1012.

[2]HAFNER J L. HoVer erasure codes for disk arrays[C]//Proc of International Conference on Dependable Systems and Networks. Washington DC:IEEE Computer Society, 2006:217-226.

[3]XU Lihao, BRUCK J. Xcode: MDS array codes with optimal encoding [J].IEEE Trans on Information Theory,1999,45(1):272-276.

[4]BLAUM M, BRADY J, BRUCK J,et al. EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures [J].IEEE Trans on Computers, 1995,44(2):192-202.

[5]PERUMAL S, KRITZINGER P. Objectoriented design of the groupware layer for the ecosystem information system [D]. Montana:University of Montana, 1995.

[6]ZAITSEV G V, ZINOVEV V A, SEMAKOV N V. Minimum check density codes for correcting bytes of errors [J].Problems in Information Transmission, 1983,19(3):29-37.

[7]周敬禮,余勝生.網(wǎng)絡(luò)存儲原理與技術(shù)[M].北京：清華大學(xué)出版社,2005:33-55.

[8]江藤良純,金子敏信.糾錯碼及其應(yīng)用[M].北京：科學(xué)出版社，2003:45-93.

[9]HAFNER J L. Weaver erasure codes for disk arrays[R].San Jose:IBM Research, 2005.

[10]XIN Qin,MILLEAR E L,SCHWARZ T,et al. Reliability mecha勃nisms for very large storage systems[C]//Proc of the 20th IEEE/11th NASA Goddard Conference on Mass Storage Systems and Technologies. Washington DC:IEEE Computer Society,2003:146-156.

[11]HAFNER J L. Matrix methods for lost data reconstruction in erasure codes[C]//Proc of the 4th USENIX Conference on File and Storage Technologies.San Francisco:[s.n.],2005:183-196.

[12]PLANK J S. T1:erasure codes for storage applications[C]//Proc of the 4th USENIX Conference on File and Storage Technologies.San Francisco:[s.n.],2005:1-74.

更多計算機與外設(shè)信息請關(guān)注：21ic計算機與外設(shè)頻道