一種基于增量存儲的多副本文件版本控制方法

王棟　邊根慶　李睿堯

摘 要：針對云計算多副本存儲的情況與傳統的全量存儲對云存儲空間消耗巨大的問題，尤其改動頻繁的大容量文件對存儲空間的消耗更大。因此文中對基于增量存儲的多副本文件版本控制方法進行研究，支持多副本文件版本控制管理。數據所有者加密數據，創建多個副本并將其存儲在云端，當更新數據時，數據文件不會被直接更新，而是將更新保存為增量。通過實驗仿真，對比了文件版本傳遞算法在不同配置運行環境下的CSP計算開銷，驗證了本方法的高效性和可用性。

關鍵詞：云存儲；多副本；文件版本控制；CSP

中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2017）09-00-03

0 引 言

在云存儲[1，2]中，數據所有者對CSP端文件的每一次動態更新操作都是DO與CSP之間的多次交互，而在云存儲平臺中每次發生版本更新更迭，系統都會將歷史版本保存下來以響應用戶的版本恢復請求。在多副本的情況下，傳統的全量存儲方式對云存儲平臺存儲空間消耗巨大，尤其對改動頻繁的大容量文件會消耗更大的存儲空間，因此文件的全量存儲方式對于多副本文件是不可取的[3，4]。

為了解決上述問題，緩解云存儲平臺的存儲空間，本文采用增量存儲方式來存儲多副本文件版本的信息[5，6]。增量存儲的基本思想是僅存儲最新版本與基本版本之間的差異信息（以下稱之為增量），由基本版本和增量構成版本信息。目前有正增量和逆增量兩種存儲模型[7，8]。

1 增量存儲模型

（1）正增量存儲模型

在正增量存儲模型中，Vi+1=Vi+Δi │條件，i≥0，當i= 0時為原始版本。Δi │條件是在Vi基礎上通過操作條件修改得到差異信息，即只存儲原始版本的完整數據，而后繼版本只保存其與前一版本的增量[9]，如圖1所示。

（2）逆增量存儲模型

在逆增量存儲模型中，只存儲最新版本的完整數據，其余歷史版本則只存儲與后繼版本之間的增量信息，即Vi存儲Vi+1和Vi之間的增量Δi │條件，最后一個版本存儲其完整內容。

2 文件版本控制

數據所有者將文件劃分為多個文件塊，并為文件塊產生多個副本和數據標簽，且每個副本可唯一標識。文件塊的多個副本由同態概率加密方法生成，文件塊的數據標簽由BLS簽名生成，將文件塊副本和文件塊的數據標簽發送到云端。這些文件塊的加密副本表示未加密文件塊的基本版本，對未加密文件塊當前版本的每一次修改都將產生新的版本，新版本的文件塊不直接存儲在云端，只存儲增量，增量為未加密文件塊的新版本與基本版本之間的差異。當需要文件塊的特定版本時，數據所有者請求云端將增量塊與文件塊的基本版本合并，從而得到文件塊所需版本。

文件版本表由五部分組成，分別為塊號（BN）、增量塊號（DBN）、文件版本（FV）、塊版本（BV）、塊操作（BO）。

（1）BN表示文件塊的索引，描述了文件塊在數據文件中的物理位置。

（2）DBN是增量塊的索引，如果增量不存在，則該值存儲為“-”。

（3）FV表示整個文件的版本。

（4）BV表示文件塊的版本。

（5）BO指出了對文件塊執行操作的類型。

FV的最大值表示文件的最新版本，并且對于特定的BN，其BV的最大值表示該文件塊的最新版本。如果在文件版本表中沒有找到文件塊號的條目，則意味著沒有對文件塊的基本版本進行更新操作，且文件的基本版本和最新版本的文件塊相同。當對塊號為b、文件版本為v和文件塊版本為y的文件塊進行修改時，數據所有者可以選擇將整個文件的版本更改為v + 1或保持原版本不變。對于這兩種情況，數據所有者在文件版本表中創建一個新條目。在第一種情況下，表條目將是，并且對于第二種情況，表條目將是，見表1所列。

數據所有者使用文件版本表來跟蹤記錄文件塊的版本更新情況，用來驗證CSP存儲的所有文件及其版本的完整性和一致性。當數據所有者對文件塊執行更新操作時，將會生成新版本的文件塊，數據更新操作包括文件塊插入、刪除或修改，當且僅當數據更新操作是“修改”時才會生成增量塊，一旦更新操作完成，數據所有者就會更新文件版本表，文件版本表僅在數據所有者端維護，有助于數據所有者隱藏CSP執行更新操作的詳細信息。

3 算法設計

3.1 文件版本動態更新

本文的文件版本動態更新操作由更新請求算法PrepareUpdate（）和更新執行算法ExecUpdate（）來執行，對應的請求操作包括數據塊修改、數據塊插入和數據塊刪除。文件版本修改操作如圖2所示。

3.1.1 更新請求算法

更新請求算法：PrepareUpdate（）→Update。本算法在數據所有者端運行，對遠程CSP存儲的外包文件副本執行更新操作，算法的輸出是更新請求。數據所有者將更新請求以的形式發送到云端，其中Idf是文件標識符，BlockOp對應塊操作，j，bi'和φ' 分別表示文件塊的索引、更新的文件塊和更新的標簽，BlockOp可以是數據插入、修改或刪除操作。

（1）數據插入：對文件F的任一版本“v”的插入操作意味著在文件中插入新的文件塊。數據所有者決定新文件塊所屬的文件版本，可以是當前文件版本v或者是下一個文件版本v+1。如果新文件塊添加到文件版本“v+1”，則“v+1”就是文件的新版本，在文件版本表中創建一個新記錄為。由于沒有增量塊且插入了新的文件塊，所以DBN值為“-”，BV值為0。

（2）數據修改：對最新版本的文件塊進行修改。數據所有者識別需要修改的文件塊塊號，并在文件版本表中搜索塊號，如果沒有找到特定塊號記錄，那么從云中下載來自基本版本的文件塊。如果找到了目標記錄，那么識別出文件塊的最新版本并從云端下載，文件塊的最新版本就是解密下載的基本版本的文件塊與增量合并得到的文件塊版本。對明文進行修改操作以獲得更新后的明文，數據所有者將計算更新的明文和基本版本明文之間的差異作為新的增量，然后將增量隨機化，并將其發送到云端。隨機化的目的在于不向云端暴露增量值。令M={bi}，其中1≤i≤s是更新操作之前的文件塊集合，M'={bi'}，1≤i≤s是更新操作之后的文件塊，增量?M值為{bi'-bi}，1≤i≤s。使用由PRF密鑰Keydata生成的隨機數來對增量進行隨機化，因此，?M={bi'-bi+N-xi}，1≤i≤s。最后將M值發送到云端。

（3）數據刪除：對文件“v”的任一版本的刪除操作意味著從文件中刪除幾個文件塊。數據所有者可以從當前版本v刪除文件塊，或者從下一版本v+1中刪除文件塊。且數據所有者在文件版本表中創建一條記錄。刪除操作的結果只是在文件版本表中添加一條記錄，而CSP不知道關于刪除操作的任何內容。

3.1.2 更新執行算法

更新執行算法：ExecUpdate （F，φ，Update）→（F'，φ'）。本算法在CSP端運行，輸入參數為文件副本F、標簽φ和更新請求（由數據所有者發送）。輸出為新的文件副本F'以及更新的標簽φ'。在每次塊操作之后，數據所有者運行挑戰協議以確保云端正確執行了更新操作，更新請求中的操作可以是插入新的文件塊或修改文件塊，數據所有者不向云端發送任何刪除請求，因此不會刪除任何數據塊。

3.2 文件版本請求與文件版本傳遞

數據所有者創建文件版本表跟蹤數據更新操作，此表中的記錄數值取決于對文件塊進行動態操作的數量。文件更新作為增量存儲在云端，為了獲得文件的特定版本，數據所有者將帶有兩個參數的FileVersionRequest發送到云端。在接收到FileVersionRequest之后，云端執行FileVersionDeliver算法。對于DBN值為“–”的文件版本請求，CSP直接將塊號為BN的文件塊傳遞給數據所有者，不涉及任何CSP計算開銷。對于具有有效DBN值的FileVersionRequest而言，云加密增量塊號為DBN的文件塊，執行同態加法運算。

（1）FileVersionRequest：數據所有者通過檢查文件版本表來識別所需版本的文件塊，并使用塊編號以的形式向CSP發送請求。此外，需要DBN才能訪問所需的文件版本，如果文件版本表中沒有DBN條目，則請求將是。

（2）FileVersionDeliver：對于“FileVersionRequest”中DBN值為“-”的所有文件塊號，將該文件的基本版本傳遞給數據所有者，如果具有有效的DBN值，則CSP利用公鑰對增量進行加密，并對基本版本的文件塊進行同態加法運算，最后得到數據所有者請求版本的文件塊。令?M={bi'-bi+N-xi}，1≤i≤s是與數據所有者請求的相應文件版本的文件塊相關聯的增量，加密的增量E（?M）={（1+（bi'-bi+N-xi）N（r）N}，其中，r∈ZN*是隨機數。最后，云端對文件基本版本上所請求的文件塊執行同態加法操作。同態加法之后得到的文件塊表示數據所有者所請求版本的加密文件塊，將加密的文件塊發送給數據所有者，數據所有者對文件塊進行解密，從而獲得其請求的版本。

4 算法性能分析

4.1 實驗環境

本文主要驗證文件版本傳遞算法的CSP計算開銷，對1MB文件在本地計算機、不同配置的虛擬機環境下進行實驗。本地計算機實驗環境為Intel（R） Core（TM） i7-6700HQ 2.60GHz處理器、16 GB RAM；虛擬機實驗環境1具有單核處理器，2 GB內存，200 GB硬盤空間；虛擬機實驗環境2具有雙核虛擬處理器，8 GB內存，500 GB硬盤空間。

4.2 文件版本傳遞算法CSP計算開銷比較

圖3中FileVersionRequest的數量用文件塊的百分比表示。例如，1 MB文件具有8 192個大小為128 B的文件塊。當數據所有者發送81個FileVersionRequest時，CSP加密81個增量塊（8 192個文件塊的1%），并執行81次同態加法運算。因此任何數目的FileVersionRequest將導致CSP對這些文件塊執行操作，并且FileVersionRequest可以用文件塊的數目來表示。MRFVCM（Multiple Replica File Version Control Method，MRFVCM）在數據所有者端不涉及執行FileVersionDeliver算法的任何計算，數據所有者的唯一成本是維護文件版本表。圖3顯示了在本地計算機和不同配置的虛擬機環境上運行FileVersionDeliver算法的CSP計算時間的比較。FileVersionDeliver算法的CSP計算時間定義為CSP將所請求版本的文件塊傳遞給數據所有者所花費的時間。FileVersionDeliver算法在本地計算機上執行得更好，因為它的配置最高。

5 結 語

本文支持多副本文件版本管理，首先構建了文件版本表，該表由數據所有者運行維護；其次，詳細闡述了用戶申請特定版本到CSP執行文件版本傳遞算法的詳細過程；最后通過實驗仿真，對比了文件版本傳遞算法在不同配置運行環境下的CSP計算開銷，驗證了本算法的高效性和可用性。

參考文獻

[1] Wu Xiao-yong，Li Hui-na. Remote backup system based on file type [J]. NetWork & Computer Security，2012（ 3） ： 40-42.

[2] He Qian，Zhuo Bi-hua. A remote file synchronization method[J]. Journal of Computer Applications，2012，32（ 2） ： 566-568.

[3] 陳康， 鄭緯民.云計算：系統實例與研究現狀[J].軟件學報，2009，20（5）：1337-1348.

[4] 薛一波，易成岐.云存儲（1）[J].中興通訊技術， 2012，18（1）：57-60.

[5] 高林， 宋相倩，王潔萍.云計算及其關鍵技術研究[J].微型機與應用，2011，30（10）：5-7.

[6] FENG DengGuo， ZHANG Min， ZHANG Yan，等.云計算安全研究[J].軟件學報，2011， 22（1）：71-83.

[7] 周可，王樺，李春花.云存儲技術及其應用[J]. 中興通訊技術，2010，16（4）：24-27.

[8] 張蓮，李京，劉煒清.云同步系統中采用增量存儲的版本控制技術研究[J].小型微型計算機系統，2015，36（3）：427-432.