網(wǎng)絡(luò)存儲系統(tǒng)容錯編碼技術(shù)進展

3 陣列編碼

上述幾種編碼各有優(yōu)缺點，那么是否存在對于多指標(biāo)同時最優(yōu)的k容錯編碼方法呢?自文獻[5]提出EVENODD碼起，一大類只使用異或運算的陣列編碼被提出并被人們廣泛研究。

多維陣列或FULL碼等二進制線性碼每塊磁盤只取一個邏輯單元進行校驗運算。而陣列碼則在每塊磁盤上取多個邏輯單元，一起交叉進行校驗運算。校驗計算同2進制線性碼一樣，只使用二進制異或運算，但冗余度卻可以與RS碼相同。

3.1 EVENODD碼

EVENODD碼的想法很簡單，每塊磁盤中取若干單元，排成方陣，然后將這些單元分成不同的校驗組，另外添加兩塊磁盤用于存儲校驗單元。所有校驗組均使用簡單的二進制奇偶校驗。

水平校驗與對角校驗如表1所示。表1中D代表用戶數(shù)據(jù)單元，P代表冗余校驗單元?？梢钥闯?，Disk1—Disk5存儲用戶數(shù)據(jù)單元;Disk6、7存儲冗余校驗單元。Disk6的各單元為用戶數(shù)據(jù)各行的水平校驗和，而Disk7的各單元為用戶數(shù)據(jù)的輔對角線校驗和。

設(shè)存儲用戶數(shù)據(jù)盤的數(shù)目為p(如上例中p=5)，則系統(tǒng)包含p+2塊磁盤，前p+1塊磁盤中的最后一個單元為虛擬0元，故每盤實際包含p-1個單元，最后一塊磁盤包含p個單元?？梢宰C明，當(dāng)p為素數(shù)時系統(tǒng)是雙容錯的。

簡單計算可知此時的系統(tǒng)的冗余度為(2p-1)/((p+2)(p-1)+1)。由于最后的校驗盤多出一個單元，所以冗余度稍稍大于最優(yōu)的2/(p+2)。為了達到最優(yōu)值，文獻[5]中使用如下技巧：將多出的單元(即輔對角交驗和)疊加到該盤其他單元上，構(gòu)造MDS的EVENODD碼如表2所示。

表2也可表示為如表3所示。

也就是說當(dāng)?shù)谝惠o對角校驗和為1時，其他各對角校驗為奇校驗;當(dāng)?shù)谝惠o對角校驗和為0時，其他各對角校驗為偶校驗。這就是它被命名為EVENODD碼的原因。

3.2 RDP碼

從表2可以看出，為了得到冗余最優(yōu)，EVENODD碼的輔對角線上的單元的更新復(fù)雜度很高。每次更新這些單元的數(shù)據(jù)時都要同時更新其他p個校驗單元。對于雙容錯編碼來說，最優(yōu)值為2。文獻[6]中構(gòu)造的RDP編碼將這些單元的更新復(fù)雜度均衡到每個單元，從而有效地消除了寫操作中更新性能的不均衡。一個包含水平校驗的對角線校驗如表4所示。

與EVENODD不同處在于，做對角校驗時也包含了水平校驗單元的一列(因此，數(shù)據(jù)單元也比EVENODD少了一列)。

同樣的，RDP的最后一個校驗盤多出一個單元，使得整個系統(tǒng)不為MDS碼。但RDP碼的優(yōu)勢在于，簡單地將多出的單元刪去，系統(tǒng)仍然為雙容錯的。即得到如表5所示陣列。

從表5可以看出，所有數(shù)據(jù)單元的更新負(fù)載為2或3，分布比EVENODD碼要均勻，不會產(chǎn)生由編碼方式帶來的額外“瓶頸”，但系統(tǒng)的平均更新復(fù)雜度是相同的。

3.3 Liberation碼

從前面幾種編碼可以看出，所使用的方法都是水平校驗加其他一種校驗共同構(gòu)成雙容錯。不同之處就在于“另一種校驗”的不同選擇。如將另一校驗盤上的校驗元看作一個“0”、“1”向量，每塊數(shù)據(jù)盤上的單元對這些校驗元的影響可用一個“0”、“1”矩陣來表示。如表5中的第1列的4個數(shù)據(jù)單元對Disk7中的各校驗元的影響可表示為如圖4所示矩陣。

在這種表示下，前面所說的更新復(fù)雜度就對應(yīng)著矩陣中1的個數(shù)。于是構(gòu)造一個雙容錯陣列碼的問題就轉(zhuǎn)變?yōu)椋簩ふ胰舾蓚€這樣的矩陣，使得其中1的個數(shù)盡量少，并且任意2個之和為滿秩。

在p為素數(shù)時，文獻[7]中構(gòu)造的Liberation碼使得p×p階矩陣1的數(shù)目不超過p+1，其構(gòu)造的p個矩陣可簡單地描述為：各對角線加一個額外單元。第k個矩陣的額外的1單元的位置可描述為(k(p-1)/2 Mod p,1+k(p=1)/2 Mod p)。得到的編碼如表6所示。

3.4 PDHLatin碼

前面這些編碼為MDS碼的充要條件均為：碼長與素數(shù)相關(guān)(RDP為p+1，其他為p+2)。它們的雙容錯解碼方法均為根據(jù)一個已知單元，然后通過校驗關(guān)系與失效單元形成的鏈?zhǔn)疥P(guān)系依次恢復(fù)所有單元。這使人們理解到其容錯能力的本質(zhì)是任意兩列都可以形成這樣的關(guān)聯(lián)結(jié)構(gòu)。文獻[8]中利用拉丁方構(gòu)造了PDHLatin碼，使得碼長不再必須關(guān)聯(lián)一個素數(shù)。

所謂拉丁方是指n×n的方陣中填入n個不同符號，使得每行每列的符號都不重復(fù)。顯然拉丁方的每兩列構(gòu)成一個n元置換。所謂漢密爾頓拉丁方是指拉丁方的任何兩列構(gòu)成的置換為單環(huán)的。圖5為一個9階漢密爾頓拉丁方。

從一個給定的漢密爾頓拉丁方，我們可以用與EVENODD碼類似的方法構(gòu)造編碼，只不過各單元對于第二校驗盤的校驗關(guān)系不再依單元所在對角線位置決定，而是根據(jù)拉丁方相應(yīng)位置的符號決定。根據(jù)圖5，得到表7所示的PDHLatin碼。

3.5 X碼

上面介紹的幾種編碼方法雖然都達到了冗余的最優(yōu)，但在更新復(fù)雜度方面均稍高于最優(yōu)值，那么是否可以達到兩者同時最優(yōu)呢?文獻[9]提出的X碼是一種這樣的雙容錯編碼。