曾賽峰，屈喜龍，2

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

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

曾賽峰1，屈喜龍1，2

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

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

0 引言

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

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

1 分組校驗(yàn)糾刪碼冗余算法

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

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

圖1 GPEC校驗(yàn)圖

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

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

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

綜上，分組校驗(yàn)糾刪碼的校驗(yàn)塊生成等式，即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，實(shí)驗(yàn)測(cè)試GPEC(6，2，2)中d最大不超過4，表明分組校驗(yàn)糾刪碼不是極大距離可分碼.根據(jù)上述四個(gè)線性方程組構(gòu)成的編碼等式中的系數(shù)矩陣，可以確定分組校驗(yàn)糾刪碼的一致校驗(yàn)矩陣中不滿足任意4列線性無關(guān)，根據(jù)最小距離定理，證明GPEC不滿足MDS[4]性質(zhì).

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

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

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

αiXi+βjYj=R

αi2Xi+βj2Yj=T

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

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

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

Ys+Yt=S

αiXi+βsYs+βtYt=R

αi2Xi+βs2Ys+βt2Yt=T

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

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

第三種，四個(gè)文件塊的丟失，且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位二進(jìn)制表示的無符號(hào)整數(shù).通過計(jì)算α和β分別有7個(gè)數(shù)值可以選取.例如(0x01，0x02，0x03，0x10，0x20，0x30)即是一組“合法”的(α0，α1，α2，β0，β1，β2).

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

2 性能對(duì)比測(cè)試與結(jié)果

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

2.1 編碼效率分析

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

圖2 編碼速度測(cè)試

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

2.2 解碼效率分析

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

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

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

3 結(jié)論

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

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

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

[3] 張 樂.云計(jì)算環(huán)境下的分布存儲(chǔ)關(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é)基金資助項(xiàng)目(2016JJ2040)；湖南工程學(xué)院博士啟動(dòng)基金項(xiàng)目(15044).

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

U462.3TM615

A

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