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

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

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

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

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

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

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

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

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

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

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

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

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

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

6進(jìn)一步工作

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

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

參考文獻(xiàn)：

[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ò)存儲(chǔ)原理與技術(shù)[M].北京：清華大學(xué)出版社,2005:33-55.

[8]江藤良純,金子敏信.糾錯(cuò)碼及其應(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.

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