RS柯西碼編碼算法改進研究

袁 煒，于 瀛，唐 聃

成都信息工程大學 軟件工程學院，成都610225

1 引言

隨著大數據產業的蓬勃發展，擁有巨大存儲量的分布式存儲系統得到了廣泛的應用。數據存儲量呈現指數級增長，對存儲系統的數據可靠性提出了更高的要求。根據調查報告顯示，在2015年，全球的存儲數據量達到8.61 ZB，并且推斷10年后，全球用于存儲的服務器總量將增長10倍[1]。分布式存儲系統的規模越大，節點越多，節點失效的概率也越大。因此，在節點失效的情況下，分布式存儲系統需要使用一種數據容錯技術來保障數據的可靠性，能夠繼續提供服務。

目前，常見的數據容錯技術主要有多副本技術和糾刪碼容錯技術。其中，多副本技術是在分布式存儲系統中最為常見的容錯技術。著名的云存儲系統GFS[2]和Hadoop[3]都采用了此技術。多副本技術具有方案簡潔、易于實施、構建成本低、便于擴展、無需任何運算等明顯優勢。但到了大數據時代，多副本技術需要消耗巨大的存儲空間來維持其高容錯能力。這導致其無法滿足數據中心等大規模的分布式存儲系統的需求。與多副本技術相比，在相同的容錯能力下，糾刪碼容錯技術的修復帶寬和更新代價更小，存儲效率更高。糾刪碼容錯技術利用編碼算法生成冗余數據，來實現對數據的容錯。編碼理論由Shannon C E首次提出，最初的應用主要在于網絡通信領域，解決網絡傳輸中的傳輸錯誤以及數據包丟失問題[4]。之后，Rizzo L 在1997 年的文獻[5]中提出利用糾刪碼提高通信協議的可靠性的方法，也提出可將其應用在分布式存儲系統中增強數據可靠性。

在分布式存儲系統中，糾刪碼容錯技術的研究熱點主要在兩大方面。一是陣列碼。陣列碼的編解碼過程都只涉及二進制異或運算，具有構建方法簡單，易于軟硬件實現，運算效率高的特點。但陣列碼的容錯能力低以及對存儲陣列尺寸有嚴格的要求，限制了陣列碼的實用性。典型的MDS 陣列碼中有二容錯的EVENODD[6]碼和X[7]碼，三容錯的STAR[8]碼。但是目前為止還沒有出現容錯能力大于3的MDS 陣列碼。第二便是RS碼?；赗S碼的糾刪碼容錯技術是分布式存儲系統容錯的熱門選擇。分布式存儲系統Ceph 以及前不久推出的Hadoop 3.0 都采用了基于RS 碼的糾刪碼容錯技術。RS 碼是糾刪碼體系中唯一一種能夠糾任意錯的MDS碼，在理論上容錯能力不受限制且擁有最優的存儲效率。然而RS 碼的編解碼過程中涉及多元有限域的運算，尤其是多元有限域的乘法運算，這使得RS碼的計算復雜度高，嚴重影響了RS 碼的編解碼效率。復雜的計算使得計算代價過高，而這種計算代價是大規模分布式存儲系統難以承受的。

針對RS 碼的計算效率問題，學者們提出了一些優化方案。例如，通過查表的方式進行有限域的運算[9]；將多元有限域的運算轉換到二元域上[10]；又或是通過指令集來加快多元有限域運算的GF-Complete[11]。其中最典型的方法是將多元有限域的計算轉換到二元域上。從以上的優化方案可以看出，目前對RS 碼的優化主要集中于對有限域運算的優化，對RS 碼本體的優化相對較少。本文提出一種方法在RS 柯西碼的基礎上，根據柯西碼的一些特性，減少計算量，并將柯西碼陣列化，降低計算復雜度，最后，通過一種重復運算優化算法再次減少計算量，以此提高編碼效率。該方法使得編解碼過程只需異或運算和較少的計算量，這對提高RS 碼在分布式存儲系統容錯領域的實用性有著重要意義。

2 RS柯西碼

2.1 算法核心

1960 年Reed I 首次提出RS 碼[12]。RS 碼主要分為兩種：一種是范德蒙碼; 另一種是柯西碼[13]。兩者的區別在于其選擇的生成矩陣不同，范德蒙碼采用的是范德蒙矩陣，而柯西碼采用的是柯西矩陣。所以，柯西碼的算法核心在于柯西矩陣的構建。

定義1 設X 和Y 是有限域中的兩個元素集。其中，X={x1,x2,…,xm} ，Y={y1,y2,…,yn}。若滿足?i ∈{1,2,…,m}，?j ∈{1,2,…,n}有：

（1）xi+yj≠0；

（2）?i,j ∈{1,2,…,m}，i ≠j，xi≠xj；

（3）?i,j ∈{1,2,…,n}，i ≠j，yi≠yj。

稱下列矩陣為柯西矩陣：

以上便是柯西矩陣的定義。

2.2 二進制矩陣

RS碼的經典優化方法是利用二進制矩陣表示有限域元素進行運算[9]。這一方法極大地減少了有限域的運算復雜度，本文提出的方法需借助此方法將RS 柯西碼進行陣列化。接下來對其進行簡要介紹。

二進制矩陣的構造方法如下：

首先，求有限域元素的系數向量。多項式g(x)可以表示有限域GF(2w)上的所有元素，其中GF(2))，列向量v(x)=(g0,g1,…,gw-1)T稱為多項式的系數向量。

然后根據定義2構造二進制矩陣。

定義2 對于任意元素e ∈GF(2w)，設α(e)是一個第i 列為xie mod p(x)的系數向量的二進制矩陣，其中p(x)是GF(2w)中度為w 的不可約多項式。

這些二進制矩陣擁有以下性質：

性質1 α 是GF(2w)到β(GF(2w))的同構，并且有：

（1）α(0)是一個全0矩陣；

（2）α(1)是一個單位矩陣；

（3）α 是一個單射；

（4）對于任意兩個元素a,b ∈GF(2w)，有α(a+b)=α(a)+α(b)；

（5）對于任意兩個元素a,b ∈GF(2w)，有α(ab)=α(a)α(b)。

在RS柯西碼中，首先選取元素集X 、Y ，然后根據X 和Y 構建柯西矩陣，最后，將柯西矩陣中的有限域元素用二進制矩陣表示。如此便達到將有限域運算轉換為二進制的異或運算的目的。

例如，在有限域GF(23)上，構建3 個數據塊，2 個校驗塊的RS柯西碼。

方案1 設選取的元素集為X={1,2},Y={0,3,4}，得到的柯西矩陣和替換后的柯西矩陣為：

方案2 設選取的元素集為X={2,7},Y={0,1,4}，得到的柯西矩陣和替換后的柯西矩陣為：

替換后的RS柯西碼的異或計算量等于替換后的柯西矩陣中1 的數量減去矩陣行數。以上給出的兩個方案，方案1矩陣中1的數量為25，方案2矩陣中1的數量為37，方案2的計算量是方案1的計算量的163%。可見選取的元素集不同，RS柯西碼的計算量也會大不相同。

3 RS柯西碼優化算法研究

在文獻[14]中，也提出選取的元素集不同，RS 柯西碼的計算量會改變的觀點，并對其進行較為深入的研究。為研究替換后的柯西矩陣中1的數量，根據柯西矩陣的性質，構建1 數量矩陣ONES(w)，其中，矩陣中的值ONES(w)i,j是二進制矩陣α()中1 的數量[14]。而在矩陣ONES(w)中選取n（數據塊數量）行以及m（校驗塊數量）列，行列相交的值之和便是替換后柯西矩陣中1 的數量。但在文獻[14]中，并未有選取元素集X 、Y 得到1 數量最少的柯西矩陣的合適方法，只能通過枚舉的方法得到。在之后的已知文獻中也未有提到過選取元素集的最優方法。

于是，本文提出一種優化方法：以一種貪心算法來選取元素集得到局部最優的柯西矩陣，再將其陣列化，并進行運算優化，使得計算量更加接近甚至超過最優柯西矩陣的RS柯西碼。

接下來，介紹在有限域GF(2w)上，構建n 個數據塊，m 個校驗塊的RS柯西碼的貪心算法以及陣列化優化方法。

3.1 貪心算法

通過對矩陣ONES(w)的研究，發現矩陣ONES(w)沿斜率為-1 的斜對角線對稱，并且第2i 、2i+1(0 ≤i ≤2w-1-1)行與第2j 、2j+1(0 ≤j ≤2w-1-1)列相交區域也沿斜率為-1的斜對角線對稱，故而只需要保證X 、Y 在ONES(w)上半部分相加之和越小，則柯西矩陣中1 的數量越小。為方便描述，設有限域中元素e 對應的二進制矩陣中1的數量為We。

以下是貪心算法的詳細步驟：

步驟1 在U1={0,1,2,…,2w-1-1}中，選取2w-2個元素{x1,x2,…,x2w-2}（除0以外），將這些元素歸入X1，選取條件為：

步驟2 再將U1-X1 剩余的2w-2個元素歸入Y1。

步驟3 在U2={2w-1,2w-1+1,…,2w-1} 中，選取2w-2個元素{x2w-2+1,x2w-2+2,…,x2w-1}，將這些元素歸入X2，選取條件為：

步驟4 再將剩余的U2-X2 個元素歸入Y2。

步驟5

（1）當m ＞n 時

①m ≤2w-1，如果n%2=0 ，則取num=n/2；如果n%2 ≠0，則取num=(n+1)/2。從X1 中選取num 個元素{x1,x2,…,xnum}歸入X3 中，選取條件：

②n ≤2w-1，將Y1,Y2 合并成Y3，Y3={y1,y2,…,y2w-1} ，從Y3 選取n 個元素歸于Y 中，選取條件：

（2）當m ≤n 時

①n ≤2w-1，如果m%2=0，則取num=m/2；如果m%2 ≠0 ，則取num=(m+1)/2。從Y1 中選取num 個元素{y1,y2,…,ynum}歸入Y3 中，選取條件：；從Y2 中選取m-num 個元素{ynum+1,ynum+2,…,yn} 歸 入Y4 中，選 取 條 件：。然后將Y3,Y4 合并成Y 。

②m ≤2w-1，將X1,X2 合并成X3，X3={x1,x2,…,x2w-1}，從X3 選取m 個元素{x1,x2,…,xm}歸于X 中，選取條件：

步驟6

（1）當集合X 中的元素個數x_num 小于m 時，從G(2w)-X-Y 中選取 m-x_num 個元素{xx_num+1,xx_num+2,…,xm}歸于X5 中，選取條件：

然后，將X5 合并入X 中。

（2）當集合Y 中的元素個數y_num小于n時，從G(2w)-X-Y 中選取n-y_num 個元素{yy_num+1,yy_num+2,…,yn}歸于Y5 中，選取條件：

然后，將Y5 合并入Y 中。

這樣就得到了最后的X 、Y 。本文算法雖在每一步都取1數量最少的元素，但是還無法保證最終總是取得最優解。

3.2 陣列化及其運算優化方法

根據3.1節的貪心算法，在有的情況下，還無法得到1數量最小的柯西矩陣。于是繼續將其陣列化，并對陣列進行優化。將其陣列化既能夠方便進行運算優化，又能夠在譯碼時使用更簡單高效的譯碼方法，避免使用復雜度高的RS柯西碼的方程求解譯碼法。

以下是陣列化以及運算優化方法的步驟：

步驟1 設3.1節得到的元素集為X 、Y 。根據元素集X 、Y 構建柯西矩陣M1。然后將矩陣M1 中有限域元素用二進制矩陣表示，替換后的矩陣為M2。

步驟2 將RS 柯西碼原來的n 個數據塊，每一個切分為w 塊。設這n×w 個數據塊分別為D1,1,D1,2,…,D1,w,D2,1,…,Dn,w。

步驟3 計算校驗塊所需的數據塊。

其中：

步驟4 進行陣列布局。為了不影響RS 柯西碼的MDS 性質，將原本屬于一個節點的抽象數據塊放置于同一列上，條帶大小依舊保持與原始的RS 柯西碼一致。設排列后的陣列為A1。

步驟5 進行運算優化。

（1）R1,1,R1,2,…,R1,w,R2,1,…,Rm,w都是由D1,1,D1,2,…,D1,w,D2,1,…,Dn,w進行異或計算得到。因此，將D1,1,D1,2,…,D1,w,D2,1,…,Dn,w中每一個數據塊都視作一個點。所有點組成點集P 。將R1,1,R1,2,…,R1,w,R2,1,…,Rm,w組成計算式集。

（2）遍歷計算式集中的計算式，如有Da1,b1⊕Da2,b2⊕Da3,b3(0 ＜ai ＜n,0 ＜bi ＜m,i=1,2,3) ，則 將 點Da1,b1與 點Da2,b2，點Da1,b1與點Da3,b3，點Da2,b2與點Da3,b3連線。若是兩點之間之前并沒有連線，則進行連線，次數記為1；如果兩點之間已有連線，則次數加1。

（3）當將計算式集中所有的計算式都連線完畢后，統計n×w 個點構成的圖中兩點之間的次數，保留次數最大的一條或多條線，如果次數都為1 則直接繼續步驟（5）。

（4）在保留的線中，如果只有一條線，則直接將線的兩個端點對應的數據塊組成的計算式，作為替換式；如果有多條線，則從中選取不相交的線，將這些不相交的線的兩個端點對應的數據塊組成的計算式，作為替換式。

（5）利用替換式，替換陣列。最后，將替換式也視為點，加入點集中，重新進行步驟（2）。

（6）所有替換完成后，最終陣列為A2，將A2 中還依然保留的替換式保存到集合S 中。

當以上步驟都完成后，便完成了對RS 柯西碼的優化過程。優化過程只需運行一次，之后的編碼直接按照構建好的陣列以及替換式進行編碼，無需重復執行。

4 具體實例

上一章對優化算法進行了系統的講解，本章將采用典型的實例來進一步分析和說明本文算法。

例 以在有限域上數據塊數為4，校驗塊數為3 的RS柯西碼為例。接下來，分為兩步簡要介紹該RS柯西碼的優化方法。

（1）貪心算法選取X 、Y

步驟1 構建有限域GF(23)的ONES(3)矩陣。

按照ONES(w)矩陣的構造方法，構造ONES(3)矩陣。得到矩陣如下：

柯西矩陣的X 中的元素不能與Y 的元素相等，所以矩陣ONES(w)對角線沒有值。

步驟2 設X1 是從U1={0,1,2,3} 中選取2 個元素（除0 以外）組成的集合。即從矩陣ONES(3)的第0 行中的第1、2、3列中選取值最小的兩列，將選取的列的序號加入到集合X1 中。X1={1,2}。

步驟3 將剩余的0、3列加入集合Y1。Y1={0,3}。

步驟4 在U2={4,5,6,7}中選取兩個元素組成X2。即從矩陣ONES(3)的第4，5，6，7列中選取第0和3行相加值最小的兩列，將選取的列的序號加入到集合X2中。X2={4,5}。

步驟3 進行陣列布局，得到陣列：

步驟5 Y2=U2-X2={6,7}。

步驟6 因為n ＞m，n=23-1，m%2=1，取num=2。從Y1 中選取2 個元素組成Y3。Y3={0,3}。從Y2 中選取1個元素組成Y4。Y4={6}。然后將Y3，Y4 合并為Y 。Y={0,3,6}。

步驟7 因為m=23-1。將X1，X2合并為X3。X3={1,2,4,5}。從X3 中選取3個元素組成X 。X={1,2,4}。選取條件為：

步驟8 集合Y 中的元素個數小于n，從G(2w)-XY 中選取1個元素組成Y5。Y5={5}。選取條件為：

然后將Y5 的元素添加入Y 中。

（2）陣列化并進行陣列運算優化

步驟1 根據貪心算法得到元素集X={1,2,4}和Y={0,3,5,6}構建柯西矩陣。并用2.2節所述的二進制矩陣替換矩陣中有限域元素，替換后的柯西矩陣為M2。

步驟2 取12個數據塊，標記為D1,1,…,D1,3,D2,1,…,D4,3，計算冗余陣列：

步驟4 將數據塊D1,1,D1,2,D1,3,D2,1,…,D4,3視為視為點。所有點組成點集P。將R1,1,R1,2,R1,3,R2,1,…,R3,3組成計算式集。

步驟5 遍歷計算集，對點集中的點進行連線，記錄次數。如圖1所示。

圖1 第一次連線圖

圖1 中只展示了部分次數較多的線條。可見連線次數最多為4，選擇次數為4的不相交的連線（如紅色線條）。然后將和作為替換式。將替換式對整個陣列進行替換。最后，將替換式也視為點，加入點集中。再次進行步驟5，直到連線次數最多為1。

步驟6 所有替換完成后，最終陣列為，將依然保留的替換式保存到集合中。如下所示：

優化結束，優化后的RS 柯西碼直接根據陣列A2和集合S 就可以直接編碼，類似于陣列碼的編碼過程。

5 性能分析與對比

對于糾刪碼而言，其關鍵在于編解碼，本文主要研究的是RS柯西碼的編碼優化方法。本文提出的改進算法在確定了數據塊數量和冗余塊數量后，需要先進行貪心算法，陣列化以及運算優化一系列過程后，才能進行編碼。在這一過程中，貪心算法需要消耗一定的計算資源，但是此過程在固定了數據塊和冗余塊數量的情況下只需要執行一次，之后的編碼過程按照最后優化后的陣列進行異或運算編碼即可。所以在分布式存儲系統中，一次貪心算法所消耗的計算資源完全可以接受。

5.1 更高的編碼效率

在有了二進制矩陣替換有限域元素的方法，將復雜的有限域運算轉換為簡單的異或運算，RS 柯西碼的計算復雜度得到了一定程度的降低。但集合X 、Y 的不同，對RS柯西碼的編碼效率影響非常大。目前，并沒有一個好的方法去得到最優集合X 和Y ，只能通過遍歷得到，隨著規模加大，得到最優集合的代價也會隨之增加。也有采取隨機的方式來選取集合X 和Y ，但得到的柯西矩陣的1的數量無法得到保證。圖2展示了優化后的RS 柯西碼與遍歷最優RS 柯西碼、隨機RS 柯西碼的編碼所需異或數對比情況，并且以兩種不同條件進行更全面的展示。圖2（a）展示的是在保持校驗塊數為4，有限域為GF(24)的條件下，數據塊數從4到9編碼所需的異或數變化情況。圖2（b）展示的是在保持數據塊數為4，有限域為GF(24)的條件下，校驗塊數從4到8編碼所需的異或數變化情況。從圖中可以看出經過優化后的RS 柯西碼編碼所需的異或數遠小于文獻[14]的遍歷最優RS 柯西碼，并且選取集合X 、Y 的代價也相對較小。

圖2 優化后的RS柯西碼的編碼所需異或數對比

編碼效率不僅能夠通過編碼所需的異或數來體現。通過編碼時間也能更直觀地反應編碼的效率。圖3與圖4 分別展示了優化后的RS 柯西碼與EVENODD碼、STAR 碼分別對1～10 MB 的文件進行編碼的編碼時間對比情況，并分為數據塊數為5 和7 分別進行對比。從圖中可以看出經過優化的RS柯西碼的編碼時間與以編碼效率著稱的陣列碼中的代表EVENODD碼和STAR碼相差不大，甚至有一些優勢。并且對于EVENODD碼和STAR碼，容錯超過3便失效了?？梢妰灮蟮腞S柯西碼編碼效率有了很大幅度的提升。

圖3 優化后的RS柯西碼與EVENODD碼的編碼時間對比

圖4 優化后的RS柯西碼與STAR碼的編碼時間對比

5.2 更簡單高效的譯碼方案選擇

本文提出的優化方法雖然主要是提升編碼效率，但是對RS 柯西碼的譯碼也有積極的影響。未優化前的RS 柯西碼雖然通過將有限域的運算轉換為異或運算，對譯碼的效率有所提升。但其在譯碼過程中仍未消除需要對矩陣進行求逆這一復雜的操作，這也導致譯碼效率無法得到更有效的提升。經過優化后的RS柯西碼在編碼的過程中更貼近于陣列碼的編碼過程，因此可以選擇使用更簡單高效的譯碼方法，不需要對矩陣進行求逆。例如文獻[15]中提出矩陣譯碼方法，在陣列碼中的應用最佳，利用該方法對優化后的RS 柯西碼進行譯碼。省去對矩陣求逆這一復雜操作，且譯碼過程只涉及異或運算，譯碼效率將有大幅度的提升。

6 結束語

本文在分析RS 柯西碼算法存在的缺陷的基礎上，提出利用貪心算法和二進制矩陣對RS柯西碼編碼的改進算法。改進后的RS柯西碼采用貪心算法減少了柯西矩陣中1 的數量，一定程度上降低了計算量，提高了編碼效率。同時，在改進的RS 柯西碼中利用二進制矩陣進行陣列化，降低計算復雜度，并加以運算優化，再次提升編碼效率，從而使算法能夠跳出局部最優的局限，將編碼效率提升至接近甚至超越最優解。

通過仿真實驗和分析可知，改進算法不僅大幅度減少了計算量，有著較高的編碼效率，并且對譯碼來說，經過陣列化的編碼過程能夠選擇更為高效簡單的譯碼方法，一定程度上提高譯碼效率，算法有較高的實用性。