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

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