基于數(shù)據(jù)局部修復(fù)的云存儲(chǔ)修復(fù)方案

韋靖康

摘? 要：隨著大數(shù)據(jù)、物聯(lián)網(wǎng)的快速發(fā)展，每天都有海量數(shù)據(jù)產(chǎn)生，如何有效存儲(chǔ)海量數(shù)據(jù)并保證數(shù)據(jù)的安全性是亟待解決的一個(gè)問(wèn)題。針對(duì)存儲(chǔ)在云端的數(shù)據(jù)，遭到破壞后如何修復(fù)這一問(wèn)題，本文提出了一種針對(duì)數(shù)據(jù)局部進(jìn)行修復(fù)的云存儲(chǔ)修復(fù)方案，該方案通過(guò)在編碼塊前添加標(biāo)簽支持對(duì)損壞編碼塊的局部修復(fù)，與已有方案相比，在計(jì)算開銷和通信開銷上都進(jìn)行了改善。

關(guān)鍵詞：局部修復(fù)、云存儲(chǔ)、安全性、計(jì)算開銷

中圖分類號(hào)：TP333? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? 文章編號(hào)：1672-4437（2022）02-0055-03

近幾年，云計(jì)算讓很多行業(yè)感受到了便利。隨著云計(jì)算的普及，云存儲(chǔ)作為一種新興的網(wǎng)絡(luò)存儲(chǔ)技術(shù)應(yīng)運(yùn)而生。人們?cè)谙硎茉苾?chǔ)存便捷服務(wù)的同時(shí)，也在關(guān)注數(shù)據(jù)安全問(wèn)題。云上數(shù)據(jù)一旦遭到破壞，需要對(duì)受損的數(shù)據(jù)進(jìn)行快速修復(fù)。現(xiàn)有的方案是對(duì)數(shù)據(jù)的完整性進(jìn)行校驗(yàn)，在用戶側(cè)生成一個(gè)數(shù)據(jù)塊的消息認(rèn)證碼，數(shù)據(jù)塊與生成的驗(yàn)證碼一起上傳到存儲(chǔ)節(jié)點(diǎn)，當(dāng)用戶獲取數(shù)據(jù)塊時(shí)，同時(shí)得到相應(yīng)的消息認(rèn)證碼，可以完成完整性的認(rèn)證[1-6]。現(xiàn)有修復(fù)方案主要是進(jìn)行整體修復(fù)，即在某一部分?jǐn)?shù)據(jù)發(fā)生損壞時(shí)通過(guò)把全部數(shù)據(jù)重新生成的方式進(jìn)行修復(fù)，修復(fù)過(guò)程中帶來(lái)較大的通信開銷和計(jì)算開銷，給系統(tǒng)帶來(lái)額外的負(fù)擔(dān)，特別是在存儲(chǔ)節(jié)點(diǎn)較多的場(chǎng)景下，云存儲(chǔ)系統(tǒng)性能將受到較大的影響，降低系統(tǒng)的可用性[7]。

針對(duì)上述問(wèn)題，本研究提出一種基于數(shù)據(jù)部分修復(fù)的云存儲(chǔ)數(shù)據(jù)修復(fù)方案（Cloud storage repair scheme based on data partial repair，簡(jiǎn)稱DPR），該方案支持僅修復(fù)部分損壞數(shù)據(jù)，無(wú)需對(duì)未損壞數(shù)據(jù)進(jìn)行修復(fù)，可以較好地節(jié)省計(jì)算開銷和通信開銷，既對(duì)存儲(chǔ)在云平臺(tái)上的數(shù)據(jù)進(jìn)行安全保護(hù)，也能迅速修復(fù)破損數(shù)據(jù)，避免云端計(jì)算數(shù)據(jù)冗長(zhǎng)、壓力過(guò)大。

1 DPR數(shù)據(jù)修復(fù)方案設(shè)計(jì)

1.1 數(shù)據(jù)存儲(chǔ)過(guò)程

（1）原始數(shù)據(jù)處理。首先將原始數(shù)據(jù)等分成m（n-m）塊，分塊的大小取決于用戶對(duì)于數(shù)據(jù)部分修復(fù)的需求，當(dāng)用戶需要支持更小數(shù)據(jù)塊修復(fù)時(shí)，可在原始數(shù)據(jù)分塊時(shí)分成更多塊，即m（n-m）可以取更大的值。

（2）選取編碼矩陣。為保證數(shù)據(jù)的私密性及數(shù)據(jù)的可修復(fù)性，在對(duì)原始數(shù)據(jù)分塊后，需要選取編碼矩陣對(duì)原始數(shù)據(jù)塊進(jìn)行編碼，將編碼后的數(shù)據(jù)塊上傳到存儲(chǔ)節(jié)點(diǎn)，選取編碼矩陣時(shí)，需要選取n（n-m）×m（n-m）階矩陣，滿足任取m（n-m）行得到的子矩陣都是滿秩矩陣，且編碼矩陣中任一元素都不為0。

（3）數(shù)據(jù)編碼。將編碼矩陣和原始數(shù)據(jù)塊進(jìn)行矩陣運(yùn)算，得到n（n-m）個(gè)編碼數(shù)據(jù)塊。為便于后期數(shù)據(jù)修復(fù)，需要在每個(gè)編碼后的數(shù)據(jù)塊前加上數(shù)據(jù)標(biāo)簽，標(biāo)簽格式為（i，q），其中i表示存儲(chǔ)節(jié)點(diǎn)編號(hào)，q表示第i個(gè)存儲(chǔ)節(jié)點(diǎn)上第q個(gè)編碼塊。

（4）數(shù)據(jù)上傳。將（3）中的n（n-m）個(gè)編碼數(shù)據(jù)塊分別存放到n個(gè)存儲(chǔ)節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)存放（n-m）個(gè)編碼塊，同時(shí)將編碼矩陣和數(shù)據(jù)標(biāo)簽同步上傳到存儲(chǔ)節(jié)點(diǎn)。

1.2 數(shù)據(jù)讀取過(guò)程

當(dāng)某個(gè)用戶需要讀取數(shù)據(jù)時(shí)，可選取任意m個(gè)存儲(chǔ)節(jié)點(diǎn)，下載其對(duì)應(yīng)的所有編碼塊和編碼矩陣，便可恢復(fù)出原始數(shù)據(jù)，數(shù)據(jù)恢復(fù)的可用性已經(jīng)在文獻(xiàn)[8]中證明。

1.3 數(shù)據(jù)修復(fù)過(guò)程

（1）選取修復(fù)矩陣。為保證修復(fù)后數(shù)據(jù)能夠正常恢復(fù)，選取的修復(fù)矩陣需要滿足以下條件：1）需選?。╪-m）×（n-1）階矩陣，且矩陣中無(wú)0元素存在;2）（n-m）×（n-1）階修復(fù)矩陣中任?。╪-m）列都是線性獨(dú)立的。

（2）數(shù)據(jù)修復(fù)過(guò)程。當(dāng)?shù)趇個(gè)節(jié)點(diǎn)的第q個(gè)數(shù)據(jù)塊發(fā)生損壞時(shí)，修復(fù)服務(wù)器從其他n-1個(gè)節(jié)點(diǎn)中各任取一個(gè)編碼塊及對(duì)應(yīng)的數(shù)據(jù)標(biāo)簽，根據(jù)數(shù)據(jù)標(biāo)簽在編碼矩陣中找到對(duì)應(yīng)的編碼系數(shù)向量，同時(shí)從修復(fù)矩陣中任取一行，將兩者進(jìn)行矩陣修復(fù)運(yùn)算，得到一個(gè)新的編碼塊和與之對(duì)應(yīng)的編碼系數(shù)向量。

（3）數(shù)據(jù)更新過(guò)程。將（2）中得到的編碼塊根據(jù)數(shù)據(jù)標(biāo)簽上傳到對(duì)應(yīng)的存儲(chǔ)節(jié)點(diǎn)上，同時(shí)更新編碼矩陣。

為了更清楚地表示修復(fù)過(guò)程，本研究以n=4，m=2場(chǎng)景為例詳細(xì)介紹修復(fù)過(guò)程，具體如下：

首先，設(shè)第1個(gè)存儲(chǔ)節(jié)點(diǎn)的第1個(gè)編碼塊發(fā)生數(shù)據(jù)損壞，修復(fù)服務(wù)器從另外3個(gè)存儲(chǔ)節(jié)點(diǎn)中各任取1個(gè)編碼塊及對(duì)應(yīng)的數(shù)據(jù)標(biāo)簽，如從另外3個(gè)為損壞的存儲(chǔ)節(jié)點(diǎn)中取的編碼塊分別是第1個(gè)、2個(gè)、1個(gè)，則對(duì)應(yīng)的數(shù)據(jù)標(biāo)簽分別為：（2，1）、（3，2）、（4，1），同時(shí)根據(jù)數(shù)據(jù)標(biāo)簽從編碼矩陣中找到對(duì)應(yīng)的編碼系數(shù)向量。

其次，從修復(fù)矩陣中任取一行，與（1）中選取參與修復(fù)的編碼塊、編碼塊對(duì)應(yīng)的編碼系數(shù)向量做矩陣運(yùn)算，得到一個(gè)新的編碼塊和對(duì)應(yīng)的編碼系數(shù)向量。

第三，更新受損存儲(chǔ)節(jié)點(diǎn)上對(duì)應(yīng)的編碼塊和編碼矩陣，完成受損節(jié)點(diǎn)的數(shù)據(jù)修復(fù)。

2 數(shù)據(jù)修復(fù)方案性能分析

2.1可用性分析

（1）理論證明

DPR修復(fù)方案可用性理論證明如下：

定理：根據(jù)DPR修復(fù)方案修復(fù)后生成的編碼塊對(duì)應(yīng)的編碼系數(shù)向量和未受損編碼塊所對(duì)應(yīng)的編碼系數(shù)向量是線性獨(dú)立的。

證明：根據(jù)線性代數(shù)相關(guān)知識(shí)可得出如下結(jié)論：

對(duì)于向量組A=（1，2，…，n），向量組中各向量線性獨(dú)立的充要條件是當(dāng)且僅當(dāng)i全為0時(shí)，

由文獻(xiàn)[2，9]中給出的理論證明過(guò)程可知，若修復(fù)時(shí)修復(fù)矩陣中所有行向量都參與修復(fù)過(guò)程，即（n-m）×（n-1）階修復(fù)矩陣中（n-m）個(gè)行向量和（n-1）個(gè)修復(fù)數(shù)據(jù)塊進(jìn)行矩陣運(yùn)算，得到個(gè)新（n-m）的編碼塊，則n-m個(gè)新的編碼塊和未受損存儲(chǔ)節(jié)點(diǎn)上的編碼塊是線性獨(dú)立的，即（1）式只有0解。

其中i表示存儲(chǔ)節(jié)點(diǎn)編號(hào)，j表示某節(jié)點(diǎn)上編碼塊的編號(hào)， 表示第i個(gè)節(jié)點(diǎn)上第j個(gè)編碼塊。

若（1）成立，則（2）也成立，即：

其中 表示新修復(fù)的編碼塊。

由公式（2）可知，新修復(fù)的編碼塊對(duì)應(yīng)的編碼系數(shù)向量和未受損編碼塊所對(duì)應(yīng)的編碼系數(shù)向量是線性獨(dú)立的，定理得證，即DPR修復(fù)滿足可用性。

（2）模擬驗(yàn)證

為驗(yàn)證DPR修復(fù)方案可用性，本研究使用Matlab 7.0在（4，2）存儲(chǔ)場(chǎng)景下模擬DPR修復(fù)方案的修復(fù)過(guò)程。模擬器的配置為：3.30 GHz CPU ，3.40G RAM，通過(guò)100次的仿真過(guò)程，均反饋修復(fù)后編碼塊對(duì)應(yīng)的編碼系數(shù)向量和（n-m）個(gè)未受損節(jié)點(diǎn)編碼塊所對(duì)應(yīng)的編碼系數(shù)向量組成的矩陣是滿秩的，即是相互獨(dú)立的。

2.2 修復(fù)計(jì)算開銷分析

本研究以文獻(xiàn)[10]中的修復(fù)方案為比較對(duì)象。由于在矩陣運(yùn)算中，乘除運(yùn)算占主要地位，所以，本研究主要比較兩種方案中乘除運(yùn)算的次數(shù)，具體如下：

其中k表示數(shù)據(jù)塊在有限域中包含的字符個(gè)數(shù)。

為更直觀反映兩種修復(fù)方案計(jì)算開銷的優(yōu)劣勢(shì)，本研究在n=4，m=2，k=1024場(chǎng)景下，給出了兩種方案修復(fù)計(jì)算開銷的具體值，其中NCCloud-PRM方案修復(fù)計(jì)算開銷45162，而DPR方案僅需22581，DPR方案修復(fù)計(jì)算開銷方面優(yōu)勢(shì)明顯。

2.3 通信開銷分析

各修復(fù)方案中，通信開銷主要來(lái)自選取修復(fù)數(shù)據(jù)塊和更新修復(fù)后的數(shù)據(jù)塊兩部分。DPR修復(fù)方案和NCCloud-PRM修復(fù)方案選取修復(fù)數(shù)據(jù)過(guò)程相似，兩者在此過(guò)程中的修復(fù)開銷相同。DPR修復(fù)方案采用的是局部數(shù)據(jù)修復(fù)方式，只需更新單個(gè)編碼塊，相較于NCCloud-PRM修復(fù)方案可以節(jié)?。╪-m-1）個(gè)編碼塊的通信開銷。

2.4存儲(chǔ)開銷分析

在NCCloud-PRM修復(fù)方案中，為使用戶能夠準(zhǔn)確恢復(fù)出原始數(shù)據(jù)，需要在每個(gè)存儲(chǔ)節(jié)點(diǎn)保存全部的編碼矩陣，而DPR修復(fù)方案引入數(shù)據(jù)標(biāo)簽后，無(wú)需保存全部編碼矩陣，僅根據(jù)數(shù)據(jù)標(biāo)簽和本節(jié)點(diǎn)存儲(chǔ)編碼塊對(duì)應(yīng)的編碼系數(shù)便可恢復(fù)，因此，DPR修復(fù)方案可以節(jié)省一定的存儲(chǔ)開銷。

3 結(jié)論

本研究針對(duì)當(dāng)下云存儲(chǔ)中面臨的數(shù)據(jù)損壞后的修復(fù)問(wèn)題，提出一種新的方案，該方案支持局部數(shù)據(jù)修復(fù)，通過(guò)在編碼塊前添加標(biāo)簽支持對(duì)損壞編碼塊的局部修復(fù)，與已有方案相比，可以節(jié)省計(jì)算開銷和通信開銷。

參考文獻(xiàn)：

[1]Shah M A，Swaminathan R，Baker M.Privacy-preserving audit and extraction of digital contents ，HP Labs Technical Report No.HPL-2008-32[R].2008.

[2]Bowers K D，Juels A，Oprea A.Proofs of retrievability：Theory and implementation [C] // Proceedings of the 2009 ACM Workshopon Cloud Computing Security.ACM，2009：43-54.

[3]Bowers K D，Juels A，Oprea A.HALL：A high-avilability?and inergrity layer for cloud storage[C]//Proceedings?of the 16th ACM Conference on Computer and Communications?Security.ACM， 2009： 187-198.

[4]Wang C，Wang Q，RenK，etal.Toward secure and dependable?storage service in cloud computing [J].IEEE Transactions on Service Computing，2012， 5（2）：220-232.

[5]Rodrigues R，Liskov B.High availability in DHTs：Erasure coding vs.replication[M]// Peer-to- Peer?Systems IV.Springer Berlin Heidelberg，2005： 226-239.

[6]王偉平，張俊峰，王建新.基于零空間的網(wǎng)絡(luò)編碼云存儲(chǔ)完整性校驗(yàn)方案[J].清華大學(xué)學(xué)報(bào)，2016（56）：83- 86，96.

[7]閔少穎.云數(shù)據(jù)精確修復(fù)方法研究[D].武漢：武漢科技大學(xué)，2018.

[8]Hu Y，Chen H C H，Lee P P C，et al.NCCloud：Applying Network Coding for the Storage Repair in a Cloud-of-Clouds[C]//USENIX FAST，2012：265–272.

[9]Subashini S，Kavitha V.A survey on security issues in service delivery models of cloud computing[J].Journal of Network&Computer Applications，2011，34（1）：1-11.

[10]張俊峰.基于網(wǎng)絡(luò)編碼云存儲(chǔ)方案研究[D].長(zhǎng)沙：中南大學(xué)，2014.