基于重復數(shù)據(jù)刪除技術的霧存儲數(shù)據(jù)去冗余方案

陳思佳 溫 蜜 陳 珊

(上海電力大學計算機科學與技術學院 上海 200090)

0 引 言

當今社會數(shù)字化信息呈爆炸式增長，《數(shù)據(jù)時代2025》白皮書中預測，2025年全球的數(shù)據(jù)量將達到163 ZB，是目前的10倍之多。數(shù)據(jù)量的劇增和泛濫對數(shù)據(jù)存儲管理技術提出了巨大的挑戰(zhàn)，如何高效地管理和存儲數(shù)據(jù)已成為研究熱點。微軟[1]和EMC[2-3]生產(chǎn)的主存儲系統(tǒng)和二級存儲系統(tǒng)中，分別有50%和85%的冗余數(shù)據(jù)，隨著時間的推移，冗余數(shù)據(jù)的比例也會成倍上升，企業(yè)在存儲這些的數(shù)據(jù)時所需要的開銷也是巨大的。

如此龐大的數(shù)據(jù)對傳統(tǒng)存儲系統(tǒng)提出了挑戰(zhàn)。于是技術人員將目標轉向容量更大，成本更低廉的云存儲系統(tǒng)。云存儲架構集成了大規(guī)模用戶數(shù)據(jù)，數(shù)據(jù)中會存在許多重復數(shù)據(jù)，因此數(shù)據(jù)去重對于維護數(shù)據(jù)開銷具有重要的意義。

根據(jù)IDC最近的一項研究[4]表明，目前近80%的企業(yè)正在尋求存儲設備的重復數(shù)據(jù)刪除技術，從而消除設備中的冗余數(shù)據(jù)。重復數(shù)據(jù)刪除技術是一種數(shù)據(jù)縮減技術，在單機設備和云平臺中都有廣泛應用，其主要作用于文件內部和文件之間的冗余數(shù)據(jù)，通過與源數(shù)據(jù)進行對比，刪除相同的數(shù)據(jù)塊(文件)，達到在磁盤中存儲更多數(shù)據(jù)的目的。在工業(yè)界Datadomain的DDFS、IBM Diligent、EMC的Avarma、Veritas的PureDisk以及Commvault的Simpana都是比較知名的重復數(shù)據(jù)刪除產(chǎn)品，這些產(chǎn)品通?？梢赃_到20∶1的重復刪除率。數(shù)據(jù)分塊和指紋管理是控制重復數(shù)據(jù)刪除性能的流程中關鍵的技術部分。傳統(tǒng)的重復數(shù)據(jù)刪除模塊是將數(shù)據(jù)流進行分塊，分塊的方式有多種：可變大小的分塊(CDC)、固定大小的分塊(fixed-size partion)以及兩者的混合，即滑動分塊(sliding block)。根據(jù)哈希函數(shù)(MD-5或SHA-1)計算每個數(shù)據(jù)塊的Hash值(我們稱之為指紋)，與已有指紋表中的指紋進行對比，判斷是否為重復數(shù)據(jù)塊。這一系列的指紋查詢操作會導致指紋表在內存中的隨機讀取，每次讀取都存在磁盤訪問，從而增加輸入和輸出(I/O)。

云存儲采取的是數(shù)據(jù)外包模式，許多云服務提供商為了降低成本，往往會將數(shù)據(jù)中心建立在低成本的偏遠地區(qū)，當云服務器距離客戶較遠時，必然會增加數(shù)據(jù)傳輸延遲。傳輸過程中的重復數(shù)據(jù)也會占用大量的網(wǎng)絡帶寬，造成數(shù)據(jù)中心和移動端的I/O瓶頸。據(jù)最新研究結果顯示，在各類云存儲產(chǎn)品中數(shù)據(jù)的重復率達到60%，龐大的重復數(shù)據(jù)對云中心去重同樣造成很大壓力。

為了解決現(xiàn)存的云存儲去重問題，并且滿足物聯(lián)網(wǎng)發(fā)展的需求，便產(chǎn)生了一種新的體系結構。即在終端和云數(shù)據(jù)中心之間加入網(wǎng)絡邊緣層，配上帶有存儲功能的小型服務器或路由器，將不需要放到云端的數(shù)據(jù)在邊緣層直接進行處理和存儲。其主要思想是將一些數(shù)據(jù)中心的任務遷移到邊緣服務器，目的是減少云端去重壓力，提升數(shù)據(jù)傳輸速率，從而快速響應底層設備的需求，減少用戶響應時間，降低時延，由此便誕生了“霧計算”[5]。

霧作為一種小型“云中心”，對附近的移動終端用戶或邊緣用戶的數(shù)據(jù)進行存儲、通信、控制、管理和測量。與云存儲不同的是，霧節(jié)點處理大多是無需放在遠端云數(shù)據(jù)中心的用戶經(jīng)常訪問的數(shù)據(jù)。隨著連接霧節(jié)點的移動終端不斷變化，在霧節(jié)點中同樣存在存儲過程中產(chǎn)生的數(shù)據(jù)冗余問題。目前大部分去重方案為云數(shù)據(jù)中心這種分布式環(huán)境，去重對象多為數(shù)量較為龐大的數(shù)據(jù)，用來滿足云數(shù)據(jù)中心下按需分配、彈性增長、快速部署等方面的要求。對于霧環(huán)境中輕量級存儲設備目前還沒有提出重復數(shù)據(jù)刪除方案。因此，本文主要針對霧節(jié)點中的輕量級服務器提出了重復數(shù)據(jù)刪除方案[6]，在數(shù)據(jù)指紋的生成和查詢兩個關鍵技術上，對于霧服務器中頻繁訪問的數(shù)據(jù)在內存中建立數(shù)據(jù)查詢機制。方案的貢獻有以下幾方面：

(1) 為了實現(xiàn)高效查詢，針對霧節(jié)點中訪問頻率較高的數(shù)據(jù)，在內存中構建索引表，每個索引值對應的紅黑樹作為存儲數(shù)據(jù)指紋的結構，減少磁盤與內存間的I/O，提高查詢速度。

(2) 為解決計算數(shù)據(jù)指紋時產(chǎn)生的Hash沖突問題，利用循環(huán)冗余碼(CRC)技術判斷具有相同數(shù)據(jù)指紋的數(shù)據(jù)塊是否重復，并將沖突數(shù)據(jù)塊用鏈表結構存儲在指紋節(jié)點中。

(3) 為防止系統(tǒng)的突然崩潰，提出在內存中持久化保存指紋表，分為內存某一時刻的映射文件和記錄更新的日志文件。通過固定時刻刷新內存將內存中的指紋表永久保存在磁盤的映射文件中，新的數(shù)據(jù)指紋插入時，將更新情況記錄在日志文件中。一旦系統(tǒng)崩潰重啟，內存中的數(shù)據(jù)會消失，此時磁盤中的兩個文件合并重新構建內存中的指紋表，同時兩個文件內容清空重新記錄。

1 預備知識

1.1 去重相關研究

重復數(shù)據(jù)刪除研究過程主要包括基于粒度的劃分、指紋的查詢、數(shù)據(jù)去冗余的時機。

Won等[7-8]發(fā)現(xiàn)分塊是重復數(shù)據(jù)刪除過程的主要開銷之一。基于粒度的重復數(shù)據(jù)刪除技術包括基于文件級的、塊級的[13-14]和字節(jié)級的?；谖募壍那闆r比較少見，只有當兩個文件內容完全相同時，才能利用去重技術刪除，所以這種方式的去重率很低?；谧止?jié)級的方式在數(shù)據(jù)量非常龐大的情況下，顯然也是不現(xiàn)實的，這種方式會耗費過多CPU資源，運算效率不理想。基于塊級的粒度是目前應用最廣泛的，散列值(MD-5,SHA-1等)可以作為唯一塊的標識，概括數(shù)據(jù)塊的內容，無需對數(shù)據(jù)塊進行讀取，從而提高查詢速度。

在指紋管理方面，也提出了許多方法。第一個方案就是Bloom等[9]提出的主存儲過濾器，即布隆過濾器(Bloom Filter)。Bloom Filter由k個散列函數(shù)和m位的數(shù)組構成，當插入n個元素時，只需要判斷該元素通過k個Hash函數(shù)映射在數(shù)組的點是否為1，若k個點都為1，則表示存在，否則不存在。其好處在于在查找指紋是否重復時可以避免不必要的磁盤I/O，同時Bloom Filter占用空間小，所以廣泛應用于備份[10]、分布式文件系統(tǒng)[11]和Web代理[12]。但Bloom Filter存在假陽性，即返回的結果不一定正確，存在概率性。誤報率如下式所示：

(1)

另一種方案就是指紋表存放數(shù)據(jù)指紋。利用傳統(tǒng)搜索結構，例如B+樹或散列表，查找序列中的相鄰指紋不可能以聚類方式存儲，這樣就會導致指紋的隨機讀取，導致查詢效率降低。

數(shù)據(jù)去冗余的時機一般分為3種：先備份再去重策略(Deduplication Ater Backup strategy，DAB)、先去重再備份策略(Deduplication Before Backup strategy，DBB)和邊備份邊去重策略(Deduplication During Backup strategy，DDB)。DBB在傳輸前將數(shù)據(jù)進行去重，可以有效提高傳輸效率，節(jié)省帶寬。

1.2 數(shù)據(jù)結構分析

對于在內存中的查找結構中，平衡二叉樹是使用較為廣泛的檢索樹。AVL樹和紅黑樹都是平衡二叉樹的一種，與AVL樹相比，紅黑樹可以確保沒有一條搜索路徑會比其他路徑長2倍，因而是近似平衡的。所以相對于嚴格要求平衡的AVL樹來說，它保持平衡的插入和刪除旋轉次數(shù)較少，從而保證了系統(tǒng)運行時間，總體性能優(yōu)于AVL樹。AVL樹與紅黑樹性能對比如表1所示。

表1 AVL樹與紅黑樹性能對比

2 系統(tǒng)模型

霧計算框架如圖1所示，結構分為三部分：移動終端區(qū)、霧計算區(qū)和遠端云計算區(qū)。霧計算位于云服務器和移動終端之間。作為云節(jié)點的服務者，移動終端區(qū)的執(zhí)行者，霧計算在框架中為上下兩層服務，起到了承上啟下的作用。

圖1 系統(tǒng)結構圖

系統(tǒng)結構三個部分的作用如下：

? 移動終端區(qū)：移動可連接局域網(wǎng)絡設備，如手機、電腦、平板電腦、智能手表等。

? 霧計算區(qū)：考慮到輕量級移動設備的有限存儲空間和計算能力，霧計算區(qū)接收來自移動終端的請求/服務，處理和存儲無需放在云端的少部分訪問頻繁的數(shù)據(jù)。每個霧計算區(qū)由霧管理員(Fog Manager)、進程日志管理服務器(Services Logging Server)、霧計算服務器(Fog Computing Server)和霧存儲服務器(Fog Storage Server)四部分構成。其在霧節(jié)點中的功能如表2所示。

表2 系統(tǒng)組成成員

? 遠端云計算區(qū)：大規(guī)模虛擬化的計算機集群，接收來自霧計算區(qū)的請求/服務。當霧計算區(qū)沒有可用虛擬機容量處理終端區(qū)的請求服務時，會將服務委托給云計算。云數(shù)據(jù)中心將請求分配給有足夠容量完成服務的其他霧節(jié)點服務器。作為系統(tǒng)的上層結構，其成員功能與霧計算區(qū)大致相同。但云數(shù)據(jù)中心作為由大量服務器聚合而成的高可靠性、高拓展性的資源共享池，其接收到的用戶請求遠超小規(guī)模的霧節(jié)點。故云節(jié)點還包括了第三方云服務器，其功能如表2所示。

進程日志管理器中的兩個記錄霧節(jié)點進程和當前虛擬機可用容量的兩張列表內容的樣例，如表3、表4所示。

表3 虛擬機資源占用表

表4 服務(請求)進程表

霧計算[15]的理念是將一些輕量級的智能處理設備部署在靠近移動用戶的地方，方便用戶可以在比較近的距離范圍內直接連接霧服務器，通常霧服務器與用戶是一跳(one-hop)的通信距離。霧節(jié)點存儲和處理的數(shù)據(jù)多是在一定的距離內用戶經(jīng)常訪問的數(shù)據(jù)，將這些數(shù)據(jù)存儲在霧節(jié)點中，用戶無需將任務請求發(fā)送到遠端的云數(shù)據(jù)中心進行處理，這樣避免了發(fā)送過程中產(chǎn)生的網(wǎng)絡延遲，進而提升數(shù)據(jù)傳輸速度，減少云服務提供商的計算壓力。

購物中心作為人流量較大的公共場所，用戶對與商場有關的購物信息會有較高的訪問頻率，包括餐廳的類型、位置、用戶評價，品牌商店的購物信息、位置、產(chǎn)品價格等。將購物中心的詳細信息放到云數(shù)據(jù)中心，讓顧客通過手機實時獲取云端上存儲的商場信息是一種可行方案，但是存在不足之處。首先用戶通過手機訪問云端具有不穩(wěn)定性，會受到信號的影響，而且云端信息需要經(jīng)過網(wǎng)絡多路轉發(fā)才能到達用戶，會影響用戶的服務體驗。如果在商場的每個角落里部署霧服務器，用戶在訪問這些數(shù)據(jù)時就會避免查詢延遲、信號弱等情況，提高了用戶的購物體驗。

3 基于霧存儲的去重方案

霧存儲中的數(shù)據(jù)通常是用戶經(jīng)常訪問和查詢的，針對這些高訪問頻率的存儲數(shù)據(jù)，霧存儲系統(tǒng)中同樣存在同一文件的多個副本，以及文件中出現(xiàn)重復數(shù)據(jù)塊的問題。目前已經(jīng)提出許多有效的重復刪除機制來解決文件冗余副本問題。這些方案通常解決的是分布式云存儲中數(shù)據(jù)量達到PB級以上的數(shù)據(jù)，大規(guī)模的數(shù)據(jù)直接導致指紋表增大。龐大的指紋表讀取時只能將一部分內容置入內存，只有置入的部分得當，才能保證查詢的命中率，并且這種方式會占用大量的隨機磁盤訪問。為了防止磁盤的隨機訪問，我們提出將霧計算中訪問頻繁的數(shù)據(jù)指紋表保存在內存中進行讀取，這樣可以減少磁盤I/O。利用紅黑樹作為數(shù)據(jù)指紋表結構，提升查詢效率。

3.1 方案流程

本文提出的數(shù)據(jù)指紋查詢方案，將完整的指紋表保存于內存中，將非重復數(shù)據(jù)塊置于磁盤中。當判斷數(shù)據(jù)指紋是否重復時，可以直接在內存中進行查詢，無需磁盤I/O讀取。若指紋表中沒有相同指紋，即為非重復數(shù)據(jù)塊指紋，插入指紋表中。若指紋表中存在相同指紋，將該指紋的數(shù)據(jù)塊與指紋表中相同指紋對應的數(shù)據(jù)塊的循環(huán)冗余碼(CRC)進行比較。如果不同，判斷該數(shù)據(jù)塊為非重復數(shù)據(jù)塊，保存在該指紋的數(shù)據(jù)塊鏈表中；反之，返回該數(shù)據(jù)塊的地址指針。方案流程如圖2所示。

圖2 方案流程圖

3.2 索引表

通過將數(shù)據(jù)指紋進行哈希計算得到索引值(由0到n構成的整數(shù))。將數(shù)據(jù)分成非重疊等分數(shù)據(jù)塊b1,b2,…,bn。運用MD5哈希算法計算每個指紋，f1=h(b1),f2=h(b2),…,fn=h(bn)。將數(shù)據(jù)指紋再次進行哈希計算，得到整數(shù)型索引值，i1=h(f1),i2=h(f2),…,in=h(fn)。用戶查詢冗余數(shù)據(jù)塊時，計算該數(shù)據(jù)塊的索引值，查詢該索引值下的指紋表。遍歷索引表的時間復雜度為O(1)，索引表如圖3所示。

圖3 索引表生成

3.3 基于紅黑樹的指紋查詢

紅黑樹作為數(shù)據(jù)指紋的搜索結構，與其他在內存中的數(shù)據(jù)結構相比，具有較低的時間復雜度。與在磁盤中的數(shù)據(jù)結構相比，查詢過程中降低了磁盤I/O讀取，加快查詢速度。遍歷紅黑樹，找到數(shù)據(jù)塊指紋的所在地址，避免存在哈希沖突情況，在計算數(shù)據(jù)塊指紋的同時，計算出數(shù)據(jù)塊的循環(huán)冗余碼附加在數(shù)據(jù)后面。當出現(xiàn)數(shù)據(jù)指紋相同的情況時，比較數(shù)據(jù)塊的CRC。若相同，表示該數(shù)據(jù)塊重復；否則，存在哈希沖突，將數(shù)據(jù)塊保存在其指紋的鏈表中(鏈表中保存的是指紋相同的不同數(shù)據(jù)塊)。若沒有找到與該數(shù)據(jù)塊指紋相同的指紋，則數(shù)據(jù)塊為非重復數(shù)據(jù)塊，將其插入在相應的紅黑樹節(jié)點中。紅黑樹的指紋插入和查詢過程如圖4所示。

圖4 指紋的插入與查詢

3.4 內存中持久化保存指紋表

為了保證數(shù)據(jù)結構在內存中的持久性，防止操作系統(tǒng)在崩潰狀況下內存中數(shù)據(jù)消失，指紋表原有的數(shù)據(jù)信息通過映射的方式寫入映射文件，在對數(shù)據(jù)指紋表做更改前，將數(shù)據(jù)指紋的插入操作信息寫入日志文件。由于日志是立即持久化的，可以作為恢復其他所有持久化結構的可靠來源。當系統(tǒng)發(fā)生崩潰，內存中的內容消失，此時再次啟動映射文件和日志文件中的內容合并成新的數(shù)據(jù)結構存入內存中，清空文件內容，新的指紋表映射到映射文件，日志文件記錄下一次的數(shù)據(jù)變更，為數(shù)據(jù)提供容災保障。

算法1介紹了數(shù)據(jù)流等分塊的過程。將數(shù)據(jù)流作為去重系統(tǒng)的輸入，根據(jù)設置的數(shù)據(jù)塊大小(size)將數(shù)據(jù)流進行等分切塊，將等分后的數(shù)據(jù)塊傳入列表中輸出。

算法1數(shù)據(jù)流定長分塊

輸入:數(shù)據(jù)流

數(shù)據(jù)流長度：len

等分數(shù)據(jù)塊的大?。簊ize

begin:

list=[]

count=len/size+1

//等分的數(shù)據(jù)塊數(shù)量

for i in count do

將等分后的數(shù)據(jù)塊依次放入list中

end for

end

輸出：list={b1,b2,…,bn}

//每個數(shù)據(jù)塊的首地址

算法2介紹了指紋和循環(huán)冗余碼的生成過程。等分后的數(shù)據(jù)塊作為輸入。MD5、SHA-1、SHA-256都是目前較為常用的散列算法，我們選擇生成指紋較小的MD5算法，得到f1=h(b1),f2=h(b2),…,fn=h(bn)。我們選擇應用最廣泛的crc32作為循環(huán)冗余碼的生成公式，得到的CRC值附加在數(shù)據(jù)后面。

算法2生成數(shù)據(jù)指紋和CRC

輸入：等分后的所有數(shù)據(jù)塊bx

數(shù)據(jù)塊數(shù)量：num

指紋生成公式(MD5)：h

CRC生成公式：crc32

begin:

for j in num do

數(shù)據(jù)指紋fx=h(bx)

CRC碼cx=crc(bx)

end for

end

輸出：數(shù)據(jù)塊指紋fx和CRC碼cx

算法3介紹了索引表的生成以及指紋的插入、查詢過程。MD5算法得到的數(shù)據(jù)塊指紋作為輸入，重哈希確定索引表中索引值的位置，遍歷索引值對應的指紋表，若沒有相同的指紋，確定該數(shù)據(jù)塊為非重復塊，指紋插入指紋表中。若存在相同指紋，通過比較數(shù)據(jù)塊的CRC值判斷是否存在哈希沖突情況，如果兩個數(shù)據(jù)塊的CRC值相同，則為重復數(shù)據(jù)塊，返回其數(shù)據(jù)塊所在地址指針，反之，則為非重復數(shù)據(jù)塊，將該數(shù)據(jù)塊插入其指紋所在的鏈表中。

算法3生成索引表和指紋插入、查詢

輸入:生成的數(shù)據(jù)指紋fx

數(shù)據(jù)指紋數(shù)量：n

索引表的索引數(shù)量：m

索引值對應的紅黑樹：T

計算索引的二次哈希公式：h1

CRC生成公式：crc32

begin:

索引值ix=h1(fx) % m

for i in n do

for j in m do

if fxin T(ix) then

//T(ix) 表示索引ix對應的紅黑樹

if crc32(fx)==crc32(T(fx)) then

//T(fx)表示紅黑樹中指紋fx連接的數(shù)據(jù)塊，返回數(shù)據(jù)塊所在

//地址指針

else

判斷為非重復數(shù)據(jù)塊，將指紋插入指紋表中，存入數(shù)據(jù)塊

end if

else

判斷為非重復數(shù)據(jù)塊，將指紋插入指紋表中，存入數(shù)據(jù)塊

end if

end for

end for

end

4 實驗分析

實驗運行平臺為Windows 10系統(tǒng)，Intel core i5 CPU，8 GB內存，處理器速度2.30 GHz，使用Python編程實現(xiàn)。實驗使用名為gcc-3.4.1和emacs-20.7的數(shù)據(jù)集，分別為19.4 MB、34.1 MB。指紋搜索效率通過計算搜索一個指紋所需的時間即查找延遲來判定，對數(shù)據(jù)進行10 KB、100 KB、1 MB、10 MB定長分塊。在這兩個數(shù)據(jù)集上對比Prefix indexing與DeFog，結果如圖5、圖6所示，可以看出，DeFog指紋搜索效率分別提高54.1%、38.78%。

圖5 emacs-20.7指紋查詢時間

圖6 gcc-3.4.1指紋查詢時間

霧計算作為云計算的邊緣延申，目前沒有針對其存儲數(shù)據(jù)的去重方案，DeFog根據(jù)霧環(huán)境的特征，對已有的prefix[13]方案進行了改進。DeFog減少了磁盤I/O，在不同的分塊情況下，查詢時間都有一定的減少。數(shù)據(jù)塊為10 KB時，gcc-3.4.1數(shù)據(jù)集的查詢速率從9.8 ms降至1.21 ms，效率提高了87.7%。隨著分塊大小增加，數(shù)據(jù)塊的個數(shù)減少，兩方案的查詢時間趨于相同。

圖7、圖8表明在運行時間上DeFog與現(xiàn)有的方案相比，效率也有了一定的提高。將數(shù)據(jù)流按100 KB、1 MB、10 MB進行分塊，索引表長度為1 000。emacs-20.7數(shù)據(jù)集中，當數(shù)據(jù)塊大小為10 MB時，DeFog的運行時間在240 ms，比現(xiàn)有的方案減少了81.2%。但在數(shù)據(jù)塊為1 MB的情況下，DeFog在兩個數(shù)據(jù)集上的運行時間與原有的方案相比沒有太大的改進，這體現(xiàn)了選取合適的數(shù)據(jù)分塊大小對實驗結果有一定的幫助。

圖7 emacs-20.7運行時間

圖8 gcc-3.4.1運行時間

在數(shù)據(jù)集中進行第一次實驗時，因為當前指紋表為空，生成的大部分指紋都是非冗余的，多為插入操作，無需檢查冗余數(shù)據(jù)。第二次實驗在指紋表非空的情況下進行，需要判斷重復數(shù)據(jù)塊，因此延遲時間會隨著冗余數(shù)據(jù)塊數(shù)量的增加而變長。但由于指紋表全部保存在內存中，不會出現(xiàn)磁盤中部分指紋表隨機讀取的情況，確保了查詢時間。

索引表對指紋的插入與查詢的影響如圖9所示。利用索引表可以迅速定位到指紋所在的紅黑樹，進而判斷指紋是否重復。索引表是鏈式結構，讀取時間基本可以忽略，與沒有索引表的方案相比，效率有所提高。但索引表的長度對運行時間影響不大，兩個數(shù)據(jù)集在索引表為10、100、1 000時運行時間基本相同。

圖9 索引表對時間的影響

霧計算作為云計算在網(wǎng)絡邊緣的延伸，其與云計算在原理是相似的，但在環(huán)境布局上也有不同之處，其方案不能直接應用于霧計算中。因此，將DeFog與近年來提出的方案進行性能對比，結果如表5所示。

表5 方案性能對比

DeFog適用于霧環(huán)境，在數(shù)據(jù)量較大且單一的情況下能夠加快查詢速度，防止查詢延遲。

5 結 語

本文提出了在霧服務器內存中置入紅黑樹作為指紋插入與查詢的數(shù)據(jù)結構，從而實現(xiàn)重復數(shù)據(jù)刪除系統(tǒng)(DeFog)。為防止系統(tǒng)突然崩潰，提出用日志文件記錄指紋的更新，為數(shù)據(jù)容災提供保障。所提出的系統(tǒng)通過減少指紋查找時間和消除冗余數(shù)據(jù)來提高重復數(shù)據(jù)刪除系統(tǒng)的性能和效率。根據(jù)實驗證明，固定分塊對冗余檢測有較好結果，并且可以減少一定的計算開銷。索引表在一定程度上加快了指紋查詢的速度，時間復雜度為O(1)。紅黑樹作為指紋表與其他數(shù)據(jù)結構相比在插入和查詢時間上都比較短，適合作為存儲指紋的結構。

霧節(jié)點的出現(xiàn)一定程度上緩解了云計算中心的壓力，DeFog針對霧服務器中頻繁訪問的數(shù)據(jù)提出了重復數(shù)據(jù)刪除技術，減少了網(wǎng)絡數(shù)據(jù)傳輸量，優(yōu)化系統(tǒng)的整體功能。在人流較大、對通信速度要求較高的霧節(jié)點中，可以加快冗余查詢速度，保證去重效率。實驗證實，本文的方案更適用于訪問頻繁的小范圍數(shù)據(jù)，通過更快的數(shù)據(jù)結構提高整體性能。