基于多級(jí)網(wǎng)絡(luò)編碼的多副本云數(shù)據(jù)存儲(chǔ)

徐光偉 史春紅 馮向陽(yáng) 羅 辛 石秀金 韓松樺 李 瑋

(東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 201620)(gwxu@dhu.edu.cn)

互聯(lián)網(wǎng)發(fā)展帶來(lái)的數(shù)據(jù)爆炸性增長(zhǎng)，對(duì)數(shù)據(jù)存儲(chǔ)提出了巨大挑戰(zhàn).企業(yè)和個(gè)人采用云存儲(chǔ)提供的在線外包存儲(chǔ)以獲取價(jià)格低廉的海量數(shù)據(jù)存儲(chǔ)空間.這種外包存儲(chǔ)的最基本要求是要保證數(shù)據(jù)的可用性.目前常用的方法是通過(guò)數(shù)據(jù)備份來(lái)保證數(shù)據(jù)可用性，如多副本[1](multiple-replica)存儲(chǔ)，通過(guò)對(duì)原始數(shù)據(jù)進(jìn)行備份，一旦數(shù)據(jù)發(fā)生損壞或丟失時(shí)，可利用備份數(shù)據(jù)進(jìn)行恢復(fù).

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

為降低數(shù)據(jù)存儲(chǔ)和損壞數(shù)據(jù)恢復(fù)時(shí)的開(kāi)銷，本文提出一種基于多級(jí)網(wǎng)絡(luò)編碼的多副本數(shù)據(jù)(hier-archical network coding multiple replica, HC-MR)生成方法.采用多級(jí)網(wǎng)絡(luò)編碼生成多副本數(shù)據(jù)并進(jìn)行分布式存儲(chǔ)和損壞數(shù)據(jù)的恢復(fù)，本文主要貢獻(xiàn)有3個(gè)方面：

1) 分析生成副本數(shù)據(jù)之間的關(guān)聯(lián)性，建立生成副本數(shù)據(jù)塊的多級(jí)編碼矩陣.在生成副本數(shù)據(jù)塊時(shí)，通過(guò)保證編碼矩陣的滿秩性來(lái)避免所生成的各編碼數(shù)據(jù)塊之間存在線性相關(guān)性.

2) 基于多級(jí)網(wǎng)絡(luò)編碼生成級(jí)聯(lián)的多副本數(shù)據(jù).在多級(jí)編碼矩陣基礎(chǔ)上，使得計(jì)算獲得的多副本數(shù)據(jù)中的編碼數(shù)據(jù)塊具有唯一性.此外，采用數(shù)據(jù)副本前后級(jí)聯(lián)方式計(jì)算多副本數(shù)據(jù)，使得各副本數(shù)據(jù)塊之間存在特定關(guān)聯(lián)性的編碼關(guān)系.

3) 損壞數(shù)據(jù)恢復(fù)時(shí)，利用編碼矩陣和具有級(jí)聯(lián)關(guān)系的多副本數(shù)據(jù)對(duì)損壞數(shù)據(jù)進(jìn)行安全恢復(fù).對(duì)副本中的損壞數(shù)據(jù)，選擇最佳的恢復(fù)副本，利用編碼矩陣和具有級(jí)聯(lián)關(guān)系的多副本數(shù)據(jù)進(jìn)行編碼計(jì)算恢復(fù)損壞數(shù)據(jù)，因無(wú)需遠(yuǎn)程下載原始數(shù)據(jù)就可恢復(fù)損壞數(shù)據(jù)，降低了計(jì)算和通信開(kāi)銷.

1 相關(guān)工作

為了保護(hù)數(shù)據(jù)的可用性，數(shù)據(jù)冗余技術(shù)是解決這個(gè)問(wèn)題的關(guān)鍵技術(shù).

1) 多副本

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

但多副本技術(shù)存儲(chǔ)效率和數(shù)據(jù)容錯(cuò)性低且需要消耗大量的磁盤存儲(chǔ)空間.

2) 糾刪碼

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

基于糾刪碼和網(wǎng)絡(luò)編碼的方法，主要解決了數(shù)據(jù)容錯(cuò)和損壞數(shù)據(jù)恢復(fù)方面的一些問(wèn)題.如何在不增加數(shù)據(jù)存儲(chǔ)冗余的條件下，盡可能地降低開(kāi)銷并保證數(shù)據(jù)的可用性和安全性，還需結(jié)合副本生成和損壞數(shù)據(jù)恢復(fù)來(lái)研究其編碼技術(shù).

Fig. 1 Model ofmulti-replica data storage圖1 多副本數(shù)據(jù)存儲(chǔ)的模型

2 云多副本數(shù)據(jù)存儲(chǔ)模型與問(wèn)題

2.1 存儲(chǔ)模型與安全威脅

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

然而，外包存儲(chǔ)并非絕對(duì)安全，因?yàn)樵品?wù)商是半不可信的[28]，即它可以“誠(chéng)實(shí)的”按照協(xié)議來(lái)存儲(chǔ)數(shù)據(jù)，也可能為了獲得更高的存儲(chǔ)效益而不按約定存夠副本數(shù).因此，云服務(wù)商會(huì)對(duì)多副本數(shù)據(jù)進(jìn)行偽造攻擊和隱私攻擊.

1) 偽造攻擊.云服務(wù)商為獲取盡可能大的數(shù)據(jù)存儲(chǔ)收益，會(huì)試圖保存盡量少的數(shù)據(jù)副本.當(dāng)數(shù)據(jù)使用者發(fā)起隨機(jī)副本數(shù)據(jù)請(qǐng)求時(shí)，云服務(wù)商通過(guò)臨時(shí)復(fù)制副本數(shù)據(jù)來(lái)欺騙數(shù)據(jù)使用者.

2) 隱私攻擊.為實(shí)現(xiàn)偽造攻擊或隱藏?fù)p壞數(shù)據(jù)，云服務(wù)商會(huì)在其參與數(shù)據(jù)恢復(fù)計(jì)算的過(guò)程中，收集和記錄敏感的編碼信息，然后通過(guò)分析，推斷出副本數(shù)據(jù)之間的關(guān)聯(lián)以實(shí)現(xiàn)偽造攻擊.

2.2 問(wèn)題提出

正如在相關(guān)工作和安全威脅中所分析的，半不可信的外包數(shù)據(jù)存儲(chǔ)面臨如下的一些問(wèn)題.

1) 數(shù)據(jù)可用性的要求增加了數(shù)據(jù)存儲(chǔ)和損壞數(shù)據(jù)恢復(fù)的開(kāi)銷.采用糾刪碼技術(shù)對(duì)存儲(chǔ)數(shù)據(jù)的容錯(cuò)性和損壞數(shù)據(jù)恢復(fù)后的數(shù)據(jù)可用性提供保障，當(dāng)損壞數(shù)據(jù)恢復(fù)時(shí)需下載并解碼原文件，會(huì)增加數(shù)據(jù)所有者的計(jì)算和通信開(kāi)銷方面的負(fù)擔(dān).

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

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

多副本數(shù)據(jù)存儲(chǔ)與恢復(fù)算法的設(shè)計(jì)目標(biāo)如下：

1) 降低多副本數(shù)據(jù)存儲(chǔ)和損壞數(shù)據(jù)恢復(fù)時(shí)的開(kāi)銷.

2) 數(shù)據(jù)存儲(chǔ)和損壞數(shù)據(jù)恢復(fù)過(guò)程中抵御安全攻擊的威脅.

3 基于多級(jí)網(wǎng)絡(luò)編碼的多副本存儲(chǔ)和損壞數(shù)據(jù)恢復(fù)

本文在糾刪碼技術(shù)基礎(chǔ)上，結(jié)合多級(jí)網(wǎng)絡(luò)編碼設(shè)計(jì)了基于多級(jí)網(wǎng)絡(luò)編碼的多副本數(shù)據(jù)，用于副本數(shù)據(jù)存儲(chǔ)和損壞數(shù)據(jù)的恢復(fù).

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

3.1 多副本數(shù)據(jù)的生成

3.1.1 數(shù)據(jù)加密及分割

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

3.1.2 利用多級(jí)編碼矩陣建立數(shù)據(jù)塊的編碼

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

本文在繼承糾刪碼的線性編碼的優(yōu)點(diǎn)基礎(chǔ)上，采用多級(jí)網(wǎng)絡(luò)編碼對(duì)矩陣B的后m行進(jìn)行改進(jìn)，提出一種多級(jí)編碼矩陣.

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

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

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

(1)

式(1)的具體構(gòu)造方式如下：當(dāng)k=1時(shí)，矩陣L1中的各元素為

(2)

當(dāng)k>1時(shí)，其余s-1個(gè)n階方陣Lk的各元素為

(3)

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

(4)

(5)

(6)

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

3.1.3 副本數(shù)據(jù)的多級(jí)編碼

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

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

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

(7)

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

3) 利用Lk計(jì)算基于多級(jí)網(wǎng)絡(luò)編碼的多副本文件.對(duì)于副本Fk，當(dāng)副本編號(hào)k=1時(shí)，可由副本F1的數(shù)據(jù)塊向量Z1=(b1,b2,…,bn)與編碼矩陣L1計(jì)算來(lái)生成數(shù)據(jù)塊編碼，即

(8)

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

(9)

Fig. 2 Multi-replicas are generated based on hierarchical network coding圖2 基于多級(jí)網(wǎng)絡(luò)編碼生成多副本文件

3.1.4 數(shù)據(jù)存儲(chǔ)

數(shù)據(jù)所有者計(jì)算出所有副本文件后，將其上傳到云服務(wù)商的數(shù)據(jù)中心(多個(gè)存儲(chǔ)節(jié)點(diǎn))進(jìn)行分布式存儲(chǔ)，編碼矩陣由數(shù)據(jù)所有者秘密保存.

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

基于多級(jí)網(wǎng)絡(luò)編碼的多副本文件生成算法(HC-MR)如算法1所示：

算法1.HC-MR算法.

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

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

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

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

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

④ (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 損壞數(shù)據(jù)的恢復(fù)

損壞數(shù)據(jù)的恢復(fù)需要利用其編碼系數(shù)與特定的副本數(shù)據(jù)進(jìn)行編碼計(jì)算來(lái)恢復(fù).此外，為避免編碼信息泄露而導(dǎo)致副本文件被偽造，需對(duì)編碼信息進(jìn)行隱藏.具體過(guò)程如下:

1) 損壞數(shù)據(jù)塊的編碼信息計(jì)算

Fig. 3 Recovery of corrupted data圖3 損壞數(shù)據(jù)的恢復(fù)

首先，檢測(cè)損壞數(shù)據(jù)的副本編號(hào).通過(guò)數(shù)據(jù)完整性驗(yàn)證[30]發(fā)現(xiàn)數(shù)據(jù)bki損壞后，獲得其所在的副本編號(hào)k.然后，選擇恢復(fù)損壞數(shù)據(jù)的最佳副本文件.通過(guò)選擇最佳副本，以最小的計(jì)算開(kāi)銷恢復(fù)損壞的副本.

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

2) 數(shù)據(jù)恢復(fù)編碼信息的加密

3) 損壞數(shù)據(jù)的恢復(fù)

云服務(wù)商收到損壞數(shù)據(jù)恢復(fù)請(qǐng)求Q后，讀取本地副本文件與其計(jì)算即可恢復(fù)損壞的數(shù)據(jù)：

最后，利用文獻(xiàn)[31]的方法對(duì)云服務(wù)商延遲或不恢復(fù)損壞數(shù)據(jù)進(jìn)行檢測(cè)，此處不再贅述.

基于多級(jí)網(wǎng)絡(luò)編碼的損壞數(shù)據(jù)恢復(fù)算法(DR)描述算法2所示：

算法2.DR算法.

輸入：矩陣生成密鑰t、編碼信息密鑰μ、損壞數(shù)據(jù)的副本編號(hào)k、損壞數(shù)據(jù)塊的序號(hào)i；

①sk=μ←genkey(μ);

4 算法安全性及計(jì)算復(fù)雜性分析

4.1 安全性分析

1) 正確性分析

2) 抵御編碼信息的泄露

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

3) 抵御偽造攻擊

HC-MR可抵御云服務(wù)商的偽造攻擊，即保存較少數(shù)量的副本，當(dāng)數(shù)據(jù)所有者發(fā)起隨機(jī)副本數(shù)據(jù)請(qǐng)求時(shí)，臨時(shí)復(fù)制副本來(lái)響應(yīng).

4.2 計(jì)算復(fù)雜性分析

本節(jié)主要分析基于多級(jí)網(wǎng)絡(luò)編碼的多副本存儲(chǔ)和損壞數(shù)據(jù)恢復(fù)的時(shí)間開(kāi)銷.

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

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

4.3 容錯(cuò)能力及數(shù)據(jù)可用性分析

1) 容錯(cuò)能力

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

2) 數(shù)據(jù)可用性

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

(10)

基于網(wǎng)絡(luò)編碼方法的數(shù)據(jù)可用性為

(11)

參考容錯(cuò)能力的分析可知，當(dāng)γ=0時(shí)，基于網(wǎng)絡(luò)編碼方法中編碼塊間不具有線性關(guān)系，此時(shí)3種存儲(chǔ)策略的容錯(cuò)能力相等，但隨著γ的增大，基于網(wǎng)絡(luò)編碼方法的數(shù)據(jù)可用性逐漸降低.

5 實(shí)驗(yàn)及性能分析

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

5.1 副本生成的計(jì)算和存儲(chǔ)開(kāi)銷

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

Fig. 4 Computation time for replicas generation圖4 副本生成的計(jì)算時(shí)間

選取文件大小為1 MB，10 MB，20 MB，30 MB，40 MB，50 MB，3種方案存儲(chǔ)3個(gè)副本的存儲(chǔ)開(kāi)銷如圖5所示，可以看出他們的存儲(chǔ)開(kāi)銷是相同的.這是因?yàn)?種方案在編碼計(jì)算前，為避免編碼計(jì)算后的數(shù)據(jù)塊增大而出現(xiàn)溢出，副本分塊時(shí)按照文獻(xiàn)[33]的方法選擇數(shù)據(jù)塊進(jìn)行編碼.

Fig. 5 Replicas generated storage overhead圖5 副本生成的存儲(chǔ)開(kāi)銷

5.2 損壞數(shù)據(jù)恢復(fù)的計(jì)算和通信開(kāi)銷

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

Fig. 6 Corrupted data recovery time圖6 損壞數(shù)據(jù)恢復(fù)的時(shí)間

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

Fig. 7 Communication overhead when recovering data圖7 恢復(fù)數(shù)據(jù)時(shí)通信開(kāi)銷

5.3 數(shù)據(jù)可用性和容錯(cuò)能力

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

Fig. 8 Data availability圖8 數(shù)據(jù)可用性

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

Fig. 9 Data fault tolerance圖9 數(shù)據(jù)的容錯(cuò)能力

通過(guò)上述實(shí)驗(yàn)，可以看出，HC-MR的副本生成的計(jì)算和存儲(chǔ)開(kāi)銷與G-CRS(不采用GPU)和NCScale相近；損壞數(shù)據(jù)恢復(fù)時(shí)的計(jì)算開(kāi)銷比G-CRS和NCScale略大，而通信開(kāi)銷最??；當(dāng)副本數(shù)較少時(shí)，HC-MR與G-CRS的數(shù)據(jù)可用性較高；當(dāng)副本數(shù)相同時(shí)，HC-MR和G-CRS的容錯(cuò)能力較高.因此，HC-MR在提高數(shù)據(jù)可用性的同時(shí)，也減少了損壞數(shù)據(jù)恢復(fù)時(shí)的通信開(kāi)銷.

6 總 結(jié)

云存儲(chǔ)數(shù)據(jù)備份應(yīng)以盡量少的存儲(chǔ)空間來(lái)滿足最大的數(shù)據(jù)可用性，本文提出了一種基于多級(jí)網(wǎng)絡(luò)編碼的多副本數(shù)據(jù)備份方案.利用多級(jí)編碼矩陣生成副本數(shù)據(jù)塊，然后基于多級(jí)編碼生成級(jí)聯(lián)的多副本數(shù)據(jù)，最后利用數(shù)據(jù)所有者提供的損壞數(shù)據(jù)的編碼向量，與存儲(chǔ)節(jié)點(diǎn)上保存的副本數(shù)據(jù)進(jìn)行計(jì)算從而恢復(fù)損壞數(shù)據(jù).與現(xiàn)有方案相比，提高了數(shù)據(jù)的可用性，并減少了損壞數(shù)據(jù)恢復(fù)時(shí)的通信開(kāi)銷.未來(lái)，將進(jìn)一步優(yōu)化數(shù)據(jù)的編碼和解碼，以及編解碼計(jì)算的效率.