陳思佳 溫 蜜 陳 珊

(上海電力大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 200090)

0 引 言

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

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

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

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

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

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

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

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

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

1 預(yù)備知識(shí)

1.1 去重相關(guān)研究

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

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

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

(1)

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

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

1.2 數(shù)據(jù)結(jié)構(gòu)分析

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

表1 AVL樹與紅黑樹性能對(duì)比

2 系統(tǒng)模型

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

圖1 系統(tǒng)結(jié)構(gòu)圖

系統(tǒng)結(jié)構(gòu)三個(gè)部分的作用如下：

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

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

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

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

進(jìn)程日志管理器中的兩個(gè)記錄霧節(jié)點(diǎn)進(jìn)程和當(dāng)前虛擬機(jī)可用容量的兩張列表內(nèi)容的樣例，如表3、表4所示。

表3 虛擬機(jī)資源占用表

表4 服務(wù)(請(qǐng)求)進(jìn)程表

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

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

3 基于霧存儲(chǔ)的去重方案

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

3.1 方案流程

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

圖2 方案流程圖

3.2 索引表

通過將數(shù)據(jù)指紋進(jìn)行哈希計(jì)算得到索引值(由0到n構(gòu)成的整數(shù))。將數(shù)據(jù)分成非重疊等分?jǐn)?shù)據(jù)塊b1,b2,…,bn。運(yùn)用MD5哈希算法計(jì)算每個(gè)指紋，f1=h(b1),f2=h(b2),…,fn=h(bn)。將數(shù)據(jù)指紋再次進(jìn)行哈希計(jì)算，得到整數(shù)型索引值，i1=h(f1),i2=h(f2),…,in=h(fn)。用戶查詢?nèi)哂鄶?shù)據(jù)塊時(shí)，計(jì)算該數(shù)據(jù)塊的索引值，查詢?cè)撍饕迪碌闹讣y表。遍歷索引表的時(shí)間復(fù)雜度為O(1)，索引表如圖3所示。

圖3 索引表生成

3.3 基于紅黑樹的指紋查詢

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

圖4 指紋的插入與查詢

3.4 內(nèi)存中持久化保存指紋表

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

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

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

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

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

等分?jǐn)?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}

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

算法2介紹了指紋和循環(huán)冗余碼的生成過程。等分后的數(shù)據(jù)塊作為輸入。MD5、SHA-1、SHA-256都是目前較為常用的散列算法，我們選擇生成指紋較小的MD5算法，得到f1=h(b1),f2=h(b2),…,fn=h(bn)。我們選擇應(yīng)用最廣泛的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ù)塊指紋作為輸入，重哈希確定索引表中索引值的位置，遍歷索引值對(duì)應(yīng)的指紋表，若沒有相同的指紋，確定該數(shù)據(jù)塊為非重復(fù)塊，指紋插入指紋表中。若存在相同指紋，通過比較數(shù)據(jù)塊的CRC值判斷是否存在哈希沖突情況，如果兩個(gè)數(shù)據(jù)塊的CRC值相同，則為重復(fù)數(shù)據(jù)塊，返回其數(shù)據(jù)塊所在地址指針，反之，則為非重復(fù)數(shù)據(jù)塊，將該數(shù)據(jù)塊插入其指紋所在的鏈表中。

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

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

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

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

索引值對(duì)應(yīng)的紅黑樹：T

計(jì)算索引的二次哈希公式：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對(duì)應(yīng)的紅黑樹

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

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

//地址指針

else

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

end if

else

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

end if

end for

end for

end

4 實(shí)驗(yàn)分析

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

圖5 emacs-20.7指紋查詢時(shí)間

圖6 gcc-3.4.1指紋查詢時(shí)間

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

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

圖7 emacs-20.7運(yùn)行時(shí)間

圖8 gcc-3.4.1運(yùn)行時(shí)間

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

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

圖9 索引表對(duì)時(shí)間的影響

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

表5 方案性能對(duì)比

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

5 結(jié) 語

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

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