基于多級網絡編碼的多副本云數據存儲

徐光偉 史春紅 馮向陽 羅 辛 石秀金 韓松樺 李 瑋

(東華大學計算機科學與技術學院 上海 201620)(gwxu@dhu.edu.cn)

互聯網發展帶來的數據爆炸性增長，對數據存儲提出了巨大挑戰.企業和個人采用云存儲提供的在線外包存儲以獲取價格低廉的海量數據存儲空間.這種外包存儲的最基本要求是要保證數據的可用性.目前常用的方法是通過數據備份來保證數據可用性，如多副本[1](multiple-replica)存儲，通過對原始數據進行備份，一旦數據發生損壞或丟失時，可利用備份數據進行恢復.

為提高云存儲的利用率和數據可用性，常采用擦除碼(erasure codes)技術[2]，其中糾刪碼reed-solomon是一種應用廣泛的擦除碼[3].利用糾刪碼計算編碼塊進行冗余存儲，可在相同的存儲空間下獲得高的數據可用性.與多副本復制相比，糾刪碼在相同的存儲開銷下提高了數據存儲的可靠性[4].目前有許多改進的糾刪碼方法，如糾雙錯的極大距離可分碼(maximum distance separable, MDS)[5]、EVENODD(efficient encoding on double disk failures)[6]、X-code[7]、RDP(row-diagonal parity) 碼[8]、自由碼(liberation code)[9]等.然而，基于糾刪碼的方法盡管節省了數據存儲空間，但損壞數據恢復時，常因文件解碼需要下載與原文件大小相同的編碼塊，造成大量的通信和計算開銷.基于網絡編碼(network coding)技術[10]應用到數據備份時，通過對數據塊之間的線性編碼來生成數據塊.損壞數據恢復時，無需解碼原文件，只需下載一定量的數據塊即可通過線性計算恢復原數據，從而降低了計算和通信開銷.但這種方法在數據譯碼時，一旦數據塊的編碼系數存在線性相關性會導致譯碼失敗，只能重新下載數據塊，反而增加了計算和通信開銷.

為降低數據存儲和損壞數據恢復時的開銷，本文提出一種基于多級網絡編碼的多副本數據(hier-archical network coding multiple replica, HC-MR)生成方法.采用多級網絡編碼生成多副本數據并進行分布式存儲和損壞數據的恢復，本文主要貢獻有3個方面：

1) 分析生成副本數據之間的關聯性，建立生成副本數據塊的多級編碼矩陣.在生成副本數據塊時，通過保證編碼矩陣的滿秩性來避免所生成的各編碼數據塊之間存在線性相關性.

2) 基于多級網絡編碼生成級聯的多副本數據.在多級編碼矩陣基礎上，使得計算獲得的多副本數據中的編碼數據塊具有唯一性.此外，采用數據副本前后級聯方式計算多副本數據，使得各副本數據塊之間存在特定關聯性的編碼關系.

3) 損壞數據恢復時，利用編碼矩陣和具有級聯關系的多副本數據對損壞數據進行安全恢復.對副本中的損壞數據，選擇最佳的恢復副本，利用編碼矩陣和具有級聯關系的多副本數據進行編碼計算恢復損壞數據，因無需遠程下載原始數據就可恢復損壞數據，降低了計算和通信開銷.

1 相關工作

為了保護數據的可用性，數據冗余技術是解決這個問題的關鍵技術.

1) 多副本

在分布式存儲系統[11-12]中，多副本技術由于其簡單、讀寫效率高而被廣泛采用.為避免云服務商偽造副本數據，Li等人[13]和Barsoum等人[14]分別提出了利用副本及數據塊編號生成隨機密鑰流加入到數據塊計算副本文件的方法.Hou等人[15]根據副本編號對每個數據塊進行加密生成副本文件，使得只有擁有密鑰的數據所有者才能得到副本數據.隨后，Yi等人[16]利用全同態加密計算副本數據，降低計算開銷.

但多副本技術存儲效率和數據容錯性低且需要消耗大量的磁盤存儲空間.

2) 糾刪碼

糾刪碼是對副本數據進行編碼后，再存儲冗余數據塊，以達到容錯目的.當數據損壞時，通過讀取剩余的完整數據塊，使用譯碼算法對損壞數據進行恢復.Blaum等人[6]在Raid存儲體系結構中提出一種有效的雙磁盤容錯方案EVENODD.隨后，又在EVENODD基礎上提出可糾多列錯的MDS陣列碼G-EVENODD[17].隨后，Huang等人[18]在EVENODD碼基礎上，提出能糾正任意3個節點故障的STAR碼.然而，基于糾刪碼的方法，需要先恢復出原文件后才能進行數據更新或損壞數據恢復，耗費了大量的通信和計算開銷.為提高數據恢復的有效性，Dimakis等人[19-20]提出一種基于網絡編碼的再生碼(regenerating coding)用于恢復數據，它利用網絡編碼對糾刪碼進行改進來降低數據的恢復帶寬.Acedanski等人[21]通過比較無編碼的隨機存儲、傳統刪除碼和隨機線性網絡編碼的有效性，建立譯碼概率和存儲、帶寬之間的函數關系以減少存儲開銷.隨后，Zakerinasab等人[22-23]提出一種減小更新帶寬的網絡編碼方法，僅需在舊碼上加個簡單的碼差函數即可實現更新，極大地降低了更新帶寬.王龍江等人[24]也提出一種基于網絡編碼的云存儲的差分數據更新方案，結合游程碼和霍夫曼碼等壓縮碼對差分編碼塊進行壓縮以減少更新帶寬.為適應存儲和冗余需求的變化，Zhang等人[25]提出一種基于網絡編碼的數據存儲模型，使各存儲節點互相發送線性編碼數據塊來降低數據更新時的通信開銷.為進一步降低損壞數據恢復時的通信開銷，Zhou等人[26]提出了局部擴散的延遲編碼算法和基于區域的重構算法，降低了部分損壞數據塊恢復時的通信開銷.為提高編碼效率，Liu等人[27]提出一種基于圖形處理單元(GPU)的糾刪碼實現方案，將位矩陣存儲在GPU中并實現并行譯碼來提高編碼效率.

基于糾刪碼和網絡編碼的方法，主要解決了數據容錯和損壞數據恢復方面的一些問題.如何在不增加數據存儲冗余的條件下，盡可能地降低開銷并保證數據的可用性和安全性，還需結合副本生成和損壞數據恢復來研究其編碼技術.

Fig. 1 Model ofmulti-replica data storage圖1 多副本數據存儲的模型

2 云多副本數據存儲模型與問題

2.1 存儲模型與安全威脅

云存儲數據的可用性常采用多副本技術，由數據所有者在本地生成多副本數據后存儲到云數據中心.典型的云多副本數據存儲模型主要由數據所有者(data owner)、云服務商(cloud server)和數據使用者(data user)組成[14,16]，如圖1所示.其中數據所有者生成多個副本并遠程存儲到云服務商的存儲空間.云服務商為外包數據提供數據存儲服務并保證其可用性.獲得訪問權限的數據使用者，通過云服務商的管理訪問這些外包存儲數據.

然而，外包存儲并非絕對安全，因為云服務商是半不可信的[28]，即它可以“誠實的”按照協議來存儲數據，也可能為了獲得更高的存儲效益而不按約定存夠副本數.因此，云服務商會對多副本數據進行偽造攻擊和隱私攻擊.

1) 偽造攻擊.云服務商為獲取盡可能大的數據存儲收益，會試圖保存盡量少的數據副本.當數據使用者發起隨機副本數據請求時，云服務商通過臨時復制副本數據來欺騙數據使用者.

2) 隱私攻擊.為實現偽造攻擊或隱藏損壞數據，云服務商會在其參與數據恢復計算的過程中，收集和記錄敏感的編碼信息，然后通過分析，推斷出副本數據之間的關聯以實現偽造攻擊.

2.2 問題提出

正如在相關工作和安全威脅中所分析的，半不可信的外包數據存儲面臨如下的一些問題.

1) 數據可用性的要求增加了數據存儲和損壞數據恢復的開銷.采用糾刪碼技術對存儲數據的容錯性和損壞數據恢復后的數據可用性提供保障，當損壞數據恢復時需下載并解碼原文件，會增加數據所有者的計算和通信開銷方面的負擔.

2) 抵御云服務商偽造數據所有者的副本數據以保障數據的可用性.數據所有者存儲多副本數據的目的是為了保障數據可用性，但會因云服務商的偽造副本而降低了數據的可用性.

3) 抵御損壞數據恢復時的數據編碼信息泄露.損壞數據恢復時，數據所有者需向云服務商提供與損壞數據相關的編碼信息.惡意云服務商會通過收集這些編碼信息，分析出各副本之間編碼關系，從而偽造副本數據.

多副本數據存儲與恢復算法的設計目標如下：

1) 降低多副本數據存儲和損壞數據恢復時的開銷.

2) 數據存儲和損壞數據恢復過程中抵御安全攻擊的威脅.

3 基于多級網絡編碼的多副本存儲和損壞數據恢復

本文在糾刪碼技術基礎上，結合多級網絡編碼設計了基于多級網絡編碼的多副本數據，用于副本數據存儲和損壞數據的恢復.

多級網絡編碼(hierarchical network coding)由Nguyen等人[29]提出，其原理是，若一個數據流被劃分為多個數據塊，每個數據塊屬于A，B，C分類中的一類.其中，A類數據塊最重要，B類次之，C類最不重要，記為A>B>C.假設該數據流共有6個數據塊，分別記為a1,a2,b1,b2,c1,c2，其中a1,a2屬于A類，b1,b2屬于B類，c1,c2屬于C類，則多級網絡編碼的構造方案為

3.1 多副本數據的生成

3.1.1 數據加密及分割

數據所有者對原文件進行加密并分割成數據塊.加密使用密鑰采用對稱加密方式.設原文件為F*，加密后的文件為F.然后，對加密文件F進行分割得到n個數據塊b1,b2,…,bn.

3.1.2 利用多級編碼矩陣建立數據塊的編碼

糾刪碼(n,m)在計算m個冗余碼時，將n個原數據塊按列排成向量，構成一個(n+m)×n的分布矩陣B.對于矩陣B，它的任意n個行向量都是相互獨立的，即這n個行向量組成n×n矩陣是可逆的.矩陣B的前n行是單位矩陣，后m行基于范德蒙矩陣構造.

本文在繼承糾刪碼的線性編碼的優點基礎上，采用多級網絡編碼對矩陣B的后m行進行改進，提出一種多級編碼矩陣.

定義1.矩陣的線性無關性.矩陣中任一向量，都不能由矩陣中其他向量進行線性表示.矩陣的行初等變換不改變列向量之間的線性關系.

定義2.多級編碼矩陣(hierarchical coding matric).對于一個a×b的矩陣L，從第一行開始，以b為單位組成一個小方陣，使得每一個方陣的行向量中不為0的數依次遞增，且每個方陣都由前一個方陣通過矩陣初等變換得到，并且所有小方陣都具有滿秩性，其中a為大于0的正整數，b為大于3的正整數且為奇數.

假設有n個數據塊，需計算m-n個冗余碼，則構建一個m×n的編碼矩陣.讓正整數k≤n-1，其中n≥3，且m=s×n.為降低編碼矩陣的計算量，讓矩陣前n行即第1個矩陣對角線上的值全部為1.多級編碼矩陣L由s個n階方陣Lk(k∈[1,s])組成，如式(1)所示：

(1)

式(1)的具體構造方式如下：當k=1時，矩陣L1中的各元素為

(2)

當k>1時，其余s-1個n階方陣Lk的各元素為

(3)

其中，i∈[1,n]，j∈[1,n]，k∈[2,s].當s取最大值n-1時，可得式(1)中的

(4)

(5)

(6)

其中ai由數據所有者利用矩陣密鑰t和隨機函數生成.通過多級編碼矩陣計算的編碼被稱為多級編碼(hierarchical coding, HC).

3.1.3 副本數據的多級編碼

利用所建立的多級編碼矩陣L，通過多級編碼生成副本數據.假設文件F需要生成s個副本，每個副本包含n個數據塊，且n為不小于3的非偶數.編碼后得到s×n個數據塊，其中每個副本的多級編碼矩陣為n行n列的方陣.具體編碼過程為：

1) 數據所有者從有限域中選取矩陣密鑰t，通過隨機函數得到n個元素ai，其中每個元素ai互不相等且不為0.然后構造成一個(n×s)×n的多級編碼矩陣L.

2) 為計算s個副本，應用式(1)～(4)分解多級編碼矩陣L，用lki表示矩陣Lk中的每個行向量，可得s個副本對應的n行n列的多級編碼矩陣Lk為

(7)

多級編碼矩陣具有以下特性：①極大距離可分碼性，即多級編碼矩陣的線性無關性，使得任選n個編碼數據塊都可有效參與編碼數據塊的解碼計算；②獨特性，即各副本的多級編碼矩陣都是滿秩矩陣，每個副本中編碼數據塊彼此都不相同；③關聯性，即每個編碼數據塊都由其他編碼數據塊通過編碼計算得到，也就與其他編碼數據塊之間存在一定的計算關系.

3) 利用Lk計算基于多級網絡編碼的多副本文件.對于副本Fk，當副本編號k=1時，可由副本F1的數據塊向量Z1=(b1,b2,…,bn)與編碼矩陣L1計算來生成數據塊編碼，即

(8)

以此類推，可由副本文件Fk-1與Lk計算得到副本Fk的數據塊編碼為

(9)

Fig. 2 Multi-replicas are generated based on hierarchical network coding圖2 基于多級網絡編碼生成多副本文件

3.1.4 數據存儲

數據所有者計算出所有副本文件后，將其上傳到云服務商的數據中心(多個存儲節點)進行分布式存儲，編碼矩陣由數據所有者秘密保存.

參考目前普遍采用的3副本存儲模式[14]，讓s=3，F=(b1,b2,b3,b4,b5)，利用編碼矩陣計算15個數據塊b11,b12,b13,b14,b15,b21,b22,b23,b24,b25,b31,b32,b33,b34,b35.可得3個副本文件F1=(b11,b12,…,b15)，F2=(b21,b22,…,b25)，F3=(b31,b32,…,b35).

基于多級網絡編碼的多副本文件生成算法(HC-MR)如算法1所示：

算法1.HC-MR算法.

輸入：原文件F，原文件加密密鑰x，矩陣生成密鑰t，副本數s；

輸出：s個副本文件Fk(k=1,2,…,s).

① 初始化密鑰參數(x，t)；

② (x,t)←Genkey(·);*生成密鑰*

③F←encrypt(F*,x);*對文件加密*

④ (b1,b2,…,bn)←devide(F);

⑤ fork=1;k≤s;k++ do

⑥Lk←createMatric(t);

⑦Fk←Genreplica(Fk-1,Lk);

⑧ end for

⑨ returnFk(k=1,2,…,s).

3.2 損壞數據的恢復

損壞數據的恢復需要利用其編碼系數與特定的副本數據進行編碼計算來恢復.此外，為避免編碼信息泄露而導致副本文件被偽造，需對編碼信息進行隱藏.具體過程如下:

1) 損壞數據塊的編碼信息計算

Fig. 3 Recovery of corrupted data圖3 損壞數據的恢復

首先，檢測損壞數據的副本編號.通過數據完整性驗證[30]發現數據bki損壞后，獲得其所在的副本編號k.然后，選擇恢復損壞數據的最佳副本文件.通過選擇最佳副本，以最小的計算開銷恢復損壞的副本.

假設副本Fk中的數據塊bki損壞.若k≠1時，應用式(9)可知Fk=LkFk-1.因此，選擇Fk-1為最佳副本，并計算第k個副本的多級編碼矩陣Lk，再根據副本Fk中的損壞數據bki選擇Lk中第i個行向量lki.

2) 數據恢復編碼信息的加密

3) 損壞數據的恢復

云服務商收到損壞數據恢復請求Q后，讀取本地副本文件與其計算即可恢復損壞的數據：

最后，利用文獻[31]的方法對云服務商延遲或不恢復損壞數據進行檢測，此處不再贅述.

基于多級網絡編碼的損壞數據恢復算法(DR)描述算法2所示：

算法2.DR算法.

輸入：矩陣生成密鑰t、編碼信息密鑰μ、損壞數據的副本編號k、損壞數據塊的序號i；

①sk=μ←genkey(μ);

4 算法安全性及計算復雜性分析

4.1 安全性分析

1) 正確性分析

2) 抵御編碼信息的泄露

HC-MR可抵御云服務商收集數據恢復編碼信息Q以獲得數據塊的編碼信息lki，并還原出Lk.

3) 抵御偽造攻擊

HC-MR可抵御云服務商的偽造攻擊，即保存較少數量的副本，當數據所有者發起隨機副本數據請求時，臨時復制副本來響應.

4.2 計算復雜性分析

本節主要分析基于多級網絡編碼的多副本存儲和損壞數據恢復的時間開銷.

設生成多級編碼矩陣的計算開銷為THCM，需要計算s個副本.采用糾刪碼時，只需要確定編碼塊數，就可確定編碼矩陣的大小，其編碼矩陣的計算開銷為THCM.此外，利用糾刪碼計算副本的編碼數據塊時，直接利用編碼矩陣，選取隨機數對數據塊進行線性計算即可得到編碼塊，因此，計算3個副本的時間復雜度為TMul=O(n3).而HC-MR中多級編碼矩陣數量與副本數成正比，多級編碼矩陣的計算開銷為s×THCM.此外，HC-MR在數據編碼計算前需要生成副本的編碼矩陣，即輸入密鑰，生成多級編碼矩陣，再基于多級網絡編碼進行多副本數據的計算，時間復雜度為THC-MR=O(n3).

若n個數據塊中num個發生損壞.利用糾刪碼進行損壞數據恢復時，需要先從云存儲空間中下載n個編碼數據塊，通過解碼得到原始數據塊，再利用矩陣生成算法計算編碼塊的編碼矩陣，最后對損壞的數據塊再重新進行編碼計算，其時間復雜度為TRS=num×O(n3).采用網絡編碼方法，為避免恢復用的編碼數據塊與其他數據塊間存在線性相關性，需要進行多次的多個完整編碼數據塊的線性計算，其時間復雜度為TNC=num×O(n3).而HC-MR方法，首先判斷每個損壞數據塊所在的副本位置，其時間復雜度為O(n).然后計算副本的多級編碼矩陣Lk，其時間復雜度為O(n).最后再利用編碼信息與相應副本計算進行損壞數據恢復.因此，其時間復雜度為THC-MR=num×O(n3)，3種方法的時間復雜度相同.

4.3 容錯能力及數據可用性分析

1) 容錯能力

容錯能力指所存儲的編碼塊可恢復出原始文件的最大容忍出錯的塊數[32].設e為原始數據塊數，p為數據冗余度.基于糾刪碼方法和本文的HC-MR，共存儲編碼塊為p×e.由于只需e個編碼塊就可恢復原文件，所以其容錯能力是(p-1)×e.基于網絡編碼的方法，因其編碼塊間可能存在線性相關性,設γ為相關系數，則其容錯能力為(p-1)e(1-γ).其數據容錯能力隨著γ的增大而降低.當γ=0時，3種方法的容錯能力相等.

2) 數據可用性

數據可用性指存儲數據可正常使用的概率，用β表示.在數據冗余度p下，系統中有p×e個數據塊，其中冗余數據塊為(p-1)×e.根據文獻[32]，基于糾刪碼方法和本文HC-MR的數據可用性為

(10)

基于網絡編碼方法的數據可用性為

(11)

參考容錯能力的分析可知，當γ=0時，基于網絡編碼方法中編碼塊間不具有線性關系，此時3種存儲策略的容錯能力相等，但隨著γ的增大，基于網絡編碼方法的數據可用性逐漸降低.

5 實驗及性能分析

為了測試算法的性能，使用一臺Intel Core i7處理器1.99 GHz，8 GB內存的筆記本電腦作為數據所有者.租用阿里云服務器的8核CPU，16 GB內存，40 GB存儲系統來模擬云服務商.實驗中各算法采用Java編寫，實驗代碼在Reed-Solomon-error-correction-1.2基礎上修改.數據編碼在有限域GF(216)中進行，將文件數據拆成字長16位后進行編碼計算.本文方案HC-MR與文獻[25]的NCScale和文獻[27]的G-CRS方案進行對比，并分別從副本生成的存儲、計算和損壞數據恢復的計算、通信開銷等方面進行性能分析.

5.1 副本生成的計算和存儲開銷

選取文件大小為1 MB，10 MB，20 MB，30 MB，40 MB，50 MB，60 MB，70 MB，80 MB，90 MB，100 MB，3種方案生成副本的計算開銷如圖4所示.可以看出HC-MR與G-CRS，NCScale的計算開銷相近，且3種方案生成副本的計算開銷隨著副本數的增加也相應的增加.其中HC-MR略微偏高，其原因是，在進行副本生成時，需先生成多級編碼矩陣，再進行副本計算，而NCScale和G-CRS方案則無需計算每個副本的編碼矩陣，因此，它們的計算開銷略小.此外，考慮到G-CRS采用了GPU計算，在有限域GF(24)中取線程數為128時，也測試了其開銷.可以看出，G-CRS(GPU)相對于HC-MR顯著減少了計算時間.這是因為G-CRS(GPU)將矩陣存儲在GPU的存儲器中實現同一編碼矩陣的并行編譯碼.

Fig. 4 Computation time for replicas generation圖4 副本生成的計算時間

選取文件大小為1 MB，10 MB，20 MB，30 MB，40 MB，50 MB，3種方案存儲3個副本的存儲開銷如圖5所示，可以看出他們的存儲開銷是相同的.這是因為3種方案在編碼計算前，為避免編碼計算后的數據塊增大而出現溢出，副本分塊時按照文獻[33]的方法選擇數據塊進行編碼.

Fig. 5 Replicas generated storage overhead圖5 副本生成的存儲開銷

5.2 損壞數據恢復的計算和通信開銷

損壞數據恢復時，3種方案的計算開銷如圖6所示，其中圖6(a)和圖6(b)分別為數據所有者和云服務商的計算時間.由于G-CRS和NCScale只涉及數據所有者的計算，所以圖6(b)的值都為0.綜合來看，HC-MR的計算開銷比G-CRS和NCScale略大.這是因為G-CRS只對編碼數據塊解碼后，計算損壞數據的編碼.NCSale需下載盡可能多的編碼塊通過線性計算來恢復，而無需解碼計算.HC-MR需要提供與損壞數據相關的數據編碼向量，以及與損壞數據相關的副本，然后進行編碼計算進行恢復.此外，HC-MR在矩陣求逆前，還要生成多級編碼矩陣，所以計算開銷略大.

Fig. 6 Corrupted data recovery time圖6 損壞數據恢復的時間

取文件大小為10 MB，30 MB，50 MB，90 MB，100 MB，讓副本數為3，這3種方案的損壞數據恢復的通信開銷如圖7所示，其中G-CRS的通信開銷最大，NCScale次之，HC-MR最小.其原因是，G-CRS需要先恢復出完整的副本文件后，才能恢復損壞的數據塊，而無論有多少損壞數據，都需要下載完整的副本.NCScale若下載的數據塊具有線性關系而不可用，又因編碼塊間線性關系的不確定性，而需下載盡可能多的編碼塊.HC-MR的編碼矩陣具有滿秩性和編碼塊間的線性無關性，數據恢復時只傳輸編碼向量即可.

Fig. 7 Communication overhead when recovering data圖7 恢復數據時通信開銷

5.3 數據可用性和容錯能力

選取副本數為2，3，4，5，6，7，8，HC-MR，G-CRS，NCScale(γ分別取0%，30%，100%)比較如圖8所示.當副本數較少即數據冗余度較小時，HC-MR，G-CRS，NCScale(γ=0%)三種算法的曲線重合且數據可用性較高，NCScale(γ=30%)次之，NCScale(γ=100%)最低.隨著數據冗余度增加，3種方案的數據可用性都增加.當副本數為7時，3種方案的數據可用性趨于一致.其原因是，數據冗余度較小時，HC-MR，G-CRS，NCScale(γ=0%)允許任意數據塊發生損壞并恢復，而NCScale(γ=100%)因冗余的編碼塊間具有線性相關性，只能恢復特定的數據塊，即每個副本中相同編號的數據塊，導致可用性最低.

Fig. 8 Data availability圖8 數據可用性

選取原文件大小為1 MB，3種方案的數據容錯能力如圖9所示.在相同副本數下，HC-MR，G-CRS，NCScale(γ=0%)三種算法的曲線重合且有較高的容錯能力，NCScale(γ=30%)次之，NCScale(γ=100%)最低.其原因是副本數增加時，HC-MR，G-CRS，NCScale(γ=0%)可有效恢復任意損壞編碼塊，而NCScale(γ=30%)只能恢復部分不存在線性相關的損壞數據.NCScale(γ=100%)因編碼塊間的線性相關性，無法恢復損壞數據.

Fig. 9 Data fault tolerance圖9 數據的容錯能力

通過上述實驗，可以看出，HC-MR的副本生成的計算和存儲開銷與G-CRS(不采用GPU)和NCScale相近；損壞數據恢復時的計算開銷比G-CRS和NCScale略大，而通信開銷最?。划敻北緮递^少時，HC-MR與G-CRS的數據可用性較高；當副本數相同時，HC-MR和G-CRS的容錯能力較高.因此，HC-MR在提高數據可用性的同時，也減少了損壞數據恢復時的通信開銷.

6 總 結

云存儲數據備份應以盡量少的存儲空間來滿足最大的數據可用性，本文提出了一種基于多級網絡編碼的多副本數據備份方案.利用多級編碼矩陣生成副本數據塊，然后基于多級編碼生成級聯的多副本數據，最后利用數據所有者提供的損壞數據的編碼向量，與存儲節點上保存的副本數據進行計算從而恢復損壞數據.與現有方案相比，提高了數據的可用性，并減少了損壞數據恢復時的通信開銷.未來，將進一步優化數據的編碼和解碼，以及編解碼計算的效率.