FSD：增量壓縮中局部特征表決的快速相似性檢測(cè)

張露維，顧榮斌，李 靜，李科心

1(國(guó)網(wǎng)上海市電力公司 信息通信公司數(shù)據(jù)運(yùn)維中心,上海 200072)

2(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京 211106)

1 引 言

云計(jì)算、大數(shù)據(jù)和人工智能技術(shù)的快速發(fā)展，對(duì)海量數(shù)據(jù)的存儲(chǔ)、傳輸及備份問題提出了新的挑戰(zhàn).數(shù)據(jù)規(guī)模的快速增長(zhǎng)對(duì)數(shù)據(jù)存儲(chǔ)技術(shù)提出了更高的要求，也使得海量數(shù)據(jù)的存儲(chǔ)、傳輸和備份成為當(dāng)前的研究熱點(diǎn)之一.如電力領(lǐng)域，隨著泛在電力物聯(lián)網(wǎng)的不斷提出，各個(gè)業(yè)務(wù)領(lǐng)域的系統(tǒng)、數(shù)據(jù)等可能會(huì)面臨大量的存儲(chǔ)、傳輸及備份等工作.由于巨大的數(shù)據(jù)量，如何對(duì)這些業(yè)務(wù)系統(tǒng)的數(shù)據(jù)進(jìn)行有效的存儲(chǔ)、備份關(guān)系到整個(gè)電力系統(tǒng)的安全穩(wěn)定運(yùn)行.

數(shù)據(jù)壓縮是指在不丟失信息的前提下，縮減數(shù)據(jù)量以減少存儲(chǔ)空間[1，2]，提高傳輸、存儲(chǔ)和處理效率的一種技術(shù)方法.數(shù)據(jù)壓縮通常需要以重復(fù)數(shù)據(jù)刪除為基礎(chǔ)，其關(guān)注的主要是重復(fù)數(shù)據(jù)刪除，而當(dāng)數(shù)據(jù)之間不包含重復(fù)但又高度相關(guān)的時(shí)候效果較不明顯.增量壓縮作為一種面向非重復(fù)而又高度相似數(shù)據(jù)的壓縮方法在云計(jì)算、容災(zāi)備份等領(lǐng)域受到越來越多的重視.它通常以塊級(jí)別進(jìn)行識(shí)別和檢測(cè)相似性數(shù)據(jù)，利用安全指紋技術(shù)[3]提取相似數(shù)據(jù)的共同特征，實(shí)現(xiàn)對(duì)數(shù)據(jù)的壓縮，其過程主要包括原始數(shù)據(jù)的重復(fù)數(shù)據(jù)刪除、相似數(shù)據(jù)檢測(cè)、共同特征提取、差異性特征提取及存儲(chǔ)基準(zhǔn)數(shù)據(jù)和數(shù)據(jù)之間的映射關(guān)系等5個(gè)步驟.其中，相似性檢測(cè)是增量壓縮的核心步驟.相似性數(shù)據(jù)檢測(cè)的工作為增量壓縮提供了壓縮候選集，其檢測(cè)的結(jié)果為增量壓縮提供輸入數(shù)據(jù).

在數(shù)據(jù)塊相似性檢測(cè)方面，Broder[4]提出一種N-transform Super-Feature方法(簡(jiǎn)稱“SF方法”)，但是該方法需要花費(fèi)較多時(shí)間對(duì)提取到的數(shù)據(jù)指紋信息進(jìn)行轉(zhuǎn)換從而得到數(shù)據(jù)特征，因此效率受到限制.需要花費(fèi)較多的時(shí)間進(jìn)行特征轉(zhuǎn)換，導(dǎo)致獲得數(shù)據(jù)特征的時(shí)間復(fù)雜性較高.Zhang Yucheng[5]等人提出一種基于數(shù)據(jù)局部信息的分組方法進(jìn)行數(shù)據(jù)的相似性檢測(cè)，但在利用數(shù)據(jù)塊局部構(gòu)造超級(jí)特征時(shí)，特征分組策略不較明確.另外，該方法在進(jìn)行特征分組的時(shí)候需要對(duì)特征的大小關(guān)系進(jìn)行排序，導(dǎo)致額外的時(shí)間開銷.針對(duì)上述研究在數(shù)據(jù)塊的相似性檢測(cè)方面存在的問題，本文基于數(shù)據(jù)局部特征構(gòu)建了一種快速的特征提取方法FSD(Fast Similarity Detection)，通過將提取到的特征進(jìn)行分組和集成以獲得超級(jí)特征，從而實(shí)現(xiàn)對(duì)數(shù)據(jù)塊的快速相似性檢測(cè).本文提出的基于數(shù)據(jù)塊局部特征集成的快速相似性檢測(cè)方法FSD降低了提取特征的開銷，提高了增量壓縮中相似性檢測(cè)的效率，實(shí)現(xiàn)了對(duì)數(shù)據(jù)的高效增量壓縮.

本文章節(jié)安排如下：第1節(jié)介紹了增量壓縮中相似性檢測(cè)存在的問題；第2節(jié)介紹了增量壓縮的相關(guān)工作；第3節(jié)介紹了增量壓縮中基于局部特征集成的快速相似性檢測(cè)方法FSD；第4節(jié)中結(jié)合公開數(shù)據(jù)集，通過對(duì)比實(shí)驗(yàn)驗(yàn)證了FSD的有效性；第5節(jié)對(duì)本文方法FSD進(jìn)行總結(jié)以及未來的研究方向.

2 相關(guān)工作

數(shù)據(jù)壓縮作為一種能夠減少數(shù)據(jù)存儲(chǔ)規(guī)模的技術(shù)在圖像壓縮、數(shù)據(jù)存儲(chǔ)、文件傳輸及容災(zāi)備份系統(tǒng)中的應(yīng)用受到越來越多的關(guān)注[6-10].用于減少和消除非重復(fù)但卻高度相似數(shù)據(jù)塊之間數(shù)據(jù)冗余的增量壓縮技術(shù)是數(shù)據(jù)壓縮中較為流行的一種技術(shù).增量壓縮可以最大化地減少壓縮損失[11]，因此被廣泛使用在數(shù)據(jù)庫存儲(chǔ)[12-14].通常增量壓縮利用相似性數(shù)據(jù)檢測(cè)技術(shù)實(shí)現(xiàn)對(duì)于數(shù)據(jù)的壓縮，相似性數(shù)據(jù)的檢測(cè)通常需要對(duì)數(shù)據(jù)進(jìn)行劃分，根據(jù)數(shù)據(jù)塊的大小可將增量壓縮劃分為整文件檢測(cè)技術(shù)[15]、數(shù)據(jù)塊檢測(cè)技術(shù)[16].對(duì)于數(shù)據(jù)塊相似性檢測(cè)技術(shù)而言，又可以進(jìn)一步分為固定長(zhǎng)度分塊檢測(cè)技術(shù)[17]、基于內(nèi)容的變長(zhǎng)分塊檢測(cè)技術(shù)和滑動(dòng)窗口檢測(cè)技術(shù)[18].對(duì)于整文件檢測(cè)技術(shù)而言，其檢測(cè)相似性數(shù)據(jù)以文件為基本單位，檢測(cè)粒度過粗，不能很好地檢測(cè)出文件內(nèi)部的相思相數(shù)據(jù).固定長(zhǎng)度分塊檢測(cè)技術(shù)在進(jìn)行數(shù)據(jù)塊劃分的時(shí)候不用過多考慮數(shù)據(jù)內(nèi)容，分塊較為簡(jiǎn)單，數(shù)據(jù)處理速度較高，固定大小的分塊有利于存儲(chǔ)和管理分塊.但其分塊邊界是由絕對(duì)偏移量決定的，當(dāng)插入或者刪除數(shù)據(jù)時(shí)，會(huì)產(chǎn)生數(shù)據(jù)塊邊界偏移問題.基于內(nèi)容的變長(zhǎng)分塊檢測(cè)技術(shù)解決了插入、刪除數(shù)據(jù)邊界偏移的問題，使新增和刪除操作影響的區(qū)域被控制在很小的范圍內(nèi)，保證更多的相似性數(shù)據(jù)被檢測(cè)出.但該方法數(shù)據(jù)塊的大小是變化的且波動(dòng)較大，這會(huì)導(dǎo)致數(shù)據(jù)塊的存儲(chǔ)和處理更加的復(fù)雜.基于滑動(dòng)窗口的數(shù)據(jù)塊相似性檢測(cè)通過逐字節(jié)滑動(dòng)的方式檢測(cè)相似性數(shù)據(jù)，可以獲得很好地壓縮比.該方法進(jìn)行分塊的時(shí)候是固定大小的，存儲(chǔ)和管理更加方便.但該方法在每一個(gè)可能出現(xiàn)重復(fù)數(shù)據(jù)塊的位置均要進(jìn)行分塊查詢，時(shí)間性能較差.相似性檢測(cè)主要用于尋找候選的壓縮對(duì)象.SF方法是目前最為流行的數(shù)據(jù)塊級(jí)別的相似性檢測(cè)方法，該方法首先獲取數(shù)據(jù)塊的特征，然后根據(jù)數(shù)據(jù)塊的特征進(jìn)行相似性檢測(cè).雖然該方法能夠最大程度地檢測(cè)到高度相似的數(shù)據(jù)塊，但需要進(jìn)行大量的線性轉(zhuǎn)換以獲取數(shù)據(jù)塊的特征.后來基于局部特征的相似性檢測(cè)Finesse方法被提出，相比于SF方法，該方法在數(shù)據(jù)塊相似性檢測(cè)的速度和效率上提升了2-3倍，且提高了壓縮效率.但該方法構(gòu)建超級(jí)特征不夠明確，需要對(duì)特征進(jìn)行排序.Zhang Y等人[11]提出一種基于緩存?zhèn)浞萘鱽斫鉀Q增量壓縮中的額外計(jì)算開銷的問題.增量壓縮是建立在無重復(fù)數(shù)據(jù)的基礎(chǔ)上的，因此在某些備份系統(tǒng)中就需要考慮重復(fù)數(shù)據(jù)刪除以及數(shù)據(jù)壓縮的平衡問題.Min Fu等人[19]提出一種在備份工作負(fù)載中平衡重復(fù)數(shù)據(jù)刪除的數(shù)據(jù)壓縮方法.Xia W等人[20，21]提出了基于內(nèi)容的變長(zhǎng)分塊相似性檢測(cè)技術(shù)的重復(fù)數(shù)據(jù)刪除和利用備用數(shù)據(jù)流的細(xì)粒度局部性特征來加速增量編碼的方法.已有的增量壓縮方法在對(duì)數(shù)據(jù)進(jìn)行壓縮時(shí)需要提取數(shù)據(jù)特征，對(duì)數(shù)據(jù)特征進(jìn)行重組、轉(zhuǎn)換實(shí)現(xiàn)數(shù)據(jù)相似性檢測(cè)，然后對(duì)相似性數(shù)據(jù)進(jìn)行編碼以減少存儲(chǔ)資源的占用.在數(shù)據(jù)塊特征提取時(shí)，已有方法大多存在特征提取過程復(fù)雜、計(jì)算開銷大等問題.對(duì)于以上問題，本文提出一種基于局部特征集成的快速相似性檢測(cè)方法FSD，用于實(shí)現(xiàn)對(duì)數(shù)據(jù)塊特征的高效提取及相似性數(shù)據(jù)塊的高效檢測(cè).

3 FSD：基于局部特征集成的快速相似性檢測(cè)

隨著信息時(shí)代的不斷發(fā)展、數(shù)據(jù)的不斷積累，數(shù)據(jù)規(guī)模的快速增長(zhǎng)對(duì)數(shù)據(jù)存儲(chǔ)技術(shù)提出了更高的要求，也使得海量數(shù)據(jù)的存儲(chǔ)、傳輸和備份成為當(dāng)前的研究熱點(diǎn)之一.增量壓縮作為一種能夠改善海量數(shù)據(jù)存儲(chǔ)、備份的技術(shù)不斷得到學(xué)者的重視.SF方法雖然在一定程度上解決了增量壓縮中數(shù)據(jù)特征的提取和相似性檢測(cè)問題，但是其仍然存在特征提取過程耗時(shí)等問題.針對(duì)相似性數(shù)據(jù)檢測(cè)過程中存在的特征提取耗時(shí)、特征分組不明確、檢測(cè)效率低等問題，本文提出一種基于數(shù)據(jù)塊局部特征集成的快速相似性檢測(cè)方法，優(yōu)化了數(shù)據(jù)特征的提取的過程；利用數(shù)據(jù)特征的分組集成，實(shí)現(xiàn)了對(duì)數(shù)據(jù)塊的快速相似性檢測(cè).基于局部特征的快速相似性檢測(cè)方法的整體架構(gòu)如圖1所示.

圖1 基于局部特征表決的快速相似性檢測(cè)框架

該方法是一種基于增量壓縮的快速相似性檢測(cè)方法主要用于檢測(cè)非重復(fù)但高度相似性的數(shù)據(jù)塊，以便為增量壓縮提供候選輸入數(shù)據(jù)集.本文方法實(shí)現(xiàn)對(duì)數(shù)據(jù)塊的相似性檢測(cè)的大致過程為：

1)對(duì)原始無重復(fù)數(shù)據(jù)集進(jìn)行數(shù)據(jù)塊的劃分，通常數(shù)據(jù)塊大小為4KB級(jí)別；

2)將劃分好的數(shù)據(jù)塊再次進(jìn)行數(shù)據(jù)子塊的劃分，以便利用數(shù)據(jù)塊的局部信息實(shí)現(xiàn)相似性檢測(cè)；

3)對(duì)劃分好的子數(shù)據(jù)塊進(jìn)行特征提取，其中本文使用改進(jìn)之后的SF方法實(shí)現(xiàn)對(duì)子數(shù)據(jù)塊特征的提取；

4)對(duì)提取到的子數(shù)據(jù)塊特征進(jìn)行集成表決，根據(jù)表決的結(jié)果構(gòu)建超級(jí)特征；

5)將數(shù)據(jù)塊間對(duì)應(yīng)的超級(jí)特征進(jìn)行對(duì)比，實(shí)現(xiàn)相似性數(shù)據(jù)塊的檢測(cè).

3.1 數(shù)據(jù)塊局部特征提取方法

SF方法作為一種相似性檢測(cè)方法在增量壓縮領(lǐng)域被廣泛使用，其在增量壓縮過程中主要負(fù)責(zé)數(shù)據(jù)塊之間相似性檢測(cè)工作，并且為后續(xù)的數(shù)據(jù)壓縮提供候選數(shù)據(jù).對(duì)于給定大小的數(shù)據(jù)塊，SF方法從其中提取固定數(shù)目的特征，然后將其中的特征按照順序進(jìn)行分組以形成超級(jí)特征，然后根據(jù)構(gòu)建的超級(jí)特征來進(jìn)行相似性數(shù)據(jù)塊的檢測(cè).該方法對(duì)數(shù)據(jù)塊進(jìn)行特征提取的過程為：

先根據(jù)安全指紋提取技術(shù)(一種滾動(dòng)哈希算法[3])獲得某個(gè)長(zhǎng)度為L(zhǎng)的數(shù)據(jù)塊位于j位置的數(shù)字指紋信息，然后再將利用一對(duì)隨機(jī)值mi和ai對(duì)數(shù)字指紋信息進(jìn)行轉(zhuǎn)換以便獲得該數(shù)據(jù)塊的一個(gè)特征，即：

(1)

其中，Rabinj是位于j位置的滑動(dòng)窗口的Rabinj指紋，對(duì)于具有一個(gè)或多個(gè)相同特征的數(shù)據(jù)塊可能非常的相似，數(shù)據(jù)細(xì)微的更改不會(huì)對(duì)數(shù)據(jù)的相似性帶來很大的干擾.

接著繼續(xù)從不同的位置開始執(zhí)行上述操作，以獲得N個(gè)特征Feature[N].然后對(duì)獲得的N個(gè)特征按順序固定特征數(shù)目分組以形成超級(jí)特征，即：

SFx=Rabin(Featurex·k,…,Featurex·k+k-1)

(2)

對(duì)于相似的數(shù)據(jù)塊之間僅有非常微小的一部分不同，因此他們的特征以及SFx應(yīng)該是相同的.這種方法能夠很好地進(jìn)行高度相似數(shù)據(jù)塊之間的檢測(cè)的原因是：首先，SFx的匹配意味著數(shù)據(jù)塊之間的很對(duì)特征是相似的；其次，多個(gè)SFx被用于數(shù)據(jù)塊之間的相似性檢測(cè).因此，更多相同和相似的SFx能夠保障相似的數(shù)據(jù)塊被檢測(cè)出來.

對(duì)于以上方法，雖然其能夠在一定程度上進(jìn)行相似數(shù)據(jù)塊之間的檢測(cè)，但是其在進(jìn)行數(shù)據(jù)塊特征提取的時(shí)候需要消耗額外的轉(zhuǎn)換工作將Rabin指紋轉(zhuǎn)換成特征.另外，由于其對(duì)子特征的分組是按照順序進(jìn)行的并且將組內(nèi)所有的特征都用于構(gòu)建超級(jí)特征.當(dāng)組內(nèi)差異性特征較多的時(shí)候，這種方法形成的不同超級(jí)特征可能會(huì)是相似的，這樣不利于對(duì)相似性數(shù)據(jù)塊的檢測(cè).針對(duì)SF方法存在的問題，本文提出一種改進(jìn)的數(shù)據(jù)塊特征提取、分組方式.文獻(xiàn)[5]中提到，相似數(shù)據(jù)塊之間的局部信息也是相似的，因此，本文將數(shù)據(jù)塊進(jìn)行二次劃分形成更小的數(shù)據(jù)塊，然后進(jìn)行子數(shù)據(jù)塊特征的提取，進(jìn)而對(duì)子數(shù)據(jù)塊的特征進(jìn)行分組表決，具體的執(zhí)行過程如偽代碼所示：

算法：改進(jìn)的SF方法提取特征

輸入：數(shù)據(jù)塊的內(nèi)容str；數(shù)據(jù)塊的長(zhǎng)度L

輸出：N個(gè)特征，feature[N]

1.子數(shù)據(jù)塊長(zhǎng)度L/N

2.fori=0 toN-1do

3.feature[i]=0

4.form=0 toN-1do

5.forj=m*L/Nto(m+1)*L/N-1do

6. 獲取子數(shù)據(jù)塊的Rabin指紋FP=RabinFunction(str,m*L/N+j)

7.iffeature[m]<=FPthen

8.feature[m]=FP

9.endif

10.endfor

11.endfor

對(duì)子數(shù)據(jù)塊進(jìn)行特征提取的過程首先是減少了對(duì)Rabin指紋的轉(zhuǎn)換過程，從而降低了特征提取過程的時(shí)間開銷；其次，實(shí)現(xiàn)了對(duì)固定大小子數(shù)據(jù)塊的特征提取，有利于對(duì)子數(shù)據(jù)特征進(jìn)行分組從而構(gòu)建超級(jí)特征.

3.2 基于局部特征集成的快速相似性檢測(cè)

針對(duì)SF方法在數(shù)據(jù)塊特征提取過程中存在的計(jì)算特征時(shí)間消耗較多、特征分組可能導(dǎo)致差異性數(shù)據(jù)塊具有較高相似性問題.本文提出了一種改進(jìn)的SF方法，降低對(duì)數(shù)據(jù)塊特征提取的時(shí)間開銷.另外，基于改進(jìn)的SF方法，本文提出了一種面向增量壓縮的基于局部特征集成的快速相似性檢測(cè)方法，該方法可以實(shí)現(xiàn)對(duì)相似性數(shù)據(jù)塊的快速檢測(cè)，進(jìn)而提高增量壓縮的效率、降低增量壓縮過程的時(shí)間開銷，其具體的過程如圖1所示.本文的快速相似性檢測(cè)方法主要是基于增量壓縮的整個(gè)過程的，下面基于增量壓縮的過程將具體介紹本文方法每一步的執(zhí)行過程.

1)數(shù)據(jù)塊的劃分，本文基于增量壓縮的局部特征集成的快速相似性檢測(cè)主要實(shí)現(xiàn)對(duì)無重復(fù)但高度相似的數(shù)據(jù)的相似性檢測(cè).因此，本文所用數(shù)據(jù)基于重復(fù)數(shù)據(jù)刪除之后的數(shù)據(jù)集，然后將該數(shù)據(jù)集劃分為4KB大小的數(shù)據(jù)塊.

2)接著將劃分好的數(shù)據(jù)塊再次進(jìn)行數(shù)據(jù)子塊的劃分.文獻(xiàn)[5]的研究表明，數(shù)據(jù)塊之間的相似性可以由數(shù)據(jù)塊局部信息之間的相似性來表示，并且兩個(gè)相似的數(shù)據(jù)塊之間的局部信息表現(xiàn)為按順序的高度相似性，具體可由圖2表示.因此，本文在4KB級(jí)別數(shù)據(jù)塊的基礎(chǔ)上再進(jìn)行劃分，將4KB大小的數(shù)據(jù)塊劃分為更小的數(shù)據(jù)子塊，以便利用數(shù)據(jù)塊的局部信息實(shí)現(xiàn)相似性檢測(cè).對(duì)于數(shù)據(jù)塊進(jìn)行子塊劃分的做法是將數(shù)據(jù)塊劃分為若干個(gè)大小相同的子數(shù)據(jù)塊.

圖2 相似數(shù)據(jù)塊局部信息之間的關(guān)系

對(duì)于數(shù)據(jù)塊的相似性檢測(cè)工作，本文通過獲取子數(shù)據(jù)塊的特征，然后對(duì)特征進(jìn)行分組以便形成超級(jí)特征，然后利用超級(jí)特征進(jìn)行數(shù)據(jù)塊相似性檢測(cè)，其中的相似性檢測(cè)依據(jù)和集合間相似性檢測(cè)依據(jù)類似.兩個(gè)集合之間相似性的計(jì)算方法為：對(duì)于兩個(gè)集合A和B，H(A)和H(B)分別是A和B中元素的散列對(duì)應(yīng)的集合，其中H是從一個(gè)極小的排列獨(dú)立族中均勻隨機(jī)地選取的.集合中的一個(gè)元素被映射到一個(gè)整數(shù).令min(S)表示整數(shù)集合S中最小的元素，則：

(3)

上面的定義指出，集合A和B具有相同的最小哈希元素的概率與它們的相似系數(shù)相同.

3)子塊劃分完成了對(duì)4KB大小的數(shù)據(jù)塊的二次分割，形成了更小的數(shù)據(jù)塊(或稱為局部數(shù)據(jù)).接下來需要完成對(duì)子數(shù)據(jù)塊特征的提取以及子數(shù)據(jù)塊特征的分組工作，其中子數(shù)據(jù)塊特征的提取工作，本文使用改進(jìn)的SF方法，如表1所示，其中子數(shù)據(jù)塊特征分組形成超級(jí)的特征的方式如圖3所示.

圖3 數(shù)據(jù)塊局部特征分組方式

如圖3所示，獲得數(shù)據(jù)塊的局部特征之后，接下來需要對(duì)局部特征進(jìn)行分組，本文選擇將若干個(gè)連續(xù)的局部特征分為一個(gè)組，從而將數(shù)據(jù)塊的所有局部特征分為不同的組別.

4)對(duì)數(shù)據(jù)塊的局部特征進(jìn)行分組之后，接下來需要完成超級(jí)特征的構(gòu)建.對(duì)于超級(jí)特征構(gòu)建問題，本文利用分組內(nèi)的若干個(gè)特征通過集成的方式構(gòu)建，在構(gòu)建超級(jí)特征的過程中采用了集成表決的方式，具體過程如圖4所示.對(duì)于數(shù)據(jù)塊A中的分組和數(shù)據(jù)塊B中與之對(duì)應(yīng)的分組而言，其超級(jí)特征的構(gòu)建過程為：

圖4 分組特征的構(gòu)建方式

a)按原始順序排列數(shù)據(jù)塊A和數(shù)據(jù)塊B對(duì)應(yīng)分組之內(nèi)的若干個(gè)局部特征，即：

(4)

b)計(jì)算數(shù)據(jù)塊A和數(shù)據(jù)塊B對(duì)應(yīng)分組中局部特征是否相同，構(gòu)建sij表示數(shù)據(jù)塊A中的局部特征和數(shù)據(jù)塊B中的局部特征，即：

(5)

然后記錄相同的特征個(gè)數(shù)Sum_same及不同的特征個(gè)數(shù)Sum_diff，即：

Sum_diff=5-Sum_sanme

(6)

c)如果相同特征個(gè)數(shù)大于相異特征個(gè)數(shù)，則利用相同的局部特征構(gòu)建分組的特征，構(gòu)建方式如圖4所示.如果相同特征個(gè)數(shù)小于相異特征個(gè)數(shù)，則利用相異的局部特征構(gòu)建分組的特征，構(gòu)建方式同上.

當(dāng)數(shù)據(jù)塊的所有超級(jí)特征構(gòu)建完成之后，即可對(duì)數(shù)據(jù)之間的相似性進(jìn)行檢測(cè)，相思相檢測(cè)的方法和上文所述的集合之間測(cè)相似性檢測(cè)方法相同.

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

為了對(duì)本文方法FSD的有效性進(jìn)行驗(yàn)證，本文利用公開增量壓縮領(lǐng)域的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).在驗(yàn)證FSD方法的有效性時(shí)，本文基于開源的原型系統(tǒng)Destor[19]對(duì)增量壓縮的整個(gè)過程分別進(jìn)行了不同層面的實(shí)驗(yàn).

4.1 實(shí)驗(yàn)配置

基于Ubuntu16.04系統(tǒng)、8核Intel i7-8565U處理器、Intel i5-9400處理器和一個(gè)1TB的硬盤等構(gòu)建實(shí)驗(yàn)環(huán)境，利用開源的重復(fù)數(shù)據(jù)刪除原型系統(tǒng)Destor實(shí)現(xiàn)增量壓縮，以此來驗(yàn)證本文方法的有效性.本文實(shí)驗(yàn)建立在重復(fù)數(shù)據(jù)刪除之后的數(shù)據(jù)集之上，因此增量壓縮的過程可以簡(jiǎn)單的分為3個(gè)部分，首先是相似性數(shù)據(jù)塊的檢測(cè)，然后是共同特征提取和差異性特征的提取，最后是建立數(shù)據(jù)塊之間的映射關(guān)系以實(shí)現(xiàn)數(shù)據(jù)的增量壓縮.對(duì)于第一個(gè)部分即相似性數(shù)據(jù)塊的檢測(cè)工作，利用本文方法首先將數(shù)據(jù)塊劃分為固定大小的子塊，然后提取子塊的特征以及子塊特征的分組.由于對(duì)子塊特征分組時(shí)采用了集成表決的思想，本文選擇將5個(gè)子塊作為一個(gè)分組，然后將對(duì)應(yīng)5個(gè)子塊的特征進(jìn)行表決，以便于減少表決時(shí)同票數(shù)的沖突.

4.2 實(shí)驗(yàn)數(shù)據(jù)集和衡量指標(biāo)

實(shí)驗(yàn)所用數(shù)據(jù)集來自典型應(yīng)用場(chǎng)景下的增量壓縮數(shù)據(jù)集，其中包含了網(wǎng)絡(luò)快照、數(shù)據(jù)庫快照、虛擬機(jī)映像、tarred源代碼文件等等，實(shí)驗(yàn)數(shù)據(jù)集具體信息如表1所示：

表1 實(shí)驗(yàn)數(shù)據(jù)集

表1中DR(Deduplication Ratio)表示重復(fù)數(shù)據(jù)刪除率，其可由公式(7)計(jì)算:

(7)

其中DSB表示重復(fù)數(shù)據(jù)刪除前的數(shù)據(jù)大小，DSA表示重復(fù)數(shù)據(jù)刪除后的數(shù)據(jù)大小.由于本文相似性檢測(cè)方法需要建立在重復(fù)數(shù)據(jù)刪除后的數(shù)據(jù)集之上，因此需要對(duì)原始的數(shù)據(jù)集進(jìn)行重復(fù)數(shù)據(jù)的刪除工作.對(duì)于相似性檢測(cè)性能的衡量，本文選擇增量壓縮比DCR(Delta Compression Ratio)和增量壓縮效率DCE(Delta Compression Efficiency)兩個(gè)指標(biāo)進(jìn)行比較.其中DCR根據(jù)增量壓縮前的數(shù)據(jù)大小和增量壓縮之后數(shù)據(jù)的大小之商計(jì)算得出，DCE根據(jù)增量壓縮后數(shù)據(jù)塊的大小和增量壓縮前的數(shù)據(jù)塊大小之比計(jì)算得出.DCR在一定程度上反映出增量壓縮后存儲(chǔ)空間的節(jié)省程度，DCE用于檢測(cè)本文方法檢測(cè)到相似性數(shù)據(jù)塊之間的相似度.根據(jù)DCR和DCE的定義可知，DCR側(cè)重的是總體空間節(jié)省，而DCE則強(qiáng)調(diào)檢測(cè)到的類似數(shù)據(jù)塊塊本身，更高的DCE說明檢測(cè)到的相似性數(shù)據(jù)塊更精確.

4.3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)1.相似性檢測(cè)效率對(duì)比

為了更好地進(jìn)行相似性檢測(cè)效率，本文在上述6個(gè)數(shù)據(jù)集上分別進(jìn)行10次實(shí)驗(yàn)，并將10次實(shí)驗(yàn)求得的平均值作為最終的結(jié)果進(jìn)行比較.實(shí)驗(yàn)中，本文選擇將經(jīng)典的數(shù)據(jù)塊相似性檢測(cè)方法SF方法、Finesse方法以及本文方法進(jìn)行比較，實(shí)驗(yàn)結(jié)果如表2所示.

表2 不同數(shù)據(jù)集上數(shù)據(jù)塊相似性檢測(cè)效率比較

DCR主要用于描述數(shù)據(jù)經(jīng)過壓縮后數(shù)據(jù)壓縮的程度.Finesse對(duì)于數(shù)據(jù)壓縮的過程，經(jīng)過了數(shù)據(jù)劃分、數(shù)據(jù)塊子特征提取、超級(jí)特征的構(gòu)造等過程，該過程雖然在整體上實(shí)現(xiàn)了對(duì)數(shù)據(jù)的高效率壓縮，但是Finesse方法對(duì)數(shù)據(jù)特征提取的過程計(jì)算復(fù)雜性大，需要額外的特征轉(zhuǎn)換開銷.本文方法FSD首先提取了一種快速的數(shù)據(jù)特征提取方法，然后基于該快速數(shù)據(jù)特征提取方法構(gòu)建了一種基于數(shù)據(jù)特征集成表決的快速相似性數(shù)據(jù)檢測(cè)方法.由于本文方法改進(jìn)和簡(jiǎn)化了數(shù)據(jù)特征的提取，所以在相似數(shù)據(jù)檢測(cè)方面得到了顯著性的提升.但是對(duì)于DCR而言，F(xiàn)inesse要適當(dāng)優(yōu)于本文方法FSD,這種優(yōu)勢(shì)是通過犧牲特征提取的效率換得的.就整體而言，本文方法在DCR表現(xiàn)方面相比于Finesse稍微不足，但DCE方面表現(xiàn)較為理想.

實(shí)驗(yàn)2.形成超級(jí)特征速度的對(duì)比

對(duì)于形成超級(jí)特征速度的比較，本文選擇在不同配置的機(jī)器上進(jìn)行對(duì)比，最終比較的數(shù)據(jù)是通過多次實(shí)驗(yàn)并求取平均值得到.這里，本文選擇Intel i7-8565U處理器、Intel i5-9400處理器作為代表進(jìn)行構(gòu)建超級(jí)特征速度的比較.由于本文方法在計(jì)算特征和特征分組的時(shí)候不需要額外的轉(zhuǎn)換操作并且形成分組的時(shí)候不需要對(duì)特征進(jìn)行排序和選擇操作，所以本文方法在構(gòu)建超級(jí)特征的時(shí)候速度較快，其具體的對(duì)比如圖5所示.

圖5 相似性計(jì)算速度的比較

圖5中，本文基于不同的處理器配置進(jìn)行了數(shù)據(jù)塊相似性計(jì)算速度的比較.在相同配置的條件下，本文方法在相似性計(jì)算的速度方面優(yōu)于其他兩種方法.對(duì)于SF方法而言，其在計(jì)算特征的時(shí)候需要額外的線性轉(zhuǎn)換操作，因此執(zhí)行速度相對(duì)較慢.而Finesse方法在計(jì)算特征時(shí)減少了線性轉(zhuǎn)換工作，但是其在進(jìn)行特征分組的時(shí)候需要按照一定的順序?qū)μ卣鬟M(jìn)行排序，故其執(zhí)行的速度也不如本文方法.

實(shí)驗(yàn)3.系統(tǒng)吞吐量的對(duì)比

由于本文方法在進(jìn)行相似性數(shù)據(jù)塊的檢測(cè)時(shí)候是以整個(gè)增量壓縮為基礎(chǔ)的，因此，對(duì)于系統(tǒng)吞吐量的比較，本文選擇以增量壓縮實(shí)現(xiàn)的整個(gè)過程進(jìn)行對(duì)比，其中包含了重復(fù)數(shù)據(jù)刪除、相似性數(shù)據(jù)檢測(cè)、共同特征的提取以及建立相似性數(shù)據(jù)塊之間的映射關(guān)系等.對(duì)于增量壓縮執(zhí)行過程中系統(tǒng)吞吐量的對(duì)比，本文也是基于不同的硬件配置進(jìn)行比較，具體執(zhí)行結(jié)果如圖6所示.

圖6 不同相似性數(shù)據(jù)塊檢測(cè)方法的增量壓縮系統(tǒng)吞吐量的對(duì)比

從圖6中可以看出，本文方法在不同配置的機(jī)器上系統(tǒng)整體吞吐量都要優(yōu)于另外兩種方法，其根本原因在于增量壓縮過程中相似數(shù)據(jù)塊檢測(cè)階段的不同.由于本文在進(jìn)行相似性數(shù)據(jù)塊檢測(cè)的時(shí)候利用了數(shù)據(jù)塊局部特征以及對(duì)特征進(jìn)行了有效、快速的分組，從而提高了對(duì)相似性數(shù)據(jù)塊的檢測(cè)效率.

為了達(dá)到更好的增量壓縮效果，本文方法基于局部特征集成的快速相似性檢測(cè)方法(FSD)需要建立在重復(fù)數(shù)據(jù)刪除之后的數(shù)據(jù)集上.我們將本文方法FSD同時(shí)應(yīng)用在重復(fù)數(shù)據(jù)刪除之后的數(shù)據(jù)集和沒有刪除重復(fù)數(shù)據(jù)的數(shù)據(jù)集上進(jìn)行對(duì)比.實(shí)驗(yàn)中，本文選擇Oracle數(shù)據(jù)庫上的測(cè)試數(shù)據(jù)作為待壓縮數(shù)據(jù)，測(cè)試FSD方法在兩種不同數(shù)據(jù)集上的壓縮效果，結(jié)果如圖7所示.

圖7 本文方法在重復(fù)數(shù)據(jù)集和無重復(fù)數(shù)據(jù)上壓縮效果對(duì)比

5 結(jié)束語

對(duì)于增量壓縮中相似性數(shù)據(jù)塊檢測(cè)過程中面臨的特征提取耗時(shí)、計(jì)算開銷大、檢測(cè)效果不好等問題.本文以增量壓縮為背景，首先提出一種改進(jìn)的數(shù)據(jù)塊局部特征提取方法，實(shí)現(xiàn)了對(duì)數(shù)據(jù)塊局部特征的快速提取.然后基于該數(shù)據(jù)塊局部特征提取方法，提出了一種基于數(shù)據(jù)塊局部特征集成的快速相似性檢測(cè)方法.該方法首先將數(shù)據(jù)塊劃分為若干個(gè)子數(shù)據(jù)塊，然后利用改進(jìn)的數(shù)據(jù)塊特征提取方法提取子數(shù)據(jù)塊的特征，接著對(duì)子數(shù)據(jù)塊的特征進(jìn)行按順序分組，以便利用集成的思想構(gòu)造超級(jí)特征，最后利用構(gòu)造的超級(jí)特征實(shí)現(xiàn)對(duì)數(shù)據(jù)塊的相似性檢測(cè).實(shí)驗(yàn)結(jié)果表明，本文方法能夠有效降低數(shù)據(jù)塊特征提取的時(shí)間開銷、提高相似數(shù)據(jù)塊的檢測(cè)效率，進(jìn)而提高增量壓縮的執(zhí)行效率.本文方法在構(gòu)造超級(jí)的特征的時(shí)候利用了分組的思想，本文所設(shè)計(jì)的分組相對(duì)來說較為簡(jiǎn)單，下一步需要深入探究子數(shù)據(jù)塊的分組問題.