容錯(cuò)存儲(chǔ)系統(tǒng)中的MDS陣列碼研究.pdf

1、隨著現(xiàn)代存儲(chǔ)系統(tǒng)在規(guī)模和復(fù)雜性上的不斷增長(zhǎng)，硬盤（節(jié)點(diǎn)）故障已經(jīng)成為系統(tǒng)運(yùn)行中的一個(gè)日常事件。為了防止各類硬件故障造成數(shù)據(jù)丟失，存儲(chǔ)系統(tǒng)一般使用兩種方式對(duì)數(shù)據(jù)進(jìn)行保護(hù)，即多路鏡像和糾刪編碼。多路鏡像雖然實(shí)現(xiàn)簡(jiǎn)單，但這種方式的存儲(chǔ)效率通常較低；而糾刪碼技術(shù)由于可以靈活地調(diào)節(jié)存儲(chǔ)效率而被越來越多的存儲(chǔ)系統(tǒng)采用。最大距離可分的（MDS）陣列碼是一類主要面向存儲(chǔ)系統(tǒng)的糾刪碼，這類碼可以使用最少的冗余來提供特定的容錯(cuò)能力，并且其編解碼過程只需要用

2、到簡(jiǎn)單的異或和循環(huán)移位運(yùn)算，因此在近幾年受到了越來越多的關(guān)注。本文主要針對(duì)糾雙刪和糾三刪的MDS陣列碼進(jìn)行了深入的研究，并取得了以下幾點(diǎn)成果：
　　1、RAID-6正在逐步取代RAID-5成為RAID的主流形式，因?yàn)樗梢栽趦蓚€(gè)磁盤同時(shí)故障的情況下也能夠恢復(fù)數(shù)據(jù)。有許多糾雙刪的MDS陣列碼是專為實(shí)現(xiàn)RAID-6設(shè)計(jì)的，但是這些碼都有它們各自的局限性。本文研究了其中一種有代表性的碼（Blaum-Roth碼），分析其優(yōu)勢(shì)及局限性，并對(duì)

3、其編解碼算法進(jìn)行改進(jìn)。改進(jìn)后的Blaum-Roth碼具有以下優(yōu)秀特性：
　　1）編碼復(fù)雜度達(dá)到理論下界；
　　2）解碼復(fù)雜度接近理論下界；
　　3）可以在幾乎沒有性能損失的前提下實(shí)現(xiàn)RAID-6的可擴(kuò)展性。與其它最常用于RAID-6的MDS陣列碼相比，改進(jìn)后的Blaum-Roth碼更適于構(gòu)建高性能并且可伸縮的RAID-6磁盤陣列。
　　2、糾雙刪的最低密度MDS陣列碼是一類結(jié)構(gòu)優(yōu)美的糾刪碼，具有最優(yōu)的編碼、解碼和

4、更新復(fù)雜度。然而，現(xiàn)有的這類碼或者對(duì)碼長(zhǎng)的限制過于嚴(yán)格，或者編碼規(guī)則沒有明顯的幾何規(guī)律，這使得它們的實(shí)用性較差。為此，本文構(gòu)造了一種新的糾雙刪最低密度MDS陣列碼，稱為對(duì)稱碼。對(duì)稱碼的編碼、解碼和更新復(fù)雜度均達(dá)到最優(yōu)，而且碼長(zhǎng)可以是素?cái)?shù)或者素?cái)?shù)減1。此外，對(duì)稱碼在恢復(fù)單個(gè)刪除列時(shí)所需的I/O開銷比大多數(shù)最低密度MDS陣列碼要少，并且在碼長(zhǎng)較短時(shí)這個(gè)開銷可以接近理論下界。
　　3、最低密度MDS陣列碼由于其編碼和更新復(fù)雜度的最優(yōu)性而

5、廣受歡迎。然而，目前已知的絕大多數(shù)最低密度MDS陣列碼都只能糾兩個(gè)刪除列，雖然有少部分例外，但是它們對(duì)碼長(zhǎng)的限制非常嚴(yán)格。例如，現(xiàn)有的糾三刪的最低密度MDS陣列碼通常要求碼長(zhǎng)為p（或p?1），其中p必須是滿足以下條件的素?cái)?shù)：2為GF(p)的一個(gè)本原元且p?1能夠被3整除。如此嚴(yán)格的碼長(zhǎng)限制使得這些碼幾乎無法被實(shí)際存儲(chǔ)系統(tǒng)采用。為此，本文構(gòu)造了一種實(shí)用的糾三刪的最低密度MDS陣列碼，能夠糾正碼字中的任意三個(gè)刪除列或者一個(gè)刪除列連同一個(gè)差錯(cuò)

6、列。這類碼的解碼復(fù)雜度可以達(dá)到或接近理論下界（取決于刪除模式），并且碼長(zhǎng)可以是p或p+1，其中p是一個(gè)奇素?cái)?shù)。這是目前已知最具實(shí)用價(jià)值的糾三刪的最低密度MDS陣列碼。
　　4、廣義RDP碼被認(rèn)為是目前最實(shí)用和最高效的強(qiáng)系統(tǒng)的MDS碼，因?yàn)槠渚幋a復(fù)雜度達(dá)到了理論下界，并且可以支持任意碼長(zhǎng)。然而，廣義RDP碼的現(xiàn)有解碼算法的解碼復(fù)雜度離理論下界有點(diǎn)遠(yuǎn)，還有一定的改進(jìn)空間。本文對(duì)糾三刪的廣義RDP碼的解碼算法進(jìn)行了研究，并提出了一種針對(duì)