張 鴻，林 兵，劉漳輝，2

(1．福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，福建福州 350116;

2．福建省網(wǎng)絡(luò)計算與智能信息處理重點實驗室，福建福州 350116)

0 引言

云計算具有超大規(guī)模、高可擴展性、高可靠性、虛擬化、按需服務(wù)和價格低廉等特點，能夠很好地滿足海量數(shù)據(jù)存儲的要求．云計算使得用戶不必構(gòu)建自己的數(shù)據(jù)中心，他們只需要根據(jù)自身需求支付一定的費用，就能夠把數(shù)據(jù)存儲到云服務(wù)商的數(shù)據(jù)中心上．在未來4年內(nèi)，云服務(wù)的市場規(guī)模將從現(xiàn)在的174億美元增長到442億美元，其中，云存儲的市場比例將從目前的9%增長到14%［1］．然而，在當(dāng)前的云存儲數(shù)據(jù)中心中，任何類型的故障都是很常見的，如電源故障，機架故障，網(wǎng)絡(luò)攻擊，硬件驅(qū)動掛機等［2］，從而使網(wǎng)絡(luò)中單個節(jié)點失效成為一種常態(tài)．GFS和HDFS文件系統(tǒng)用生成多個數(shù)據(jù)副本的方法來提高數(shù)據(jù)可用性［3］．但副本也會帶來幾個問題:副本集的統(tǒng)一性問題，副本均衡負(fù)載問題以及合適的副本數(shù)量及放置問題．副本數(shù)量的增多可以有效提高數(shù)據(jù)的可靠性，但副本的過度增加會導(dǎo)致數(shù)據(jù)中心運營商的成本過高，導(dǎo)致經(jīng)濟效益下降．云計算服務(wù)的基礎(chǔ)設(shè)施和數(shù)據(jù)中心一般分布在世界范圍內(nèi)的適宜地點，因為用戶的訪問請求來自全球范圍內(nèi)的不同的地方，為了兼顧用戶的訪問需求和數(shù)據(jù)中心的負(fù)載均衡，要求副本的放置策略要有效合理．如果副本放置不當(dāng)，如集中于某個地區(qū)，則會導(dǎo)致遠(yuǎn)處的用戶數(shù)據(jù)訪問帶寬下降，網(wǎng)絡(luò)延遲;如果副本的放置過于分散，則會導(dǎo)致副本的管理和維護成本代價過高．應(yīng)該如何放置和管理這些副本，以有效地分配工作負(fù)載，保證負(fù)載均衡，提高系統(tǒng)性能?

通過副本提高數(shù)據(jù)的訪問率已經(jīng)在許多存儲系統(tǒng)中應(yīng)用，如P2P系統(tǒng)［4］、分布式數(shù)據(jù)庫［5－6］和分布式文件系統(tǒng)［7－8］．然而，在這些系統(tǒng)中，都是采用靜態(tài)副本機制，副本的數(shù)量和位置都是事先決定的，這樣會消耗不必要的成本代價．在動態(tài)副本機制中，也有很多文獻對此做了研究．Agnesswaran等［9］提出了一種副本管理策略，通過建立一個模型，來維持?jǐn)?shù)據(jù)可用性水平．該方法首先根據(jù)用戶要求的可用率計算每個文件塊需要被復(fù)制的數(shù)量，然后根據(jù)網(wǎng)絡(luò)帶寬和存儲成本選擇副本放置的最佳節(jié)點．Ranganathan等［10］提出了動態(tài)模型驅(qū)動的副本策略，在這個機制中，在P2P存儲系統(tǒng)的對等兩端都運行這個模型區(qū)計算文件所需要的最低副本數(shù)量．IFoster等［11］在數(shù)據(jù)網(wǎng)格中提出了動態(tài)副本策略，根據(jù)用戶的不同訪問模式來應(yīng)用不同的副本策略．Mistarihi等［12］提出應(yīng)該根據(jù)數(shù)據(jù)塊的請求次數(shù)和生命周期來選擇最好的數(shù)據(jù)塊進行復(fù)制．以上這些文獻都是在分布式存儲系統(tǒng)的背景下展開的．Wei等［13］提出了一種有效節(jié)約成本的動態(tài)副本管理模型CDRM，這種模型兼顧了可用性和副本數(shù)量．在保證所需可用性的基礎(chǔ)上，CDRM維持了所需的最小副本數(shù)量．副本的放置位置是由數(shù)據(jù)節(jié)點的容量和阻塞概率決定的．根據(jù)負(fù)載變化和節(jié)點容量來調(diào)整副本數(shù)量和位置．Jeon等［14］提出檢測用戶的數(shù)據(jù)訪問模式的變化來動態(tài)改變副本的最優(yōu)復(fù)制策略，因為副本策略大多與用戶的訪問模式有密切的關(guān)系．但是，以上文獻沒有考慮到云存儲系統(tǒng)中網(wǎng)絡(luò)的廣域性和動態(tài)性等特點，未對副本在云環(huán)境系統(tǒng)中的成本和效率做充分考慮．

本文提出一個云存儲系統(tǒng)下基于競標(biāo)模式的云存儲副本管理策略來解決上述問題．將競標(biāo)模式和云存儲中的副本結(jié)合起來，在文件的可用性達(dá)不到用戶的要求時，舉行競標(biāo)，將新的副本放置在最適合的節(jié)點上面．同時，在副本放置完之后，優(yōu)化和管理副本的分布情況．這個方案能夠找出適合副本放置的節(jié)點且動態(tài)適應(yīng)環(huán)境的變化，在滿足用戶需求的基礎(chǔ)上，縮短用戶的響應(yīng)時間，保持整個存儲系統(tǒng)的穩(wěn)定．仿真實驗表明，該方案能夠顯著提高系統(tǒng)性能．

在文中，首先提出文件系統(tǒng)的存儲結(jié)構(gòu);然后，提出基于競標(biāo)的副本管理策略和實驗環(huán)境，并給出算法的實驗結(jié)果以及比較分析，以證明該分配策略的有效性;最后，指出副本策略在未來將面臨的挑戰(zhàn)以及需要開展的研究工作．

1 云存儲模型

云存儲模型采用谷歌文件系統(tǒng)(Google file system，GFS)的星形拓?fù)浣Y(jié)構(gòu)．GFS中包含主節(jié)點(master)和多個子節(jié)點(chunk nodes)，主結(jié)點保存了整個文件系統(tǒng)的名字空間、客戶端對文件的訪問及數(shù)據(jù)塊到子節(jié)點的映射等，具體的數(shù)據(jù)存儲工作由子結(jié)點負(fù)責(zé)［15］．主節(jié)點和子節(jié)點之間通過心跳包來通信，同時，還把客戶端的操作指令發(fā)送給子結(jié)點，如圖1所示．當(dāng)客戶端向文件系統(tǒng)讀取數(shù)據(jù)時，首先，跟主節(jié)點通信，獲得具體保存數(shù)據(jù)塊的子節(jié)點信息，然后，客戶端再和子節(jié)點建立數(shù)據(jù)傳輸連接，直接從子節(jié)點下載數(shù)據(jù)．將數(shù)據(jù)分割成大小為64 MB的數(shù)據(jù)塊存儲在子節(jié)點上，每個數(shù)據(jù)塊初始化3個副本存放在子結(jié)點上．主節(jié)點先隨機挑選某個副本為主副本．在系統(tǒng)運行的時候，主結(jié)點開始收集每個子節(jié)點和數(shù)據(jù)塊的信息，包括數(shù)據(jù)的分布信息、子節(jié)點的當(dāng)前負(fù)載量信息和客戶端訪問數(shù)據(jù)的信息等等．最后，主節(jié)點就可根據(jù)本文的策略動態(tài)調(diào)整副本的分布情況．

圖1 云存儲系統(tǒng)拓?fù)浣Y(jié)構(gòu)Fig．1 Cloud storage system topology structure

2 基于競標(biāo)模式的副本管理方法

在有底價競標(biāo)過程中，存在賣家、買家、競標(biāo)時間、競標(biāo)底價和競標(biāo)價格等幾個重要的組合部分．賣家會根據(jù)買家出的競標(biāo)價格和自己的底價來決定競標(biāo)物品的最終歸屬權(quán)．在云存儲環(huán)境中，副本的放置是一個棘手的問題，如果副本的位置與用戶相距太遠(yuǎn)，則失去了數(shù)據(jù)副本的優(yōu)勢，如果把所有數(shù)據(jù)副本放置在數(shù)據(jù)請求者周圍，則會提高查詢請求的響應(yīng)時間和負(fù)載均衡．將副本放置過程和競標(biāo)模式結(jié)合起來，通過賣家和買家的互動，使副本放置在最合適的地方．在副本放置完畢之后，主節(jié)點實時監(jiān)測各數(shù)據(jù)的可訪問率情況，動態(tài)管理副本的分布情況．

在競標(biāo)模式中，有賣方和買方兩種角色，將云存儲系統(tǒng)中的主節(jié)點定義為賣方，將參與競標(biāo)的子節(jié)點定義為買方．在副本放置的競標(biāo)過程中，賣家即主節(jié)點發(fā)起競標(biāo)活動，出售副本的放置權(quán)，符合競標(biāo)底價的買家即子節(jié)點參與競標(biāo)，取得副本的放置權(quán)．在節(jié)點獲得副本的放置權(quán)之后，開始副本的管理過程．

2．1 競標(biāo)開始時間

在云計算中，用戶都會與提供商簽訂一份服務(wù)等級協(xié)議(service layer agreement，SLA)，里面規(guī)定了用戶對云提供商的一些基本要求，其中就有云服務(wù)商保證給用戶的最低數(shù)據(jù)訪問可用率aval．假設(shè)數(shù)據(jù)對象i有n個數(shù)據(jù)副本，即S=(R1，R2，R3，…，Rn)，每個副本存放在不同的服務(wù)器上，每個副本的失效率為Fj，這些事件彼此可能是相互獨立或相關(guān)的，不失一般性，假設(shè)事件F1，…，F(xiàn)k是獨立的，而事件Fk+1，…，是具有相關(guān)性的．?dāng)?shù)據(jù)對象i不能被訪問的概率為:

為了簡化問題，假設(shè)每個副本的可訪問率都為RAi，j(j∈n)，每個副本失效事件的概率是獨立的，則數(shù)據(jù)對象i的n個副本提供的綜合可訪問率RAi可以由下式得到:

所以，當(dāng)n個副本提供的綜合訪問率不能滿足提供商保證給用戶的可用率時，即RAi＜aval，master節(jié)點就開始準(zhǔn)備生成數(shù)據(jù)i的新的副本，以提高數(shù)據(jù)i的訪問率．這就是副本放置的競標(biāo)活動的開始．

2．2 競標(biāo)底價

在有底價的競標(biāo)活動中，底價是賣家對物品所愿意接受的最低價格．這個價格表示著賣家對買家的要求．在副本放置的競標(biāo)過程中，也有相類似的定義．

副本的分布情況與用戶訪問數(shù)據(jù)的響應(yīng)時間、維護副本一致性操作的代價有著密切的關(guān)系，如果某個數(shù)據(jù)的副本集存放得過于集中，那么遠(yuǎn)程用戶的數(shù)據(jù)訪問響應(yīng)時間勢必會增加;相反，如果副本集的分布過于分散，在維護副本數(shù)據(jù)一致性時代價會非常昂貴．所以，為了給用戶一個良好的用戶體驗，系統(tǒng)要嚴(yán)格控制副本集的分布情況．副本集的分布情況主要由副本的實際地理分布和副本之間的網(wǎng)絡(luò)帶寬決定．用副本分布程度RD(replication distribution)來描述副本的放置情況是分散還是集中．

副本之間的地理距離可以用distance來表示，distancej，k表示數(shù)據(jù)對象i的第j個副本和第k個副本之間的距離．副本之間的距離可以用副本所在的子結(jié)點之間的地理距離表示，子節(jié)點的地理位置按照文獻［16］中副本位置的表示方法，定義為:

NLOC=(國家編號，地區(qū)編號，數(shù)據(jù)中心編號，機架編號，物理機編號)

式中:國家和地區(qū)編號采用電話區(qū)號表示;數(shù)據(jù)中心編號采用數(shù)據(jù)中心名稱縮寫進行區(qū)分;機架編號與物理機編號均為數(shù)據(jù)中心內(nèi)部統(tǒng)一編號．用15位二進制表示兩個節(jié)點之間的距離，如果兩個節(jié)點之間的國家編號不同，則節(jié)點距離的第1到第5位(從左到右)置為1，后面都為0，否則就把1到5位置為0;如果兩個節(jié)點之間的地區(qū)編號不同，則節(jié)點距離的第6到第9位置為1，后面都為0，否則就把6到9位都置為0;其余以此類推．

表1為節(jié)點i與節(jié)點j的距離．在表1中，節(jié)點i為中國福建省福州市超級計算機數(shù)據(jù)中心的第01號機架上的03號物理機，節(jié)點j為中國福建省廈門市廈門大學(xué)數(shù)據(jù)中心的第02號機架上的02號物理機，兩點間的物理距離定義為distancei，j=00000111100000(二進制)=960(十進制)．

表示M×N的數(shù)據(jù)和服務(wù)器關(guān)系的放置矩陣，如果一個數(shù)據(jù)對象i的副本存放在服務(wù)器j上，則Lij=1;若沒有，則Lij=0．因此副本集S=(R1，R2，…，Rn)的副本之間所有帶寬的總和可以由下式得到:其中:是一個N×N的上三角矩陣，矩陣中的元素代表任意兩個服務(wù)器之間的網(wǎng)絡(luò)帶寬;sum函數(shù)為矩陣所有元素的求和．

表1 節(jié)點i與節(jié)點j的距離Tab．1 Distance of node i and node j

所以，數(shù)據(jù)對象i的副本集合S=(R1，R2，…，Rn)的副本分布程度可由下式得到:

圖2 副本分布與可用性和成本的關(guān)系Fig．2 Availability and cost varies with replica distance

式中:RDi是原先副本集的分布程度;RD'i是假設(shè)某個節(jié)點放置副本Rn+1后，副本集更新之后的副本分布程度．要讓副本集的副本分布程度接近標(biāo)準(zhǔn)副本分布程度RDstandard的節(jié)點才有資格參與競標(biāo)．

2．3 競標(biāo)價格

在有資格參與競標(biāo)的節(jié)點中，要提供競標(biāo)價格BP(bidding price)給賣家，對于參與競標(biāo)的子結(jié)點來說，其影響副本性能的主要屬性包括:節(jié)點的請求率，節(jié)點的平均服務(wù)時間，可靠性，網(wǎng)絡(luò)帶寬和磁盤空間負(fù)載，用五元組N=(λ，τ，f，bw，load)表示．將競標(biāo)價格和這五個屬性結(jié)合起來，則有公式:其中:?1、?2、?3、?4和?5分別為節(jié)點的請求率、節(jié)點的平均服務(wù)時間、失效率、網(wǎng)絡(luò)帶寬和磁盤空間負(fù)載在競標(biāo)價格中所占的權(quán)值．在本研究中，利用層次分析法(AHP)的核心思想［17］對這些指標(biāo)進行量化處理，以確定這些權(quán)重的值．根據(jù)副本節(jié)點的性能屬性偏好，結(jié)合1～9比率標(biāo)度法(具體含義見表2)，對這五個屬性先構(gòu)造判斷矩陣．構(gòu)造完的判斷矩陣如下所示:

表2 1～9比率標(biāo)度法含義Tab．2 1 ～9 ratio scale method

2．4 競標(biāo)管理過程

在競標(biāo)的結(jié)束階段，主節(jié)點需要查看系統(tǒng)中每個數(shù)據(jù)的可訪問率，如果某個數(shù)據(jù)i的可訪問率沒達(dá)到用戶的要求，則開始新一輪的競標(biāo)活動．若數(shù)據(jù)i的可用性得到用戶的滿足，則主節(jié)點就要開始管理和優(yōu)化本系統(tǒng)的副本分布情況，以降低副本集的成本．

在數(shù)據(jù)對象i的副本集提供的訪問率高于用戶期望的數(shù)據(jù)可用率時，主節(jié)點找出訪問率最低的副本，如果刪除這個副本后，數(shù)據(jù)對象i的可用性依舊得到滿足，則刪除該副本．如果刪除該副本后，數(shù)據(jù)對象i的訪問率不能達(dá)到用戶的要求，則不能刪除該對象的某個副本，此時要考慮降低訪問率的副本j，在選取準(zhǔn)備遷移的副本j之后，尋找新的節(jié)點存放副本，此時又回到了副本放置的競標(biāo)過程．整個流程如圖3所示．

圖3 副本管理流程圖Fig．3 Replica management flowchart

3 實驗與性能分析

3．1 實驗環(huán)境

用CloudSim［18］作為實驗平臺，進行仿真實驗．模擬出10個數(shù)據(jù)中心，每個數(shù)據(jù)中心隨機分布著10到100個物理機，每個物理機為2．8 GHz的Intel Pentium4核CPU，1 GB或2 GB的內(nèi)存，80 GB或160 GB的硬盤．虛擬機部署在物理機上，虛擬機的操作系統(tǒng)是Ubuntu 12．04以及java版本是1．6．0．每個數(shù)據(jù)被分割為64 MB的數(shù)據(jù)對象，初始情況為每個對象沒有副本隨機分布在子節(jié)點上．各對象訪問概率服從參數(shù)為λ的Poisson分布，訪問量和訪問類型服從Pareto(1，50)．由于仿真實驗中網(wǎng)絡(luò)的通信情況良好，所以將副本可用性aval設(shè)置為0．8．同時，在CloudSim平臺上運行副本的傳統(tǒng)靜態(tài)策略和文獻［13］的CDRM策略，以用作對比．

3．2 實驗結(jié)果與分析

1)負(fù)載均衡．通過計算每個節(jié)點的負(fù)載方差來衡量系統(tǒng)的負(fù)載均衡．圖4描述了本文策略在用戶訪問過程中的負(fù)載方差．可以看到，負(fù)載方差的變化相對平穩(wěn)且基本保持在12%以下．圖5展示了本文副本策略與傳統(tǒng)靜態(tài)副本策略和CDRM副本策略的比較結(jié)果．可以看到，在副本數(shù)量不是很多的時候，三者并沒有很大的差距，有一點的隨機性;在副本數(shù)量為60時，其他的兩個副本策略的負(fù)載方差低于本文的策略，因為本文副本策略在競標(biāo)過程中需要耗費網(wǎng)絡(luò)帶寬;隨著副本數(shù)量的急劇上升，本文策略在負(fù)載方面低于其他兩種副本策略的負(fù)載方差．

圖4 負(fù)載方差隨時間間隔的變化Fig．4 Load variance varies with time interval

圖5 負(fù)載方差隨副本數(shù)量的變化Fig．5 Load variance varies with replica number

2)響應(yīng)時間．為研究本文的副本策略的性能，在仿真云數(shù)據(jù)環(huán)境中安排了數(shù)量變化的負(fù)載來查看三種策略的不同響應(yīng)時間．圖6顯示了三種不同策略的響應(yīng)時間，可以看到，隨著工作負(fù)載的數(shù)量增加，與其他兩種策略相比，本文策略的響應(yīng)時間明顯減少，這說明了本文策略在負(fù)載數(shù)量多時的有效性．因為本文策略可以控制副本的分布范圍，能有效地減少用戶的遠(yuǎn)程文件訪問數(shù)．

圖6 負(fù)載數(shù)量變化的響應(yīng)時間Fig．6 Response time varies with load

圖7 時間間隔下的網(wǎng)絡(luò)帶寬負(fù)載Fig．7 Network bandwidth load varies with time interval

3)網(wǎng)絡(luò)帶寬．在本文副本策略與傳統(tǒng)靜態(tài)策略運行過程中的某一段時間，在Δt時間間隔下監(jiān)測系統(tǒng)中的網(wǎng)絡(luò)帶寬負(fù)載．圖7為不同時間間隔下的網(wǎng)絡(luò)帶寬負(fù)載，從圖中可以看到，傳統(tǒng)靜態(tài)策略的網(wǎng)絡(luò)帶寬負(fù)載波動相對平緩，但本文副本策略在某些時刻突然占用了極大的網(wǎng)絡(luò)帶寬，因為這些時刻是競標(biāo)活動周期，在這周期內(nèi)，競標(biāo)過程的通信要耗費比較多的網(wǎng)絡(luò)帶寬．在某些時刻犧牲一點網(wǎng)絡(luò)帶寬來提升整個系統(tǒng)的性能是值得的．

上述實驗結(jié)果表明，在消耗一點網(wǎng)絡(luò)帶寬的代價下，本文副本管理策略可以有效提高用戶訪問數(shù)據(jù)的響應(yīng)時間和負(fù)載平衡．

4 結(jié)語

對云存儲環(huán)境下的副本問題提出了基于競標(biāo)模式的動態(tài)副本管理策略．該策略引入競標(biāo)機制中的競標(biāo)時間、競標(biāo)底價和競標(biāo)價格等，將主節(jié)點和子節(jié)點作為賣家和買家．本文策略考慮了系統(tǒng)的負(fù)載均衡和可用性和一致性的均衡問題．實驗結(jié)果表明，與傳統(tǒng)靜態(tài)副本策略和CDRM副本策略相比，本文策略有著比較好的系統(tǒng)性能．

在未來的工作中，將深入研究針對用戶訪問模式的變化來進行副本分布以及通過灰色預(yù)測用戶未來的數(shù)據(jù)訪問熱度來優(yōu)化副本分布．