基于二元域再生碼的編碼研究?

喬平安 任 靜 田晶晶

（西安郵電大學(xué)計(jì)算機(jī)學(xué)院 西安 710061）

1 引言

大數(shù)據(jù)時(shí)代，信息資源的急速增長(zhǎng)，存儲(chǔ)系統(tǒng)對(duì)存儲(chǔ)容量、數(shù)據(jù)可用性和可靠性提出了越來(lái)越高的要求。為了保護(hù)數(shù)據(jù)，存儲(chǔ)系統(tǒng)常常會(huì)采用一些冗余策略。在過(guò)去的存儲(chǔ)系統(tǒng)如GPFS，Ceph［1］采用的冗余策略是完全復(fù)制。雖然數(shù)據(jù)的完全復(fù)制適合于高負(fù)載系統(tǒng)，但它在存儲(chǔ)空間或系統(tǒng)中整體性能的效率都十分低下。因而，研究分布式存儲(chǔ)系統(tǒng)［2～4］中基于糾刪碼的冗余策略對(duì)海量數(shù)據(jù)存儲(chǔ)具有重要意義。

2 基本概念

2.1 糾刪碼

分布式存儲(chǔ)系統(tǒng)要提高系統(tǒng)的可靠性和容錯(cuò)性需要采用一定的策略。傳統(tǒng)的冗余策略通常是采用完全副本技術(shù)。完整的復(fù)制生成源文件的多個(gè)副本，然后將它們分發(fā)到不同的存儲(chǔ)節(jié)點(diǎn)。只需要源文件和副本有一個(gè)是完整的，就不會(huì)使得數(shù)據(jù)丟失。完整副本技術(shù)容易實(shí)現(xiàn)，比較適合高負(fù)荷的系統(tǒng)，但有耗費(fèi)較多的存儲(chǔ)空問(wèn)的缺點(diǎn)［5～6］。

另一種冗余策略，糾刪編碼［7～11］。一般來(lái)說(shuō)，糾刪碼可以用一個(gè)四元組｛n，k，b，k'｝來(lái)表示，其中，n是編碼后的文件塊個(gè)數(shù)，k是編碼前文件塊的個(gè)數(shù)，b 是每個(gè)文件塊包含的比特?cái)?shù)，k'是不小于k 的數(shù)。首先，用戶的文件數(shù)據(jù)被分成k 個(gè)塊，用集合表示為F=｛F1，F(xiàn)2，…，F(xiàn)k｝，其中Fi（1 ≤i ≤k）是一個(gè)包含b 比特的文件塊。我們假設(shè)糾刪碼的編碼函數(shù)是E 并且解碼函數(shù)是D，對(duì)原文件編碼E（F）=｛F1'，F(xiàn)2'，…，F(xiàn)n'｝，F(xiàn)i'（1 ≤i ≤n）大小仍為b 比特。設(shè)E（F'）是E（F）中任意k'（k' ≥k）個(gè)文件塊組成的了文件，那么D（E（F'））=F，即得到E（F）中的任意k'個(gè)文件塊就可以用解碼函數(shù)D還原出原文件。

通俗講，一個(gè)（n，k）糾刪碼是把k 個(gè)源數(shù)據(jù)編碼為n（n＞k）個(gè)數(shù)據(jù)，用其中任意k 個(gè)數(shù)據(jù)就可以還原出原來(lái)的數(shù)據(jù)。作為一種高效的數(shù)據(jù)冗余方式，它被運(yùn)用于存儲(chǔ)系統(tǒng)中。首先用戶將要存儲(chǔ)的文件被劃分成固定大小的數(shù)據(jù)塊，然后使用編碼理論對(duì)其進(jìn)行編碼。對(duì)于k 個(gè)數(shù)據(jù)塊，根據(jù)糾刪碼生成n 個(gè)一樣大小并唯一標(biāo)識(shí)的數(shù)據(jù)塊（n＞k），存儲(chǔ)在相應(yīng)的存儲(chǔ)系統(tǒng)中，只要保證存儲(chǔ)系統(tǒng)中有k 個(gè)數(shù)據(jù)塊是正確的，那么存儲(chǔ)系統(tǒng)就被認(rèn)為是可靠的。

糾冊(cè)碼提供了一種存儲(chǔ)優(yōu)化的冗余機(jī)制來(lái)保護(hù)存儲(chǔ)的數(shù)據(jù)。在分布式存儲(chǔ)系統(tǒng)中，編碼的文件塊存儲(chǔ)在不同的節(jié)點(diǎn)上。當(dāng)系統(tǒng)中某些節(jié)點(diǎn)由于某種原因失效時(shí)，用戶仍然可以從文件的其余部分恢復(fù)原始文件。也就是說(shuō)一定數(shù)量的節(jié)點(diǎn)故障不會(huì)導(dǎo)致用戶數(shù)據(jù)丟失。

2.2 二元域再生碼

再生碼作為一種糾刪碼，首次由Dimakis 等提出［12］。再生碼可用于對(duì)失效的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)修復(fù)且滿足MDS 性質(zhì)［13］。節(jié)點(diǎn)數(shù)據(jù)修復(fù)方法包括精確修復(fù)與功能性修復(fù)。在精確修復(fù)中，新加入的節(jié)點(diǎn)中的數(shù)據(jù)必須同失效的節(jié)點(diǎn)中的數(shù)據(jù)保持一致。而在功能性修復(fù)中，并不要求新加入節(jié)點(diǎn)的數(shù)據(jù)與失效節(jié)點(diǎn)的數(shù)據(jù)保持一致，只需要保證任取k 個(gè)節(jié)點(diǎn)的數(shù)據(jù)即可恢復(fù)所有的原始數(shù)據(jù)。

2013年，Hou等提出了一種基于二元域異或操作的再生碼［14］，該種再生碼以移位相加的方式進(jìn)行編碼。隨后，Kenneth 等提出另一種運(yùn)算在二元域上的再生碼［15］。

表1 二進(jìn)制循環(huán)移位再生碼

表1 表示的是Kenneth 等提出的碼長(zhǎng)為5 位的二元域再生碼的數(shù)據(jù)包構(gòu)成。數(shù)據(jù)包c(diǎn)1和c2的前4位數(shù)據(jù)為原始數(shù)據(jù)，最后一位數(shù)據(jù)b1，4=b1，0+b1，1+b1，2+b1，3，同理b2，4=b2，0+b2，1+b2，2+b2，3。數(shù)據(jù)包c(diǎn)3和c4經(jīng)c1移位異或c2而得。該種再生碼基于循環(huán)移位相加方式進(jìn)行編碼，因此稱之為二進(jìn)制循環(huán)移位再生碼。該再生碼因只運(yùn)算在二元域上，因此其編解碼的復(fù)雜度較低，重建帶寬效率較高，是一種性能較好的分布式存儲(chǔ)方案。但是，該再生碼的節(jié)點(diǎn)可擴(kuò)展性較差，目前只適用于4 個(gè)分布式存儲(chǔ)節(jié)點(diǎn)，有比較大的局限性。

3 基于二元域循環(huán)移位的編碼設(shè)計(jì)

3.1 編碼方案

基于上文提到的再生碼編碼的思想，本文提出一種適用于8 個(gè)分布式存儲(chǔ)節(jié)點(diǎn)的編碼方式，不僅滿足MDS 碼性質(zhì)，還操作在二元域，具有較低的編解碼復(fù)雜度和較低的存儲(chǔ)開(kāi)銷，同時(shí)提高了存儲(chǔ)系統(tǒng)的安全性和容錯(cuò)能力，具體方案如下。

將數(shù)據(jù)存儲(chǔ)在8個(gè)存儲(chǔ)節(jié)點(diǎn)中。其中，節(jié)點(diǎn)1、節(jié)點(diǎn)2、節(jié)點(diǎn)3 和節(jié)點(diǎn)4 存儲(chǔ)4 個(gè)原始數(shù)據(jù)包，節(jié)點(diǎn)5、節(jié)點(diǎn)6、節(jié)點(diǎn)7、節(jié)點(diǎn)8存儲(chǔ)4個(gè)編碼數(shù)據(jù)包。前4個(gè)節(jié)點(diǎn)稱為數(shù)據(jù)節(jié)點(diǎn)，后4 個(gè)節(jié)點(diǎn)稱為校驗(yàn)節(jié)點(diǎn)。在這8 個(gè)節(jié)點(diǎn)中，每個(gè)節(jié)點(diǎn)中都存儲(chǔ)m 位的信息，且m為正奇數(shù)。該編碼過(guò)程包括兩個(gè)步驟：數(shù)據(jù)節(jié)點(diǎn)內(nèi)冗余編碼和校驗(yàn)節(jié)點(diǎn)內(nèi)冗余編碼。

1）數(shù)據(jù)節(jié)點(diǎn)內(nèi)冗余編碼

假設(shè)有一個(gè)大小為B 的文件需要存儲(chǔ)，首先將B 均分為4 等份，每份大小為B/4，令每份大小為m-1，即B/3=m-1。分別記這4 等份數(shù)據(jù)為b1'、b2'、b3'、b4'。然后對(duì)b1'、b2'、b3'、b4'進(jìn)行編碼，得到b1、b2、b3、b4這4個(gè)數(shù)據(jù)包，每份大小為m。碼編碼過(guò)程為將4個(gè)數(shù)據(jù)包中的m 位信息分成兩部分，第一部分為bi，0，bi，1，…，bi，m-2，i∈（1，2，3，4）；第二部分為bi，m-1，i∈（1，2，3，4）。其中，根據(jù)式（1）編碼得到bi，m-1。

2）校驗(yàn)節(jié)點(diǎn)內(nèi)冗余編碼

設(shè)有公式：

由公式可定義c1，c2，c3和c4。b（z）是一個(gè)4維向量，其第i個(gè)組成部分是bi（z）。

對(duì)c1，c2，c3和c4這4 個(gè)數(shù)據(jù)包進(jìn)行編碼，得到編碼數(shù)據(jù)包c(diǎn)5，c6，c7和c8。c1～c8都是原始數(shù)據(jù)b（z）的線性組合，有：

將c1（z）～c8（z）依次串聯(lián)得到c（z），即矩陣c（z）是一個(gè)8維向量，其第i個(gè)組成部分是ci（z），有：

其中：

A（z）是一個(gè)8×4 的矩陣，ai，j是其第（i，j）個(gè)元素，i=1，2，…，8。

最后，將ci（z）對(duì)應(yīng)的8 個(gè)數(shù)據(jù)包。分散存儲(chǔ)在8個(gè)分布式節(jié)點(diǎn)中。

3.2 編碼應(yīng)用實(shí)例

一個(gè)根據(jù)編碼方案構(gòu)成的碼長(zhǎng)為5 位的二進(jìn)制循環(huán)移位再生碼數(shù)據(jù)包構(gòu)成如表2 所示，其中，m=5，其中c1包含b1，j，這5 位信息，j∈（0，1，2，3，4）；c5包含b1，j1+b2，j2+b3，j3+b4，j4這5 位信息，其中j1=j2且依次取1，2，3，4，0，而j3=j4且依次取0，1，2，3，4。如表2所示。

3.3 解碼過(guò)程

解碼過(guò)程分4 種情況，下面分別闡述各種情況的解碼過(guò)程。

1）三個(gè)數(shù)據(jù)節(jié)點(diǎn)、一個(gè)校驗(yàn)節(jié)點(diǎn)

首先，從c1，c2，c3，c4中任取3 個(gè)數(shù)據(jù)包c(diǎn)i1，ci2和ci3，i1，i2，i3∈｛1，2，3，4｝；再?gòu)腸5，c6，c7和c8中取1個(gè)數(shù)據(jù)包c(diǎn)i1'，i1'∈｛5，6，7，8｝；將ci1，ci2和ci3代入ci1'可解出ci4，i4∈｛1，2，3，4｝｛i1，i2，i3｝。

2）兩個(gè)數(shù)據(jù)節(jié)點(diǎn)、兩個(gè)校驗(yàn)節(jié)點(diǎn)

首先，從c1，c2，c3，c4中任取2 個(gè)數(shù)據(jù)包c(diǎn)i1，ci2，i1，i2∈｛1，2，3，4｝；再?gòu)腸5，c6，c7和c8中取2 個(gè)數(shù)據(jù)包c(diǎn)i1'，ci2'，i1'i2'∈｛5，6，7，8｝；解出bi，m-2，i∈｛1，2，3，4｝｛i1，i2｝，最后利用bi，m-2啟動(dòng)鋸齒形解碼過(guò)程。

3）一個(gè)數(shù)據(jù)節(jié)點(diǎn)、三個(gè)校驗(yàn)節(jié)點(diǎn)

首先，從c1，c2，c3，c4中任取1 個(gè)數(shù)據(jù)包c(diǎn)i1，i1∈｛1，2，3，4｝；再?gòu)腸5，c6，c7和c8中取3 個(gè)數(shù)據(jù)包c(diǎn)i1'，ci2'，ci3'，i1'i2'i3'∈｛5，6，7，8｝；將ci1帶入ci1'，ci2'，ci3'，取ci1'，ci2'，ci3'的所有奇數(shù)位信息ci1，k'，ci2，k'，ci3，k'，k=2n+1，n∈｛0，1，…，（m-3）/2｝，可以解出bi，1，i∈｛1，2，3，4｝｛i1｝，然后將其帶入ci1'，ci2'，ci3'，可以解出bi，2，依次迭代，直到解出所有信息位。

4）四個(gè)校驗(yàn)節(jié)點(diǎn)

取c5，c6，c7和c8來(lái)恢復(fù)出數(shù)據(jù)節(jié)點(diǎn)中所有的信息位。取c5，c6，c7和c8的所有奇數(shù)位信息c5，k，c6，k，c7，k，c8，k，k=2n+1，n∈｛0，1，…，（m-3）/2｝，可以解出：b4，1=c8，0+c5，k+c6，k+c7，k，b3，1=c7，0+c5，k+c6，k+c8，k，b2，1=c6，0+c5，k+c7，k+c8，k，b1，1=c5，0+c6，k+c7，k+c8，k，然后將其帶入c5，c6，c7和c8可以解出b1，2，b2，2，b3，2，b4，2，依次迭代，直到解出所有信息位。

4 實(shí)驗(yàn)及性能分析

4.1 安全性和可靠性

由上述編解碼的方法可以知道，當(dāng)偷竊者竊取到任意存儲(chǔ)節(jié)點(diǎn)的數(shù)目小于4 時(shí)，都不能完整地譯碼出源始編碼，因此，任何一個(gè)節(jié)點(diǎn)編碼后的備份數(shù)據(jù)對(duì)于偷竊者來(lái)說(shuō)都不可用。同時(shí)，當(dāng)失效節(jié)點(diǎn)數(shù)小于4 時(shí)，就可以成功地恢復(fù)出原始的數(shù)據(jù)。實(shí)驗(yàn)結(jié)果如表3。

從實(shí)驗(yàn)結(jié)果可以看出，在失效節(jié)點(diǎn)數(shù)小于4時(shí)，備份數(shù)據(jù)均可以以100%的概率成功恢復(fù)。可知本文提出的編碼方式提高了系統(tǒng)的安全性，同時(shí)與傳統(tǒng)的編碼方式相比較增加了存儲(chǔ)系統(tǒng)的容錯(cuò)能力，提高了系統(tǒng)的可靠性。

表3 二進(jìn)制循環(huán)移位再生碼可靠性測(cè)試

4.2 計(jì)算復(fù)雜度

1）編碼復(fù)雜度

（1）數(shù)據(jù)節(jié)點(diǎn)編碼

對(duì)于一個(gè)大小為4（m-1）的文件，首先將其分等分為4 個(gè)數(shù)據(jù)包，每個(gè)數(shù)據(jù)包包含（m-1）個(gè)信息位。然后再對(duì)這4個(gè)數(shù)據(jù)包中的（m-1）個(gè)信息位進(jìn)行XOR運(yùn)算，得到數(shù)據(jù)節(jié)點(diǎn)中的4個(gè)校驗(yàn)位。該過(guò)程共需4（m-2）步XOR運(yùn)算。

（2）校驗(yàn)節(jié)點(diǎn)編碼

將c1，c2，c3，c4編碼得到c5，c6，c7，c8。需要4×3×m=12m步XOR運(yùn)算。

因此，整個(gè)編碼過(guò)程的復(fù)雜度為O（4（m-2）+12m）=O（16m-8）。

2）解碼復(fù)雜度

解碼有4 種情況，下面分別4 種情況討論解碼復(fù)雜度。

（1）三個(gè)數(shù)據(jù)節(jié)點(diǎn)、一個(gè)校驗(yàn)節(jié)點(diǎn)

抓取個(gè)數(shù)據(jù)包c(diǎn)i1，ci2，ci3，ci1'，將ci1，ci2和ci3代入ci1'可解出ci4，i4∈｛1，2，3，4｝｛i1，i2，i3｝。

上述過(guò)程中，解出ci4中的一個(gè)信息位需要3 步XOR 運(yùn)算，因此解出m 個(gè)信息位共需要3m 步XOR運(yùn)算。綜上所述，整個(gè)解碼過(guò)程的復(fù)雜度為O（3m）。

（2）兩個(gè)數(shù)據(jù)節(jié)點(diǎn)、兩個(gè)校驗(yàn)節(jié)點(diǎn)

抓取數(shù)據(jù)包c(diǎn)i1，ci2，ci1'，ci2'，將ci1，ci2代入ci1'，ci2'該過(guò)程需要4m 步XOR 操作。解出bi，m-2和剩下的2m-1個(gè)信息位分別需要m-2和2m-1步XOR操作。

因此，整個(gè)解碼過(guò)程的復(fù)雜度為O（7m-3）。

（3）一個(gè)數(shù)據(jù)節(jié)點(diǎn)、三個(gè)校驗(yàn)節(jié)點(diǎn)

抓取數(shù)據(jù)包c(diǎn)i1，ci1'，ci2'，ci3'將ci1代入ci1'，ci2'，ci3'該過(guò)程需要m 步XOR 操作。利用數(shù)據(jù)包c(diǎn)i1'，ci2'，ci3'中所有處于奇數(shù)位的信息ci1，k'，ci2，k'，ci3，k'，解出bi，1，i∈｛1，2，3，4｝｛i1｝，該過(guò)程需要3（m-1）步XOR 操作。解出余下的信息位bi，j的過(guò)程需要6（m-1）步XOR操作。

因此，整個(gè)解碼過(guò)程的復(fù)雜度為O（10m-9）。

（4）四個(gè)校驗(yàn)節(jié)點(diǎn)

利用數(shù)據(jù)包c(diǎn)5，c6，c7和c8中所有處于奇數(shù)位的信息c5，k，c6，k，c7，k，c8，k解出bi，1，i∈｛1，2，3，4｝｛i1｝，該過(guò)程需要4（m-1）步XOR 操作。解出余下的信息位bi，j的過(guò)程需要12（m-1）步XOR操作。

因此，整個(gè)解碼過(guò)程的復(fù)雜度為O（16m-16）。

3）實(shí)驗(yàn)驗(yàn)證

由上述分析可知，這種編解碼方式復(fù)雜度與節(jié)點(diǎn)編碼信息量參數(shù)m 呈線性關(guān)系。在不同的文件大小及不同容錯(cuò)參數(shù)下，對(duì)編解碼時(shí)間進(jìn)行了測(cè)試，結(jié)果如圖1所示。

從圖1（a）分析可知編解碼時(shí)間隨文件數(shù)據(jù)量的增加而呈線性增加趨勢(shì)，圖1（b）分析可知當(dāng)文件數(shù)據(jù)量一定時(shí)，解碼時(shí)間隨著失效節(jié)點(diǎn)數(shù)增加呈增加趨勢(shì)。傳統(tǒng)的適用于4 個(gè)節(jié)點(diǎn)的編碼方式只能容許2 個(gè)節(jié)點(diǎn)失效，雖然復(fù)雜度較低但是有比較大的局限性且靈活性不強(qiáng)，可以看出本文提出的編碼方式相較傳統(tǒng)的編碼方式雖然時(shí)間復(fù)雜度略微有所增加，但是具有選取參數(shù)的靈活性和線性的運(yùn)算復(fù)雜度的優(yōu)勢(shì)。

圖1 編解碼耗時(shí)隨參數(shù)變化圖

5 結(jié)語(yǔ)

本文分析了當(dāng)前分布式存儲(chǔ)系統(tǒng)中的常用的的冗余策略，并介紹了一種基于二元域異或操作的再生碼，基于這種編碼方式我們提出一種適用于8個(gè)分布式存儲(chǔ)節(jié)點(diǎn)的編碼方式，通過(guò)理論分析和初步實(shí)驗(yàn)得出它以數(shù)據(jù)恢復(fù)時(shí)間的略微增加為代價(jià)，換取了更高的存儲(chǔ)系統(tǒng)安全性能，同時(shí)具有線性的編解碼復(fù)雜度，提升了系統(tǒng)可靠性。