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

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

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

1 引 言

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

(2)

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

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

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

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

輸出：N個特征，feature[N]

1.子數(shù)據(jù)塊長度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

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

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

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

1)數(shù)據(jù)塊的劃分，本文基于增量壓縮的局部特征集成的快速相似性檢測主要實現(xiàn)對無重復(fù)但高度相似的數(shù)據(jù)的相似性檢測.因此，本文所用數(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ù)塊局部信息之間的相似性來表示，并且兩個相似的數(shù)據(jù)塊之間的局部信息表現(xiàn)為按順序的高度相似性，具體可由圖2表示.因此，本文在4KB級別數(shù)據(jù)塊的基礎(chǔ)上再進(jìn)行劃分，將4KB大小的數(shù)據(jù)塊劃分為更小的數(shù)據(jù)子塊，以便利用數(shù)據(jù)塊的局部信息實現(xiàn)相似性檢測.對于數(shù)據(jù)塊進(jìn)行子塊劃分的做法是將數(shù)據(jù)塊劃分為若干個大小相同的子數(shù)據(jù)塊.

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

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

(3)

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

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

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

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

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

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

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

(4)

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

(5)

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

Sum_diff=5-Sum_sanme

(6)

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

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

4 實 驗

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

4.1 實驗配置

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

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

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

表1 實驗數(shù)據(jù)集

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

(7)

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

4.3 實驗結(jié)果

實驗1.相似性檢測效率對比

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

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

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

實驗2.形成超級特征速度的對比

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

圖5 相似性計算速度的比較

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

實驗3.系統(tǒng)吞吐量的對比

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

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

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

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

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

5 結(jié)束語

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