基于EEOD碼的一種有效的數(shù)據(jù)分布策略

在EVENODD碼的基礎(chǔ)上，提出一種新的基于EEOD碼的數(shù)據(jù)布局分布策略。該策略只需要三個(gè)額外的存儲(chǔ)設(shè)備保存校驗(yàn)信息，能容許任意三個(gè)存儲(chǔ)設(shè)備同時(shí)故障。策略中的校驗(yàn)方程組用圖的回路表示，可將其頂點(diǎn)逐步消除，把譯碼過(guò)程歸結(jié)為圖回路的疊加。討論了基于EEOD碼數(shù)據(jù)分布策略的性能，與其他策略相比，其容災(zāi)能力大幅度提高，編碼和譯碼過(guò)程只需要簡(jiǎn)單的異或運(yùn)算，但空間利用率和系統(tǒng)吞吐量的影響非常小。
關(guān) 鍵 詞 數(shù)據(jù)分布策略; EEOD碼; EVENODD碼; 可靠性

可靠性是分布式存儲(chǔ)系統(tǒng)最重要的指標(biāo)之一，也是當(dāng)今信息社會(huì)對(duì)信息存儲(chǔ)的迫切需求[1]。文獻(xiàn)[2]提出了利用編碼技術(shù)構(gòu)建高可靠性的分布式存儲(chǔ)系統(tǒng)，其基本思想為：一個(gè)目標(biāo)文件可劃分為m塊，然后利用某編碼把m塊編碼為n塊，并分別存儲(chǔ)在n個(gè)不同的存儲(chǔ)設(shè)備上；當(dāng)發(fā)生特殊狀況(自然災(zāi)害、戰(zhàn)爭(zhēng)、意外損壞等)造成其中某些存儲(chǔ)設(shè)備部分或者全部發(fā)生損壞時(shí)，可以通過(guò)存放在該系統(tǒng)其他存儲(chǔ)設(shè)備上經(jīng)過(guò)編碼的冗余數(shù)據(jù)恢復(fù)損壞的數(shù)據(jù)，從而增強(qiáng)系統(tǒng)的安全性。
目前，容許兩個(gè)存儲(chǔ)設(shè)備同時(shí)故障的數(shù)據(jù)分布策略的編碼有EVENODD碼[3]、X碼、B碼[4]、S碼[5]等；容許多個(gè)設(shè)備同時(shí)故障，特別是容許三個(gè)設(shè)備同時(shí)故障的數(shù)據(jù)分布策略的編碼，如Blaum碼[6]、WEAVER碼[7]、HoVer碼[8]、HDD1碼和HDD2碼[9]等。但是Blaum碼解碼方法是解多項(xiàng)式環(huán)上的一組線(xiàn)性方程，解碼算法不易實(shí)現(xiàn)、復(fù)雜度高。HoVer碼、WEAVER碼不是MDS碼，冗余盤(pán)數(shù)目并不是隨著磁盤(pán)陣列系統(tǒng)總盤(pán)數(shù)的線(xiàn)性增長(zhǎng)，冗余信息量太大、代價(jià)昂貴。而HDD1碼和HDD2碼的解碼過(guò)程需要做線(xiàn)性方程高斯消元求解，其解碼復(fù)雜度等于9。
本文在EVENODD碼的基礎(chǔ)上，提出了一種擴(kuò)展EVENODD碼——EEOD碼，能容許任意三個(gè)存儲(chǔ)設(shè)備同時(shí)故障，同時(shí)校驗(yàn)方程組用圖的回路表示，譯碼過(guò)程可看作圖回路的疊加。與其他策略相比，冗余率達(dá)到最優(yōu)，編譯碼復(fù)雜度和更新復(fù)雜度都相對(duì)較低。
1 EEOD碼的編碼方法
1.1 EVENODD碼
為了能夠承受三個(gè)磁盤(pán)同時(shí)故障，EEOD在EVENODD碼的基礎(chǔ)上進(jìn)行了擴(kuò)展，其編碼矩陣為m+3列，行為m?1列，其中前m列存放原始數(shù)據(jù)，后3列存放冗余校驗(yàn)數(shù)據(jù)。EEOD碼的前兩列冗余的構(gòu)造與EVENODD完全一樣，后一列為增加1列冗余校驗(yàn)列，則三列冗余校驗(yàn)位構(gòu)造公式為：