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

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

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