一種基于可用性的動態云數據副本管理機制

陶永才,巴 陽,石 磊,衛 琳

1(鄭州大學 信息工程學院,鄭州 450001) 2(鄭州大學 軟件技術學院,鄭州 450002)

1 引 言

近年來隨著科學技術的快速發展,云計算、物聯網、社會網絡等新技術應運而生,數據的類型和數量呈現爆炸式增長,大數據時代已經到來.

云存儲把互聯網上大量地理上分散的存儲設備整合到一個存儲池中,應用虛擬化技術,基于低成本、不可靠的節點和網絡資源,為用戶提供大容量和高性能的云存儲服務[1].云存儲是云計算的基礎,其規模正以驚人的速度擴大.目前比較流行的云存儲系統有RAID 1,GFS[1],Ceph[2]和HDFS[3].

在云存儲中,為提高性能,數據分塊是一種廣泛采用的技術[4].除了最后一個塊,文件被分割成多個大小相同的塊.這些塊分布存儲在各數據節點中,通過并行傳輸數據,提高數據帶寬.然而,由于云存儲系統的動態性、分布性和異構性,節點軟硬件故障、電源故障和網絡故障時常發生,導致數據塊無法訪問[16].因此,一個數據塊訪問故障可能會導致整個文件不可用.為了避免由節點故障引起的訪問失敗和數據丟失,數據副本被廣泛采用,通過在不同節點上放置數據副本來保證云存儲中數據的可靠性和可用性[5].數據副本保證如果一個數據節點失效,數據仍然可用,服務將不中斷.除了提高數據可靠性和可用性之外,如果副本的分布和請求合理,副本機制將能改善系統負載平衡和總體性能.

現有的云存儲系統(如Amazon S3[6]、GFS和HDFS)主要采用靜態副本管理策略,副本因子一般為3,放置策略是將一個副本放置在本地機架上的節點,另一個副本放在同一機架上的其他節點,最后一個副本放在不同機架上的任意一個節點[7].這種機制存在一些缺點.首先,在可靠性高的云存儲系統中,副本會占用大量的存儲空間,提高云存儲系統的可靠性成本,最終轉嫁給用戶.其次,該機制無法適應動態變化的數據訪問量和節點性能變化,導致系統負載不均衡和性能低.

為解決上述問題,本文提出一種動態副本管理機制DRM(Dynamic Replica Management scheme),DRM主要貢獻如下:

1)研究確定數據可用性和副本數之間的關系模型,并利用此模型來動態計算和維護給定可用性要求的最小副本數.

2)基于節點性能和用戶訪問特性確定副本放置位置.

本研究在HDFS上實現了DRM,實驗結果表明DRM在成本、負載平衡和性能都優于現有HDFS副本管理機制.

2 相關工作

現有的GFS和HDFS的副本管理使用默認數量,通過數據遷移實現負載均衡,消耗較多的帶寬資源[3].

副本放置對于存儲系統的數據可用性和容錯至關重要[12].一個好的副本放置策略可以提高數據可靠性、可用性和網絡帶寬利用率.因此,如果副本分布和請求合理,優化副本策略不僅可以提高可用性,還可以提高負載均衡和總體性能.文獻[8]提出面向用戶的副本放置策略,把副本放置在距離用戶較近的節點上,使得訪問數據時能夠較快地獲取數據.文獻[9]提出面向請求的副本放置策略,對經常訪問的數據創建較多的副本,并把副本放置到用戶訪問密集的區域.此方法能夠明顯減少查找路徑長度,從而提高查詢效率.文獻[10]提出面向業務的副本放置策略在具有最多轉發流量的節點上進行副本放置,與面向請求的方法相比,其副本可以為大多數請求者服務,使得利用率更高.文獻[11]提出了一種改進的數據放置策略,該策略基于數據負載和結點網絡距離計算各個結點的調度評價值,依據此調度評價值選擇一個最佳的遠程數據副本的放置結點.

上述研究都是采用類似HDFS中的靜態副本管理策略.在很多情況下,僅僅使用三個副本放置策略會引起巨大的空間資源的浪費,它無法適應動態變化的數據訪問和節點性能,并會導致糟糕的性能和負載不均衡,本文提出的動態副本管理機制,根據可用性來決定副本的數量,基于節點性能和用戶訪問特性確定副本放置位置.不僅節省了大量的存儲空間,也提高了大規模云存儲的性能.

3 問題分析

數據副本一定程度上滿足了數據可靠性的要求,但是需要更多的存儲空間.在云存儲中,如果采用一些適當的策略,數據副本機制仍可以減少對存儲空間的占用.數據副本機制必須面臨兩個挑戰:副本數量和副本放置.

在實際應用中,數據訪問是高度不規則的,呈現時間局部性和空間局部性,數據時間局部性是一些數據在一定時間段內被訪問頻率很高,數據空間局部性是用戶對數據的訪問主要集中一些熱點區域[17].因此,熱點區副本訪問量通常偏高,節點負載過大,無法滿足用戶的訪問質量.相反,一些數據副本很少被訪問,而且有些熱點區副本隨著時間的推移會被冷卻,所以,過多的副本將浪費存儲資源,并導致不必要的維護開銷.

Hadoop[7]采用3副本策略,存儲1 GB數據需要3 GB的數據空間,這將導致200%的額外成本.對于一些數據密集型應用程序,額外的花費可能是巨大的.然而,在實際中,有些數據不需要可靠性保證,比如一些應用的中間結果數據.對于這類數據,可以不采用副本機制.此外,對于有高可靠性保證要求的關鍵數據,固定的3副本策略并不能保證.在爆炸性訪問突發的情況下應該始終保持最大數量的副本,還是保持較少副本以犧牲性能為代價來節省資源？因此,系統應保留多少個副本以滿足可用性要求是云存儲需要解決的一個難題？

另一方面,與小規模同構系統相比,分布式大規模異構存儲系統中的副本放置更復雜,其中每個數據節點可能具有不同的處理能力(包括CPU、存儲、網絡帶寬等),并且只能提供有限數量的訪問請求.在這種異構存儲系統中平均的副本分配策略不能達到負載均衡和優化總體性能.相反,可能會發生訪問傾斜,使得熱數據節點的請求被拒絕,而其他數據節點處于空閑,從而導致系統負載不均衡和低性能[18].

為了降低存儲成本,提高存儲性能和負載均衡,上述問題必須予以考慮.

4 動態副本管理機制DRM

本文提出一種動態副本管理機制DRM,旨在優化如何基于可用性來確定副本數目和副本放置位置問題.

4.1 基于可用性的副本創建模型

DRM研究數據可用性和副本數之間的關系,設計基于可用性的副本創建模型,并利用此模型來動態計算和維護給定可用性要求的最小副本數[13].

符號定義如表1所示.

表1 符號的定義
Table 1 Definition of symbols

符號定義P(NAi)數據節點Ai的可用概率P(NAi)數據節點Ai的不可用概率P(BAi)數據塊Bi的可用概率P(BAi)數據塊Bi的不可用概率P(FA)文件F的可用概率P(FA)文件F的不可用概率Aexcept期望文件F的可用性

在云存儲系統中,假設文件F由m個數據塊組成,標記為{b1,b2,…,bm},并存放到不同的數據節點中.假設塊bi有rj個副本,如果這個塊的所有節點都是不可用的,說明這個塊是不可用的,所以塊bi不可用的概率如式(1)所示.

(1)

因為所有節點都是獨立的,所以可以得到:

(2)

云存儲數據可靠性服從指數分布.根據經典理論[14],假設一個云存儲節點的可靠性在時間T內服從指數分布:

F(T)=e-λ T

(3)

其中λ是云存儲節點的故障率,F(T)表示在某時間段內云存儲節點故障的期望值.

假設多個副本存儲在不同的存儲節點中.根據云存儲節點可靠性,數據的可靠性與多個副本的關系可以由式(4)計算.

(4)

Trj為rj個副本的存儲生命期時間.

要保證文件的可用性就必須要求所有的塊可用,一個不可用的塊會導致整個文件不可用,如式(5)所示.

(5)

DRM假設數據塊相互獨立,即塊bj的不可用不會影響塊bk.可以獲得:

(6)

由式(4)和(5)可計算得式(7).

(7)

則文件F的可用性如式(8)所示.

(8)

如果要滿足文件F的可用性Aexcept,則式(9)應滿足成立.

(9)

DRM使用式(9)計算最小副本數rmin以滿足具有平均數據節點故障率的預期可用性.在數據節點失效或者數據塊的當前副本數量小于rmin的情況下,額外的副本將被創建到云存儲的數據節點中.

此外,對于不是關鍵的并且僅用于短期的數據類型,可以采用相對低的可靠性保證,并且不需要必要的數據回復,因此副本的數量可以設置為1.

4.2 智能副本放置機制

大型云存儲系統的存儲節點通常分布在集群的多個機架中,節點間通過交換機互連.不同機架節點間的通信必須經過交換機.通常情況下,同一機架節點間的網絡帶寬大于不同機架節點間的網絡帶寬.

目前的云存儲系統(HDFS)采用靜態副本管理機制,不考慮節點異構性,地理分布性.這將導致副本成本增加、負載不均衡和低性能.因此,在智能副本放置機制應考慮一些重要因素,例如:訪問熱點變化、網絡帶寬、阻塞概率、節點異構性、負載不均衡等.

為解決上述問題,DRM采用智能副本放置機制,采用三種不同的副本放置策略(面向用戶,面向請求和面向業務)適應不同的應用場景.副本放置機制可以分為如下兩個步驟:

1.副本創建階段.在此階段,DRM使用面向用戶的副本放置策略.在初始階段,副本創建的目的是保證數據可用性,而不是增加訪問量.在開始階段,系統不能確定用戶訪問密集的區域,訪問量低難以判斷轉發業務量大的節點,并且難以預測未來的訪問速率和訪問來源.因此,面向請求和面向業務的副本放置策略不適合.此外,由于復制成本較低,因此復制失敗的可能性也較低,所以使用面向用戶的策略更優.DRM采用的面向用戶策略的算法如下.

首先,系統將客戶端作為起始點,其標記為0.最靠近客戶端的機架標記為1,需要通過標記1機架的其他機架標記為2,以此類推.系統選擇具有最小標記機架中的節點來放置副本.

第二,在同一機架中,根據四個性能指標選擇節點:(1)自由空間存儲,(2)CPU性能,(3)I/O性能,(4)網絡帶寬.

2.副本運行時調整.在系統運行期間,數據的訪問率高度不規則.如果數據塊訪問量增加并成為熱分區,則將創建新的副本以保證負載均衡,并且在指定的時間內對客戶端做出響應.因此,系統采用面向業務的策略,在具有最多轉發流量的節點(許多必要的路由路徑的連接節點)上放置副本數據.與面向請求策略相比,面向業務策略下的副本可以為大多數請求者服務,保證更高的利用率.

在路由轉發過程中,轉發查詢根據不同的路由算法產生的流量也不同.在此,只計算直接到目的地的有效流量,不包括向所有鄰居轉發信息.每個請求者j到副本Bi存在路由路徑,該路徑中的所有節點的集合被表示為Aij.

Aij={Nk|Nk表示此節點在節點Ni到節點Nj的路由路徑上}

在單位時間t內,假設trijkt表示節點Nk從請求者j到副本Bi的業務負載,trikt表示節點Nk用于副本Bi的轉發流量.節點Nk的處理能力和副本數分別為Cikl(0

(10)

在單位時間t內將來自請求者j到副本Bi的查詢數量定義為qijt,假設節點Nkx是路由路徑中節點Nk之前的任何一個節點,因此Nkx∈Aij.節點Nkx的處理能力和副本數分別為Cikxl(0

(11)

(12)

對于轉發節點,如果其流量大于系統平均查詢的γ倍,則認為它是過載的并且被標記為流量中心節點,即:

(13)

DRM采用文獻[15]提出的動態副本調整策略,利用灰色預測技術,根據最近數據的訪問特征來預測未來數據塊的訪問熱度,并且動態調整副本數目.當數據塊訪問增加成為熱點時,動態增加副本數目,以提高數據訪問效率.如果數據塊為非熱點訪問數據,則動態刪除最近訪問頻數最少的副本,以節省系統存儲空間.

4.3 DRM控制策略

算法1為動態副本控制算法.首先是基于可用性的副本創建模型,使用式(9)根據用戶給定的文件可用性算出最小副本數rmin(第2-6行).其次是智能副本放置機制,在副本創建階段,采用面向用戶的策略將副本放置在離用戶最近的機架上,以保證數據的可用性(第11-12行);而在副本運行調整階段,采用面向業務的策略,在具有最多轉發流量的節點放置副本,保證為大多數請求者服務,有效的提高利用率(第14-15行).最后是動態副本調整策略,數據塊的訪問頻率并不總是保持很高,根據文獻[13]提出的算法,如果當前副本數大于rmin并且數據塊平均訪問頻率下降到刪除閾值thdel,則根據文獻[15]提出的LFU算法計算出數據塊各個副本i在當前時刻之前的N個單位時間段T內的總訪問頻數VNi,刪除最近訪問頻數最少的副本,調整副本數目以節省存儲空間(第18-22行).

算法1.動態副本控制算法

輸入:Aexcept,文件的可用性；

trk,路由路徑上節點k用于副本的轉發流量；

q,副本的平均查詢；

thdel,刪除閾值.

輸出:data nodel k,副本放置的流量中心節點.

1.foreach time window Tdo

2.foreachfile

3.ifavailability reset by user

4. Calculate rmin

5.endif

6.endfor

7.foreach block do

8. rj=current replica number of block j

9. aj=Access frequency of block j

10.ifr < rmin

11.ifr=0 //副本創建階段

12. add rminreplicas to the nearest data nodes

13.else

14.iftrk>= γq

15. add one replica to the data node k

16.endif

17.else

18.ifaj< thdelthen

19.fori=1 to rjdo

20. calculate VNi

21.endfor

22. delete the replicas of smallest VNito the data nodes

23.endif

24.endfor

25.endfor

該算法可以很好的解決靜態副本策略無法適應云計算的動態性特征,算法中提出的動態副本控制策略可以根據資源環境的變化而動態調整副本的數目與位置,以適應資源環境不穩定的情況.該算法雖然會增加一些額外的開銷,但是計算主要集中在系統CPU空閑時間,對整體性能影響很小.

5 DRM實現

除了默認的副本管理策略,HDFS還提供了靈活的API方便擴展和實施高效的副本管理.副本因子在HDFS中按文件進行配置.應用程序可以指定文件的副本數.副本因子可以在文件創建時被指定,以后可以更改.但是,HDFS不提供確定副本因子的策略.本文可用于確定給定可用性要求下的最小副本數.HDFS還為Datanode之間的數據遷移提供接口,以平衡工作負載.因此,HDFS是實現和評估DRM的良好平臺.

為了在HDFS中實現本文提出的DRM,使用副本因子來表示Namenode的元數據中的最小副本數.圖1顯示了HDFS中DRM的框架.由于DRM需要塊數來計算給定可用性需求的最小副本數,因此修改HDFS客戶端以將整個文件數據緩存到本地文件而不是第一塊.將整個中間文件緩存在本地文件中是合理的,其大小范圍從幾百兆字節到千兆字節.這簡化了在HDFS中的原型實現,但可能不適用于大型(太字節)的文件.找到將DRM有效地集成到HDFS中的最佳方式是未來工作的一個重要方向.

圖1 動態副本管理框架Fig.1 Dynamic replication management framework

將整個數據寫入本地文件后,客戶端通過可用性設置和塊號聯系NameNode.NameNode將文件名插入到文件系統層次結構中,基于式(9)計算副本因子,并利用面向用戶的策略獲得每個數據塊的DataNode的列表.NameNode使用每個塊的DataNode列表,目標數據塊和副本因子來響應客戶機請求.然后客戶端以流水線方式將每個數據塊從本地臨時文件刷新到指定的DataNode及其副本到選定的DataNode.

系統運行期間,在數據節點不可達或者當前副本數小于最小副本數rmin的情況下,新副本將被動態地添加到數據節點以保證可用性要求.

6 性能評估

測試平臺建立在由一個NameNode節點和二十個DataNode節點的集群上.每個節點都有2.8GHz的Intel Pentium 4 CPU,1GB或2GB的內存,80GB或160GB的SATA磁盤.操作系統是帶有內核2.6.20的Red Hat AS4.4.Hadoop版本為0.16.1,java版本為1.6.0.

6.1 可用性

為了評估式(9)的準確性,實驗隨時調整系統中存在的副本數目,并測量文件可用性.

在這個實驗中,文件被分割成4塊.圖2比較對應于預期可用性的副本數目.例如,假設數據節點失效率為0.1和用戶期望的文件可用性為0.8,基于式(9)的計算,最小副本數為2.當系統將每個塊的副本數保持為2時,我們測量文件的平均可用性為0.93左右.雖然模型預測在圖中的坐標可能都不是特別準確,但這驗證了模型指向的總趨勢.

為了評估DRM作為動態算法的優勢,測量實驗中運行的副本數目.結果如圖3所示,將Aexcept設置為0.8,開始階段每個塊設置一個副本.從結果中可以看到,在實驗開始時副本數目不斷增加.達到一定程度后,實驗中副本的數目維持在一個恒定的水平.這表明如果當前副本數目不滿足可用性需求,DRM便會動態添加更多副本.

圖2 可用性模型的準確性比較Fig.2 Accuracy comparison of availability model

圖3 數據節點故障率為0.1和0.2,期望值為0.8的動態復制Fig.3 Dynamic replication with data node failure rate of 0.1 and 0.2,Aexcept=0.8

6.2 訪問延遲

在不同的訪問流行度和訪問率下比較DRM和HDFS的平均訪問延遲.HDFS靜態維護配置系統中的副本數目,并采用機架感知副本放置策略.當副本因子為3時,HDFS將兩個副本放置在同一機架中,將一個副本放置在不同的機架中.然而,在同一機架中的Datanode是隨機選擇的,而不考慮Datanode之間的性能和工作負載差異.假設有20個數據節點,訪問率為 δ(0<δ<1),設置Aexcept= 0.8,數據節點失效率為0.1,系統最初每塊保持2個副本.測試結果繪制在圖4中.

由圖4可以看出,隨著訪問流行度的增加,DRM和HDFS的訪問延遲都會降低.但是,當訪問流行度很小時,DRM的性能比HDFS的性能好.這是因為DRM可以通過增加流行塊的副本數目并根據面向業務的策略調整副本位置,在數據節點之間動態分配工作負載.從實驗結果還可以發現,當將訪問率從0.2增加到0.6時,DRM的性能優于HDFS.這表明DRM利用面向業務的策略在數據節點集群之間分配繁重的工作負載,并利用整個集群的資源來實現整體性能的提高.

實驗結果表明,DRM可以適應環境的變化,保持一個合理數量的副本,這不僅滿足可用性,而且還提高了訪問延遲,負載均衡,并保持整個存儲系統穩定.

7 結 論

目前的分布式系統都是采用數據副本的方法來提高數據的可用性,但是當前的數據副本方法大多都是靜態地提供固定個數的數據副本,無法適應動態變化的數據訪問和節點性能,并會導致糟糕的性能和負載不均衡,本文提出的DRM策略充分考慮到了這些問題,該策略能根據可用性計算得到合適的數據副本個數,不僅考慮到數據可靠性還避免了不必要的數據復制,基于節點性能和用戶訪問特性確定副本放置位置.實驗結果表明DRM在成本、負載平衡和性能都優于現有HDFS副本管理機制.

[1] Ghemawat S,Gobioff H,Leung S T.The google file system[J].Acm Sigops Operating Systems Review,2003,37(5):29-43.

[2] Weil S A,Brandt S A,Miller E L,et al.Ceph:a scalable,high-performance distributed file system[C].Symposium on Operating Systems Design and Implementation,USENIX Association,2006:307-320.

[3] Konstantin Shvachko K,Hairong Kuang,Radia S,et al． The hadoop distributed file system[C]．In Proc．of the 26th Mass Storage System and Technologies,2010:1-10.

[4] Rahman R M,Barker K,Alhajj R.Replica placement strategies in data grid[J].Journal of Grid Computing,2008,6(1):103-123.

[5] Xu Jing,Yang Shou-bao,Wang Shu-ling,et al.CDRS:an adaptive cost-driven replication strategy in cloud storage[J].Journal of the Graduate School of the Chinese Academy of Sciences,2011,28(6):759-767.

[6] Amazon simple storage service website[EB/OL].http://aws.amazon.com/s3/,Jan,2017.

[7] Melorose J,Perroy R,Careas S.Hadoop definitive guide[M].Hadoop:The Definitive Guide.Yahoo! Press,2015:1-4.

[8] Chandy J A.A generalized replica placement strategy to optimize latency in a wide area distributed storage system[M].Proceedings of the 2008 International Workshop on Data-aware Distributed Computing (DADC′08),Boston,USA,New York NY,USA,ACM,2008:49-54.

[9] Ding Y,Lu Y.Automatic data placement and replication in grids[C].High Performance Computing (HiPC),2009 International Conference on.IEEE,2009:30-39.

[10] Qu Y,Xiong N.RFH:a resilient,fault-tolerant and high-efficient replication algorithm for distributed cloud storage[C].International Conference on Parallel Processing,IEEE,2012:520-529.

[11] Lin Wei-wei.An improved data placement strategy for hadoop[J].Journal of South China University of Technology,2012,40(1):152-158.

[12] Ibrahim I A,Wei D,Bassiouni M.Intelligent data placement mechanism for replicas distribution in cloud storage systems[C].IEEE International Conference on Smart Cloud,IEEE Computer Society,2016:134-139.

[13] Wei Q,Veeravalli B,Gong B,et al.CDRM:a cost-effective dynamic replication management scheme for cloud storage cluster[C].IEEE International Conference on CLUSTER Computing.IEEE,2010:188-196.

[14] Deng J L.Control problems of grey systems[J].Systems & Control Letters,1982,1(5):288-294.

[15] Tao Yong-cai,Zhang Ning-ning,Shi Lei,et al.Researching on dynamic management of data replicas of cloud computing in heterogeneous environments[J].Journal of Chinese Computer Systems,2013,34(7):1487-1492.

[16] Lin Chang-hang,Guo Wen-zhong,Chen Huang-ning.Node-capability-aimed data distribution strategy in heterogeneous hadoop cluster[J].Journal of Chinese Computer Systems,2015,36(1):83-88.

[17] Xun Ya-ling,Zhang Ji-fu,Qin Xiao.Data placement strategy for MapReduce cluster environment[J].Journal of Software,2015,26(8):2056-2073.

[18] Qu K,Meng L,Yang Y.A dynamic replica strategy based on Markov model for hadoop distributed file system (HDFS)[C].Cloud Computing and Intelligence Systems (CCIS),2016 4th International Conference on.IEEE,2016:337-342.

附中文參考文獻:

[5] 徐 婧,楊壽保,王淑玲,等.CDRS:云存儲中一種代價驅動的自適應副本策略[J].中國科學院大學學報,2011,28(6):759-767.

[11] 林偉偉.一種改進的Hadoop數據放置策略[J].華南理工大學學報:自然科學版,2012,40(1):152-158.

[15] 陶永才,張寧寧,石 磊,等.異構環境下云計算數據副本動態管理研究[J].小型微型計算機系統,2013,34(7):1487-1492.

[16] 林常航,郭文忠,陳煌寧.針對Hadoop異構集群節點性能的數據分配策略[J].小型微型計算機系統,2015,36(1):83-88.

[17] 荀亞玲,張繼福,秦 嘯.MapReduce集群環境下的數據放置策略[J].軟件學報,2015,26(8):2056-2073.