基于糾刪碼的動(dòng)態(tài)副本冗余存儲(chǔ)研究

鄭志蘊(yùn)，孟慧平，李 鈍，王振飛

（鄭州大學(xué) 信息工程學(xué)院，河南 鄭州450001）

0 引 言

目前，云存儲(chǔ)中數(shù)據(jù)冗余存儲(chǔ)技術(shù)主要包括副本冗余和糾刪碼冗余兩種技術(shù)。副本冗余存儲(chǔ)設(shè)計(jì)簡(jiǎn)單，支持高并發(fā)訪問(wèn)，但消耗空間大；糾刪碼機(jī)制雖然能夠節(jié)省存儲(chǔ)開銷，但造成了讀數(shù)據(jù)性能的下降［1］。本文在分析現(xiàn)有冗余存儲(chǔ)方案的基礎(chǔ)上，從存儲(chǔ)開銷和訪問(wèn)質(zhì)量等方面考慮，提出一種基于糾刪碼的動(dòng)態(tài)副本冗余存儲(chǔ)方案DRBEC（dynamic replication based on erasure codes），將糾刪碼策略和副本策略合理結(jié)合，在盡量減小空間消耗的同時(shí)，提高系統(tǒng)的訪問(wèn)效率。

1 相關(guān)技術(shù)和研究

副本冗余和糾刪碼冗余采用完全不同的方式對(duì)文件數(shù)據(jù)進(jìn)行冗余存儲(chǔ)。副本冗余策略是對(duì)文件進(jìn)行簡(jiǎn)單的復(fù)制后，將各個(gè)副本文件分別存儲(chǔ)在不同的集群節(jié)點(diǎn)服務(wù)器上，進(jìn)行多副本靜態(tài)保存，提高系統(tǒng)的容錯(cuò)能力、提升數(shù)據(jù)資源的使用效率和數(shù)據(jù)的訪問(wèn)性能。糾刪碼冗余策略則是將文件分割后進(jìn)行編碼冗余保存?；诩m刪碼的容錯(cuò)技術(shù)可以簡(jiǎn)單記為 （n，k，t，Q），其編碼使用過(guò)程為：

（1）將待存文件數(shù)據(jù)分為k個(gè)分片；

（2）將k個(gè)分片進(jìn)行冗余編碼，生成n （n＞k）個(gè)冗余分片，并且將它們分別存儲(chǔ)在不同的服務(wù)器節(jié)點(diǎn)上；

（3）當(dāng)用戶訪問(wèn)或者修復(fù)數(shù)據(jù)時(shí)，從n個(gè)分片中選取t（k≤t＜n）個(gè)有效分片，從每個(gè)分片上下載Q 比例的存儲(chǔ)量來(lái)進(jìn)行譯碼，恢復(fù)原文件數(shù)據(jù)。

云存儲(chǔ)中最常用的糾刪碼為 RS （reed－solomon codes）［2］糾刪碼，它是一種線性編碼，可記為 （n，k，k，1），即譯碼時(shí)需要下載k個(gè)完全分片?？紤]到修復(fù)網(wǎng)絡(luò)帶寬問(wèn)題，Dimakis等人在Infocomm 會(huì)議中提出的一種基于網(wǎng)絡(luò)的新型糾刪碼——再生碼 （regenerating codes，RC）［3］。RC碼的參數(shù)表示為 ｛［n，k，d］， （α，β，B）｝，將大小為B的文件編碼存儲(chǔ)在n個(gè)節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)存儲(chǔ)α數(shù)據(jù)量，修復(fù)節(jié)點(diǎn)時(shí)連接任意存活的d （k≤d≤n－1，系統(tǒng)節(jié)點(diǎn)k為修復(fù)節(jié)點(diǎn)的最小連接個(gè)數(shù)）個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的下載量為β（β≤α），節(jié)點(diǎn)的修復(fù)帶寬為γ＝d·β。

相同冗余度情況下，糾刪碼消耗的空間比純副本方案更小，容錯(cuò)能力較強(qiáng)，空間利用率高［4］?？▋?nèi)基梅隆大學(xué)的PDL （parallel data lab）實(shí)驗(yàn)室提出了DiskReduce［5］的系統(tǒng)方案，采用異步編碼方式，先將文件進(jìn)行3倍副本的存儲(chǔ)，之后在后臺(tái)進(jìn)行編碼，利用多副本的高效訪問(wèn)來(lái)提高系統(tǒng)的I／O 吞吐量和計(jì)算并行性。DiskReduce考慮到系統(tǒng)的訪問(wèn)效率和存儲(chǔ)消耗，但僅以時(shí)間關(guān)系來(lái)判斷編碼的時(shí)機(jī)，沒(méi)有提出更好地編碼機(jī)制。文獻(xiàn) ［6］提出了一種改進(jìn)方案Noah，該方案基于編碼策略和動(dòng)態(tài)副本策略的結(jié)合，將編碼后的分片進(jìn)行冗余存儲(chǔ)，實(shí)時(shí)監(jiān)控文件的訪問(wèn)頻度，并根據(jù)需求動(dòng)態(tài)改變分片副本的數(shù)量和位置，有效減少空間的浪費(fèi)、改善了系統(tǒng)的負(fù)載均衡能力，但用戶的訪問(wèn)仍然需要譯碼開銷?，F(xiàn)有研究結(jié)果表明，由于網(wǎng)絡(luò)問(wèn)題而致使用戶無(wú)法接入集中式服務(wù)的時(shí)間達(dá)1.5%～2%［7］，這種實(shí)時(shí)監(jiān)控下進(jìn)行的動(dòng)態(tài)調(diào)整沒(méi)有考慮網(wǎng)絡(luò)延遲給用戶訪問(wèn)性能造成的影響。

文獻(xiàn) ［1］中，作者經(jīng)過(guò)實(shí)驗(yàn)結(jié)果表明副本數(shù)量的增加會(huì)顯著提高讀數(shù)據(jù)的吞吐量。根據(jù)一些行業(yè)報(bào)告，云存儲(chǔ)中有70%以上的數(shù)據(jù)是被靜態(tài)存儲(chǔ)的，很少甚至可能不會(huì)再被訪問(wèn)，對(duì)于靜態(tài)存儲(chǔ)的數(shù)據(jù)若用副本方案存儲(chǔ)會(huì)浪費(fèi)大量的存儲(chǔ)空間。

綜上所述，本文結(jié)合糾刪碼和副本策略的優(yōu)缺點(diǎn)，提出一種基于糾刪碼的動(dòng)態(tài)副本冗余存儲(chǔ)方案DRBEC，在糾刪碼策略的基礎(chǔ)上使用副本策略，并動(dòng)態(tài)調(diào)整副本的數(shù)量。

2 DRBEC方案

本文提出的基于糾刪碼的動(dòng)態(tài)副本冗余存儲(chǔ)方案DRBEC，其基本設(shè)計(jì)思想如下：

（1）首先，在未知文件使用熱度的情況下，通過(guò)對(duì)RS碼和RC碼的比較，創(chuàng)新地使用RC碼對(duì)文件進(jìn)行編碼，實(shí)現(xiàn)文件的編碼冗余存儲(chǔ)；

（2）其次，根據(jù)文件的訪問(wèn)記錄，預(yù)測(cè)其訪問(wèn)熱度，再結(jié)合系統(tǒng)當(dāng)前的狀態(tài)，在糾刪碼的基礎(chǔ)上增加原文件的副本存在形式，并動(dòng)態(tài)調(diào)整原文件的副本數(shù)量。

對(duì)于靜態(tài)文件，系統(tǒng)將它們以糾刪碼的方式冗余存儲(chǔ)，用較小的空間消耗保證了數(shù)據(jù)的可靠性；對(duì)于訪問(wèn)頻繁的熱點(diǎn)文件，系統(tǒng)根據(jù)其訪問(wèn)熱度將文件還原后，適時(shí)調(diào)整原文件副本的數(shù)量，從而提高用戶的訪問(wèn)質(zhì)量。

2.1 基于RC再生碼的編碼冗余存儲(chǔ)

云存儲(chǔ)中，使用糾刪碼冗余策略來(lái)存儲(chǔ)數(shù)據(jù)，可以高效的利用存儲(chǔ)空間保證系統(tǒng)的可靠性，但編碼和譯碼過(guò)程將帶來(lái)不容忽視的帶寬消耗問(wèn)題。云計(jì)算環(huán)境下，帶寬消耗應(yīng)作為糾刪碼設(shè)計(jì)主要關(guān)注的指標(biāo)［8］。

2.1.1 RC碼的帶寬優(yōu)勢(shì)

RC碼是一種基于網(wǎng)絡(luò)的編碼。最小存儲(chǔ)量的RC 編碼稱為MSR （minimum storage regenerating）編碼，對(duì)于大小為B的文件，節(jié)點(diǎn)存儲(chǔ)量αMSR＝B／k，修復(fù)帶寬γMSR＝B＊d／ （k＊d－k2＋k）。相比RS編碼，RC 編碼擁有更小的恢復(fù)帶寬。MSR 編碼與RS編碼的比較結(jié)果見表1。

表1 MSR 編碼與RS編碼的對(duì)比

從表1中可以看出，RS編碼與MSR 編碼的空間消耗和系統(tǒng)可靠性是相同的。當(dāng)d＝k時(shí)，MSR 編碼的修復(fù)帶寬與RC碼的修復(fù)帶寬相同，即γMSR＝γRC＝B；但當(dāng)d＞k時(shí)，修復(fù)帶寬γMSR＜γRC＝B。MSR 編碼的修復(fù)帶寬與連接節(jié)點(diǎn)個(gè)數(shù)d的關(guān)系如圖1所示，當(dāng)d－k＞0時(shí)，MSR 編碼的修復(fù)帶寬遠(yuǎn)遠(yuǎn)小于RS編碼，并且隨著連接節(jié)點(diǎn)d－k值的增大，節(jié)點(diǎn)的修復(fù)帶寬減小。

圖1 MSR 編碼的修復(fù)帶寬消耗與d－k值的關(guān)系

2.1.2 基于RC碼的分組編碼存儲(chǔ)

在使用糾刪碼進(jìn)行文件冗余存儲(chǔ)時(shí)，通常是將整個(gè)文件分片后直接進(jìn)行編碼存儲(chǔ)，導(dǎo)致文件更新時(shí)需要將整個(gè)文件還原更新后重新編碼。為了降低用戶更新數(shù)據(jù)引起的重新編碼開銷，本文中對(duì)文件進(jìn)行RC 碼編碼時(shí)提出先分組后編碼的思想：將文件分片后分為兩組，最后一個(gè)分片作為單獨(dú)一組進(jìn)行多副本保存，其它分片作為另一組進(jìn)行糾刪碼編碼冗余保存。文件更新時(shí)，只需追加到最后一個(gè)分片上，對(duì)最后一個(gè)分片的各個(gè)副本進(jìn)行更新，而無(wú)需對(duì)整個(gè)文件進(jìn)行重新編碼。

Rashmi等人在文獻(xiàn) ［9］中給出RC碼的最小存儲(chǔ)量編碼方案PM＿M(jìn)SR：令β＝t，取d＝2k－2，則B＝k＊ （k－1）＊t，α＝ （k－1）＊t?；赑M＿M(jìn)SR 方案的RC 碼分組編碼算法如下：

（1）將原文件分為k＊ （k－1）＋1 個(gè)分片：b1，b2，…，bk（k－1），bk（k－1）＋1，將前k＊ （k－1）個(gè)分片劃分為組B1，最后一個(gè)分片bk（k－1）＋1劃分為組B2；

（2）將B1組中各個(gè)分片進(jìn)行條帶化，用向量珚B＝ ［b1，b2，…，bk（k－1）］表示。取珚B 的前 （k－1）＊k／2個(gè)分片構(gòu)成的 （α×α）矩陣X 的上三角部分，且XT＝X。B1組剩余的分片構(gòu)成 （α×α）矩陣Y 的上三角，且YT＝Y(jié)。定義 （d×α）的數(shù)據(jù)矩陣為

（3）定義基于有限域Fq上運(yùn)算的范德蒙德修復(fù)矩陣R＝ ［ф Λф］，ф是 （n×α）維矩陣，Λ為 （n×n）的對(duì)角矩陣，其對(duì)角線元素互不相同，且矩陣R 的任意2α行線性無(wú)關(guān)、Λ的任意α行線性無(wú)關(guān)；

（4）RC碼編碼矩陣為C（b），且有

第i行的編碼向量Ci＝Ri·D（b），由節(jié)點(diǎn)i存儲(chǔ)。

如圖2所示，當(dāng)還原文件時(shí)，先還原組B1數(shù)據(jù)。由任意k個(gè)節(jié)點(diǎn)得到C（b）的k行向量，組成 （k×d）矩陣。由式 （1）和式 （2）可知Rk·D（b）＝Wk·X＋Zk·Y。由于矩陣R 的任意2α行線性無(wú)關(guān)，且矩陣X 和Y 為對(duì)稱矩陣，可以解出矩陣X 和Y，從而得到D（b）并還原出珚B＝ ［b1，b2，…，bk（k－1）］。得到B1組數(shù)據(jù)后，將恢復(fù)出的B1數(shù)據(jù)與B2組數(shù)據(jù)的副本結(jié)合，從而還原出整個(gè)原文件。而修復(fù)失效節(jié)點(diǎn)時(shí)，則從剩余有效節(jié)點(diǎn)中任選d個(gè)節(jié)點(diǎn)獲取γ＝d·β的有效數(shù)據(jù)來(lái)精確恢復(fù)失效節(jié)點(diǎn)。

圖2 基于PM＿M(jìn)SR 分組編碼的數(shù)據(jù)重構(gòu)過(guò)程

2.2 動(dòng)態(tài)調(diào)整文件副本

文件上傳后，如果單純以糾刪碼方式存儲(chǔ)文件，其提供訪問(wèn)的能力有限，并且用戶訪問(wèn)延遲過(guò)大。因此當(dāng)文件訪問(wèn)熱度增加到一定程度后，本文通過(guò)調(diào)整原文件的副本數(shù)量來(lái)保證用戶的訪問(wèn)質(zhì)量。對(duì)于云存儲(chǔ)這種特殊服務(wù)，在網(wǎng)絡(luò)傳輸帶寬和磁盤I／O 帶寬有限的情況下，通過(guò)預(yù)測(cè)來(lái)尋找合適的副本創(chuàng)建時(shí)機(jī)，可以提高系統(tǒng)的整體性能。

2.2.1 文件熱度預(yù)測(cè)

將文件的周期訪問(wèn)量按時(shí)間排列后呈現(xiàn)時(shí)間序列，一份文件相近周期的訪問(wèn)量具有相似性，隨著文件創(chuàng)建時(shí)間的推移，文件的訪問(wèn)熱度呈現(xiàn)先上升后下降的趨勢(shì)［10］。因此本文采用基于多項(xiàng)式的非線性曲線擬合預(yù)測(cè)方法來(lái)預(yù)測(cè)文件的訪問(wèn)熱度，根據(jù)歷史記錄對(duì)時(shí)間序列值進(jìn)行多項(xiàng)式擬合，得到被測(cè)對(duì)象的發(fā)展趨勢(shì)，從而預(yù)測(cè)下個(gè)序列值。多項(xiàng)式曲線擬合模型為

將訪問(wèn)量按觀察周期T 的先后列為時(shí)間序列，得到自變量和因變量的n個(gè)觀察值為：x11，x22，x33，…，xTn和y（T1），y（T2），y（T3），…，y（Tn），則輸入矩陣X 和Y如下

系數(shù)矩陣β＝ ［β0β1… βn］，由式 （3）知Y＝X·βT，從而求出β，得到時(shí)間序列的擬合曲線。

不同時(shí)間段，用戶對(duì)于數(shù)據(jù)的訪問(wèn)熱度呈現(xiàn)波動(dòng)現(xiàn)象。對(duì)文件周期訪問(wèn)量的時(shí)間序列，將Tn＋1前的n個(gè)周期T1，T2，T3，T4，T5，…，Tn的周期訪問(wèn)量進(jìn)行t次曲線擬合，次數(shù)為t（t＝2，3，4）的擬合曲線的擬合誤差為

式中：yTi——周期Ti的實(shí)際訪問(wèn)量，yt（Ti）為Ti的擬合訪問(wèn)值。通過(guò)比較t，得到擬合誤差最小的ts，其對(duì)應(yīng)的擬合曲線為yts。則預(yù)測(cè)得到周期Tn＋1的訪問(wèn)量為

鑒于用戶對(duì)文件訪問(wèn)的隨機(jī)性，訪問(wèn)量在短期內(nèi)隨著時(shí)間呈現(xiàn)波動(dòng)，如果僅僅通過(guò)n個(gè)觀察周期擬合得到的整體趨勢(shì)來(lái)進(jìn)行預(yù)測(cè)，預(yù)測(cè)結(jié)果誤差較大。本文對(duì)基于n個(gè)周期進(jìn)行的簡(jiǎn)單曲線擬合預(yù)測(cè)方法進(jìn)行改進(jìn)，將預(yù)測(cè)周期Tn＋1前的3個(gè)周期作為短周期進(jìn)行小趨勢(shì)預(yù)測(cè)，而后把該結(jié)果與基于n個(gè)周期的整體趨勢(shì)得到的預(yù)測(cè)值進(jìn)行加權(quán)平均，用近期小趨勢(shì)預(yù)測(cè)值調(diào)整n個(gè)周期的大趨勢(shì)預(yù)測(cè)結(jié)果，從而減小預(yù)測(cè)誤差。

近期小趨勢(shì)預(yù)測(cè)采用二次曲線的預(yù)測(cè)，其模型為

2.2.2 副本的動(dòng)態(tài)生成和刪除

對(duì)于云中的文件資源R，當(dāng)實(shí)際訪問(wèn)量超過(guò)了云系統(tǒng)中R 所能提供的訪問(wèn)上限時(shí)，增加資源R 的副本數(shù)量，則可以增加R 提供訪問(wèn)的能力；若文件訪問(wèn)量減少，減少副本以減少存儲(chǔ)開銷。為此，本文結(jié)合2.2.1 小節(jié)給出的文件訪問(wèn)熱度預(yù)測(cè)結(jié)果，動(dòng)態(tài)管理副本的生成和刪除。

用戶在周期Tz中對(duì)資源R 訪問(wèn)總數(shù)WR（Tz）和文件當(dāng)前的副本數(shù)量r（Tz）由主節(jié)點(diǎn)nameNode記錄保存。R在服務(wù)器i上的副本或編碼分片Ri的訪問(wèn)隊(duì)列被記錄在一張表中，由數(shù)據(jù)節(jié)點(diǎn)dataNode服務(wù)器i動(dòng)態(tài)維護(hù)。將服務(wù)器i上Ri的周期訪問(wèn)量，即隊(duì)列個(gè)數(shù)記為Ri（Tz）。在本文中，為了更加清晰的說(shuō)明副本生成和刪除時(shí)機(jī)的計(jì)算模型，特給出以下幾個(gè)定義：

定義1 令η為存儲(chǔ)資源R 編碼分片的服務(wù)器節(jié)點(diǎn)集合，ε為擁有資源R 副本的服務(wù)器節(jié)點(diǎn)集合，δk（Tz）為服務(wù)器k在周期Tz內(nèi)可響應(yīng)的訪問(wèn)次數(shù)。資源R 以糾刪碼形式提供訪問(wèn)的上限為ζ（Tz），并且對(duì)任意i都有ζ（Tz）≤ζi∈η（Tz）。則資源R 的總訪問(wèn)上限為

定義2 當(dāng)文件基于 ［n，k，d］MSR 編碼時(shí)，周期Tz中文件冗余度MR定義為：MR（Tz）＝n／k＋r（Tz），其中r（Tz）為當(dāng)前周期中文件R 的副本數(shù)量。則定義資源R 的副本價(jià)值系數(shù)為

定義3 周期Tz中資源R 的訪問(wèn)權(quán)重函數(shù)定義為

式中：n——最近n個(gè)周期。則服務(wù)器i上資源R 的副本Ri的訪問(wèn)權(quán)重為

在判斷副本的生成時(shí)機(jī)時(shí)，在周期Tz中根據(jù)式 （8）預(yù)測(cè)得到資源R 在周期Tz＋1的訪問(wèn)總量WR（Tz＋1），再由定義1中式 （9）計(jì)算出資源R 當(dāng)前的訪問(wèn)上限ΨR（Tz），如果有WR（Tz＋1）≥ΨR（Tz）時(shí)，表示在Tz的下個(gè)周期Tz＋1中，對(duì)資源R 的訪問(wèn)量將大于系統(tǒng)當(dāng)前所能提供的訪問(wèn)上限，則應(yīng)該為資源R 創(chuàng)建副本。用戶可以選擇訪問(wèn)新增副本服務(wù)器上的資源R。

在定義刪除副本的時(shí)機(jī)時(shí)，在周期Tz中，當(dāng)由定義2中式 （10）計(jì)算出副本價(jià)值系數(shù)SR（Tz）≤1，即文件的訪問(wèn)量小于文件的冗余度，或者當(dāng)系統(tǒng)檢測(cè)到?jīng)]有足夠的存儲(chǔ)空間時(shí)，需要選取適當(dāng)?shù)母北具M(jìn)行刪除操作。由定義3中式 （11）和式 （12）計(jì)算各個(gè)副本資源的訪問(wèn)權(quán)重，按照最近最久不用 （least recently used，LRU）置換算法進(jìn)行資源選取，選擇權(quán)重θRi（Tz）最小的服務(wù)器上的副本資源對(duì)其進(jìn)行懶惰刪除，即僅將空間狀態(tài)為標(biāo)為可用，但仍保留其數(shù)據(jù)信息。當(dāng)系統(tǒng)需要該空間時(shí)，才將磁盤信息進(jìn)行徹底刪除并用新數(shù)據(jù)覆蓋。

3 仿真實(shí)驗(yàn)

為了驗(yàn)證本文提出的基于糾刪碼的動(dòng)態(tài)副本冗余方案（DRBEC）的有效性，實(shí)驗(yàn)分為兩部分，首先從網(wǎng)絡(luò)上捕獲數(shù)據(jù)，對(duì)改進(jìn)的曲線擬合預(yù)測(cè)效果進(jìn)行驗(yàn)證。其次，搭建集群實(shí)驗(yàn)環(huán)境，驗(yàn)證該方案在數(shù)據(jù)存儲(chǔ)空間消耗和用戶訪問(wèn)質(zhì)量方面的效果。

3.1 改進(jìn)后曲線擬合的預(yù)測(cè)準(zhǔn)確度

實(shí)驗(yàn)數(shù)據(jù)基于對(duì)100個(gè)網(wǎng)絡(luò)熱點(diǎn)視頻和熱點(diǎn)文獻(xiàn) （每天訪問(wèn)量大于1000）的跟蹤記錄，設(shè)定周期為10min，記錄這些文件的各個(gè)周期訪問(wèn)量。依據(jù)2.2.1 小節(jié)改進(jìn)前和改進(jìn)后的曲線擬合方法，對(duì)這些文件的周期訪問(wèn)量進(jìn)行預(yù)測(cè)。圖3展示了預(yù)測(cè)準(zhǔn)確度大于80%的概率。

圖3 2種曲線擬合預(yù)測(cè)準(zhǔn)確度大于80%的概率

由圖3可以看出改進(jìn)前簡(jiǎn)單的曲線擬合預(yù)測(cè)的準(zhǔn)確度達(dá)到80%以上的概率只有60%左右，而改進(jìn)后利用大趨勢(shì)和小趨勢(shì)的結(jié)合來(lái)減小波動(dòng)給預(yù)測(cè)結(jié)果造成的誤差，使改進(jìn)后的曲線擬合的預(yù)測(cè)準(zhǔn)確度在80%以上的概率達(dá)到90%左右，遠(yuǎn)遠(yuǎn)大于改進(jìn)前的簡(jiǎn)單曲線擬合。

3.2 集群環(huán)境下DRBEC方案的驗(yàn)證實(shí)驗(yàn)

基于Xen虛擬機(jī)搭建hadoop集群存儲(chǔ)平臺(tái)，1個(gè)name－Node和6個(gè)dataNode節(jié)點(diǎn)服務(wù)器使用內(nèi)存為2G，硬盤為50G，系統(tǒng)為Red hat Enterprise Linux 5。使用Hadoop集群的基準(zhǔn)測(cè)試系統(tǒng)SWIM （statistical workload injector for mapreduce）［11］，根據(jù)Yahoo的2000個(gè)Hadoop集群節(jié)點(diǎn)1個(gè)月的歷史信息，產(chǎn)生新的模擬數(shù)據(jù)訪問(wèn)程序，來(lái)訪問(wèn)系統(tǒng)中50GB的存儲(chǔ)文件。在不考慮刪除文件的情況下，圖4展示了SWIM 進(jìn)行基準(zhǔn)測(cè)試時(shí)系統(tǒng)的空間消耗情況。

圖4 系統(tǒng)存儲(chǔ)空間消耗

對(duì)于冗余度r＝3的純副本方案，消耗的存儲(chǔ)空間始終是原文件的3倍，大于150GB。而DRBEC 方案中，采用［n＝5，k＝3，d＝4］的RC 碼進(jìn)行編碼，由于采用分組編碼，文件上傳后最初消耗的存儲(chǔ)空間100G。隨后系統(tǒng)中一些文件的訪問(wèn)熱度增加，文件的副本數(shù)量也隨之改變，空間消耗呈現(xiàn)波動(dòng)。當(dāng)文件訪問(wèn)熱度下降并趨于平穩(wěn)時(shí)，空間消耗也下降趨于平穩(wěn)，并且DRBEC方案整體空間消耗量遠(yuǎn)遠(yuǎn)小于純副本方案。

在使用Apache組織開發(fā)的壓力測(cè)試工具jmeter模擬用戶對(duì)于熱點(diǎn)文件的訪問(wèn)時(shí)，用戶對(duì)不同大小的文件訪問(wèn)的平均延遲時(shí)間如圖5所示。

圖5 對(duì)不同大小文件訪問(wèn)的平均延遲

當(dāng)熱點(diǎn)文件的并發(fā)訪問(wèn)量很高時(shí)，Noah方案中動(dòng)態(tài)副本策略采用實(shí)時(shí)監(jiān)控方式，副本生成時(shí)的網(wǎng)絡(luò)延遲影響用戶的訪問(wèn)質(zhì)量，而DRBEC方案預(yù)測(cè)文件的訪問(wèn)熱度，針對(duì)預(yù)測(cè)結(jié)果提前更改文件的副本數(shù)量，有效減少了實(shí)時(shí)檢測(cè)方式下網(wǎng)絡(luò)和磁盤I／O 帶來(lái)的延遲，提高了用戶的訪問(wèn)成功率。

圖6展示2種方式下對(duì)不同大小的文件訪問(wèn)成功率對(duì)比。隨著文件的增大，訪問(wèn)延遲時(shí)間就越長(zhǎng)，文件請(qǐng)求超過(guò)一定時(shí)間時(shí)，訪問(wèn)就失敗，因此實(shí)時(shí)監(jiān)控下文件創(chuàng)建的延遲造成不能及時(shí)響應(yīng)用戶的訪問(wèn)，降低了文件的訪問(wèn)成功率。而DRBEC方案下，由于預(yù)測(cè)而提前增加的副本服務(wù)器減小了文件創(chuàng)建延遲的影響，使用戶的訪問(wèn)能夠得到及時(shí)地響應(yīng)，提高了用戶訪問(wèn)的成功率。

圖6 對(duì)不同大小文件的訪問(wèn)成功率

4 結(jié)束語(yǔ)

本文針對(duì)單一冗余策略的不足，提出DRBEC方案，基于恢復(fù)帶寬更小的RC 碼冗余存儲(chǔ)的基礎(chǔ)上使用動(dòng)態(tài)副本策略，采用預(yù)測(cè)得到文件的訪問(wèn)熱度實(shí)時(shí)改變文件的副本數(shù)量。通過(guò)搭建原型系統(tǒng)的實(shí)驗(yàn)和分析結(jié)果表明，DRBEC方案能有效降低網(wǎng)絡(luò)延遲和磁盤I／O 性能給用戶帶來(lái)的訪問(wèn)延遲，提高用戶的訪問(wèn)質(zhì)量，解決了冗余存儲(chǔ)帶來(lái)的空間消耗和用戶數(shù)據(jù)的高可靠性、高效訪問(wèn)之間的矛盾。

在未來(lái)的工作中，將對(duì)DRBEC方案中數(shù)據(jù)存放的安全性做進(jìn)一步研究，并且考慮系統(tǒng)的負(fù)載均衡問(wèn)題，使存儲(chǔ)系統(tǒng)更加可靠，為用戶提供更加高效的訪問(wèn)，并在實(shí)際場(chǎng)景下對(duì)其效果進(jìn)行測(cè)試。

［1］CHENG Zhendong，LUAN Zhongzhi，MENG You，et al.Research and practice on erasure codes in cloud ［J］.Computer Science and Exploration，2013，7 （4）：315－325 （in Chinese）.［程振東，欒鐘治，孟由，等.云文件系統(tǒng)中糾刪碼技術(shù)的研究與實(shí)現(xiàn) ［J］.計(jì)算機(jī)科學(xué)與探索，2013，7 （4）：315－325.］

［2］DU Junchao，LIU Hui，LI Xiaojun，et al.The performance evaluation of the wireless sensor network information distribution protocol based on RS code［J］.Computer Science，2011，38 （B10）：315－318 （in Chinese）. ［杜軍朝，劉惠，李曉軍，等.基于RS糾刪碼的無(wú)線傳感器網(wǎng)絡(luò)信息分發(fā)協(xié)議性能評(píng)價(jià)［J］.計(jì)算機(jī)科學(xué)，2011，38 （B10）：315－318.］

［3］Dimakis A G，Godfrey P B，Wu Y，et al.Network coding for distributed storage systems ［J］.IEEE Transactions on Information Theory，2010，56 （9）：4539－4551.

［4］Dimakis A G，Ramchandran K，Wu Y，et al.A survey on network codes for distributed storage ［J］.Proceedings of the IEEE，2011，99 （3）：476－489.

［5］Fan B，Tantisiriroj W，Xiao L，et al.DiskReduce：RAID for data－intensive scalable computing ［C］／／Proceedings of the 4th Annual Workshop on Petascale Data Storage.ACM，2009：6－10.

［6］LI Xiaokai，DAI Xiang，LI Wenjie，et al.HDFS improvement system based on dynamic replication redundancy and erasure code strategy ［J］.Computer Application，2012，32 （8）：2150－2153 （in Chinese）.［李曉愷，代翔，李文杰，等.基于糾刪碼和動(dòng)態(tài)副本策略的HDFS 改進(jìn)系統(tǒng) ［J］.計(jì)算機(jī)應(yīng)用，2012，32 （8）：2150－2153.］

［7］Bonvin N，Papaioannou T G，Aberer K.The costs and limits of availability for replicated services［C］∥ACDC，2009.

［8］Khan O，Burns R，Plank J，et al.Rethinking erasure codes for cloud file systems：Minimizing I／O for recovery and degraded reads［C］／／Proc of USENIX FAST，2012.

［9］Rashmi K V，Shah N B，Kumar P V.Optimal exact－regenerating codes for distributed storage at the MSR and MBR points via a product－matrix construction ［J］.IEEE Transactions on Information Theory，2011，57 （8）：5227－5239.

［10］DONG Jiguang，CHEN Weiwei，WU Haijia，et al.The research on load balance based on dynamic copy in cloud storage［J］.Computer Application and Rearch，2012，29 （9）：3422－3424 （in Chinese）.［董繼光，陳衛(wèi)衛(wèi)，吳海佳，等.基于動(dòng)態(tài)副本技術(shù)的云存儲(chǔ)負(fù)載均衡研究 ［J］.計(jì)算機(jī)應(yīng)用研究，2012，29 （9）：3422－3424.］

［11］Chen Y，Ganapathi A，Griffith R，et al.The case for evaluating MapReduce performance using workload suites［C］／／IEEE 19th International Symposium on Modeling，Analysis ＆ Simulation of Computer and Telecommunication Systems，2011：390－399.