曾賽峰，屈喜龍，2

(1.湖南工程學(xué)院 計算機與通信學(xué)院，湘潭 411104；2.湖南工程學(xué)院 風(fēng)力發(fā)電機組及控制 湖南省重點實驗室，湘潭 411104)

云存儲環(huán)境下分組校驗糾刪碼冗余算法研究*

曾賽峰1，屈喜龍1，2

(1.湖南工程學(xué)院 計算機與通信學(xué)院，湘潭 411104；2.湖南工程學(xué)院 風(fēng)力發(fā)電機組及控制 湖南省重點實驗室，湘潭 411104)

在海量云存儲系統(tǒng)中,提高存儲利用率,降低冗余方案的計算復(fù)雜度是熱點研究問題.分組校驗糾刪碼冗余算法能夠減少在數(shù)據(jù)重構(gòu)時所需的糾刪碼片段，從而減少對存儲網(wǎng)絡(luò)帶寬以及系統(tǒng)I/O的需求，降低存儲系統(tǒng)的負載.介紹了分組校驗糾刪碼的編碼規(guī)則，參數(shù)設(shè)置，通過實驗分析算法具有良好的容錯能力與空間利用率，能夠滿足云存儲系統(tǒng)需要的編解碼性能. 關(guān)鍵詞：關(guān)鍵詞：云存儲；糾刪碼；冗余算法；分組校驗

0 引言

在分布式存儲系統(tǒng)中，特別是云計算、云存儲系統(tǒng)中數(shù)據(jù)冗余是保證系統(tǒng)可靠性，提高數(shù)據(jù)可用性和持久性最基本的方法[1].通過存儲同一數(shù)據(jù)文件的多個實例到不同節(jié)點，即使部分數(shù)據(jù)不可用，剩余節(jié)點也能足夠重構(gòu)原有數(shù)據(jù)，廣泛使用的冗余策略為副本[2]和糾刪碼[3]兩種.

副本冗余實現(xiàn)簡單，響應(yīng)速度快，但極大地浪費存儲資源，在規(guī)模龐大的云存儲中心勢必會增加系統(tǒng)的投入成本；糾刪碼能夠提高存儲利用率，但是對數(shù)據(jù)分片及解碼算法的引入將增加系統(tǒng)設(shè)計的復(fù)雜度.其次，糾刪碼分片冗余機制要求用戶必須從網(wǎng)絡(luò)的多個節(jié)點中獲得所有分片才可以恢復(fù)原始數(shù)據(jù)，由于地理位置等因素，用戶到多個節(jié)點的時延存在差異，這樣獲取數(shù)據(jù)的最終時延總是取決于到各節(jié)點中的最大者，導(dǎo)致數(shù)據(jù)下載效率降低.本文基于傳統(tǒng)的糾刪碼技術(shù)設(shè)計并實現(xiàn)了分組校驗糾刪碼(Group Parity Erasure Code， GPEC)算法，該算法在保證存儲利用率的同時，能夠降低系統(tǒng)負載，其容錯能力和編解碼效率能滿足云存儲系統(tǒng)對系統(tǒng)可靠性和可用性的要求.

1 分組校驗糾刪碼冗余算法

為能夠減少針對單個數(shù)據(jù)塊重構(gòu)的數(shù)據(jù)塊請求個數(shù)，同時提供高磁盤利用率和數(shù)據(jù)持久性，以里德所羅門編碼[4]為基礎(chǔ)設(shè)計了分組校驗糾刪碼冗余算法.分組校驗糾刪碼冗余算法主要目標是減少分塊重構(gòu)代價，即恢復(fù)一個不可用數(shù)據(jù)塊所需要的最少數(shù)據(jù)塊的個數(shù).如里德所羅門編碼RS(6，3)，表示將文件分為6塊，然后通過這6塊計算出3個校驗塊，總共9個數(shù)據(jù)塊.其中任何一個數(shù)據(jù)塊的丟失都需要6個其他數(shù)據(jù)塊來進行重構(gòu)，不管是原文件分塊還是校驗塊，其分塊重構(gòu)代價則為6.

如圖1所示，GPEC(k，m，g)編碼，將一個文件劃分為k個文件塊(File Parity)，以此計算出m個文件校驗塊(Group Parity)，然后將k個分塊分為g個組，每組計算出一個組校驗塊，即每k/g個文件塊計算出一個組校驗塊.按照傳統(tǒng)糾刪碼的參數(shù)，n等于k+m+g，即經(jīng)過GPEC編碼后總共有k+m+g個數(shù)據(jù)塊，碼率即磁盤利用率為k/n，額外磁盤開銷為(m+g)/k. GPEC(6，2，2)的額外磁盤開銷為0.67，RS(6，3)的額外磁盤開銷為0.5，而三副本冗余方式的額外磁盤開銷為2，通過對比GPEC擁有可接受的磁盤開銷.

圖1 GPEC校驗圖

1.1 分組校驗糾刪碼編碼規(guī)則

編碼規(guī)則是糾刪碼算法的核心內(nèi)容，描述了糾刪碼算法的編碼過程，其對應(yīng)的逆過程即為算法的解碼過程.以GPEC(6，2，2)為例，將文件分為6塊，每三個文件塊一組分為兩組.假設(shè)6個文件塊分別為X0、X1、X2、Y0、Y1、Y2.其中X組包含X0、X1、X2，Y組包含Y0、Y1、Y2.假設(shè)組X和組Y的編碼系數(shù)分別為α、β，在伽羅瓦有限域GF(28)中定義乘法和加法兩種運算，則可建立如下等式：

α00x0+α01x1+α02x2=r1

α10x0+α11x1+α12x2=r2

α20x0+α21x1+α22x2=r3

β00y0+β01y1+β02y2=r4

β10y0+β11y1+β12y2=r5

β20y0+β21y1+β22y2=r6

以此為基礎(chǔ)，定義校驗塊數(shù)據(jù)分別為：GP1=r1，GP2=r4，F(xiàn)P1 =r2+r5，F(xiàn)P2 =r3+r6.為了便于簡化系數(shù)矩陣的尋找過程，假設(shè)α、β矩陣都為范德蒙矩陣，如下所示：

綜上，分組校驗糾刪碼的校驗塊生成等式，即GPEC的編碼規(guī)則為：

X0+X1+X2=GP1

Y0+Y1+Y2=GP2

α0X0+α1X1+α2X2+β0Y0+

β1Y1+β2Y2=FP1

由該編碼規(guī)則可知，GPEC是GF(2w)上的線性碼.根據(jù)Singleton界定理，有漢明距離最小值d≤n-k+1，實驗測試GPEC(6，2，2)中d最大不超過4，表明分組校驗糾刪碼不是極大距離可分碼.根據(jù)上述四個線性方程組構(gòu)成的編碼等式中的系數(shù)矩陣，可以確定分組校驗糾刪碼的一致校驗矩陣中不滿足任意4列線性無關(guān)，根據(jù)最小距離定理，證明GPEC不滿足MDS[4]性質(zhì).

1.2 編碼系數(shù)設(shè)置

依據(jù)上述編碼等式，我們得到一個初步的編碼系數(shù)矩陣即分組校驗糾刪碼的生成矩陣.為了使等式可逆，即數(shù)據(jù)塊丟失時可恢復(fù)，需要找到合適的α和β.GPEC(k，m，g)使用了m+g個校驗塊，根據(jù)編碼后的數(shù)據(jù)丟失情況構(gòu)成解碼方程組，而α和β必須使線性方程組可解.這樣要求線性方程組的系數(shù)矩陣必須可逆，考慮下面這三種數(shù)據(jù)塊丟失情況：

第一種，兩個組校驗塊(GP1，GP2)和兩個文件塊丟失.假設(shè)兩個文件塊各自在X和Y組中，用Xi，Yj表示，則其方程組為：

αiXi+βjYj=R

αi2Xi+βj2Yj=T

從而其解碼系數(shù)矩陣和對應(yīng)的行列式分別為：

由于X組或Y組中任意數(shù)據(jù)塊都有丟失的可能，故下標i、j都分別為0，1，2中的任何一個.從參數(shù)向量中的元素α0，α1，α2，β0，β1，β2都必須滿足基于該系數(shù)矩陣的要求，下面的矩陣或等式中同理.

第二種，一個組校驗塊和三個文件塊的丟失，三個文件塊分別在X和Y組中.假設(shè)三個文件塊中一個在X組中，兩個在Y組中，丟失的組校驗塊為GP2，則可以得到如下線性方程組：

Ys+Yt=S

αiXi+βsYs+βtYt=R

αi2Xi+βs2Ys+βt2Yt=T

故其解碼系數(shù)矩陣為：

=αi(βs-βt)(βs+βt-αi)

第三種，四個文件塊的丟失，且X組和Y組各有兩塊.同前面兩種情況一樣，我們可以得到線性方程組的系數(shù)矩陣為：

αi,αj,βs,βt≠0

αi≠βs

αi≠αj,βs≠βt

αi≠βs+βt,αi+αj≠βs

αi+αj≠βs+βt

為了找到符合該條件的α、β，我們可以查找伽羅瓦有限域GF(28)中的數(shù)值，即αi，βs都是用8位二進制表示的無符號整數(shù).通過計算α和β分別有7個數(shù)值可以選取.例如(0x01，0x02，0x03，0x10，0x20，0x30)即是一組“合法”的(α0，α1，α2，β0，β1，β2).

由于不等式的建立過程中，因式分解丟失了對β2的考察.由于范德蒙矩陣在有限域中滿秩的特性，在參數(shù)設(shè)置的初期我們選擇了范德蒙矩陣作為系數(shù)矩陣.可以看到在GF(28)中，上面有效的β值(二進制低4位和最高位0為0的值)的平方模256皆為0.顯然，這樣的系數(shù)矩陣不屬于范德蒙矩陣，導(dǎo)致在編碼過程中會丟失對應(yīng)的值.為了解決這個問題，需要使用β的低四位，比如將最低的位置1即可保證其平方值在GF(28)下不為零.因為β中高四位的特性，上述不等式仍然可以滿足.最后找到滿足上述所有條件的α和β值，如(0x01，0x02，0x03，0x15，0x25，0x45)即是一組符合條件且保證生成矩陣為非奇異陣的參數(shù).

2 性能對比測試與結(jié)果

本文以目前流行的開源云計算項目Openstack中的分布式對象存儲系統(tǒng)Swift為原型搭建了云存儲系統(tǒng).系統(tǒng)部署在三個機架上的12臺HP服務(wù)器上，其中兩臺服務(wù)器作為代理節(jié)點，其他10臺作為存儲節(jié)點.每個節(jié)點均采用同樣的配置：CPU四核2.0 GHz，千兆網(wǎng)卡、500 G硬盤、操作系統(tǒng)CentOS 6.3.

2.1 編碼效率分析

編碼時間與文件的大小和讀寫速度有很大的關(guān)系，故測試了幾種不同大小的文件， 分別比較分組校驗算法和RS編碼、柯西編碼三種算法的編碼速度.參數(shù)分別為GPEC(k=6,m=2,g=2)、RS(k=6,m=3)、CRS(k=6，m=3).

圖2 編碼速度測試

圖2中結(jié)果顯示，Cauchy RS編碼具有較好的編碼優(yōu)勢，平均編碼速度達到40 MB/s，而標準RS編碼為35 MB/s，分組校驗糾刪碼算法平均速度為32 MB/s，達到了基準速度47.5 MB/s的67.4%，也就是實際編碼計算只占用了其中32.6%的時間.分組校驗糾刪碼算法在文件小于200 MB時，和RS編碼算法效率比較接近，整體上和RS編碼以及Cauchy編碼還有一定的距離和優(yōu)化空間.

2.2 解碼效率分析

當(dāng)出現(xiàn)節(jié)點故障等問題導(dǎo)致數(shù)據(jù)丟失或損壞時，需要對數(shù)據(jù)進行修復(fù)，即解碼.解碼速度主要由數(shù)據(jù)塊讀取速度、網(wǎng)絡(luò)帶寬、譯碼速度等決定.為了更好的體現(xiàn)算法的譯碼速度，所有解碼的數(shù)據(jù)塊均保存到一臺服務(wù)器上.同編碼測試一樣，本節(jié)繼續(xù)以不同大小的文件作為測試的變量，比較分組校驗糾刪碼算法、里德所羅門RS編碼和柯西RS編碼.比較結(jié)果如圖3所示.

圖3 單個數(shù)據(jù)塊丟失文件解碼速度

RS編碼在單個數(shù)據(jù)塊丟失時的平均解碼速度與文件的平均編碼速度較相似，大約在31.5 MB/s左右.Cauchy編碼相對RS編碼，有一定的優(yōu)化，達到38 MB/s.相比RS編碼和Cauchy編碼，分組校驗糾刪碼算法在數(shù)據(jù)塊解碼上花費時間最少，100 M文件不到2 s，平均解碼速度達到50 MB/s.

3 結(jié)論

本文以里德所羅門編碼為基礎(chǔ)設(shè)計了分組校驗糾刪碼冗余算法，詳細說明了分組校驗糾刪碼的編碼規(guī)則和參數(shù)設(shè)置，并通過具體實驗驗證該編碼規(guī)則的性能，相比傳統(tǒng)糾刪碼技術(shù)，分組校驗?zāi)軌颢@得較好的解碼效率，從而使各項評價指標達到平衡.

[1] 羅 亮，吳文峻，張 飛.面向云計算數(shù)據(jù)中心的能耗建模方法[J].軟件學(xué)報，2014，25(7)：1371-1387.

[2] 張 松，杜慶偉.基于預(yù)測的云計算熱點數(shù)據(jù)副本因子決策算法[J].計算機與現(xiàn)代化,2015(2)：62-67.

[3] 張 樂.云計算環(huán)境下的分布存儲關(guān)鍵技術(shù)研究[J].電子技術(shù)與工程，2015(23)：185-189.

[4] L.Xu.and J.Bruck.X-code.MDS Array Codes with Optimal Encoding[J]. IEEE Trans.on Information Theory. Jan，1999，45(1):272-276.

Redundancy Algorithm of Group Parity Erasure Code Under Cloud Storage Environment

ZENG Sai-feng，QU Xi-long

(School of Computer and Communication, Hunan Institute of Engineering, Xiangtan 411104, China;2. Hunan Provincial Key Laboratory of Wind Generator and Its Control, Hunan Institute of Engineering, Xiangtan 411104, China)

In the massive cloud storage system,the hot research problem is to improve storage utilization and reduce the computation complexity of redundancy scheme. Redundancy algorithm of group parity erasure code can reduce the erasure code fragments required for data reconstruction, thereby decreasing the demand for storage network bandwidth and system I/O, and reducing the load of the storage system. Coding rules and parameter settings of group parity erasure code are described in this paper. Good fault tolerance and space utilization are verified through experimental analysis algorithm, meeting the codec performance required for cloud storage system.

cloud storage; erasure code; redundancy algorithm; group parity

2016-05-06

湖南省自然科學(xué)基金資助項目(2016JJ2040)；湖南工程學(xué)院博士啟動基金項目(15044).

曾賽峰(1983-)，男，博士，講師，研究方向：網(wǎng)絡(luò)存儲、大規(guī)模分布式存儲、云存儲.

U462.3TM615

A

1671-119X(2016)04-0042-04