姚文斌，葉鵬迪，李小勇，常靜坤

(1.北京郵電大學(xué) 智能通信軟件與多媒體北京市重點(diǎn)實(shí)驗(yàn)室，北京 100876；2.北京郵電大學(xué) 計(jì)算機(jī)學(xué)院，北京 100876；3.中國(guó)鐵道科學(xué)研究院 機(jī)車(chē)車(chē)輛研究所，北京 100081；4.北京郵電大學(xué) 可信分布式計(jì)算與服務(wù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100876)

1 引言

隨著信息量的爆炸式增長(zhǎng)，數(shù)據(jù)占用空間及帶寬越來(lái)越大，企業(yè)面臨的快速備份和恢復(fù)的時(shí)間點(diǎn)越來(lái)越多，管理、保存、傳輸數(shù)據(jù)的成本及數(shù)據(jù)中心空間和電源的耗費(fèi)也變得越來(lái)越昂貴。研究發(fā)現(xiàn)，應(yīng)用系統(tǒng)所保存的數(shù)據(jù)，高達(dá)60%是冗余的，而且隨著時(shí)間的推移會(huì)變得越來(lái)越嚴(yán)重，重復(fù)數(shù)據(jù)刪除技術(shù)受到越來(lái)越多的關(guān)注。

常用的基于塊的重復(fù)數(shù)據(jù)刪除算法將數(shù)據(jù)切分成定長(zhǎng)或可變長(zhǎng)的數(shù)據(jù)塊，并計(jì)算每個(gè)數(shù)據(jù)塊的散列值作為數(shù)據(jù)塊指紋，擁有相同指紋的數(shù)據(jù)塊即被認(rèn)為是重復(fù)的。這種基于塊的重復(fù)數(shù)據(jù)刪除算法對(duì)那些變化緩慢、尤其是修改較少的備份數(shù)據(jù)具有較好的效果。然而隨著數(shù)據(jù)集的增大，數(shù)據(jù)塊指紋等元數(shù)據(jù)信息會(huì)迅速超過(guò)內(nèi)存容量，并且由于散列算法的天然隨機(jī)性，很難對(duì)這些指紋實(shí)現(xiàn)有效的緩存，容易造成頻繁訪(fǎng)問(wèn)磁盤(pán)、降低重復(fù)數(shù)據(jù)刪除的性能。

為了解決數(shù)據(jù)塊指紋檢索過(guò)程中面臨磁盤(pán)瓶頸問(wèn)題，DDFS[1]、Sparse Indexing[2]提出通過(guò)利用備份數(shù)據(jù)流中的數(shù)據(jù)塊局部性特征來(lái)構(gòu)建內(nèi)存中的查重索引，借此提高塊指紋檢索的命中率，減少磁盤(pán)操作。Extreme Binning[3]、Silo[4]和重復(fù)數(shù)據(jù)刪除系統(tǒng)[5～7]通過(guò)比較數(shù)據(jù)對(duì)象之間的相似性，將與待去重?cái)?shù)據(jù)對(duì)象較為相似的數(shù)據(jù)對(duì)象的塊指紋數(shù)據(jù)讀入內(nèi)存來(lái)構(gòu)建查重索引，在數(shù)據(jù)局部性特征較少的情況下，也能解決指紋檢索面臨磁盤(pán)瓶頸問(wèn)題。然而，常用的相似數(shù)據(jù)檢測(cè)算法如 shingle detection[8]、Bloom filter[9]都是利用較小的數(shù)據(jù)片段來(lái)代表原始數(shù)據(jù)對(duì)象以實(shí)現(xiàn)文件間的相似性檢測(cè)，這些片段的長(zhǎng)度與數(shù)據(jù)對(duì)象大小相關(guān)，在大文件較多的環(huán)境下，所產(chǎn)生的較長(zhǎng)的數(shù)據(jù)片段會(huì)加重存儲(chǔ)資源開(kāi)銷(xiāo)。

CDFS[10]基于定長(zhǎng)的traits[11]指紋來(lái)計(jì)算數(shù)據(jù)對(duì)象之間的相似性。Simdedup[12]基于simhash[13]算法，用simhash指紋值來(lái)代表原始數(shù)據(jù)對(duì)象，通過(guò)比較simhash指紋值來(lái)計(jì)算數(shù)據(jù)對(duì)象之間的相似性，并基于相似數(shù)據(jù)對(duì)象的塊指紋信息來(lái)構(gòu)建查重緩存，減少磁盤(pán)讀寫(xiě)次數(shù)，由于simhash指紋值的長(zhǎng)度固定且極小，因此可以將大量數(shù)據(jù)對(duì)象的指紋索引保存在內(nèi)存中作為相似索引，實(shí)現(xiàn)在保持較少的額外系統(tǒng)資源開(kāi)銷(xiāo)的基礎(chǔ)上，提高重復(fù)數(shù)據(jù)刪除效率。

然而，每個(gè)重復(fù)數(shù)據(jù)刪除系統(tǒng)都需要額外的空間來(lái)存儲(chǔ)刪重過(guò)程中產(chǎn)生元數(shù)據(jù)信息。例如清單文件，其中保存著包含數(shù)據(jù)塊指紋值及指向該數(shù)據(jù)塊所在的磁盤(pán)存儲(chǔ)位置的指針的數(shù)據(jù)塊描述符。通過(guò)這些清單文件，順序讀取數(shù)據(jù)塊描述符，同時(shí)加載并串聯(lián)描述符所指向的數(shù)據(jù)塊，便可以重構(gòu)數(shù)據(jù)內(nèi)容。這些數(shù)據(jù)塊描述符和標(biāo)準(zhǔn)文件系統(tǒng)中的數(shù)據(jù)塊指針的不同之處就是大小的不同，一般文件系統(tǒng)中的數(shù)據(jù)塊指針都是8 byte，而重復(fù)數(shù)據(jù)刪除系統(tǒng)中的文件描述符一般至少是20 byte。

現(xiàn)有的對(duì)重復(fù)數(shù)據(jù)刪除技術(shù)的研究往往會(huì)忽略這些元數(shù)據(jù)信息，認(rèn)為這些文件一般不會(huì)成為系統(tǒng)吞吐量的性能瓶頸。然而，隨著數(shù)據(jù)集的增加，元數(shù)據(jù)也會(huì)隨之增長(zhǎng)，并會(huì)占用大量的存儲(chǔ)空間。在重復(fù)數(shù)據(jù)刪除技術(shù)的幫助下，存儲(chǔ)數(shù)據(jù)所需的磁盤(pán)空間隨時(shí)間緩慢增長(zhǎng)，如Zhu等[1]通過(guò)應(yīng)用重復(fù)數(shù)據(jù)刪除技術(shù)，在每天備份的環(huán)境下，對(duì)數(shù)據(jù)達(dá)到了近40:1的壓縮比，數(shù)據(jù)對(duì)存儲(chǔ)空間的需求逐步趨緩。而清單數(shù)據(jù)等元數(shù)據(jù)信息卻會(huì)隨著去重次數(shù)的增加而穩(wěn)步增長(zhǎng)。假設(shè)一個(gè)數(shù)據(jù)塊大小為4 KB，那么1 TB的數(shù)據(jù)就至少需要5 GB的空間來(lái)存儲(chǔ)這些清單文件。在備份系統(tǒng)環(huán)境下，假如每周執(zhí)行一次全備份，且保留期為52周，那么對(duì)于20 TB的備份數(shù)據(jù)來(lái)說(shuō)，就會(huì)產(chǎn)生至少5 TB的清單數(shù)據(jù)。因此，在海量數(shù)據(jù)環(huán)境下，保存這些元數(shù)據(jù)信息將會(huì)產(chǎn)生巨大的額外存儲(chǔ)資源開(kāi)銷(xiāo)。

Simdedup這類(lèi)基于相似性的重復(fù)數(shù)據(jù)刪除算法對(duì)每個(gè)已去重?cái)?shù)據(jù)對(duì)象都會(huì)產(chǎn)生查重元數(shù)據(jù)，供以后的重復(fù)數(shù)據(jù)刪除操作使用，由于數(shù)據(jù)對(duì)象之間存在較高的相似性，那么，所產(chǎn)生的清單文件等元數(shù)據(jù)也會(huì)包含大量的相似數(shù)據(jù)，增加了存儲(chǔ)資源開(kāi)銷(xiāo)。此外，隨著數(shù)據(jù)集持續(xù)增大，用于檢測(cè)數(shù)據(jù)相似性的相似索引的數(shù)據(jù)量也會(huì)不斷增加并最終導(dǎo)致索引過(guò)大以致于難以存放在內(nèi)存中，影響相似數(shù)據(jù)檢索的效率，進(jìn)而影響重復(fù)數(shù)據(jù)刪除效率。在重復(fù)數(shù)據(jù)刪除過(guò)程中，使用更大的平均數(shù)據(jù)塊固然能夠減少數(shù)據(jù)塊數(shù)量，降低清單文件的大小，然而，這種方法會(huì)導(dǎo)致重復(fù)數(shù)據(jù)刪除率的下降[14～16]。隨著人們對(duì)數(shù)據(jù)資源的愈發(fā)重視，全備份的時(shí)間間隔越來(lái)越短，且數(shù)據(jù)保存周期越來(lái)越長(zhǎng)，清單文件等元數(shù)據(jù)信息的壓縮已經(jīng)成為重復(fù)數(shù)據(jù)刪除系統(tǒng)中不容忽視的環(huán)節(jié)。

常用的元數(shù)據(jù)壓縮技術(shù)中，Zero-Chunk壓縮技術(shù)[17,18]只能通過(guò)對(duì)內(nèi)容全是0的數(shù)據(jù)塊給予較短的編碼，來(lái)間接對(duì)元數(shù)據(jù)進(jìn)行壓縮，無(wú)法處理其他類(lèi)型數(shù)據(jù)塊?；谥貜?fù)序列的壓縮技術(shù)[19～21]只能通過(guò)合并重復(fù)序列來(lái)間接降低元數(shù)據(jù)大小，無(wú)法應(yīng)對(duì)實(shí)際環(huán)境中，數(shù)據(jù)塊本身存在冗余，但序列相對(duì)較亂的情況。基于統(tǒng)計(jì)的壓縮技術(shù)[14,22]除了維護(hù)數(shù)據(jù)塊使用率索引外，還需要維護(hù)額外的編碼索引，該索引的存放位置是一個(gè)需要權(quán)衡的問(wèn)題，如果存儲(chǔ)在內(nèi)存中，固然會(huì)提高訪(fǎng)問(wèn)速度，但卻會(huì)限制編碼的數(shù)量，如果存儲(chǔ)在磁盤(pán)上，編碼的數(shù)量不會(huì)有太多限制，但卻會(huì)需要額外的I/O操作。因此，在不對(duì)重復(fù)數(shù)據(jù)刪除比造成太大影響的前提下，消除查重元數(shù)據(jù)集中重復(fù)度較高的樣本，降低元數(shù)據(jù)集的數(shù)量，使在海量數(shù)據(jù)環(huán)境下，依然維持較低的系統(tǒng)資源開(kāi)銷(xiāo)，是亟待解決的問(wèn)題。

本文在Simdedup的基礎(chǔ)上，基于壓縮近鄰[23]的思想，提出了查重元數(shù)據(jù)的去冗算法Dedup2，在維持重復(fù)數(shù)據(jù)刪除比的同時(shí)，可以有效降低用于查重的數(shù)據(jù)量，使資源開(kāi)銷(xiāo)保持在一個(gè)較低的位置。

2 Dedup2設(shè)計(jì)思路

Simdedup進(jìn)行重復(fù)數(shù)據(jù)刪除操作時(shí)，由于數(shù)據(jù)段之間存在較高的相似性，那么，所產(chǎn)生的元數(shù)據(jù)信息中也必然包含大量的相似數(shù)據(jù)。

因此，Simdedup中元數(shù)據(jù)壓縮面臨的問(wèn)題的描述如圖1所示。圖中的每個(gè)點(diǎn)都表示一個(gè)對(duì)應(yīng)的數(shù)據(jù)段，2個(gè)數(shù)據(jù)段距離的遠(yuǎn)近表示兩者之間相似度的高低，那么按照兩兩之間的相似性，可以對(duì)數(shù)據(jù)段進(jìn)行聚類(lèi)，最后獲得k個(gè)類(lèi)，圖1所示為k=3的情況。由于類(lèi)中的數(shù)據(jù)段擁有較高的相似性，那么可以合并相似度高的數(shù)據(jù)段的清單文件，消除其中的重復(fù)數(shù)據(jù)塊指紋描述符，以減少清單文件大小。

圖1 問(wèn)題描述

然而，單純通過(guò)聚類(lèi)的方法無(wú)法處理相似索引SFIndex，該索引數(shù)據(jù)量的增加依然會(huì)給系統(tǒng)帶來(lái)較大的負(fù)擔(dān)，因此需要針對(duì)各個(gè)類(lèi)中數(shù)據(jù)對(duì)象的重要性，消除SFIndex中對(duì)重復(fù)數(shù)據(jù)刪除率貢獻(xiàn)相對(duì)較小的數(shù)據(jù)段的指紋。

對(duì)于一個(gè)新的數(shù)據(jù)段來(lái)說(shuō)，基于Simdedup算法，其相似特征會(huì)出現(xiàn)2種情況，分別如圖1中的黑點(diǎn)S1和S2所示。其中，黑點(diǎn)S1表示該數(shù)據(jù)段在平面中的位置處于 3個(gè)類(lèi)邊界的外部，其最相似數(shù)據(jù)段就是與其距離最近的分屬于不同類(lèi)別幾個(gè)白點(diǎn)，這些白點(diǎn)都在類(lèi)的邊界部位；黑點(diǎn)S2表示該數(shù)據(jù)段在平面中的位置處于類(lèi)的內(nèi)部，其最相似數(shù)據(jù)段就是與其距離最近的同一類(lèi)中的幾個(gè)白點(diǎn)，由于同類(lèi)中數(shù)據(jù)對(duì)象相似度較高，所以選擇類(lèi)邊界的數(shù)據(jù)段來(lái)構(gòu)建查重緩存，也能提供較好的重復(fù)數(shù)據(jù)刪除率。

因此，消除 Simdedup元數(shù)據(jù)中處于類(lèi)中心位置的數(shù)據(jù)段信息，盡可能保留類(lèi)邊界位置的數(shù)據(jù)段信息，便能夠?qū)崿F(xiàn)元數(shù)據(jù)的壓縮，并縮小相似索引SFIndex，使之能夠完整存放于內(nèi)存中，提高重復(fù)數(shù)據(jù)刪除效率，同時(shí)維持較低的系統(tǒng)資源開(kāi)銷(xiāo)。

壓縮近鄰（CNN, condensed nearest neighbor rule）算法主要用于尋找樣本的一致子集。對(duì)于一個(gè)集合E的一個(gè)子集E'，如果利用最近鄰算法（1-NN），E'中樣本可完全正確地分類(lèi)E中的樣本，那么E'就是集合E的一致子集。從集合E中創(chuàng)建一致子集E'時(shí)，首先將所有少數(shù)類(lèi)中的樣本以及隨機(jī)選取的一個(gè)多數(shù)類(lèi)中的樣本加入E'中進(jìn)行初始化。然后用E'中的樣本以最近鄰算法（1-NN）對(duì)E中樣本分類(lèi)，將所有錯(cuò)分的樣本加入到E'中。

壓縮近鄰算法保留了多數(shù)類(lèi)中邊界附近的樣本，同時(shí)去掉了多數(shù)類(lèi)中遠(yuǎn)離邊界的樣本，使一致子集在保留最少量樣本的條件下，仍能對(duì)原有全部樣本用最近鄰法正確分類(lèi)，那么也就能夠?qū)ΥR(shí)別樣本進(jìn)行分類(lèi)，并保持正常識(shí)別率。因此，其設(shè)計(jì)思想和 Simdedup消除相似度較高的元數(shù)據(jù)，降低查重元數(shù)據(jù)大小后，仍需保持相近重復(fù)數(shù)據(jù)刪除率的需求是等同的。

基于壓縮近鄰的思想，從相似度過(guò)高的元數(shù)據(jù)對(duì)重復(fù)數(shù)據(jù)刪除率影響有限的角度出發(fā)，提出了查重元數(shù)據(jù)去冗算法Dedup2，首先對(duì)查重?cái)?shù)據(jù)集進(jìn)行聚類(lèi)，然后利用壓縮近鄰算法獲得查重子集，并基于該查重子集消除相似度較高的元數(shù)據(jù)，進(jìn)而降低查重索引大小。消除相似度較高的元數(shù)據(jù)，在維持重復(fù)數(shù)據(jù)刪除率的同時(shí)，可以有效降低元數(shù)據(jù)的數(shù)量，進(jìn)一步降低系統(tǒng)資源開(kāi)銷(xiāo)。

3 Dedup2系統(tǒng)架構(gòu)

重復(fù)數(shù)據(jù)刪除算法的系統(tǒng)整體結(jié)構(gòu)如圖2所示。Simdedup中查重所需要的元數(shù)據(jù)信息數(shù)據(jù)被分成 2個(gè)索引分別保存，分別是simhash指紋索引（SFIndex）和數(shù)據(jù)塊指紋索引（CFIndex）。其中，SFIndex保存所有的數(shù)據(jù)段的simhash指紋，而每個(gè)數(shù)據(jù)段所包含的所有數(shù)據(jù)塊的指紋值將存儲(chǔ)在磁盤(pán)的一個(gè)清單文件中，這些清單文件信息則保存在CFIndex里面。由于Simdedup對(duì)每個(gè)已去重的數(shù)據(jù)對(duì)象都會(huì)產(chǎn)生這2種元數(shù)據(jù)信息，并保存在查重索引中，因此，隨著數(shù)據(jù)集持續(xù)增大，查重索引的數(shù)據(jù)量也會(huì)不斷增加，最終必然導(dǎo)致查重索引無(wú)法有效存放在內(nèi)存中。

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

Dedup2通過(guò)離線(xiàn)處理的方式對(duì)查重的元數(shù)據(jù)信息進(jìn)行周期性去冗，獲得較小的查重子集。通過(guò)消除SFIndex中冗余度較高的元素，可以獲得較小的 simhash指紋子索引 Sub-SFIndex。同時(shí)，合并CFIndex中冗余度較高的清單文件，可以獲得較小的清單文件子索引Sub-CFIndex。

對(duì)一個(gè)數(shù)據(jù)對(duì)象作重復(fù)數(shù)據(jù)刪除操作時(shí)，每個(gè)數(shù)據(jù)段都利用可變長(zhǎng)分塊算法進(jìn)行切塊，并利用SHA-1算法計(jì)算該數(shù)據(jù)段所包含數(shù)據(jù)塊的指紋值?；谒玫降臄?shù)據(jù)塊，可以計(jì)算得到每個(gè)數(shù)據(jù)段的simhash指紋。若用于構(gòu)建內(nèi)存中數(shù)據(jù)塊指紋索引的數(shù)據(jù)段個(gè)數(shù)設(shè)為w，那么通過(guò)相似性檢索，比較該指紋和Sub-SFIndex中的其他指紋，可以按照相似度的高低，獲得與待去重?cái)?shù)據(jù)段最相似的w個(gè)數(shù)據(jù)段?；谶@些數(shù)據(jù)段，便可以通過(guò) Sub-CFIndex檢索清單文件，獲得各數(shù)據(jù)段對(duì)應(yīng)的塊指紋信息，進(jìn)而將這些指紋值讀到內(nèi)存中，構(gòu)建查重緩存。最后，比對(duì)新數(shù)據(jù)段的指紋值和查重緩存中的指紋值，就可以消除重復(fù)的數(shù)據(jù)塊。

Dedup2能夠消除查重元數(shù)據(jù)中的重復(fù)數(shù)據(jù)，大大降低查重索引的大小，從而使查重索引能更好地存放在內(nèi)存中，減少磁盤(pán)訪(fǎng)問(wèn)，保證數(shù)據(jù)塊指紋檢索速度和較低的系統(tǒng)資源開(kāi)銷(xiāo)，同時(shí)，保持相似的重復(fù)數(shù)據(jù)刪除比。

4 Dedup2算法描述

Dedup2基于壓縮近鄰的思想，以消除元數(shù)據(jù)中的冗余信息，獲取精簡(jiǎn)的查重子集為目的，整個(gè)算法流程如圖3所示，可以分為聚類(lèi)階段和去冗階段2個(gè)階段。該方法首先將查重?cái)?shù)據(jù)集聚成k類(lèi){C1,C2, …,Ck}，從每一類(lèi)別樣本中各隨機(jī)選擇一個(gè)樣本以構(gòu)成初始子集，然后按最近鄰原則用該子集對(duì)剩余訓(xùn)練集分類(lèi)，并將誤分樣本加入查重子集，遍歷整個(gè)查重?cái)?shù)據(jù)集后，便可獲得所需查重子集。

圖3 Dedup2流程

基于該查重子集，消除元數(shù)據(jù)中對(duì)重復(fù)數(shù)據(jù)刪除率影響有限的樣本，進(jìn)而降低元數(shù)據(jù)的大小，從而使simhash指紋索引能更好地存放在內(nèi)存中，減少磁盤(pán)訪(fǎng)問(wèn)，保證數(shù)據(jù)塊指紋檢索速度和較低的系統(tǒng)資源開(kāi)銷(xiāo)，同時(shí)，保持相似的重復(fù)數(shù)據(jù)刪除比。下面對(duì)Dedup2算法的聚類(lèi)階段和去冗階段分別作詳細(xì)描述。

4.1 聚類(lèi)階段

由于在使用壓縮近鄰算法前需要對(duì)各個(gè)元數(shù)據(jù)進(jìn)行歸類(lèi)，同時(shí)因?yàn)樵獢?shù)據(jù)的主要指標(biāo)是simhash值，且無(wú)法通過(guò)k-means聚類(lèi)算法對(duì)simhash值計(jì)算歐氏距離，所以需通過(guò)k中心點(diǎn)聚類(lèi)算法進(jìn)行歸類(lèi)。partitioning around medoids (PAM)算法是較常用的k中心點(diǎn)聚類(lèi)算法，具有數(shù)據(jù)頑健性強(qiáng)、聚類(lèi)結(jié)果與輸入順序無(wú)關(guān)以及對(duì)小的數(shù)據(jù)集聚類(lèi)效果明顯等特點(diǎn)。

為了后續(xù)描述清晰，對(duì)后續(xù)所用符號(hào)進(jìn)行統(tǒng)一定義：定義待查重?cái)?shù)據(jù)的simhash指紋集合為S={s1,s2, …,sn}；定義聚類(lèi)前的簇為C={C1,C2, …,Ck}，聚類(lèi)過(guò)程完成后的簇為C'={C1',C2', …,Ck'}；定義2個(gè)相似數(shù)據(jù)段之間的距離度量為dist(si，sj)，2個(gè)simhash指紋值的海明距離為Hamming(si，sj)。

本文選用 PAM 算法對(duì)元數(shù)據(jù)進(jìn)行聚類(lèi)，以SFIndex中所保存的 simhash指紋值信息來(lái)表示一個(gè)數(shù)據(jù)對(duì)象，獲得查重?cái)?shù)據(jù)的指紋集合S={s1,s2, …,sn}。然后，對(duì)集合S中的數(shù)據(jù)對(duì)象進(jìn)行聚類(lèi)，將數(shù)據(jù)段分為k類(lèi)C'={C1',C2', …,Ck'}。

2個(gè)相似數(shù)據(jù)段之間的距離度量表示為兩者simhash指紋值的海明距離，即

所以，整個(gè)聚類(lèi)過(guò)程可以描述如下。

1) 從S中任意選擇k個(gè)代表對(duì)象{m1,m2, …,mk}作為初始的中心點(diǎn)。

2) 指派每個(gè)剩余對(duì)象給離它最近的中心點(diǎn)所代表的簇C={C1,C2, …,Ck}。

3) 對(duì)于每一個(gè)簇Ci，i∈{1, 2, …,k}，遍歷簇中的li個(gè)非中心點(diǎn)對(duì)象sj。

a) 計(jì)算用sj代替中心點(diǎn)mi的總代價(jià)

b) 選擇總代價(jià)最小的那個(gè)對(duì)象作為新的中心點(diǎn)；

4) 重復(fù)2)，3)，直到k個(gè)中心點(diǎn)不再發(fā)生變化。

最終所獲得的k個(gè)簇C'={C1',C2', …,Ck'}，就是所需要的k類(lèi)相似數(shù)據(jù)段。

4.2 去冗階段

去冗階段利用壓縮近鄰算法，消除相似度過(guò)高的元數(shù)據(jù)。這里定義壓縮后的查重子集S'={s1',s2', …,sv'}。去冗余階段的過(guò)程可以描述如下。

1) 同樣以數(shù)據(jù)段的simhash指紋值指代各個(gè)數(shù)據(jù)段，獲取SFIndex中的所有數(shù)據(jù)段simhash指紋集合S={s1,s2, …,sn}。

2) 對(duì)集合S設(shè)置2個(gè)存儲(chǔ)器store和grabbag。

3) 將S的所有樣本放入grabbag中。

4) 從grabbag中隨機(jī)取一個(gè)數(shù)據(jù)段simhash指紋s1，放入store。

5) 從grabbag中隨機(jī)取出一個(gè)數(shù)據(jù)段simhash指紋sk，用store中的simhash指紋做參考集。

a) 采用近鄰法對(duì)sk進(jìn)行分類(lèi)，從store中找到一個(gè)與sk最近的snb，若snb∈Ci，且sk∈Ci，i∈{1,2, …,k}，則認(rèn)為分類(lèi)正確，刪除sk；

b) 否則，sk作為新的一個(gè)類(lèi)別放入store中。

6) 對(duì)grabbag中所有樣本進(jìn)行步驟5)的操作，直到grabbag為空。

7) 此時(shí)，store中存放的就是壓縮后的查重子集S'={s1',s2', …,sv'}。根據(jù)查重子集S'中的元素，通過(guò)消除SFIndex中冗余度較高的元素，同時(shí)，合并CFIndex中冗余度較高的cfs清單文件，以實(shí)現(xiàn)對(duì)元數(shù)據(jù)進(jìn)行壓縮，進(jìn)而獲得新的Sub-SFIndex和Sub-CFIndex。

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

為了驗(yàn)證Dedup2算法的有效性，利用一臺(tái)計(jì)算機(jī)作為平臺(tái)進(jìn)行了一系列的實(shí)驗(yàn)，其配置如下：CPU為 Intel Core Duo 2.93 GHz，內(nèi)存為2 GB，磁盤(pán)為SATA 5 600轉(zhuǎn)。在此實(shí)驗(yàn)平臺(tái)上利用Java對(duì)算法進(jìn)行了編碼實(shí)現(xiàn)，利用Linux源碼包作為待去重?cái)?shù)據(jù)，對(duì)查重?cái)?shù)據(jù)的去冗效果，讓 Simdedup重復(fù)數(shù)據(jù)刪除算法分別運(yùn)行在原查重?cái)?shù)據(jù)集和通過(guò)Dedup2產(chǎn)生的查重子集上，從元數(shù)據(jù)去重比和重復(fù)數(shù)據(jù)刪除比這2個(gè)方面進(jìn)行了對(duì)比實(shí)驗(yàn)。

5.1 元數(shù)據(jù)去冗分析

實(shí)驗(yàn)通過(guò)查重索引去重比，即已消除的冗余數(shù)據(jù)占原查重?cái)?shù)據(jù)集的比重，來(lái)驗(yàn)證Dedup2對(duì)查重?cái)?shù)據(jù)集的去冗效果。在不同聚類(lèi)個(gè)數(shù)k的條件下，在2個(gè)數(shù)據(jù)集中進(jìn)行實(shí)驗(yàn)，獲得的元數(shù)據(jù)去重比如圖4所示。其中數(shù)據(jù)集1包含40 GB的Linux源碼包，數(shù)據(jù)集2中包含80 GB的Linux源碼包。

圖4 查重子集占原查重?cái)?shù)據(jù)的比重

由實(shí)驗(yàn)結(jié)果可見(jiàn)，總體來(lái)看，Dedup2對(duì)原查重?cái)?shù)據(jù)集的去冗效果可以達(dá)到50%以上。聚類(lèi)個(gè)數(shù)k的越小，最后產(chǎn)生查重子集的也越小，但彼此間的差距并不大。這是由于聚類(lèi)個(gè)數(shù)k越大，那么聚類(lèi)得到的類(lèi)別也越多，那么在去冗階段采用近鄰法對(duì)某個(gè)樣本進(jìn)行分類(lèi)時(shí)，尤其是那些位于2個(gè)類(lèi)邊界上的樣本，發(fā)生錯(cuò)分的概率也會(huì)相應(yīng)增加，因此，該樣本就會(huì)被保留下來(lái)，進(jìn)而影響了去冗效果。

此外k=8去重比相對(duì)k=10的時(shí)候要高一點(diǎn)。這是由于PAM算法對(duì)初始中心是隨機(jī)選擇的，聚類(lèi)結(jié)果會(huì)隨著初始點(diǎn)選擇的變化而改變，容易陷入局部最優(yōu)的情況，進(jìn)而會(huì)影響最后的聚類(lèi)效果。而壓縮近鄰算法基于聚類(lèi)的結(jié)果運(yùn)行，那么去冗效果也相應(yīng)的會(huì)受到影響。k=8與k=10的類(lèi)別個(gè)數(shù)相差不大，就比較容易發(fā)生這種因?yàn)榫垲?lèi)效果的差異，而導(dǎo)致聚類(lèi)個(gè)數(shù)k的較小，但最后冗余數(shù)據(jù)量也較少的情況。但從大趨勢(shì)來(lái)看，例如比較k=5、k=10以及k=15這三者，還是能清晰地得出聚類(lèi)個(gè)數(shù)k越小，消除的冗余數(shù)據(jù)量越高的結(jié)論。

此外，還可以發(fā)現(xiàn)當(dāng)數(shù)據(jù)集增大時(shí)，最后產(chǎn)生查重子集的也越小。這說(shuō)明數(shù)據(jù)集越大，數(shù)據(jù)中的冗余數(shù)據(jù)越多，便越能產(chǎn)生更好的去冗效果。

5.2 重復(fù)數(shù)據(jù)刪除比分析

重復(fù)數(shù)據(jù)刪除比的實(shí)驗(yàn)在數(shù)據(jù)集1上進(jìn)行。在對(duì)新數(shù)據(jù)段執(zhí)行重復(fù)數(shù)據(jù)刪除操作時(shí)，用于構(gòu)建內(nèi)存中數(shù)據(jù)塊指紋索引的數(shù)據(jù)段個(gè)數(shù)w越多，那么指紋索引中所包含的已存儲(chǔ)數(shù)據(jù)塊指紋信息也越多，便越能找出重復(fù)數(shù)據(jù)。

在用于構(gòu)建查重緩存的最相似數(shù)據(jù)段數(shù)量w=3，而聚類(lèi)個(gè)數(shù)k不同的條件下產(chǎn)生多個(gè)查重子集，基于這些查重子集和原始查重?cái)?shù)據(jù)集，分別對(duì)數(shù)據(jù)對(duì)象完成去重操作的重復(fù)數(shù)據(jù)刪除率對(duì)比結(jié)果如圖5所示。從實(shí)驗(yàn)結(jié)果可以看出聚類(lèi)個(gè)數(shù)k不同對(duì)重復(fù)數(shù)據(jù)刪除比沒(méi)有特定的影響。此外，圖中重復(fù)數(shù)據(jù)刪除比最低的是基于k=15時(shí)獲取的查重子集所獲得，為60.3%；而重復(fù)數(shù)據(jù)刪除比最高的則是基于原始查重?cái)?shù)據(jù)集所獲得，為61.4%，該結(jié)果說(shuō)明雖然查重子集的大小僅為原始查重?cái)?shù)據(jù)集的一半不到，但依然能夠獲得近似的重復(fù)數(shù)據(jù)刪除比，進(jìn)而證明了Dedup2的有效性。

在所用的查重子集為聚類(lèi)個(gè)數(shù)k=5時(shí)生成，而用于構(gòu)建查重緩存的最相似數(shù)據(jù)段數(shù)量w不同的條件下，基于該查重子集和原始查重索引，分別對(duì)數(shù)據(jù)對(duì)象完成去重操作后的重復(fù)數(shù)據(jù)刪除比對(duì)比結(jié)果如圖6所示。對(duì)比結(jié)果說(shuō)明隨著用于構(gòu)建查重緩存的最相似數(shù)據(jù)段數(shù)量w增加，利用查重子集進(jìn)行重復(fù)數(shù)據(jù)刪除操作時(shí)，重復(fù)數(shù)據(jù)刪除比也會(huì)逐步升高，w=3之前的上升幅度較高，之后仍然會(huì)緩慢上升。而當(dāng)利用原查重索引進(jìn)行重復(fù)數(shù)據(jù)刪除操作時(shí)，同樣w=3之前的上升幅度較高，然而在w=5之后，重復(fù)數(shù)據(jù)刪除比則基本停止上升。這便說(shuō)明了原查重索引中，w=5之后獲得的查重?cái)?shù)據(jù)與之前的數(shù)據(jù)重復(fù)度過(guò)高，所以雖然構(gòu)建查重緩存的最相似數(shù)據(jù)段數(shù)量w增加了，但對(duì)重復(fù)數(shù)據(jù)刪除比卻沒(méi)有幫助。這也證明了Dedup2元數(shù)據(jù)去冗的有效性。

圖5 k不同條件下的重復(fù)數(shù)據(jù)刪除比（w=3）

圖6 w不同條件下的重復(fù)數(shù)據(jù)刪除比

6 結(jié)束語(yǔ)

本文提出一種基于壓縮近鄰的查重元數(shù)據(jù)去冗算法Dedup2，該算法定期對(duì)用于查重的元數(shù)據(jù)集進(jìn)行聚類(lèi)，并在此基礎(chǔ)上利用壓縮近鄰算法去除查重元數(shù)據(jù)中的冗余數(shù)據(jù)，以獲得精簡(jiǎn)的查重子集，基于該子集消除相似度較高的元數(shù)據(jù)，進(jìn)而降低查重索引大小。結(jié)合 Simdedup重復(fù)數(shù)據(jù)刪除系統(tǒng)，可以基于文件相似性獲取子集中與待去重?cái)?shù)據(jù)對(duì)象相似度高的索引數(shù)據(jù)構(gòu)成查重緩存，以完成重復(fù)數(shù)據(jù)刪除操作。實(shí)驗(yàn)結(jié)果證明，Dedup2可以在保持近似的重復(fù)數(shù)據(jù)刪除比的前提下，有效消除查重元數(shù)據(jù)中的冗余信息，降低查重索引的大小。

[1] ZHU B, LI K, PATTERSON H.Avoiding the disk bottleneck in the data domain deduplication file system[A].Proceedings of the 6th USENIX Conference on File and Storage Technologies, USENIX Association[C].2008.1-14.

[2] LILLIBRIDGE M, ESHGHI K, BHAGWAT D,et al.Sparse indexing:large scale, inline deduplication using sampling and locality[A].Proccedings of the 7th Conference on File and Storage Technologies,USENIX Association[C].2009.111-123.

[3] BHAGWAT D, ESHGHI K, LONG D,et al.Extreme binning: scalable,parallel deduplication for chunk-based file backup[A].In Modeling,Analysis & Simulation of Computer and Telecommunication Systems,IEEE International Symposium[C].IEEE, 2009.1-9.

[4] XIA W, JIANG H, FENG D,et al.SiLo: a similarity-locality based near-exact deduplication scheme with low RAM overhead and high throughput[A].Proceedings of the 2011 USENIX Annual Technical Conference (ATC), USENIX Association[C].2011.26-28.

[5] ARONOVICH L, ASHER R, BACHMAT E,et al.The design of a similarity based deduplication system[A].Proceedings of SYSTOR 2009, The Israeli Experimental Systems Conference[C].ACM, 2009.1-14.

[6] ROMA?SKI B, HELDT ?, KILIAN W,et al.Anchor-driven subchunk deduplication[A].Proceedings of the 4th Annual International Conference on Systems and Storage[C].2011.16-28.

[7] ZHANG Z, BHAGWAT D, LITWIN W,et al.Improved deduplication through parallel binning[A].Performance Computing and Communications Conference (IPCCC), 2012 IEEE 31st International[C].2012.130-141.

[8] DOUGLIS F, IYENGAR A.Application-specific deltaencoding via resemblance detection[A].Proceedings of the 2003 USENIX Annual Technical Conference[C].San Antonio, Texas, 2003.113-126.

[9] BRODER A Z, MITZENMACHER M.Network applications of Bloom filters: a survey[J].Internet Mathematics, 2004, 1(4): 485-509.

[10] TAN L J, YAO W B, LIU Z Y.et al.CDFS: a cloud-based deduplication filesystem[J].Advanced Science Letters, American Scientific Publishers, 2012, 9(1): 855-860.

[11] TEODOSIU D, BJORNER N, GUREVICH Y,et al.Optimizing file replication over limited-bandwidth networks using remote differential compression[R].Technical Report MSR-TR-2006-157, Microsoft Research, 2006.

[12] YAO W B, YE P D.Simdedup: a new deduplication scheme based on simhash[A].In Web-Age Information Management[C].Springer Berlin Heidelberg, 2013.79-88.

[13] CHARIKAR M.Similarity estimation techniques from rounding algorithms[A].Proc 34th Annual Symposium on Theory of Computing(STOC2002)[C].2002.380-388.

[14] MEISTER D, BRINKMANN A.Multi-level comparison of data deduplication in a backup scenario[A].Proceedings of SYSTOR 2009, The Israeli Experimental Systems Conference[C].ACM, 2009.

[15] MEYER D T, BOLOSKY W J.A study of practical deduplication[J].ACM Transactions on Storage (TOS), 2012, 7(4): 14.

[16] WALLACE G, DOUGLIS F, QIAN H,et al.Characteristics of backup workloads in production systems[A].Proceedings of the Tenth USENIX Conference on File and Storage Technologies (FAST'12)[C].2012.

[17] WEI J, JIANG H, ZHOU K,et al.MAD2: a scalable high-throughput exact deduplication approach for network backup services[A].Mass Storage Systems and Technologies (MSST), 2010 IEEE 26th Symposium[C].IEEE, 2010.1-14.

[18] KAISER J, MEISTER D, BRINKMANN A,et al.Design of an exact data deduplication cluster[A].Mass Storage Systems and Technologies(MSST), 2012 IEEE 28th Symposium[C].IEEE, 2012.1-12.

[19] BALACHANDRAN S, CONSTANTINESCU C.Sequence of hashes compression in data de-duplication[A].Data Compression Conference,DCC 2008[C].IEEE, 2008.505.

[20] CONSTANTINESCU C, PIEPER J, LI T.Block size optimization in deduplication systems[A].Data Compression Conference, DCC'09[C].IEEE, 2009.442-442.

[21] ESHGHI K, LILLIBRIDGE M, WILCOCK L,et al.Jumbo store:providing efficient incremental upload and versioning for a utility rendering service[A].FAST[C].2007.123-138.

[22] MEISTER D, BRINKMANN A, Sü? T.File recipe compression in data deduplication systems[A].Proceedings of 11th USENIX Conference on File and Storage Technologies (FAST)[C].2013.175-182.

[23] HART P E.The condensed nearest neighbor rule[J].IEEE Transactions on Information Theory IT-14, 1968: 515-516.