一種改進的細粒度云存儲安全去重方案

呂世濤，柳毅

（廣東工業大學，廣州510006）

0 引言

隨著電子設備和5G技術的不斷普及，數據總量將以指數級的趨勢增長。世界互聯網數據中心發布的數據顯示，2020年全球的數據總量達到44 ZB，根據他們的研究顯示表明，這些數據中重復的數據超過35 ZB，重復率在80%以上[1]。Microsoft[2]和EMC[3]的報道也指出在他們的主要存儲系統和二級存儲系統中數據重復率分別達到50%和85%。因為重復數據的比例較大，數據去重技術的研究也變地及其重要。云環境下數據去重技術[4]是指在云存儲環境下只存儲重復數據的一個副本，減少其相同文件的存儲，可以有效減少物理存儲設備的使用，降低網絡消耗，但云環境下的安全問題一直存在爭議，特別是當數據是多用戶共享時，會給數據的安全問題帶來極大的挑戰。

因為將數據上傳至云存儲服務器之后，會導致用戶對數據的所有權分離，一般在上傳數據之前，用戶會在客戶端對數據先進行加密，確保在上傳的過程中數據明文不會直接被暴露，但因為不同客戶端是選擇的數據加密方式不同，導致在數據到云存儲服務器之后云存儲服務器不能通過密文來判斷原始上傳數據是否相同，這樣就不能做到對重復數據的對比。為了解決此問題，Douceur等人[5]提出了一種收斂加密（Convergent Encryption，CE）的思想，該方案使用的是對稱加密思想，可以保證相同的明文M經過加密以后會得到相同的密文C，云服務器可以直接通過對密文的比較來判斷明文是否存在重復。Bellare等人[6]提出了消息鎖收斂加密方案（Message-Locked En?cryption，MLE），在收斂加密的基礎上，對其安全模型和形式化模型進行嚴格規范。

許多研究者分別提出了基于消息鎖收斂加密的改進的云存儲安全去重方案。這些方案主要針對消息鎖收斂加密存在的3個不足進行改進：①消息鎖收斂加密的塊標簽完全由數據本身決定，塊標簽的安全性存在問題。Abadi等人提出了一種采用了完全隨機化的標簽，使數據塊的標簽不完全由數據塊本身決定，提高了原有消息鎖加密的安全性[7]。之后，Bellare等人對他們提出的MLE方案的基礎上進行改進，提出了一種數據塊標簽由系統參數和文件內容共同決定的安全性更高的交互式消息鎖加密方案（interac?tive Message-Locked Encryption，iMLE）[8]。②消息鎖收斂加密的密鑰是根據數據產生的，密鑰容易遭受暴力破解，而且密鑰的數量很多，帶來管理上的不方便。針對密鑰的安全問題，文獻[9-10]提出了一種基于可信第三方服務器的保護密鑰的思想，用來保證密鑰不能被暴力破解，提高了密鑰的安全性。針對密鑰的數量較多，存在管理上的問題，文獻[11]提出了一種基于Shamir秘密共享機制的密鑰管理方案，文獻[12]提出update-MLE方案，引進樹結構構建密鑰樹來管理密鑰。③消息鎖收斂加密的所有權問題一直沒有得到足夠的重視，在所有權問題上，文獻[13]提出對數據擁有者的所有權撤銷引進樹形結構來進行管理，文獻[14]提出了一種基于布隆過濾器（Bloom Filter）的所有權證明方案，對所有權問題進行處理。

Chen等人提出了一種BL-MLE方案[15]，該方案將收斂加密的密鑰保存在數據塊標簽中，既能保證塊標簽的安全性問題，又解決了密鑰容易遭受破解攻擊的風險，而且該方案還可以使用數據塊標簽來進行去重時的所有權證明問題。該方案同時解決了傳統MLE方案3個方面的不足，節約了密鑰的生成和計算成本，同時節約了很大的存儲開銷。

雖然BL-MLE方案同時解決了傳統MLE方案存在的3個方面的不足，但因為BL-MLE方案使用的是固定長度分塊技術，所有在原始數據上進行很小的改動都會使得數據塊的劃分產生較大的改變；在使用數據塊標簽進行所有權證明時會存在很大的計算成本。本文提出一種新的數據安全去重方案，改進了數據分塊的技術和用戶的所有權驗證，在保證原方案的優點的同時，可以對數據進行細粒度的去重，使得去重率更高，引入了一種樹形結構對所有權進行管理，使得所有權更加明確。

1 預備知識

1.1 BL-MLE

通過使用加密哈希函數從文件本身生成主密鑰，并通過該主密鑰對塊密鑰進行加密。因此，僅要求用戶記住單個主密鑰。但是，以前的方案不支持有效的文件更新。為了更新云中的文件，用戶應下載整個文件，對其進行解密和修改，然后重新加密并將其重新上傳到云中。因此，用于更新的計算和通信開銷隨文件大小線性增加，這阻礙了這些方法對實際應用的適應性，特別是對于大文件。

1.2 可變長度分塊

在數據去重技術中，數據分塊[16]是數據去重技術的前提，一個數據分塊技術的好壞，將直接決定數據去重技術的去重率和去重效率。數據分塊技術一般按照數據劃分之后數據塊的每個大小可以分為固定長度分（Fixed-Sized Partition，FSP）[17]和可變長度分塊，現有的可變長度分塊技術主要使用的是基于內容的可變長分塊技術（Content-Defined Chunking，CDC）[18]。由于重復數據的每個擁有者均可能對重復數據進行過簡單操作，固定長度分塊技術的思想是按固定的數據塊長度對數據進行分塊，這種算法在重復數據發生細微改變時塊的劃分會發生很大的變化，顯然不適合當前的數據去重技術。可變長度分塊技術解決了這種對細微改變較為敏感的缺陷，它利用數據指紋將數據分給成長度大小不一的數據塊，是基于數據內容來對數據進行切分。但基于內容的可變長度分塊技術（CDC）因為其滑動窗口大小難以選擇，需要人工設定參數，且參數的設置會對結果的好壞產生較大的影響，計算開銷大等問題，逐漸不被使用。CDC算法的底層實現原理是字符串匹配，本文結合數據指紋算法和字符串匹配算法，引入了一種計算開銷較小，且分塊方式更為靈活的分塊算法。

1.3 所有權證明

所有權驗證技術是指云存儲服務器端與用戶客戶端的交互協議，用于解決通過蠻力攻擊擊穿云存儲服務器從而獲得數據，Haleve等人[15，20]提出了所有權證明（Proof of Ownership，PoW），在數據去重方案中所有權的驗證主要用于客戶在向云存儲服務器端發起上傳請求時，服務器會在對應的數據庫中對用戶將要上傳的數據進行檢索，如果數據不存在，則要求用戶將數據上傳，并將該數據與其用戶的所有權進行存儲，如果該數據存在，則要求用戶在客戶端證明是該數據的擁有者，具體的步驟為：云存儲服務器端會對用戶上傳的數據進行檢索找到相關數據信息，在對已存在的數據和獨特的算法產生一個挑戰發送給客戶端。用戶客戶端在收到云存儲服務器端發起的挑戰之后，會對發出的挑戰與擁有的數據信息給出自己的應答。云存儲服務器端會對用戶客戶端給出的應答與預設的結果進行匹配，如果能匹配上，則說明該用戶有此數據的所有權，否則表明用戶不是數據的擁有者。

1.4 雙數組Tire樹

Tire數是一種高效的索引方法，一般常用于對數據的統計，現有的數據中，可能數據擁有這對同一個數據擁有的大小不一致，如果對存在大部分相同的數據判斷為不相同的數據則存儲開銷較大。本文引入雙數組Tire樹，用雙數組Tire樹的兩個不同數組分別存儲數據和用戶信息，可以做到對數據細粒度去重的同時，減少了對數據擁有者信息的存儲開銷。

2 問題描述

2.1 系統模型

系統模型如圖1所示。

圖1 系統模型

云用戶（Users）：將數據存儲在云中，并可以對云中數據進行操作的用戶。用戶將明文數據加密，并將加密后的文件分別生成文件標簽和文件塊標簽，一起打包存入云存儲系統。如果經過云服務器對比，云存儲系統中不存在相同的文件，則稱該文件上傳用戶為初始上傳用戶，如果云存儲系統中已經存在與該文件完全相同的文件，則稱該用戶為后續上傳者，如果將要上傳的數據在云存儲服務器中已經存在且云存儲服務器中的數據包含即將要上傳的數據，則稱該上傳者為后續部分上傳者，如果新上傳的文件包含云存儲系統中已經存在的文件，則將新上傳該文件的用戶變成文件初始上傳者，將原有云存儲系統中的用戶變成后續部分上傳者。云存儲系統中擁有相同文件的用戶稱為該文件的所有權組用戶。

云服務提供商（Cloud Server Provider，CSP）：提供云環境下數據存儲和對數據所有權進行驗證的商家稱為云服務提供商。云服務提供商負責對用戶上傳的文件是否重復進行判斷，同時根據判斷的結果實時更新文件的所有權組用戶的信息。

2.2 威脅模型

按照攻擊者來源不同來進行分類，可以將本方案的攻擊者分為兩類：

（1）內部攻擊者。云存儲服務器認為是誠實的執行系統分配的任務的同時，又想更多的了解加密數據背后的信息。而內部攻擊者是可能借助一定手段更改數據擁有者信息，或拿到數據擁有者提供的權限，對數據擁有者造成損害的攻擊者。

（2）外部攻擊者。外部攻擊者主要是來自CSP外部的攻擊者。他們試圖通過各種方法獲得數據信息或數據擁有者擁有的數據的信息，冒充數據擁有者身份對數據進行更改、刪除等不法操作。

3 本文提出的方案

本文提出的方案是在原有BL-MLE方案的基礎上進行改進，主要針對兩個方面的問題進行改進：①原有BL-MLE方案的數據分塊技術的改進，改進因原有數據去重技術的缺陷而帶來的去重效率不足和去重計算開銷大的問題。②在原有BL-MLE方案的基礎上引進了雙數組Tire樹，用于對數據的所有權進行認證。

3.1 本文提出的數據安全去重方案

開始執行：輸入1λ，算法生成一個素數p，構造兩個滿足雙線性映射e的p階循環乘法群G、GT，并且滿足G×G->GT，選擇一個G的生成元g，并構造3個函數哈希函數，H1:{0，1}*->Zp，H2:{Zp}->G，H3:G->{Zp}，系統參數P={p，g，G，GT，e，H1，H2，H3}。

KeyGen（F）：將文件F上傳至云存儲系統，上傳之前先將文件F進行分塊，F=F[1]||F[2]||...||F[n]，本方案采用的是變長分塊技術，變長分塊技術的使用可以對上傳的文件F進行更細粒度的去重。本方案使用下面兩個子算法分別對文件F和文件塊F[i]進行收斂加密得到主密鑰Kmas和塊密鑰Ki。

File-KeyGen（F）：將參數P和待上傳的文件F作為輸入，通過哈希函數H1進行文件的主密鑰計算，得到文件的主密鑰Kmas=H1（F）。

Block-KeyGen（Fi）：將參數P和待上傳文件F已分塊的文件塊F[i]作為輸入，通過哈希函數H2進行每個文件塊的塊密鑰計算，得到文件塊的塊密鑰Ki=H2（F[i]）。

Enc（Ki，F[i]）：在上傳到云存儲服務器之前將已經分塊后的文件塊F[i]和已經加密后的塊密鑰作為輸入，對文件塊F[i]分別進行加密，得到每一個文件塊的密文C[i]，C[i]=H3（Ki）⊕F[i]。

Dec（Ki，C[i]）：如果有用戶需要在云存儲服務器中取出某個文件或文件塊F[i]，則需要將相應的文件塊F[i]的密鑰Ki和文件塊F[i]密文C[i]作為輸入，通過解密算法計算F[i]=H3（Ki）⊕C[i]。將計算得出的F[i]'與用戶想要獲得的F[i]對比，如果F[i]'=F[i]，則說明該用戶擁有下載該文件塊的權利，否則，拒絕為用戶提供服務。

TagGen：在用戶將文件上傳到云存儲服務器之前，先將文件F和分塊過后的文件塊F[i]進行文件和文件塊標簽的計算。

-F-TagGen：將參數P和明文M作為輸入，返回一個明文標簽T0。

-B-TagGen：將參數P和明文M以及索引為i的明文塊作為輸入，返回一個明文塊標簽。

ConTest：將塊標簽T[i]和對用的密文C[i]作為輸入，返回兩個是否對應的結果True或False。

EqTest：以兩個塊標記T、T'和相應的文件標記T0、T0'作為輸入，返回True或False。

B-KeyRet：以主密鑰Kmas、塊標記Ti和塊密文C[i]作為輸入，返回塊密鑰Ki/⊥。

PowPrf：以挑戰Q和文件M作為輸入，返回響應P。

PoWVer：以挑戰Q，明文標簽T0，和塊標簽T[i]作為輸入，返回所有權的判定結果True或False。

針對原有BL-MLE方案中存在的計算開銷較大和去重效率不夠穩定這個問題，本文引進了一種新的數據分塊技術。通過分析可以知道，在我們將數據上傳到云存儲服務器之前我們可能會對文件進行一些較小的或者較大的改變，傳統的定長數據分塊技術，在對文件進行的改動，都會對改動部分以后的數據分塊產生較大的影響，所以本方案不使用BL-MLE方案中的定長分塊技術。本方案采用一種非定長數據分塊技術，在文件內容存在改動時對改動后的文件內容分塊差異最小化。

3.2 基于雙數組Tire樹的所有權驗證算法

針對Chen等人提出的BL-MLE方案中不存在用戶所有權驗證算法，本文提出了一種新的所有權驗證算法。在云存儲系統中所有權的驗證是有效保護用戶數據安全的方式，本文提出了一種在數據塊級去重的基礎上的基于雙數組Tire樹的所有權驗證算法。

通過引入雙數組Tire樹對文件塊進行存儲的同時對用戶的所有權進行驗證，使原本需要大量計算開銷的所有權驗證算法直接與數據塊的存儲進行融合，可以在減少計算開銷的同時使得整個去重方案更加完善與整體。其具體算法如下：

算法1基于雙數組Tire樹的所有權驗證算法（Pow-Ver-Tire）

（1）文件上傳：云存儲服務器收到客戶端發送的上傳文件請求，請求將文件上傳到云中，在云存儲服務器在接收到上傳請求并給與客戶端反饋以后，客戶端對將要上傳的文件備份，同時，客戶端對將要上傳的文件進行數據分塊，并對要上傳的文件及該文件分塊過后的文件塊分別進行文件標簽計算和文件塊標簽計算。在客戶端的上傳請求到達云存儲服務器以后，云存儲服務器會建立兩個臨時數組，分別為文件塊信息base數組和用戶信息check數組。

（2）用戶信息上傳：當客戶端的文件上傳完成以后，云存儲服務器將會通知客戶端收集該文件擁有者的用戶信息，并將該文件用戶擁有者的用戶信息上傳到云存儲服務器，保存在臨時的check數組中。

（3）重復檢測：文件在存儲到云中之前，云存儲服務器會通過本文提出的方案對上傳的文件和文件塊進行重復檢測。如果文件標簽匹配成功，則說明已經存在完全相同的文件在云中，此時，云存儲服務器會找到相應的文件標簽并找到該文件的用戶信息check數組，將新上傳的文件擁有者的用戶信息更新到check數組中，并銷毀該文件生成的臨時數組check。如果文件塊標簽匹配成功，則說明云中已經存在與上傳的文件塊相似的文件或相同的文件塊，此時需要通過云存儲服務器找到云中存儲的文件塊，如果云中存儲的文件塊包含新上傳的文件塊，則將新上傳的文件塊的用戶信息更新到已存在的文件塊的用戶信息數組check中，并銷毀該文件臨時生成的用戶信息數組check；如果新上傳的文件塊包含云中原有的文件塊，則將云中存儲的文件塊的個人信息數組check轉為臨時個人信息數組，將該文件塊的個人信息check數組全部添加到臨時生成的個人信息check數組中，同時銷毀云中原始文件塊的個人信息check數組。如果新上傳的文件未能匹配，則說明將要上傳的文件在云中不存在，此時云存儲服務器將會在云中存儲該文件的base數組，同時將文件的個人信息臨時數組check數組轉為永久數組。

（4）文件下載：在客戶端向云存儲服務器發送文件下載指令，云存儲服務器在其內部將需要下載的數據進行檢索然后將用戶信息和要下載的文件信息下載到客戶端，在客戶端對要下載的文件信息進行文件標簽計算和文件塊標簽計算，將計算結果發送給云存儲服務器，云存儲服務器查找文件標簽，如果存在該文件標簽，則打開該文件標簽下的個人信息check數組，查找用戶信息是否存在，如果存在，則可以對文件進行下載，否則，給與客戶端不能下載的提示。

（5）文件刪除：與文件下載步驟相同，如果可以找到要刪除的文件個人信息數組check中存在請求刪除的個人信息，則執行文件刪除操作。

4 安全性分析

4.1 數據隱私安全

在云存儲環境下，數據隱私安全分為兩個部分：①客戶端數據隱私安全：客戶端數據隱私安全主要是指在用戶個人設備對數據隱私的保護，客戶端數據隱私安全較為容易保障，現有的許多產品均能保障客戶端數據隱私的安全。②云存儲服務器端數據隱私安全：當用戶將數據上傳到云存儲服務器之后也要保證數據的隱私安全，但是云存儲服務器也是好奇的，可能會非法訪問云中的數據。在本方案中，我們對數據進行兩方面的加密操作，不僅對數據明文、明文塊進行加密，而且對數據標簽、數據塊標簽也進行加密。云存儲服務器即使非法訪問數據，因為使用收斂加密方案對數據進行加密，云存儲服務器端即使獲得數據的密文，在沒有通過收斂加密獲得數據、數據塊密鑰的條件下，服務器端也不能獲得數據的明文。

在云存儲環境下，因為數據全部存儲在云中，可能存在未授權的用戶對云中數據進行訪問，造成數據隱私安全的問題隱患。在本方案中，在數據存儲到云中之后會對數據生成一個的所有權數組，只有在所有權數組中的用戶才能對數據進行訪問，未經授權的用戶無法通過數據所有權數組的驗證，從而不能訪問數據，保證了數據隱私安全。

4.2 抗側信道攻擊

在云存儲環境下，一種常見且有效的攻擊手段為側信道攻擊。側信道攻擊是指通過對加密設備的時間消耗、功率消耗和電磁輻射消耗等的監聽，通過分析，得到加密設備中的信息。

在云存儲環境下，側信道攻擊可能發生在用戶將加密后的數據上傳到云存儲服務器的過程中通過對傳輸通道的功耗監聽，來判斷在云中是否已經存在客戶端將要上傳的數據。在傳統方案中，如果云中已經存在客戶端將要上傳的數據，則用戶不需要將數據上傳到云中，此時側信道攻擊者通過對通信信道上的功耗進行監聽，因為不需上傳數據到云中，功耗消耗較少，則可以判定客戶端將要上傳的文件在云中已經存在，這種情況下，結合其他因素，攻擊者可能會推斷出用戶上傳的數據內容。

本文方案中，在進行去重的同時對所有權信息進行驗證，且實現了數據的細粒度去重，在數據上傳到云中時，側信道攻擊者通過功耗分析無法分析出將要上傳的數據在云中是否存在。

4.3 前向后向加密

在云存儲環境下，前向加密安全是指已經撤銷所有權的用戶，不能訪問在其撤銷所有權之后存儲的文件，后向加密安全是指新增加的擁有所有權的用戶，不能訪問在其加入之前的已經存儲的文件。

本文方案中，因為雙數組Tire樹的引入，可以有效的解決前向后向加密安全問題。對于前向加密安全，當用戶的所有權撤銷以后，在存入新的數據的同時，會對用戶的所有權進行驗證，已經撤銷所有權的用戶，無法通過雙數組Tire樹的用戶信息數組check數組的驗證，所以對后存入的數據不能進行破解，從而保證了方案的前向加密安全。對于后向加密安全，當新用戶信息添加到用戶信息check數組以后，對于已經存在的數據，因為其用戶信息check數組中不存在新用戶的信息，在試圖訪問已經存在的數據的時候，因為新用戶信息無法通過已存在數據的用戶信息check數組的檢驗，不能對已經存在的數據進行破解，從而保證了方案的后向加密安全。

5 性能與實驗分析

5.1 性能分析

在云存儲環境下去重方案性能的分析，可以從以下兩個角度對方案的性能進行分析，分別是方案的去重率和去重效率。

（1）去重率。減少重復數據的存儲，降低存儲開銷，傳輸開銷等因素是我們設計數據去重方案的原因，所以去重率是評價一個數據去重方案優劣的重要標準。在BL-MLE方案中，對數據分塊采用的是固定長度分塊技術，當數據出現較小變動，就會對出現變動以后的數據產生較大的影響，因為這種分塊技術的使用，所以BL-MLE方案的去重率不是很理想。在文獻[21]中針對BL-MLE方案中使用的固定長度分塊技術去重率低，計算開銷大的情況，提出了一種基于內容的可變長度數據分塊技術，這種數據分塊技術很大程度上解決了去重效率低的問題，但因為數據類型的不同，數據中存在的重復數據比例不同等因素，使其分塊效果也不是很好，從而影響整個方案的去重率。本文方案提出的數據分塊技術能夠很好解決上述問題，從而提高了方案整體的去重率。

（2）去重效率。隨著現在數據指數式的增長現狀，去重方案的去重效率是一個方案可行性的重要標準。本方案對去重效率采用兩個方面的評價：①整體去重方案的計算開銷，②整體去重方案的存儲開銷。

在方案整體的計算開銷上，本方案是在BL-MLE方案的基礎上進行改進，提出的新的數據分塊技術可以在很大程度上減少在數據分塊環節的計算開銷，在其他環節的計算開銷變化不大的情況下，可以有效減少方案的計算開銷。在方案整體的存儲開銷上，本文方案在引進所有權驗證和管理的情況下，不需要特地開辟新的存儲空間來存儲用戶的個人信息，將用戶個人信息的存儲與驗證放在一起進行，極大減少了存儲開銷。

5.2 實驗分析

（1）實驗環境。方案使用的是NTL庫實現橢圓曲線上的計算操作，使用Java語言分別實現3種數據分塊技術的實現，最終使用C++語言在Window 10操作系統下Visual Studio 2019上模擬了BL-MLE方案，文獻[21]提出的改進的BL-MLE方案，以及本文提出的方案。實驗設備處理器為Intel Core i5-8300H，CPU主頻為2.30 GHz，內存為8 GB。

（2）去重率對比。本文提出方案是在BL-MLE方案的基礎上進行改進的，3種方案的其他步驟均不會對方案的去重率產生影響，所以在對3種方案的去重率對比上，主要是通過3種數據分塊技術對數據的去重率作為3種方案的去重率的對比。圖2可以看出，在數據量較小時3種方案的去重率相差不大，隨著數據數量的增長，3種方案的去重率都處于下降趨勢，固定長度分塊技術因為其分塊的固定，去重率急劇下降。因為本文方案使用的基于字符串匹配的分塊技術，所以隨著數據數量的增長，去重率存在一定的上漲趨勢。

圖2 不同分塊算法下的去重率對比

（3）去重效率對比。去重方案能夠實施的可行性主要取決于去重效率，本文方案在去重方案的計算開銷和存儲開銷兩個方面對去重效率進行評價。

表1是對3種去重方案計算開銷的分析，Mul代表在算法循環群G上的乘法操作，Exp代表在G上的指數操作，Hash代表Hash映射操作，XOR代表異或操作，AES表示一次AES加密。由表中我們可以看出在客戶端，即數據進行去重部分的計算開銷為方案的主要計算開銷，因為BL-MLE方案使用的是固定長度分塊技術，所以在對數據進行去重時會進行s次Mul操作和s+1次Exp操作，因為是在乘法循環群上進行這些操作，所以方案的整個計算開銷很大，文獻[21]采用的是數據可變長度分塊技術，但因為這種分塊技術存在滑動窗口大小難以選擇，指紋計算和對比開銷較大，雖說對數據塊操作的計算開銷變小，但在分塊時計算開銷的增大影響更大，整體的計算開銷相較于固定長度分塊技術沒有太大的改進。本文方案中，對數據的分塊采用的是字符串匹配，增加了一定的計算開銷，但隨著數據數量的增長，重復數據的檢測率不斷提高，所要進行的對比次數不斷減少，整體的計算開銷要遠遠小于上面兩種方案。在服務器端，本文方案增加了對數據所有權的管理和驗證，計算開銷不做比較。

表1 3種方案的整體去重計算開銷對比

圖3是使用3種方案對一定大小的數據進行去重之后所需要消耗的存儲空間的比較。因為前兩種去重方案在設計時沒有考慮到用戶所有權的問題，在圖3中默認對用戶信息建表，用來保存用戶信息。從圖3中我們可以看出，因為去重率的提高，存儲空間的消耗不斷減小，本文方案引入了雙數組Tire對數據所有權的管理和驗證，在這種存儲結構下，數據所有者的信息存儲在數組中，并不用開辟新的存儲空間用來存放數據擁有者信息，所以本文方案的整體存儲消耗也是大大低于前兩種方案的。

圖3 3種方案的整體存儲開銷對比

6 結語

綜合上面3個實驗結果，我們可以看出，本文方案在原始BL-MLE的基礎上，對重復數據的檢測有更好效果的同時，也大大減小了去重方案的計算開銷和存儲開銷。但本文方案主要針對的是純文本數據，現實生活中視頻、音頻類數據已經成為主要的數據，接下來在純文本數據去重的基礎上，研究各種數據類型的去重方案。