新型存儲設(shè)備上重復(fù)數(shù)據(jù)刪除指紋查找優(yōu)化

何柯文 張佳辰 劉曉光 王 剛

(南開大學(xué)計算機(jī)學(xué)院 天津 300350) (天津市網(wǎng)絡(luò)與數(shù)據(jù)安全技術(shù)重點實驗室(南開大學(xué)) 天津 300350)

隨著大數(shù)據(jù)時代的到來，如何高效、可靠地存儲海量數(shù)據(jù)成為業(yè)界所關(guān)注的一個重點.微軟[1]和易安信公司[2]的研究稱在他們的數(shù)據(jù)中50%～85%都是重復(fù)數(shù)據(jù)，如果能將這些重復(fù)數(shù)據(jù)進(jìn)行刪除，就能節(jié)約出大量空間來存儲更多數(shù)據(jù)并且能提升云備份系統(tǒng)的帶寬.但重復(fù)數(shù)據(jù)刪除系統(tǒng)既是計算密集型系統(tǒng)，也是IO密集型系統(tǒng)，外存的存儲介質(zhì)的性能很大程度影響到了重復(fù)數(shù)據(jù)刪除系統(tǒng)的指紋查找效率，最終影響到了重復(fù)數(shù)據(jù)刪除系統(tǒng)的性能.其中，我們稱Data Domain重復(fù)數(shù)據(jù)刪除文件系統(tǒng)(data domain deduplication file fystem, DDFS)[3]采用的指紋查找算法為勤奮指紋查找算法，是通過預(yù)取整個數(shù)據(jù)塊的指紋，利用重復(fù)數(shù)據(jù)塊中指紋的空間連續(xù)性減少對外存的訪問. 而懶惰指紋查找算法[4]則是在勤奮指紋查找算法的基礎(chǔ)上，將通過合并IO的方式進(jìn)一步減少外存的訪問來增加指紋查找效率，并且通過局部性環(huán)的方式保證了其指紋查找算法的Cache命中率接近勤奮指紋查找算法.

近年來，高性能固態(tài)硬盤和持久性內(nèi)存(persis-tent memory, PM)的出現(xiàn)，使得外存的隨機(jī)寫延遲能夠接近順序?qū)懷舆t，隨機(jī)讀寫并不會成為外存訪問的瓶頸.所以，原來針對機(jī)械硬盤(hard disk drive, HDD)優(yōu)化的重復(fù)數(shù)據(jù)刪除指紋查找算法需要進(jìn)行改進(jìn).本文以提升重復(fù)數(shù)據(jù)刪除系統(tǒng)指紋查找性能為目的，對新型存儲設(shè)備上的勤奮指紋查找算法和懶惰指紋查找算法的表現(xiàn)進(jìn)行了研究.

本文的主要貢獻(xiàn)包括3個方面:

1) 分析了重復(fù)數(shù)據(jù)刪除系統(tǒng)中的勤奮指紋查找算法和致力于減少外存訪問的懶惰指紋查找算法[4]，并實驗說明這2種指紋查找算法在HDD、傲騰固態(tài)硬盤(Optane solid state drive， Optane SSD)和PM上的性能表現(xiàn)；

2) 對勤奮指紋查找算法和懶惰指紋查找算法進(jìn)行數(shù)學(xué)建模，理論分析新型存儲設(shè)備對2種指紋查找算法的影響，并得出在新型存儲設(shè)備上的指紋查找算法優(yōu)化結(jié)論；

3) 通過在HDD，Optane SSD，PM上進(jìn)行指紋查找算法的實驗，驗證了模型的正確性以及建模得到的優(yōu)化結(jié)論的有效性.

由于PM并未大范圍生產(chǎn)，市場上無法獲得，所以本文對持久性內(nèi)存的實驗，采用Quartz模擬器[5]來進(jìn)行模擬實驗.

1 相關(guān)工作

面對全世界的數(shù)據(jù)量不斷增加的挑戰(zhàn)，如何處理重復(fù)數(shù)據(jù)、減少數(shù)據(jù)冗余，逐漸成為學(xué)術(shù)界和工業(yè)界關(guān)注的目標(biāo).從 1950 年利用Huffman 編碼的基于編碼的靜態(tài)模型[6]、基于字典的字符串壓縮模型[7]再到現(xiàn)在的基于數(shù)據(jù)塊或者文件級別的重復(fù)數(shù)據(jù)刪除[8]，處理的重復(fù)數(shù)據(jù)的量越來越大，對于處理重復(fù)數(shù)據(jù)的帶寬、延遲要求也越來越高.

Optane SSD和PM等快速存儲設(shè)備的出現(xiàn)，以及基于持久性內(nèi)存的新編程模式的提出[12]，對加速指紋索引帶來了新的可能性.學(xué)術(shù)界一些研究針對這些性能更佳的新型存儲設(shè)備上的數(shù)據(jù)結(jié)構(gòu)、文件系統(tǒng)和應(yīng)用程序進(jìn)行改進(jìn)，例如為解決葉子結(jié)點排序所導(dǎo)致的寫放大問題而改進(jìn) B+樹[13]，再如修改擴(kuò)容機(jī)制來降低散列的寫次數(shù)和一致性問題[14]，以及設(shè)計持久性內(nèi)存和DRAM混合的新文件系統(tǒng)(NOVA)[15]等.另一方面，也有工作專門對SSD進(jìn)行指紋索引優(yōu)化[16-18]和對PM文件系統(tǒng)研究重復(fù)數(shù)據(jù)刪除方法[19].

本文探究的新型存儲設(shè)備下的重復(fù)數(shù)據(jù)刪除系統(tǒng)指紋查找算法優(yōu)化，是為了比較在新型存儲設(shè)備下，原來針對HDD進(jìn)行優(yōu)化的重復(fù)數(shù)據(jù)刪除系統(tǒng)指紋查找算法是否有效，并提出在新型存儲設(shè)備上的重復(fù)數(shù)據(jù)刪除系統(tǒng)指紋查找算法的優(yōu)化方案.

2 重復(fù)數(shù)據(jù)刪除系統(tǒng)指紋查找算法

本節(jié)主要介紹重復(fù)數(shù)據(jù)刪除系統(tǒng)的結(jié)構(gòu)、針對HDD優(yōu)化的懶惰指紋查找算法以及對應(yīng)的Cache改進(jìn)策略.

2.1 重復(fù)數(shù)據(jù)刪除系統(tǒng)基本結(jié)構(gòu)

重復(fù)數(shù)據(jù)刪除系統(tǒng)作為一個針對數(shù)據(jù)流進(jìn)行重復(fù)數(shù)據(jù)刪除的系統(tǒng)，在目前的海量數(shù)據(jù)場景下顯得非常重要.重復(fù)數(shù)據(jù)刪除系統(tǒng)不同于常見的壓縮算法，傳統(tǒng)的壓縮算法針對的粒度是字符或者字符串級別的，但是重復(fù)數(shù)據(jù)刪除系統(tǒng)所針對的粒度是塊級別(一般為 4～12 KB的塊)或者文件級別.重復(fù)數(shù)據(jù)刪除系統(tǒng)的主體流程圖如圖1所示：

其中，重復(fù)數(shù)據(jù)刪除算法的基本流程描述如下：

1) 數(shù)據(jù)分塊.一般采用4～12 KB的定長塊分塊或者采用Rabin-Hash的非定長塊分塊.

2) 指紋計算.對每個數(shù)據(jù)塊進(jìn)行指紋計算，一般計算的方法采用安全散列算法(secure Hash algorithm-256, SHA-256)或者消息摘要算法(message digest algorithm-5, MD5)等方法進(jìn)行計算.

3) 指紋查找.將得到的指紋針與外存中的指紋進(jìn)行比對，判斷指紋是否重復(fù).

4) 數(shù)據(jù)壓縮.主要針對重復(fù)刪除過后的數(shù)據(jù)塊進(jìn)行壓縮，本部分為可選部分.

5) 數(shù)據(jù)存儲.將非重復(fù)指紋和對應(yīng)磁盤存入外存或者傳輸給遠(yuǎn)端的數(shù)據(jù)中心，實現(xiàn)重復(fù)數(shù)據(jù)的合并.

在上述5個環(huán)節(jié)中，數(shù)據(jù)分塊、指紋計算、數(shù)據(jù)壓縮都是計算密集型任務(wù)，剩下的指紋查找、數(shù)據(jù)存儲則是IO密集型的任務(wù).對于計算密集型任務(wù)我們可以通過多核并行計算或者GPU設(shè)備來進(jìn)行加速.

但是，隨著數(shù)據(jù)量的增長，指紋查找的環(huán)節(jié)將會頻繁訪問HDD，HDD的延遲相較于DRAM有萬倍以上的差距.所以，利用數(shù)據(jù)的局部性等特點在指紋查找環(huán)節(jié)減少對慢速HDD設(shè)備的訪問次數(shù)是至關(guān)重要的.

2.2 勤奮指紋查找算法

類似DDFS[3]采用的指紋查找算法為勤奮指紋查找算法，其基本思想是利用Bloom Filter進(jìn)行初次篩選，然后再利用重復(fù)數(shù)據(jù)塊中指紋具有連續(xù)性的特點，預(yù)取同一重復(fù)塊中所有指紋裝載進(jìn)Cache，來減少對外存的訪問.本文只聚焦討論指紋查找的效率，所以并未使用DDFS上層的文件接口.該算法也將作為與懶惰指紋查找算法的一個基準(zhǔn)線來進(jìn)行比較，勤奮指紋查找算法如下所示.

算法1.勤奮指紋查找算法.

輸入：指紋數(shù)據(jù)流；

輸出：指紋是否重復(fù)并進(jìn)行存儲.

1) 輸入指紋進(jìn)行Bloom Filter初次篩選，被判斷為不存在于Bloom Filter的指紋說明為非重復(fù)指紋，存入外存；判斷為重復(fù)的指紋，進(jìn)行下面的環(huán)節(jié)繼續(xù)查找.

2) 指紋進(jìn)入DRAM的Cache進(jìn)行查找，如果查找該指紋，說明指紋是重復(fù)的；否則，進(jìn)入第3環(huán)節(jié)進(jìn)行外存查找.

3) 指紋進(jìn)行外存查找，判斷為相同指紋后，預(yù)取進(jìn)Cache；沒有找到相同指紋，則說明該指紋不重復(fù)，存入外存.

2.3 懶惰指紋查找算法

為了盡可能地減少對外存的訪問，Ma等人[4]提出了一種懶惰指紋算法.其基本思想就是將多次指紋查找合并成一次指紋查找，在Buffer(內(nèi)存緩沖區(qū))中建立散列桶來暫存待查找指紋，即，請求的指紋在Cache中查找不到時，并不馬上進(jìn)行外存查找，而是保存在Buffer的散列桶中，當(dāng)散列桶中積累的待查找指紋數(shù)超過閾值時，再將其統(tǒng)一在磁盤中進(jìn)行查找.懶惰指紋查找的合并查找方式如圖2所示：

Fig. 2 The lazy deduplication fingerprint group search圖2 懶惰指紋算法批查找

圖2中的Buffer Bucket的指紋2，6，10，14四個指針達(dá)到了Buffer的閾值，則說明Buffer中的指紋存儲滿了，再將這些指紋一并在磁盤中查找，即4次外存訪問合并成1次外存訪問(閾值可進(jìn)行調(diào)整)，減少了讀取磁盤的次數(shù).

懶惰指紋查找算法這種基于外存訪問延遲的算法會破壞指紋的空間局部性.空間上相鄰的指紋通過散列函數(shù)映射到不同的桶中，所以Buffer中同一個桶中的指紋并不為相鄰的指紋.這就導(dǎo)致了Cache命中率低的問題，大部分的指紋都不會在Cache中找到，這樣延遲外存訪問的操作又增加了外存訪問的次數(shù)，對于性能較差的HDD來說，降低了指紋查找的性能.因此，懶惰指紋查找算法采用局部性環(huán)和標(biāo)記指紋秩的順序數(shù)來改進(jìn)懶惰指紋查找算法的Cache命中率.局部性環(huán)和秩本質(zhì)上是利用了指紋的空間局部性.例如，在備份系統(tǒng)中，如果每天都進(jìn)行全量備份，則會出現(xiàn)大量的相同連續(xù)數(shù)據(jù)塊.

Fig. 4 Lazy deduplication fingerprint search圖4 懶惰指紋查找算法流程

局部性環(huán)的基本思想就是用一個循環(huán)鏈表將在空間上連續(xù)的指紋進(jìn)行連接.在重復(fù)數(shù)據(jù)刪除開始時，局部性環(huán)為一個空環(huán)，然后當(dāng)每次進(jìn)行指紋查找，通過Bloom Filter篩選之后，認(rèn)定為重復(fù)的指紋會被加入到局部性環(huán)當(dāng)中，來保證局部性環(huán)中相近的指紋具有局部性，當(dāng)局部性環(huán)中的指紋超過閾值(閾值一般為Cache中指紋的容量)，則重新開啟一個新的局部性環(huán).

同時，Buffer中的指紋還保留每個指紋的秩，即指紋到來的順序.在局部性環(huán)中，第1個到來的指紋的秩為0，后面的指紋依次進(jìn)行遞增(0,1,2,…).由于指紋的秩目的是為了保持指紋的相對位置關(guān)系，所以被Bloom Filter判斷為非重復(fù)的指紋，仍需要記錄其指紋的秩.局部性環(huán)和秩的結(jié)構(gòu)如圖3所示.

Fig. 3 Local ring and rank圖3 局部性環(huán)和秩示意圖

在加入局部性環(huán)和秩之后，懶惰指紋查找算法的流程如下所示，具體流程圖如圖4所示.

算法2.懶惰指紋查找算法.

輸入：指紋數(shù)據(jù)流；

輸出：指紋是否重復(fù)并進(jìn)行存儲.

1) 指紋輸入到Bloom Filter進(jìn)行初次篩選，被判斷為不存在于Bloom Filter中的指紋說明為非重復(fù)指紋，存入磁盤；判斷為重復(fù)的指紋，進(jìn)行后續(xù)查找.

2) 指紋進(jìn)行Pre Lookup(先驗查找)，利用指紋間存在時間局部性來進(jìn)行Cache查找.

3) 指紋進(jìn)入Buffer的對應(yīng)散列桶中，當(dāng)散列桶的指紋數(shù)量達(dá)到閾值，則將散列桶的指紋全部進(jìn)行磁盤進(jìn)行查找，指紋不存在，則說明非重復(fù)指紋；指紋如果存在，則說明是重復(fù)指紋.

4) 在磁盤查找為重復(fù)指紋時，將磁盤中該指紋周圍存在空間局部性的指紋進(jìn)行預(yù)取.然后，再對Buffer中同一局部性環(huán)的指紋進(jìn)行Post Lookup(后驗查找)來達(dá)到提升Cache命中率的目的.懶惰指紋查找環(huán)節(jié)結(jié)束.

其中，Pre Lookup是在指紋進(jìn)入Buffer前進(jìn)入Cache查找，為的是利用指紋的時間局部性,即上一次被訪問的指紋下一次還可能被訪問到.而Post Lookup是在指紋進(jìn)入外存進(jìn)行查找之后，將具有空間局部性的指紋進(jìn)行預(yù)取并在Cache中進(jìn)行查找，目的是利用指紋的空間局部性，讓局部性環(huán)中的指紋盡可能命中，讓Buffer中的桶盡可能不滿，從而減少外存訪問.二者都是通過增加對Cache的訪問減少外存磁盤的隨機(jī)訪問，從而提高指紋查找的性能.

3 研究的動機(jī)和意義

本節(jié)將針對第2節(jié)所討論的懶惰指紋查找算法和勤奮指紋查找算法，討論新型存儲設(shè)備(Optane SSD和PM)的低延遲特性對指紋查找算法的影響，同時說明本文對新型存儲設(shè)備上的重復(fù)數(shù)據(jù)刪除指紋查找算法的研究意義.

3.1 指紋查找算法在新型存儲設(shè)備的性能表現(xiàn)

本文所研究的新型存儲設(shè)備主要是Optane SSD和持久性內(nèi)存，Optane SSD和持久性內(nèi)存相對于傳統(tǒng)的HDD而言具有高帶寬、低延遲的特性，由于我們的研究對象是指紋查找，這里主要討論Optane SSD和持久性內(nèi)存的延遲，各存儲設(shè)備的讀延遲如表1所示:

Table 1 Device Access Delay表1 存儲設(shè)備訪問延遲 μs

HDD的延遲是Optane SSD的400多倍，是持久性內(nèi)存的一萬倍左右，并且持久性內(nèi)存的延遲只有DRAM的6～7倍.這意味著10 000次的持久性內(nèi)存訪問的時間才相當(dāng)于1次的HDD訪問，而7次持久性內(nèi)存的訪問代價相當(dāng)于1次DRAM訪問.這使得當(dāng)我們外存采用更快存儲設(shè)備時，懶惰指紋查找算法的優(yōu)化不再高效，可能勤奮指紋查找算法反而更加高效.

其中，HDD,SSD,Optane SSD都是用Fio[20]以1 KB塊大小測試的平均延遲，DRAM則是以1 KB塊大小利用函數(shù)memcpy測試的平均延遲，持久性內(nèi)存是通過Quartz進(jìn)行模擬[21]，模擬的延遲是DRAM的7～8倍.

我們還測試了第2節(jié)介紹的勤奮指紋查找算法和懶惰指紋查找算法在HDD、Optane SSD、持久性內(nèi)存上的性能，指紋查找延遲時間如圖5所示，其中總數(shù)據(jù)量為104 GB,Eager代表勤奮指紋查找，Lazy代表懶惰指紋查找.

Fig. 5 The fingerprint lookup time圖5 指紋查找時間

從圖5可以看出，在慢速的外存設(shè)備HDD上，懶惰指紋查找算法相較于勤奮指紋查找算法降低了50%的指紋查找時間，這說明了懶惰指紋查找算法的查找請求延遲策略有效地減少了對外存HDD的訪問次數(shù)，并且利用局部性環(huán)以及秩有效地提升了Cache命中率，這在較慢速的HDD上帶來了顯著的性能提升.但是，在快速外存介質(zhì)Optane SSD和持久性內(nèi)存上，懶惰指紋查找的總時間略大于勤奮指紋查找，這說明懶惰指紋查找優(yōu)化策略在Optane SSD和PM已經(jīng)不明顯，懶惰指紋查找策略的效率需要在新型存儲設(shè)備上重新分析以及優(yōu)化.

3.2 新型存儲設(shè)備對指紋查找的影響分析

懶惰指紋查找方法通過延遲查找以及批提交來重復(fù)利用磁盤的帶寬,減少對磁盤的訪問，并且利用局部性環(huán)和秩保持指紋和指紋之間的時間與空間局部性，利用Cache來減少對磁盤的訪問，但是Cache訪問次數(shù)變多，相當(dāng)于增加了對DRAM的額外訪問.在外存為HDD時，根據(jù)圖5可知，增加DRAM訪問次數(shù)來減少對外存的訪問是有效的；但是當(dāng)外存設(shè)備為更加快速的Optane SSD或者持久性內(nèi)存時，大幅度增加DRAM的訪問來減少對快速外存設(shè)備的訪問就不再有效.

懶惰指紋查找算法基本可以分為Bloom Filter,Pre Lookup,Buffer,Disk Lookup,Post Lookup這5個階段，其中Bloom Filter全在DRAM中進(jìn)行查找，并且只和數(shù)據(jù)集大小有關(guān)，其時間與外存和DRAM的訪問延遲無關(guān).而Buffer,Disk都可以認(rèn)為受外存的訪問延遲影響，Pre Lookup，Post Lookup可以認(rèn)為受DRAM的訪問延遲影響.而懶惰指紋查找算法相當(dāng)于是增加Pre Lookup，Post Lookup的DRAM訪問次數(shù)來減少Buffer，Disk Lookup的訪問次數(shù)，而Pre Lookup在勤奮指紋查找算法和懶惰指紋查找算法中均存在，代價相同.因此，懶惰指紋查找算法是否優(yōu)于勤奮指紋查找算法的關(guān)鍵在于Post Lookup增加的DRAM訪問代價是否少于減少的外存訪問代價.這也是本文所研究新型存儲設(shè)備下的指紋查找性能的動機(jī)和意義.

4 指紋查找算法建模與優(yōu)化

本節(jié)將把不同存儲設(shè)備的延遲進(jìn)行量化，通過數(shù)學(xué)建模分析外存設(shè)備的延遲對指紋查找的影響.并根據(jù)建立的模型分析，得出如何在快速的Optane SSD設(shè)備持久性內(nèi)存上優(yōu)化本文第2節(jié)所提到的懶惰指紋查找算法.本文將對懶惰指紋查找算法與勤奮指紋查找算法進(jìn)行比較，得到對應(yīng)的優(yōu)化結(jié)論.

4.1 指紋查找數(shù)學(xué)建模

本節(jié)建模的目的是探究在考慮外存設(shè)備延遲等系統(tǒng)參數(shù)為自變量的前提下，勤奮指紋查找算法會優(yōu)于懶惰指紋查找算法的條件.即，在輸入數(shù)據(jù)量相同的情況下，勤奮指紋查找算法的時間會大于懶惰指紋查找算法的時間，可表達(dá)為

Teager>Tlazy,

(1)

其中，Teager為勤奮指紋查找算法的時間，Tlazy為懶惰指紋查找算法的時間.

那么對應(yīng)勤奮指紋查找算法模型，指紋查找總時間表示為

(2)

為了具體討論外存訪問延遲對總體指紋查找的影響，可以將式(2)轉(zhuǎn)換為

(3)

接下來與采用Post Lookup，Pre Lookup的懶惰指紋查找算法進(jìn)行對比，懶惰指紋查找的順序是Bloom Filter, Pre Lookup, Buffer, Disk Lookup,Post Lookup.由于Pre Lookup，Post Lookup，懶惰指紋查找環(huán)節(jié)變多，所以除了正常Cache命中所帶來的Cache訪問，還有多次遍歷局部性環(huán)的Post Lookup帶來Cache訪問.于是，我們懶惰指紋查找的訪問時間為

(4)

為了討論具體的存儲介質(zhì)訪問延遲對指紋查找的影響，將存儲介質(zhì)的延遲等參數(shù)加入，得到:

(5)

將式(3)和式(5)代入式(1)，可得:

(6)

由于Tbloom的時間只跟數(shù)據(jù)集的數(shù)量有關(guān)，在此比較過程中，勤奮和懶惰的Bloom Filter時間相同，所以可以抵消，并且有：

(7)

得到最后的比較式為

(8)

只有當(dāng)式(8)成立時，才會有式(1)成立，接下來我們來討論式(8)成立的條件.

4.2 建模分析及優(yōu)化結(jié)論

式(8)的不等式左邊可以理解為外存的速度與DRAM速度的比值，而公式右邊可以理解為采用2種方案在外存中的訪問數(shù)據(jù)量的差值和在Cache中訪問數(shù)據(jù)量的差值的比值.采用懶惰策略的優(yōu)化方案是否比勤奮方案好，取決于這2個比值的大小關(guān)系.

根據(jù)以上的相關(guān)關(guān)系可以針對不同的外存配置場景進(jìn)行分析，一般的存儲設(shè)備如HDD的延遲都是DRAM設(shè)備的80 000倍左右(SSD為1 000倍左右)，由式(8)可知，公式左邊設(shè)備延遲的比值會遠(yuǎn)大于公式右邊訪問數(shù)據(jù)的差值的比值.所以，采取懶惰指紋查找算法會使得指紋查找時間小于勤奮指紋查找算法.

為了讓式(8)成立，公式右邊盡可能大，即我們指紋查找的IO優(yōu)化方案有效，可以給出3個建議：

2) 減少局部性環(huán)大小，即減少Post Lookup所帶來的額外Cache查找的時間，局部性環(huán)存在一個最優(yōu)值.

3) 當(dāng)外存的存儲介質(zhì)足夠快能夠接近DRAM速度時，針對于Cache命中方面的優(yōu)化作用變小，這時候采用勤奮指紋查找算法的效果要比懶惰指紋查找算法好.

5 實 驗

本節(jié)針對第4節(jié)對重復(fù)數(shù)據(jù)刪除指紋查找算法建模分析得到的優(yōu)化結(jié)論進(jìn)行實驗驗證，探究這2種指紋查找算法在不同存儲設(shè)備上的性能如何.

5.1 實驗基本條件

本文實驗平臺的基本配置如表2所示:

Table 2 The Configuration of the Experimental Platform表2 實驗平臺配置情況

實驗將使用Quartz模擬器[21]作為持久性內(nèi)存，設(shè)置持久性內(nèi)存的延遲為DRAM的7倍左右.為了更好地探究在真實環(huán)境下重復(fù)數(shù)據(jù)刪除系統(tǒng)性能，實驗數(shù)據(jù)集中將采用與文獻(xiàn)[4]中類似的數(shù)據(jù)集——MIRROR，該數(shù)據(jù)集來自是浙江大學(xué)鏡像站(1)http://mirrors.zju.edu.cn的鏡像文件.數(shù)據(jù)集中包含從2010年開始到2019年6月的Arch Linux,CentOS,Cygwin,Debian,Deepin,Docker CE等系統(tǒng)的所有鏡像文件，每個系統(tǒng)的版本數(shù)量在5～20.將系統(tǒng)軟件的不同版本鏡像根據(jù)時間順序依次寫入磁盤，可以重現(xiàn)這些系統(tǒng)軟件每個版本的歸檔過程，是一個典型的備份系統(tǒng)動態(tài)數(shù)據(jù)寫入過程.數(shù)據(jù)集的大小、文件數(shù)量、文件時間范圍、重復(fù)數(shù)據(jù)、重復(fù)數(shù)據(jù)情況如表3所示：

Table 3 The Dataset Description表3 數(shù)據(jù)集描述

由于本文的實驗更關(guān)注指紋查找的部分，所以在下面的實驗過程中，我們將只討論指紋查找部分的時間，下面實驗結(jié)果給出的時間都是處理整數(shù)據(jù)集所有指紋查找的總時間.

5.2 不同存儲介質(zhì)的指紋查找算法各部分時間

下面的實驗中，Bloom Filter的大小為1 MB，局部性環(huán)的大小為2 048，Cache和緩存區(qū)占用的空間在256 MB，分塊是采用Rabin-Hash加上滑動窗口的變長分塊算法[22]，平均的塊大小為4 KB，而指紋摘要算法利用SHA-1，即每一個4KB塊對應(yīng)的指紋大小為160 b.外存采用3種存儲設(shè)備：HDD，Optane SSD，PM，PM是通過Quartz模擬器[21]來模擬，其延遲為DRAM的7～8倍.

為了說明勤奮和懶惰指紋查找算法在HDD，Optane SSD和PM上的查找總時間以及2種指紋查找算法的各部分延遲.實驗統(tǒng)計了2種指紋查找算法的各部分時間.指紋查找大致可以分為3部分時間：外存訪問時間、Cache訪問時間和Bloom Filter查找時間，實驗結(jié)果如圖6、表4所示.

Fig.6 The time of each step in eager and lazy fingerprint search圖6 勤奮和懶惰指紋查找的各部分時間

Table 4 Specific Time of Fingerprint Search 表4 指紋查找具體時間 s

從圖6可以看出，在Optane SSD和持久性內(nèi)存上，勤奮和懶惰指紋查找算法的時間是HDD上的勤奮和懶惰指紋查找算法的總時間的10%左右，并且HDD上的指紋查找算法時間占比最大的是在外存的查找時間，懶惰指紋查找算法優(yōu)于勤奮指紋查找算法也就是在外存查找上節(jié)約了時間.但是在Optane SSD和持久性內(nèi)存上，2種算法的外存查找時間相差不多，而懶惰指紋查找算法增加的Post Lookup時間使得懶惰算法性能比勤奮算法的總時間更多.各部分的具體時間如表4所示.

為了驗證式(8)的正確性，我們將一些參數(shù)值代入式(8).式(8)的左邊是外存與DRAM的延遲比值，當(dāng)外存分別是HDD,Optane SSD、持久性內(nèi)存時，其延遲與DRAM延遲的比值分別為88 415.38,192.31,6.15.再討論式(8)的右邊，我們統(tǒng)計得到了處理MIRROR數(shù)據(jù)集產(chǎn)生的總指紋量，因為外存設(shè)備快慢本身不會影響處理的指紋量與Cache命中率，所以式(8)右邊的值為554.06.當(dāng)使用HDD時，88 415.38遠(yuǎn)大于554.06，所以懶惰指紋查找算法優(yōu)于勤奮指紋查找算法；而當(dāng)使用Optane SSD和持久性內(nèi)存時，192.31,6.15遠(yuǎn)小于554.06，所以勤奮指紋查找算法優(yōu)于懶惰指紋查找算法，圖6中的指紋查找總時間也驗證了該計算分析的結(jié)果.同時也驗證了第4節(jié)的結(jié)論3.

5.3 局部性環(huán)大小對整體性能的影響

Fig. 7 The impact of local ring size on lazy fingerprint lookup time (HDD)圖7 局部性環(huán)大小對懶惰指紋查找時間的影響(HDD)

根據(jù)第4節(jié)的分析，局部性環(huán)的閾值對整體指紋查找的性能有著較大的影響，當(dāng)局部性環(huán)的閾值為1時，即沒有采用Post Lookup，Cache命中率會降低，但是節(jié)約了查找局部性環(huán)的時間.為了更好地探究在不同局部性環(huán)大小的影響下，指紋查找時間在不同存儲設(shè)備上將會如何變化，下面針對局部性環(huán)不同的取值進(jìn)行實驗，以下實驗都是基于懶惰指紋查找算法來做的.

首先分析理論上能夠增加Cache命中率的局部性環(huán)取值.因為在Post Lookup的過程是查找到一個指紋，然后在將這個指紋的局部性環(huán)上其他指紋都進(jìn)行Cache查找.所以，局部性環(huán)的大小設(shè)定為和Cache中桶大小相同比較合適(默認(rèn)設(shè)置為2 048).

本文將局部性環(huán)的大小配置為2,4,8,16,32,64,512,1 024,2 048，其他的配置與5.2節(jié)相同.查看對于指紋查找時間的影響.實驗結(jié)果如圖7、圖8所示.

Fig. 8 The impact of local ring size on lazy fingerprint lookup time (Optane SSD,PM)圖8 局部性環(huán)大小對懶惰指紋查找時間的影響(Optane SSD和PM)

圖7為HDD上采用不同局部性環(huán)大小時的各部分時間，圖8表示在Optane SSD，PM上采用不同局部性環(huán)大小時的各部分時間.

從圖7可知，對于HDD而言，隨著局部性環(huán)的增長，外存訪問時間不斷減少，Cache訪問時間增加，局部性環(huán)的訪問時間增長.但是由于在HDD上，指紋查找的性能主要受限于外存訪問時間，所以局部性環(huán)大小越大，指紋查找的性能越好.但是局部性環(huán)仍有一個最優(yōu)值，超過這個最優(yōu)值，就不能再明顯地減少磁盤訪問時間，指紋查找時間基本沒有變化.在HDD上的局部性環(huán)最優(yōu)值為512，查找時間為68.82 s.

而通過圖8(a)可以看出，在采用更快的外存設(shè)備Optane SSD和持久性內(nèi)存，當(dāng)局部性環(huán)增大時，懶惰指紋查找的總時間會有一個增加.并且觀察Optane SSD和持久性內(nèi)存的局部性環(huán)最優(yōu)值，會發(fā)現(xiàn)其最優(yōu)值相較于HDD有明顯的前移，從HDD的512，前移到64,32，這也符合第4節(jié)的結(jié)論2.為了更加細(xì)致地分析在不同設(shè)備上局部性環(huán)大小對懶惰指紋查找的影響，我們還對指紋查找的不同環(huán)節(jié)進(jìn)行了時間變化的記錄.從圖8(b)、圖8(c)可以看出，指紋查找的4個部分時間，Disk Lookup，Cache_Post，Cache，Bloom Filter的基本趨勢在Optane SSD和持久性內(nèi)存上相近.Bloom Filter基本沒有大幅度的變化，說明局部性環(huán)大小并不影響B(tài)loom Filter的時間.Post Lookup的時間都隨著局部性環(huán)大小的增大而增大，Pre Lookup的時間和外存查找的時間都隨著局部性環(huán)大小的增大而減小.在局部性環(huán)較大時，Post Lookup的時間已經(jīng)成為影響指紋查找總時間的主要因素.

下面說明3種存儲設(shè)備上的最優(yōu)局部性環(huán)大小和最優(yōu)指紋查找時間，如表5所示.

Table 5 The Optimal Local Ring Size and Corresponding Fingerprint Lookup Time表5 局部性環(huán)最優(yōu)值和對應(yīng)指紋查找時間

設(shè)備速度越快，局部性環(huán)大小降低，符合第4節(jié)結(jié)論1和2.

綜合上述實驗可以得到如下結(jié)論：

1) 當(dāng)外存存儲設(shè)備采用Optane SSD這種新型SSD時，這種存儲設(shè)備的優(yōu)化針對于重復(fù)數(shù)據(jù)刪除系統(tǒng)的指紋查找效率足夠，再采用更快的存儲設(shè)備(例如PM)，性能提升并不明顯.

2) 當(dāng)外存存儲設(shè)備的性能越來越好時，最優(yōu)局部性環(huán)的值會越來越小.

3) 當(dāng)使用Optane SSD或者持久型內(nèi)存時，甚至不采用局部性環(huán)的相關(guān)優(yōu)化，采用勤奮指紋查找算法的效率更高.

6 結(jié) 語

本文針對新型存儲設(shè)備上的重復(fù)數(shù)據(jù)刪除指紋查找算法進(jìn)行研究.首先介紹2種典型的指紋查找算法：一種是傳統(tǒng)的勤奮指紋查找算法，另一種是針對于HDD等慢速設(shè)備優(yōu)化外存訪問的懶惰指紋查找算法.然后將外存存儲介質(zhì)的延遲作為變量，對2種指紋查找算法進(jìn)行建模，分析并得到3點的優(yōu)化結(jié)論：降低Buffer的大小、降低局部性環(huán)的大小、在高性能設(shè)備上勤奮重復(fù)數(shù)據(jù)刪除算法性能優(yōu)于懶惰重復(fù)數(shù)據(jù)刪除算法.在實際數(shù)據(jù)集上的實驗結(jié)果驗證了模型的正確性以及3點優(yōu)化結(jié)論.