崔 敏，吳慶濤，張旭龍，鄭瑞娟，張明川

（河南科技大學 信息工程學院，河南 洛陽471023）

0 引 言

如何提高分布在眾多彈性節(jié)點中的數據可用性同時降低數據冗余度已成為云存儲［1－5］中一個重要問題。目前的冗余災備［6－8］方案，將整個數據文件復制3份以上分別存儲于不同位置的服務器節(jié)點上，對其主文件進行操作后同步到其它各節(jié)點的副本上進行修改。在存儲備份時對大文件的多數據塊分布式存儲管理忽略了安全可用性，一旦存儲數據塊的節(jié)點發(fā)生故障將影響整個數據文件的可用性；而對于云存儲系統(tǒng)中大文件的復制將占用額外的存儲空間且呈倍數增加，對存儲資源不斷提出需求，造成存儲成本負擔增大。因此優(yōu)化冗余存儲是保障云存儲系統(tǒng)可擴展性的關鍵。

Wang等提出了一種基于工作負載的選擇性云架構云RAID，對主存儲和備份存儲采取不同的RAID 方法，與傳統(tǒng)的三通復制相比減少了存儲開銷，但是忽略了存儲資源的異構性［9］；文獻 ［10］介紹了異構配置下優(yōu)化冗余的云存儲方案，通過分析分布式冗余方案在異構節(jié)點上的優(yōu)化部署，提出了一種衡量數據可用性的方法?？紤]到編碼冗余的優(yōu)勢，很多學者致力于將編碼冗余應用到云存儲系統(tǒng)中，文獻 ［11－13］在分布式存儲系統(tǒng)中，使用網絡編碼對存儲節(jié)點上的數據進行編碼和重構，一定程度上降低了存儲冗余度，但是計算消耗和流量消耗增大。

本文提出一種高可用的云存儲方案以降低存儲空間的冗余度。主要工作包含以下兩個方面：采用編碼方式進行數據文件冗余容錯；優(yōu)化用戶讀取數據時數據塊的檢索及恢復效率。

1 基于擦除碼的云存儲系統(tǒng)模型

1.1 云存儲系統(tǒng)模型

云存儲系統(tǒng)可以用一個有向圖G＝ （V，E）表示，其中V 是頂點的集合，E 是連接兩個點的邊的集合。把云存儲系統(tǒng)中的所有存儲節(jié)點以及終端看作頂點，節(jié)點與節(jié)點之間的網絡連接看作為圖中的邊。如圖1所示，頂點集合V 根據節(jié)點的不同被分為3 個類別：服務器節(jié)點 （VS＝｛S1，S2，…，Sn｝）擁有存儲系統(tǒng)里每個文件的原始副本；存儲節(jié)點 （VN＝ ｛N1，N2，…，Nm｝）接收并存儲每個文件產生的R 個副本；終端節(jié)點 （VT＝ ｛T1，T2，…，Ts｝）是那些需要獲得數據文件的節(jié)點或用戶端。邊集合E 根據傳輸數據的類別可分為兩大類：從服務器節(jié)點向存儲節(jié)點傳輸數據的ES，以及從存儲節(jié)點向終端節(jié)點傳輸數據的ET。而有向圖邊的方向為數據的流動方向。

存儲節(jié)點和服務器節(jié)點構成的網絡就是一個簡單的云存儲模型，終端節(jié)點是連接到云的客戶端。服務器節(jié)點上包含一系列的數據文件Fn，而每個存儲節(jié)點上接受并存儲隨機量的數據文件Fn的分塊Fin，對于終端節(jié)點可從不同的存儲節(jié)點上獲取到一定量所需的數據文件分塊進行數據文件恢復。因此需要相應的存儲節(jié)點連接到所有的包含源數據文件的服務器即存在關系Fin∪Si∈SFSi。每一個終端節(jié)點必須連接到一組能夠下載到完整副本的一組存儲節(jié)點。

為了使云存儲模型簡化，并不失一般性，我們提出以下幾點假設：

（1）每一個文件的原始副本只存在于某一個服務器節(jié)點中，即各服務器節(jié)點Si與Sj之間的交集不屬于文件Fn，即Si∩SjFn。

（2）一個節(jié)點的類型是單一的，相同類型的節(jié)點之間不進行通信。事實上，一個節(jié)點可以作為文件1的服務器節(jié)點，文件2的存儲節(jié)點以及文件3的終端節(jié)點。我們在這里對其類型進行劃分，將多重類型的節(jié)點擴展為多個單一類型的節(jié)點。

（3）假定云存儲系統(tǒng)中每個文件有R 個副本來提供數據冗余，這里的R 是備份因子。

圖1中標出的方向不是數據鏈路，而是云存儲模型中的數據流的流向，模型中不涉及鏈路的重新分布，由于目標應用是一個存儲系統(tǒng)，鏈路帶寬只影響數據的傳送速度。

1.2 數據編碼存儲與恢復

圖1 一個簡單的云存儲系統(tǒng)模型

擦除碼 （erasure coding）是將原始數據文件編碼成一個數據流 （包含多個編碼數據分塊），由接收者進行重構他們獲取到的額定數量數據分塊后得到原始數據文件。在傳輸過程中編碼后的數據塊的丟失是相互獨立的。圖2為基于擦除碼的云存儲系統(tǒng)。

對于數據文件F，首先進行擦除碼，將編碼后的數據塊分發(fā)到各個存儲節(jié)點N 上，如圖2所示，假如這4個存儲節(jié)點有一個出現故障而不工作時，可以從余下的存儲節(jié)點上取額定數量的數據塊進行解碼，從而得到終端節(jié)點需要的數據文件F。同時可利用正常存儲節(jié)點上的數據塊進行編碼對出錯節(jié)點上的數據塊進行恢復或轉存其它存儲節(jié)點。

為了保障數據的高可用性以及存儲空間的低消耗，我們在擦除碼時需要調整冗余因子，冗余因子太大存儲空間將過度消耗，而冗余因子過小則會導致可用性降低。圖3為一個簡單的數據文件編碼過程。

k個原始數據塊經過編碼生成k＋m 個數據塊，然后將k＋m 個數據塊分散的存儲到云存儲系統(tǒng)中的多個存儲節(jié)點上。其中有m 個是冗余的數據塊，但是具有容錯的能力；k個數據塊具有恢復數據的功能，即對于任意丟失不超過m個的數據塊，這k個數據塊都能將它們恢復成原始的數據。該編碼器是利用 “生成矩陣 （C）和向量組 （F）”的乘法運算進行實現的。其中C 是一個k＋m 行k 列的矩陣，F 是由相同大小的原始數據塊組成的向量組。

有限域［14］的線性運算是編碼器的核心運算，構造有限域是編碼過程的第一步。對于編碼器的構造采用Vandermonde［15］矩陣作為生成矩陣的源矩陣，根據Vandermonde矩陣的行列式性質構造出源矩陣G（n，k），如式 （1）所示

圖2 基于擦除碼的云存儲模型

圖3 一個簡單的數據文件編碼過程

由Vandermonde矩陣的性質可知，從式 （1）中任意抽取的k個行向量相互之間是線性獨立的。于是將式 （1）經過行變換得到式 （2），作為生成矩陣C

在生成矩陣的作用下，對原始數據生成冗余項。假設需要進行存儲的文件是F，它由 （F1，F2，F3，…，Fk）k個同樣大小 （最后一塊若不是整塊進行填充）數據塊組成，經過編碼器的生成矩陣后，生成冗余數據 （D1，D2，D3，…，Dm），于 是 （F1，F2，F3，…，Fk，D1，D2，D3，…，Dm）則構成一個新的冗余存儲向量組，該向量組和生成矩陣C 滿足式 （3）

當存儲在云端的數據冗余分塊中任意數據發(fā)生改變，式 （3）就不成立，因此利用此方法可以驗證云存儲數據的完整性，以增強存儲的安全性。

由式 （2）和式 （3）可推出式 （4）

式 （4）中說明了m 個數據冗余塊可由原始數據分塊經行變換矩陣計算得到，因此在小范圍修改數據時可利用該原理，將被修改的數據塊單獨標記并進行計算，最終將生成的對應冗余數據塊和源數據塊單獨分發(fā)到存儲節(jié)點即可，不需要重新將所有數據塊都進行銷毀再計算以及重新分發(fā)部署存儲節(jié)點。

數據解碼與數據編碼是一個逆過程，需要將從存儲節(jié)點上檢索到的多個同項目數據塊進行解碼并合并為用戶需要的數據文件。分別設編碼前原始數據塊個數和經過編碼后的數據塊總數為k和n，并設各個數據塊的塊長為z，其n行k 列的生成矩陣表示為C（n，k）。而編碼對象D（k，z）即k行z 列的原始數 據 矩陣，E（n，z）表 示 編 碼 后得 到 的n 行z 列 的編碼數據矩陣，則編碼過程如式 （5）所示

令R（k，z）表示E（n，z）中任意k 行組成的新矩陣，那么由生成矩陣中的對應的k行可生成R（k，z）如式 （6）所示

C（n，k）是 由Vandermonde 矩 陣 轉 換 得 到，因 此 利 用Vandermonde矩陣性質可以得出解碼矩陣T（k，k），如式 （7）所示

于是式 （8）成立

將式 （6）代入式 （8）可得解碼過程

利用式 （9）可完成對用戶所需要的數據進行恢復。

1.3 數據塊高效檢索

在云存儲系統(tǒng)中，原數據文件在編碼分成數據塊分散存儲到存儲服務器節(jié)點上后，在需要取回數據文件時，就需要在眾多的存儲服務節(jié)點中檢索對應數據文件的數據編碼分塊。在傳統(tǒng)的簡單拷貝冗余備份中，檢索相對簡單，只需要找到其中一份就能完成請求響應。而在擦除碼的分布式存儲冗余備份下，需要取回額定數量的數據塊才能還原出原數據文件，因此對數據塊檢索提出很高的要求。

為了提高數據塊檢索效率，我們采用Chord協(xié)議［16，17］的點對點檢索方法，設計了基于Chord的快速資源定位方法，存儲節(jié)點通過對自身的屬性做SHA－1運算得到一個m位的標識號記作ID，然后根據ID 的大小順序組成一個邏輯環(huán)，即Chord環(huán)。下面給出相關定義：

定義1 主節(jié)點環(huán) （master chord），為云存儲系統(tǒng)中的每一個存儲節(jié)點構建一個邏輯環(huán)，將各主節(jié)點的物理信息進行哈希后映射到Chord，其對應哈希函數設為Hash－Master。

定義2 存儲節(jié)點環(huán) （storage chord），為定位一個文件分割編碼后的多個數據塊的存儲位置而在存儲相關數據塊的節(jié)點之間構建邏輯環(huán)，將相同文件的數據塊所在的存儲節(jié)點信息哈希到Chord 中，其對應哈希函數設為HashStorage。

通過Master Chord可以快速定位存儲文件所在的主存儲節(jié)點，然后利用Storage Chord快速檢索對應文件分塊所存放的存儲節(jié)點。Chord環(huán)中的每一個節(jié)點都需要維護一個路由表，路由表中記錄了環(huán)中其它節(jié)點的信息，在查找的時候其時間復雜度為O （log N）。而隨著節(jié)點的彈性變化，在增加或減少存儲節(jié)點時，只需要O （1／N）數量級的節(jié)點便信息變更。

按照如下方法將數據資源對象分配到云存儲節(jié)點上。所有文件哈希后與主節(jié)點信息哈希后組成的Chord環(huán)進行掛載，隨著文件的創(chuàng)建與刪除主節(jié)點環(huán)中的Chord節(jié)點也會不斷匹配新文件。所有數據分塊進行哈希后生成專屬ID，按照ID 遞增的順序組成一個環(huán)，與環(huán)上每個節(jié)點記錄的存儲節(jié)點信息組成鍵值對，同一個存儲節(jié)點可供不同主節(jié)點環(huán)連接。

令Chord環(huán)中的每個節(jié)點對應維護一個Chord路由表，這可以更加方便的定位數據塊資源，減少資源查找的時間。每個路由表有m 個表項。Chord中節(jié)點n 的路由表結構見表1。

為了尋找節(jié)點k的后繼，當節(jié)點n中路由表沒有節(jié)點k的鍵值時，則進行以下操作：節(jié)點n 從路由表中選擇離k最近的節(jié)點m，然后通過節(jié)點m 查找更接近于k 的節(jié)點。通過重復該操作，最終可以定位到所需資源。

表1 Chord路由表結構

存儲節(jié)點的資源定位在算法1中給出了相應偽碼。該算法通過遞歸來判斷節(jié)點n是不是資源k的前驅，路由表中找不到所需資源時，就尋找與目標資源所在節(jié)點最近的節(jié)點n′，并由節(jié)點n′繼續(xù)重復該算法，直到找到目標資源為止。

從Chord路由表的構造和存儲節(jié)點資源定位算法可以看出，每次尋找最近節(jié)點后，新找到的節(jié)點離資源對象的距離通常比原來少一半，通常情況下最多尋找最近節(jié)點logN次就可以定位成功，因此能夠加速存儲節(jié)點的數據塊定位。

算法1 資源定位算法1. n.findSuccessor（k）2. if（k（n，n.successor］）3. return n.successor；4. end if 5. for（i＝m；i＞1；i－－）6. if（finger［i］.node in（n，k））7. return finger［i］.node；8. end if 9. end for 10. n′＝n；11. return n′.findSuccessor（k）；

當m＝4，n＝2，k＝14時的查找示例如圖4所示。

圖4 資源定位

2 實驗與結果分析

為了云存儲方案的驗證，我們利用3臺服務器構建了基于Hadoop的云存儲平臺，平臺中3個服務器作為3個云數據中心，并對每個數據中心的物理機進行了虛擬化。云存儲平臺總共包含3個數據中心，24個虛擬機。表2為數據中心1的資源配置情況。

表2 云存儲平臺的數據中心資源配置

在Hadoop構建的私有云存儲平臺基礎上，我們進行了存儲方案Java實現，主要是以云任務的形式提交給數據中心進行云存儲服務數據存儲過程處理實驗。我們的擦除碼模塊主要是負責對提交的存儲文件進行編碼分塊，檢索數據模塊提供虛擬節(jié)點中數據分塊的快速取回并進行合并解碼處理，具體操作的實現由各數據中心主機分配給工作節(jié)點完成，所有的操作由主節(jié)點進行調度。圖5為數據中心上多個云任務在3臺虛擬機上的時間運行。

圖5 數據中心云任務虛擬機分配運行時間

從圖5可以看出300個云任務提交到云端分配給3臺虛擬機進行處理時，它們以分時并行的作業(yè)調度機制將云任務Map到各運算節(jié)點，最后由主節(jié)點進行Reduce操作，從而完成整個存儲服務的需求響應。

為了驗證擦除碼存儲方案的效能和冗余消耗，我們在不同的冗余因子下進行了存儲編解碼實驗，在高可靠性的要求下冗余度越高越好，這樣能夠保障在節(jié)點發(fā)生故障時其它節(jié)點能夠提供備份，但高冗余度導致存儲查找取回解碼產生巨大消耗。因此，需要選擇適當的冗余因子來保障存儲數據的高可用性以及存儲編解碼的高效性。在Hadoop云存儲的基礎上，我們將數據編碼模塊和資源檢索定位模塊接入云任務調度，選取一個大小為1005kb的圖片文件，將其作為一個云存儲請求進行處理，圖6是在數據分塊個數N＝10，不同冗余因子下文件的編解碼時間以及存儲空間的消耗。

圖6 不同擦除碼冗余因子的云存儲效率與冗余消耗

從圖6 （a）中可以看出，在60次重復實驗中，對于1 Mb大小的圖片文件進行編碼時，不同冗余度對編碼的時間要求變化不大，基本保持在平均40ms左右，而從分散的存儲節(jié)點取回額定數據塊進行合并解碼時，隨著冗余因子的減小解碼響應時間隨之增大。而對于存儲空間的占用從圖6 （b）中可以明顯看出1 Mb大小的圖片文件在不同的冗余因子作用下所占用的存儲空間逐漸增多。與單文件三備份相比顯然節(jié)省了大量的存儲空間，同時增加了存儲節(jié)點的靈活性與機動性。

為了比較我們提出的存儲方案與三備份的可用性，首先定義數據可用性R，可用性為訪問數據時所有可用資源成功交付的概率。設定每個存儲節(jié)點的出錯退出概率為p，則三備份存儲方案的可用性為Rt＝（1－p3）C3n。而我們提出的方案的可用性為Re＝（1－pm＋1）Ck＋mn。當Re＝Rt時，即（k＝1，m＝2）而此時我們的方案冗余度為0，三備份冗余度為2。隨著冗余因子增大，可用性Re不斷增大，而Rt保持不變。顯然我們提出的方案在理論上能夠保證較高的可用性同時降低冗余度。

由于云存儲中數據的格式以及大小多樣性，我們針對不同大小規(guī)模以及不同格式的數據文件進行了上傳存儲與云端取回響應時間實驗。實驗中選取的文件、大小及數據類型見表3。

表3 不同格式及大小的數據文件

實驗中對表3中的文件分別進行上傳存儲，云端取回操作。在數據分塊為10，冗余因子為1.2時，記錄不同大小文件的存儲響應時間如圖7所示。

圖7 不同大小文件存儲與取回響應時間

從圖7中可以看出，在相同冗余因子和文件數據分塊下，對于小于50 M 的數據文件其編解碼和查找所用的時間都較短，上傳存儲時間與取回響應時間相當，但取回響應時間要比上傳存儲時間長。隨著數據文件的不斷增大，由于上傳存儲所需要的編碼數據量加大，向異地存儲節(jié)點分發(fā)需要的時間增加，所以上傳存儲的時間較大幅度的增加。而采用Chord的檢索在云端數據取回時提高了檢索效率，降低了檢索的時間，同時由于編碼冗余的特性，使得只需要檢索到額定數量的數據塊就可以合并解碼出原始文件。因此，取回響應時間雖數據塊的增大變化較緩慢。

目前已經有一些相關的研究，針對云存儲冗余優(yōu)化方案有傳統(tǒng)的三備份，以及網絡編碼冗余和噴泉碼等。為了檢驗我們提出的基于擦除碼以及Chord協(xié)議的云存儲優(yōu)化方案 （C擦除碼）的性能。針對同樣的存儲文件在同樣的存儲條件下進行了三組對比實驗。主要從文件上傳與取回所消耗的時間和上分別進行實驗，結果如圖8和圖9所示。

圖8 不同編碼方式下上傳云端存儲的響應時間

圖9 不同編碼方式下從云端取回解碼的響應時間

通過實驗，我們提出的云存儲方案 （C 擦除碼）能夠有效的降低云端存儲的冗余度，同時保障用戶數據的可靠性。該方法適宜于云端大數據的存儲共享，可以保障數據在云存儲平臺中的有效性，能夠支持多用戶以只讀的方式快速獲取大文件文件，對于小文件的讀寫能夠高效響應，但是在對大數據文件修改上傳時還需要進一步優(yōu)化，以提高分布式存儲編碼同步效率。

3 結束語

本文提出了一種基于擦除碼的高效云存儲數據冗余方案，研究了云存儲服務器以及運算服務器和終端節(jié)點組成的云存儲系統(tǒng)的數據冗余優(yōu)化問題。在服務器節(jié)點對原始數據文件進行擦除碼，將編碼后的數據塊分發(fā)到各個存儲節(jié)點上，在終端節(jié)點取回解碼并恢復成用戶所需要的數據文件。利用Chord環(huán)的分布式存儲邏輯結構，提高終端節(jié)點與云存儲平臺間的上傳與存儲取回效率。該方案保障了用戶云端數據可靠性的同時，降低云端存儲數據的冗余度，增強了存儲節(jié)點容錯能力以及可伸縮性。

［1］Zhang Y，Ren SQ，Chen SB，et al.DifferCloudStor：Differentiated quality of service for cloud storage ［J］.IEEE Transactions on Magnetics，2012，49 （6）：2451－2458.

［2］Spillner J，Müller J，Schill A.Creating optimal cloud storage systems［J］.Future Generation Computer Systems，2013，29（4）：1062－1072.

［3］Baldor SA，Quiroz C，Wood P.Applying a cloud computing approach to storage architectures for spacecraft ［C］／／Aerospace Conference，2013：1－6.

［4］Chen W，Zhao YL，Long SQ，et al.Research on cloud storage security ［J］.Applied Mechanics and Materials，2013，263：3068－3072.

［5］Wang C，Wang Q，Ren K，et al.Toward secure and dependable storage services in cloud computing ［J］.IEEE Transactions on Services Computing，2012，5 （2）：220－232.

［6］AlZain MA，Soh B，Pardede E.A New approach using redundancy technique to improve security in cloud computing ［C］／／International Conference on Cyber Security，Cyber Warfare and Digital Forensic（CyberSec），2012：230－235.

［7］Zhu C，Xin－ran L，Yi－xian Y，et al.A redundant scheduling algorithm based on trust model for internet－based virtual computing environment ［J］.Advances in Information Sciences and Service Sciences，2012，4 （12）：394－404.

［8］Huang Z，Lin Y，Peng Y.Robust redundancy scheme for the repair process：Hierarchical codes in the bandwidth－limited systems［J］.Journal of Grid Computing，2012，10 （3）：579－597.

［9］Wang J，Gong W，Varman P，et al.Reducing storage over－h(huán)ead with small write bottleneck avoiding in cloud RAID system［C］／／ACM／IEEE 13th International Conference on Grid Computing，2012：174－183.

［10］Pamies－Juarez L，García－López P，Sánchez－Artigas M，et al.Towards the design of optimal data redundancy schemes for heterogeneous cloud storage infrastructures ［J］.Computer Networks，2011，55 （5）：1100－1113.

［11］Zakerinasab MR，Wang M.An update model for network coding in cloud storage systems［C］／／50th Annual Allerton Conference on Communication，Control，and Computing（Allerton），2012：1158－1165.

［12］Oliveira PF，Lima L，Vinhoza TTV，et al.Coding for trusted storage in untrusted networks［J］.IEEE Trans Inf Forensic Secur，2012，7 （6）：1890－1899.

［13］Cao N，Yu S，Yang Z，et al.Lt codes－based secure and reliable cloud storage service［C］／／Proceedings IEEE INFOCOM，2012：693－701.

［14］Grange P，Mathiot JF，Mutet B，et al.Aspects of finetuning of the Higgs mass within finite field theories ［J］.Physical Review D，2013，88 （12）：125015.

［15］Respondek JS.Recursive numerical recipes for the high efficient inversion of the confluent Vandermonde matrices ［J］.Applied Mathematics and Computation，2013，225：718－730.

［16］Zhang Y，He H，Teng J.Chord－based semantic service discovery with QoS ［C］／／Fifth International Conference on Measuring Technology and Mechatronics Automation，2013：365－367.

［17］Jie Y.A spiral curve based chord enabling resource sharing for wireless mesh networks：A location awareness and cross－layering approach ［J］.IEICE transactions on Communications，2013，96 （2）：508－521.