網絡存儲系統容錯編碼技術進展

3 陣列編碼

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

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

3.1 EVENODD碼

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

水平校驗與對角校驗如表1所示。表1中D代表用戶數據單元，P代表冗余校驗單元。可以看出，Disk1—Disk5存儲用戶數據單元;Disk6、7存儲冗余校驗單元。Disk6的各單元為用戶數據各行的水平校驗和，而Disk7的各單元為用戶數據的輔對角線校驗和。

設存儲用戶數據盤的數目為p(如上例中p=5)，則系統包含p+2塊磁盤，前p+1塊磁盤中的最后一個單元為虛擬0元，故每盤實際包含p-1個單元，最后一塊磁盤包含p個單元。可以證明，當p為素數時系統是雙容錯的。

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

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

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

3.2 RDP碼

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

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

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

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

3.3 Liberation碼

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

在這種表示下，前面所說的更新復雜度就對應著矩陣中1的個數。于是構造一個雙容錯陣列碼的問題就轉變為：尋找若干個這樣的矩陣，使得其中1的個數盡量少，并且任意2個之和為滿秩。

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

3.4 PDHLatin碼

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

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

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

3.5 X碼

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