云存儲中基于競標模式的副本管理策略

張 鴻，林 兵，劉漳輝，2

(1．福州大學數學與計算機科學學院，福建福州 350116;

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

0 引言

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

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

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

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

1 云存儲模型

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

圖1 云存儲系統(tǒng)拓撲結構Fig．1 Cloud storage system topology structure

2 基于競標模式的副本管理方法

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

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

2．1 競標開始時間

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

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

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

2．2 競標底價

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

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

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

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

式中:國家和地區(qū)編號采用電話區(qū)號表示;數據中心編號采用數據中心名稱縮寫進行區(qū)分;機架編號與物理機編號均為數據中心內部統(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為中國福建省福州市超級計算機數據中心的第01號機架上的03號物理機，節(jié)點j為中國福建省廈門市廈門大學數據中心的第02號機架上的02號物理機，兩點間的物理距離定義為distancei，j=00000111100000(二進制)=960(十進制)．

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

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

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

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

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

2．3 競標價格

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

表2 1～9比率標度法含義Tab．2 1 ～9 ratio scale method

2．4 競標管理過程

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

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

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

3 實驗與性能分析

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

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

3．2 實驗結果與分析

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

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

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

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

圖6 負載數量變化的響應時間Fig．6 Response time varies with load

圖7 時間間隔下的網絡帶寬負載Fig．7 Network bandwidth load varies with time interval

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

上述實驗結果表明，在消耗一點網絡帶寬的代價下，本文副本管理策略可以有效提高用戶訪問數據的響應時間和負載平衡．

4 結語

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

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