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

3 陣列編碼

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

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

3.1 EVENODD碼

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

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

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

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

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

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

3.2 RDP碼

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

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

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

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

3.3 Liberation碼

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

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

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

3.4 PDHLatin碼

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

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

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

3.5 X碼

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