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

引 言

在云存儲(chǔ) [1,2] 中，數(shù)據(jù)所有者對(duì) CSP 端文件的每一次動(dòng)態(tài)更新操作都是DO 與CSP 之間的多次交互，而在云存儲(chǔ)平臺(tái)中每次發(fā)生版本更新更迭，系統(tǒng)都會(huì)將歷史版本保存下來以響應(yīng)用戶的版本恢復(fù)請(qǐng)求。在多副本的情況下，傳統(tǒng)的全量存儲(chǔ)方式對(duì)云存儲(chǔ)平臺(tái)存儲(chǔ)空間消耗巨大，尤其對(duì)改動(dòng)頻繁的大容量文件會(huì)消耗更大的存儲(chǔ)空間，因此文件的全量存儲(chǔ)方式對(duì)于多副本文件是不可取的[3,4]。

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

1 增量存儲(chǔ)模型

(1) 正增量存儲(chǔ)模型

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

(2) 逆增量存儲(chǔ)模型

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

2 文件版本控制

數(shù)據(jù)所有者將文件劃分為多個(gè)文件塊，并為文件塊產(chǎn)生多個(gè)副本和數(shù)據(jù)標(biāo)簽，且每個(gè)副本可唯一標(biāo)識(shí)。文件塊的多個(gè)副本由同態(tài)概率加密方法生成，文件塊的數(shù)據(jù)標(biāo)簽由BLS 簽名生成，將文件塊副本和文件塊的數(shù)據(jù)標(biāo)簽發(fā)送到云端。這些文件塊的加密副本表示未加密文件塊的基本版本，對(duì)未加密文件塊當(dāng)前版本的每一次修改都將產(chǎn)生新的版本，新版本的文件塊不直接存儲(chǔ)在云端，只存儲(chǔ)增量，增量為未加密文件塊的新版本與基本版本之間的差異。當(dāng)需要文件塊的特定版本時(shí)， 數(shù)據(jù)所有者請(qǐng)求云端將增量塊與文件塊的基本版本合并，從而得到文件塊所需版本。

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

(1) BN表示文件塊的索引，描述了文件塊在數(shù)據(jù)文件中的物理位置。

(2) DBN是增量塊的索引，如果增量不存在，則該值存儲(chǔ) 為 - 。

(3) FV表示整個(gè)文件的版本。

(4) BV表示文件塊的版本。

(5) BO指出了對(duì)文件塊執(zhí)行操作的類型。

FV 的最大值表示文件的最新版本，并且對(duì)于特定的BN， 其BV 的最大值表示該文件塊的最新版本。如果在文件版本表中沒有找到文件塊號(hào)的條目，則意味著沒有對(duì)文件塊的基本版本進(jìn)行更新操作，且文件的基本版本和最新版本的文件塊相同。當(dāng)對(duì)塊號(hào)為b、文件版本為 v 和文件塊版本為 y 的文件塊進(jìn)行修改時(shí)，數(shù)據(jù)所有者可以選擇將整個(gè)文件的版本更改為 v + 1 或保持原版本不變。對(duì)于這兩種情況，數(shù)據(jù)所有者在文件版本表中創(chuàng)建一個(gè)新條目。在第一種情況下，表?xiàng)l目將是 <b，-，v+1，0，Modify>，并且對(duì)于第二種情況，表?xiàng)l目將是 <b，-，v， y+1，Modify>，見表 1 所列。

數(shù)據(jù)所有者使用文件版本表來跟蹤記錄文件塊的版本更新情況，用來驗(yàn)證 CSP 存儲(chǔ)的所有文件及其版本的完整性和一致性。當(dāng)數(shù)據(jù)所有者對(duì)文件塊執(zhí)行更新操作時(shí)，將會(huì)生成新版本的文件塊，數(shù)據(jù)更新操作包括文件塊插入、刪除或修改， 當(dāng)且僅當(dāng)數(shù)據(jù)更新操作是 修改 時(shí)才會(huì)生成增量塊，一旦更新操作完成，數(shù)據(jù)所有者就會(huì)更新文件版本表，文件版本表僅在數(shù)據(jù)所有者端維護(hù)，有助于數(shù)據(jù)所有者隱藏 CSP 執(zhí)行更新操作的詳細(xì)信息。

3 算法設(shè)計(jì)

3.1 文件版本動(dòng)態(tài)更新

本文的文件版本動(dòng)態(tài)更新操作由更新 請(qǐng)求算法PrepareUpdate（） 和更新執(zhí)行算法 ExecUpdate（） 來執(zhí)行， 對(duì)應(yīng)的請(qǐng)求操作包括數(shù)據(jù)塊修改、數(shù)據(jù)塊插入和數(shù)據(jù)塊刪除。文件版本修改操作如圖 2 所示。

3.1.1 更新請(qǐng)求算法

更新請(qǐng)求算法：PrepareUpdate（）→ Update。本算法在數(shù)據(jù)所有者端運(yùn)行，對(duì)遠(yuǎn)程 CSP 存儲(chǔ)的外包文件副本執(zhí)行更新操作，算法的輸出是更新請(qǐng)求。數(shù)據(jù)所有者將更新請(qǐng)求以<Idf，BlockOp，j，bi '，φ' > 的形式發(fā)送到云端，其中Idf 是文件標(biāo)識(shí)符，BlockOp 對(duì)應(yīng)塊操作，j，bi ' 和φ' 分別表示文件塊的索引、更新的文件塊和更新的標(biāo)簽，BlockOp 可以是數(shù)據(jù)插入、修改或刪除操作。

(1) 數(shù)據(jù)插入 ：對(duì)文件 F的任一版本 v的插入操作意味著在文件中插入新的文件塊。數(shù)據(jù)所有者決定新文件塊所屬的文件版本，可以是當(dāng)前文件版本v或者是下一個(gè)文件版本v+1。如果新文件塊添加到文件版本 v+1，則 v+1就是文件的新版本，在文件版本表中創(chuàng)建一個(gè)新記錄為<BN，-， v或v+1，0，Insert>。由于沒有增量塊且插入了新的文件塊， 所以 DBN值為 - ，BV值為 0。

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

(3) 數(shù)據(jù)刪除：對(duì)文件 v的任一版本的刪除操作意味著從文件中刪除幾個(gè)文件塊。數(shù)據(jù)所有者可以從當(dāng)前版本 v刪除文件塊，或者從下一版本v+1中刪除文件塊。且數(shù)據(jù)所有者在文件版本表中創(chuàng)建一條記錄 <BN，-，v或v+1，0， Delete>。刪除操作的結(jié)果只是在文件版本表中添加一條記錄， 而CSP不知道關(guān)于刪除操作的任何內(nèi)容。

3.1.2 更新執(zhí)行算法

更新執(zhí)行算法：ExecUpdate（F，φ，Update）→（F'，φ'）。本算法在CSP 端運(yùn)行，輸入?yún)?shù)為文件副本 F、標(biāo)簽φ和更新請(qǐng)求（由數(shù)據(jù)所有者發(fā)送）。輸出為新的文件副本 F' 以及更新的標(biāo)簽 φ'。在每次塊操作之后，數(shù)據(jù)所有者運(yùn)行挑戰(zhàn)協(xié)議以確保云端正確執(zhí)行了更新操作，更新請(qǐng)求中的操作可以是插入新的文件塊或修改文件塊，數(shù)據(jù)所有者不向云端發(fā)送任何刪除請(qǐng)求，因此不會(huì)刪除任何數(shù)據(jù)塊。

3.2 文件版本請(qǐng)求與文件版本傳遞

數(shù)據(jù)所有者創(chuàng)建文件版本表跟蹤數(shù)據(jù)更新操作，此表中的記錄數(shù)值取決于對(duì)文件塊進(jìn)行動(dòng)態(tài)操作的數(shù)量。文件更新作為增量存儲(chǔ)在云端，為了獲得文件的特定版本，數(shù)據(jù)所有者將帶有兩個(gè)參數(shù)<BN，DBN>的FileVersionRequest 發(fā)送到云端。在接收到FileVersionRequest之后，云端執(zhí)行FileVersionDeliver算法。對(duì)于DBN值為–的文件版本請(qǐng)求，CSP直接將塊號(hào)為BN 的文件塊傳遞給數(shù)據(jù)所有者，不涉及任何CSP計(jì)算開銷。對(duì)于具有有效DBN值的FileVersionRequest而言，云加密增量塊號(hào)為DBN的文件塊， 執(zhí)行同態(tài)加法運(yùn)算。

（1）FileVersionRequest ：數(shù)據(jù)所有者通過檢查文件版本表來識(shí)別所需版本的文件塊，并使用塊編號(hào)以<BN，DBN> 的形式向CSP 發(fā)送請(qǐng)求。此外，需要 DBN 才能訪問所需的文件版本，如果文件版本表中沒有 DBN 條目，則請(qǐng)求將是

<BN，->。

（2）FileVersionDeliver：對(duì)于FileVersionRequest中DBN值為-的所有文件塊號(hào)，將該文件的基本版本傳遞給數(shù)據(jù)所有者，如果具有有效的DBN值，則CSP 利用公鑰對(duì)增量進(jìn)行加密，并對(duì)基本版本的文件塊進(jìn)行同態(tài)加法運(yùn)算， 最后得到數(shù)據(jù)所有者請(qǐng)求版本的文件塊。令?M={bi'-bi+N- xi}，1≤i≤s是與數(shù)據(jù)所有者請(qǐng)求的相應(yīng)文件版本的文件塊相關(guān)聯(lián)的增量，加密的增量 E（? M）={（1+（b'-b+N-x）N（r）N}，其中，r ∈ ZN* 是隨機(jī)數(shù)。最后，云端對(duì)文件基本版本上所請(qǐng) 求的文件塊執(zhí)行同態(tài)加法操作。同態(tài)加法之后得到的文件塊 表示數(shù)據(jù)所有者所請(qǐng)求版本的加密文件塊，將加密的文件塊 發(fā)送給數(shù)據(jù)所有者，數(shù)據(jù)所有者對(duì)文件塊進(jìn)行解密，從而獲 得其請(qǐng)求的版本。

4 算法性能分析

4.1 實(shí)驗(yàn)環(huán)境

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

4.2 文件版本傳遞算法 CSP 計(jì)算開銷比較

圖 3 中 FileVersionRequest 的 數(shù) 量 用文件 塊 的百分比 表示。例如，1 MB 文件具有 8 192 個(gè)大小為 128 B 的文件 塊。當(dāng)數(shù)據(jù)所有者發(fā)送 81 個(gè) FileVersionRequest 時(shí)，CSP 加 密 81 個(gè)增量塊（8 192 個(gè)文件塊的 1％），并執(zhí)行 81 次同態(tài)加 法運(yùn)算。因此任何數(shù)目的 FileVersionRequest 將導(dǎo)致 CSP 對(duì) 這些文件塊執(zhí)行操作，并且 FileVersionRequest 可以用文件 塊 的 數(shù)目來 表 示。MRFVCM（Multiple Replica File Version Control Method，MRFVCM）在數(shù) 據(jù)所有者端不涉及執(zhí)行 FileVersionDeliver 算法的任何計(jì)算，數(shù)據(jù)所有者的唯一成 本是維護(hù)文件版本表。圖 3 顯示了在本地計(jì)算機(jī)和不同配置 的虛擬機(jī)環(huán)境上運(yùn)行 FileVersionDeliver 算法的 CSP 計(jì)算時(shí) 間的比較。FileVersionDeliver 算法的 CSP 計(jì)算時(shí)間定義為 CSP 將所請(qǐng)求版本的文件塊傳遞給數(shù)據(jù)所有者所花費(fèi)的時(shí)間。 FileVersionDeliver 算法在本地計(jì)算機(jī)上執(zhí)行得更好，因?yàn)樗?的配置最高。

5 結(jié) 語

本文支持多副本文件版本管理，首先構(gòu)建了文件版本表， 該表由數(shù)據(jù)所有者運(yùn)行維護(hù)；其次，詳細(xì)闡述了用戶申請(qǐng)?zhí)囟?版本到 CSP 執(zhí)行文件版本傳遞算法的詳細(xì)過程 ；最后通過實(shí) 驗(yàn)仿真，對(duì)比了文件版本傳遞算法在不同配置運(yùn)行環(huán)境下的 CSP 計(jì)算開銷，驗(yàn)證了本算法的高效性和可用性。