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

3 陣列編碼

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

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

3.1 EVENODD碼

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

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

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

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

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

也就是說(shuō)當第一輔對角校驗和為1時(shí)，其他各對角校驗為奇校驗;當第一輔對角校驗和為0時(shí)，其他各對角校驗為偶校驗。這就是它被命名為EVENODD碼的原因。

3.2 RDP碼

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

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

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

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

3.3 Liberation碼

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

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

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

3.4 PDHLatin碼

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

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

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

3.5 X碼

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