動態部署與分塊存儲策略的數據恢復模型

黃春梅，姜春茂，曲明成

(1.哈爾濱師范大學計算機科學與信息工程學院，黑龍江哈爾濱150025;2.哈爾濱工業大學計算機科學與技術學院，黑龍江哈爾濱150001)

隨著云計算和大數據計算的飛速發展，以及網絡傳輸速度快速提升和無線通信(3G4G)技術廣泛應用，為數據的網絡存儲帶來了新的契機。為了增加數據存儲的可靠性和易用性，學術界涌現出很多的研究成果［1-3］。研究方向主要分成2類，基于編碼解碼的分布式存儲，和基于冗余塊的分布式存儲。基于編碼的策略主要源于通信領域，其核心思想是將原始數據等分為m塊，進而融合一定冗余編碼成n塊，n＞m，當存在x個節點失效時(x＜n-m)，可以從其余節點恢復出原始數據。而基于冗余塊的分布式存儲，出現了2個研究方向，完全多副本存儲和分塊冗余存儲。前者將完整的副本數據直接存儲網絡節點，并多不考慮動態部署過程，根據數據存儲可靠性和節點的可靠性采用靜態初始發布機制來確定最終數據的可靠性［6-8］。但是隨著信息技術的飛速發展，對數據存儲提出了更高的要求，如何在現有網絡和節點環境下進一步大夫提升數據的可靠性是一個亟待解決的重要問題。融合動態數據恢復技術的Google公司的GFS系統和Apache基金會的Hadoop系統，采用了分塊分布式冗余存儲策略，在數據存儲節點發生故障時，通過其他節點存儲的冗余數據，將故障節點數據快速重新部署到新的節點，以保證數據整體的可靠性［9-10］。

綜上，編碼策略、分塊冗余存儲與動態部署技術對于數據高可靠存儲管理具有較大的優勢，但是目前能夠將三者融合考慮的相關研究較少，并且采用這種數據存儲管理機制，數據的可靠性可以達到何種程度是一個關鍵性問題，而在當前的研究中很少有研究成果評估這種機制對數據可靠性的影響，缺乏一個有效的評估方法或評估模型。

基于上述理論和存在的問題，本文基于分塊存儲［5，11］、編碼策略、動態恢復提出了多個動態數據恢復模型(數據失效概率模型)。采用指數分布函數來刻畫存儲節點的可靠性，通過模擬正常和異常網絡情況，分析了數據可靠性模型的數據可靠性，結果顯示，本文提出的模型在已知網絡存儲環境的前提下能有效度量數據的可靠性，給出較好的評估，并且較直接分塊存儲和編碼解碼策略對數據的可靠性有很大的提升，并進一步對可靠性模型的影響因子進行了分析，從而增強了可靠性模型的實用性和易用性。

1 基本原理

在可靠性設計中常用分布函數有:二項分布、泊松分布、指數分布、正態分布、對數正態分布和韋布爾分布。而對處于穩定工作狀態的電子機械或電子系統的失效概率基本上服從指數分布。

定義1 可靠度(reliability)也叫可靠性，指的是產品在規定的時間內，在規定的條件下，完成預定功能的能力，它包括結構的安全性，適用性和耐久性，當以概率來度量時，稱可靠度。

對產品而言，可靠度越高就越好。可靠度高則可以更長時間的正常使用，消費者或許希望看到這點(其中也有質量成本問題);從專業名詞的角度來說，可靠度越高的產品，意味著產品正常工作無故障的時間就越長。

1)指數分布可靠度

當失效率為常數時，即:λ(t)=λ時則有

2)指數分布失效概率密度函數

其分布均值和方差分別為

通過對密度函數積分可以求出節點在確定時間點的失效概率函數:

3)指數分布曲線

指數分布概率密度函數、節點失效概率、節點可靠度分布曲線分別如圖1中的(a)、(b)和(c)所示。

4)一段時間的平均失效概率:

為了簡化計算過程，令從時間節點0開始計時，則由式(7)可以化簡推出:

圖1 指數分布曲線Fig.1 Exponential distribution curve

5)基于動態恢復技術的數據失效概率。

從動態部署技術的過程可以看出，如果采用冗余結構存儲數據，當節點發生失效時，需要根據其他節點快速部署失效節點存儲的數據。

定義2 數據失效概率f將當前可用的存儲了同一數據的所有節點的數據作并集處理，如果得到的數據是不完整的，則稱發生了數據失效，發生的概率為f。

比如有3個節點，節點N1、N2存儲相同的數據data1，當檢測到N1發生失效時，需要從N2向N3重新部署數據data1，以保證同時有2個節點存儲了data1。

2 基本存儲與可靠性模型

2.1 完全雙副本存儲

傳統的雙副本存儲過程是，對于一個大小為M的數據D，將其完整副本分別存儲2臺服務器上形成2個完整的拷貝，如圖2。

顯然這種存儲方式占用的存儲空間大小為2M。

基于雙副本和動態部署技術，在一個節點發生失效時，選取一個新的節點恢復數據，令從一個節點恢復數據量M所需要的時間長度為Δt。

圖2 完整雙副本存儲Fig.2 The complete double copy storage

那么在Δt時間內，如果2個節點都失效，則發生數據失效。根據式(8)，得出其數據失效概率模型:

2.2 分塊雙副本存儲

定義3 I等分雙副本存儲(I aliquot double copy，IADC)對于一個大小為M的數據D，將其等分成i份即D=D1+D2+… +Di，且其大小M1=M2=Mi=M/i。稱這種劃分和存儲策略為I等分雙副本存儲。如圖3所示。

顯然I等分雙副本存儲占用的存儲空間總量為2M。

基于I等分雙副本存儲和動態部署技術，需要2i個節點存儲數據，peer(2i-1)與peer(2i)相當于傳統的雙副本存儲。

每個 peer節點存儲的數據量為 M/i，則如果peer(2i-1)、peer(2i)中如果有一個節點發生失效時，對于數據Di的數據失效概率為，則整體的數據失效概率fc為

圖3 I等分雙副本量存儲策略Fig.3 I aliquots double copy storage strategy

3 I等分和模型散列存儲的可靠性模型

文獻［5，11］中提出了一個存儲模型，通過對原始數據進行規則劃分，在i個節點上基于雙倍副本量存儲，當有1個節點失效失效，其他i-1個節點存儲的數據仍然是完整的。基于該模型取存儲節點為3。

定義4 k等分模型散列存儲(Kaliquot model hash，KAMH)對于一個大小為M的數據D，將其等分成i份(i＞ =1)即M=m1+m2+…+mk，且其大小m1=m2=mk=M/i。稱這種劃分和存儲策略為i等分模型散列存儲。如圖4所示。

為了使占用的存儲空間為2M，可以控制散列模型中的冗余量，使占用的存儲空間總量也為2M。

在這種存儲策略中，每個G-peer組由y個節點構成，先令y=3。當一個G-peer中有不多于一個節點失效時，可以從其他2個節點進行動態恢復。

恢復的數據量為2M/3，恢復速度為2V。則恢復時間為Δt/3。

圖4 I等分和模型散列存儲原理圖Fig.4 I aliquots and model hash stored schematic

單個節點在(0，Δt/3)跨度內的失效概率f為

當i=1，y=3時，數據失效概率為

當i＞1，y=3時，數據失效概率為

3.1 G-peer組成員為3時性能分析

1)網絡傳輸正常時比較。令i與λΔt取不同值，記錄相應fd取值，如表1所示，從中可以看出隨著i的增加，fd取值逐漸降低。

表1 i與 λΔt變化時fd取值Table 1 The value of fd when i and λΔt changes

觀測i=2時，fd/fc的比值，如圖5所示，隨著λΔt的增加，fd/fc逐漸增加，但是都小于0.5，說明fd一直優于fc。

圖5 k=2時λΔt與fd/fc的關系Fig.5 Relationship between λΔt and fd/fc when k=2

觀測λΔt=0.001，i取不同值，fd走勢。如圖6所示，隨著k的增加fd逐漸降低。

圖6 λΔt=0.001時i與fd的影響Fig.6 The impact of i and fd when λΔt=0.001

2)網絡傳輸非正常時比較。傳輸速度降級時的性能。檢測i=2時速度降低時的性能，此時如果出現如果數據恢復，一次恢復的數據量為，則從2個點恢復數據的聚集速度位于(V，2V)。則相應的恢復時間為(Δt/6，Δt/3)。此時式(11)變為

從表2可以看出，隨著x的增加，a值逐漸降低，模型性能越好。

比較fd/fc，2等分。取幾組數值，形成圖7，從中可以看出，當x=1.1時fd/fc＞1，除此均小于1，而且隨著x的增加，逐漸降低，說明fd越優于fc。比較fd/fa，2等分。取幾組數值，形成圖8，從中可以看出，x取任意值時fd/fc＜1，而且隨著x的增加，逐漸 降低，說明fd越優于fa。

表2 k=2時速度變化對模型的影響Table 2 Effect of velocity change on the model when k=2

圖7 i=2時速度變化對fd/fc的影響Fig.7 Effect of velocity change on fd/fc when i=2

圖8 i=2時速度變化對fd/fa的影響Fig.8 Effect of velocity change on fd/fa when i=2

3.2 G-peer組成員大于3時性能分析

1)速度呈比例增長時分析。

當y＞3時，式(13)變為

取 k=2，y=3，4，5，λΔt取不同數值，代入式(13)，結果如表3所示。可以看出在λΔt取相同數值時，y值越大fd值越小。Y取3與y取4時fd的相應比值近似為2，而y取4與y取5時fd的相應比值明顯小于2，說明隨著y值增加，可靠性增加變緩。

表3 k=2，y變化對模型的影響Tab le 3 The im pact of y changes on the model when k=2，

2)速度呈非線性增長時分析。

隨著y的增加，動態恢復速度實際不會呈現比例增加。為了有效分析模型在這種情況下的性能，給出一個較為簡潔的恢復速度增長函數如式(16)所示，b為增長系數，后面將對b={0.2，0.4}進行數值分析。如表4、5所示。

表4 b=0.2時fd取值Table 4 The value of fd when b=0.2

將表4、5形成圖9，可以看出b=0.2曲線位于b=0.4曲線上方，說明fd受到影響更大，但是2條曲線都位于fc=1.25×10-7的下方，都優于fc。

圖9 k=2，y變化時fd走勢Fig.9 The fd trend when k=2 and y changes

4 編碼模型散列存儲與可靠性模型

4.1 模型構建

定義5 編碼模型散列存儲對于一個大小為M的數據D，先將其等分x份(x＞1)即M=m1+m2+… +mx，且其大小m1=m2=mk=M/x。然后采用糾刪碼進行編碼，編碼無效率為ε(0＜ε＜1)，編碼后塊數為k(k＞x)，對k個數據塊進行模型散列存儲。稱這種策略為編碼模型散列存儲。

如圖10所示，從糾刪碼的基本原理可知，通過對原始數據M進行x等分，然后進行編碼，編碼無效率為ε(0＜ε＜1)，編碼后塊數為k(k＞x)，則只要有z=(1+ε)x個數據塊存在，就可以恢復出原始數據。編碼后單個數據塊的數據量為Mα/x。每一個G-peer組采用y個節點對散列后的數據進行存儲，則G-peer(k)組中的數據塊nk失效的概率推導fg如下:

如果原來從一個節點恢復M數據時用時為Δt，編碼后處理后采用3個節點模型散列Mα/x的數據，當有一個節點失效后，從2個節點恢復。恢復的時間為

在上述恢復時間內每個節點的失效概率為

則G-peer(k)組中的數據塊nk失效的概率fg:

由于只要在k個數據塊中獲得z=(1+ε)x個數據塊即可以恢復出原始數據，則數據M的失效概率fh為

為了保證存儲的總數據量不超過2M，則編碼后塊數k為

圖10 編碼和模型散列存儲Fig.10 Coding and model hash storage

4.2 性能比較分析

根據目前糾刪碼相關研究，取x=10、ε=0.2、α=1.2、k==17、z=(1+ε)x=12。得出f、fg、fh的數據如表6所示。

如果直接采用糾刪碼存儲，當有節點失效時，較難進行直接恢復，因為所有的節點都是通過完整的原始數據編碼產生，如果需要恢復，則會產生較大的網絡流量，且復雜度較高，時間很難保證。

表6 x=10，ε=0.2，α=1.2時fh取值Table 6 The value of fh when x=10，ε=0.2，α =1.2

那么對于采用糾刪碼存儲，在Δt時間內數據失效概率fj為

根據目前糾刪碼相關研究，取x=10、ε=0.2、α=1.2、k=「2x/α?=17、z=(1+ε)x=12。得到fx、fj的數據如表7所示。

表7 x=10，ε=0.2，α=1.2時 fj取值Table 7 The value of fj when x=10，ε=0.2，α =1.2

為了比較fh與fj的性能，取二者的比值為縱坐標，形成圖11。

圖11 x=10，ε=0.2，α=1.2時fh/fj的比值Fig.11 fh/fj when x=10，ε=0.2，α=1.2

可以看出 fh性能遠遠優于 fj，在正常情況下(0.001 ＜ λΔt＜0.1)，fh優于 fj達到104量級。在 λΔt=2時，也可以達到103的量級。因此可以得出fh遠遠優于fj。令α取不同數值，檢測其對模型性能影響，如圖12所示。隨著α的變化，fh先降低后升高，在α=1.4左右時fh最小，性能最好。

圖12 λΔt=0.001和1時α變化對fh影響分析Fig.12 Analysis of αchange impact on fh whenλΔt=0.001 and 1

同樣取fh與 fc和 fh與fa的比值，如圖13、14所示，fh性能由于二者2～3個數量級，優勢明顯。

圖13 x=10，ε=0.2，α=1.2時fh/fc的比值Fig.13 fh/fc when x=10，ε=0.2，α =1.2

圖14 x=10，ε=0.2，α=1.2時 fh/fa的比值Fig.14 fh/fa when x=10，ε=0.2，α =1.2

4 結束語

編碼解碼、分塊存儲、動態恢復3種機制的有效融合可以在現有網絡存儲環境下大幅提升數據的可靠性，本文通過有效融合3種方法，提出了多種數據可靠性評估模型，模擬分析顯示本文的模型較先前的多副本(分塊)存儲、編碼存儲具有更高的可靠性。通過應用模型可以為具有高可靠性數據存儲需求的服務提供網絡存儲機制和節點選擇方法。通過模擬分析和比較正常和異常網絡情況下模型的可靠性評估結果，增強了模型的可用性和實用性。

［1］陳蘭香，許力.云存儲服務中可證明數據持有及恢復技術研究［J］.計算機研究與發展，2012，49:19-25.CHEN Lanxiang，XU Li.Cloud storage service can prove data held and recovery technology［J］.Computer Research and Development，2012，49:19-25.

［2］孟小峰，慈祥.大數據管理:概念、技術與挑戰［J］.計算機研究與發展，2013，50(1):146-169.MENG Xia of eng，CIXiang.Big data management:concepts，technology，and challenges［J］.Computer Research and Development，2013，50(1):146-169.

［3］YU Xiangzhan，WU Guanjun.An disaster tolerance model based on dataflow replication［C］//Proceedings of the 2008 IEEE International Conference on Information Automation.Zhangjiajie，China，2008:1590-1594.

［4］PITKANEN M，MOUSSA R.Erasure codes for increasing the availability of grid data storage［C］//International Conference on Internet a n d Web Applications and Services-AICT/ICIW＇06.Guadeloupe，France，2006:1-10.

［5］曲明成，吳翔虎，廖明宏，等.一種數據網格容災存儲模型及其數據失效模型［J］.電子學報，2010(2):315-320.QU Mingcheng，WU Xianghu，LIAO Minghong，et al.A data grid disaster recovery storage model and its data failure model［J］.Chinese Journal of Electronics，2010(2):315-320.

［6］WILKINS R S，DU Xing.Disaster tolerant wolfpack geoclusters［C］//Proceedings of the 2002 IEEE International Conference on Cluster Computing.Chicago，USA，2002:1-6.

［7］WANG Yanlong，LI Zhanhuai.RWAR:a resilient windowconsistent asynchronous replication protocol［C］//Proceedings of the The SecO International Conference Availability，Relaibility and Security.Vienna，Austria，2007:499-505.

［8］YANG C T，WANGSY，WILLIAM CC.Implementation of a dynamic adjustment strategy for parallel file transfer in coallocation data grids［J］.J Supercomput，2010，54:180-205.

［9］GHEMAWAT S，GOBIOFF H，SHUN T L.The Google file system［C］//SOSP＇03.New York，USA，2003:1-15.

［10］The hadoop distributed file system:Architecture and design［EB/OL］.［2013-09-13］.http://hadoop.apache.org/common/docs/r0.18.0/hdfs_design.pdf.

［11］曲明成，吳翔虎，廖明宏，等.一種數據網格存儲模型與并行傳輸調度算法［J］.高技術通訊，2010，20(1):26-32.QU Mingcheng，WU Xianghu，LIAO Minghong，et al.A data grid storage model and scheduling algorithm for parallel transmission［J］.High-tech Communications，2010，20(1):26-32.