新型存儲設備上重復數據刪除指紋查找優化

何柯文 張佳辰 劉曉光 王 剛

(南開大學計算機學院 天津 300350) (天津市網絡與數據安全技術重點實驗室(南開大學) 天津 300350)

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

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

本文的主要貢獻包括3個方面:

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

2) 對勤奮指紋查找算法和懶惰指紋查找算法進行數學建模，理論分析新型存儲設備對2種指紋查找算法的影響，并得出在新型存儲設備上的指紋查找算法優化結論；

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

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

1 相關工作

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

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

本文探究的新型存儲設備下的重復數據刪除系統指紋查找算法優化，是為了比較在新型存儲設備下，原來針對HDD進行優化的重復數據刪除系統指紋查找算法是否有效，并提出在新型存儲設備上的重復數據刪除系統指紋查找算法的優化方案.

2 重復數據刪除系統指紋查找算法

本節主要介紹重復數據刪除系統的結構、針對HDD優化的懶惰指紋查找算法以及對應的Cache改進策略.

2.1 重復數據刪除系統基本結構

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

其中，重復數據刪除算法的基本流程描述如下：

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

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

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

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

5) 數據存儲.將非重復指紋和對應磁盤存入外存或者傳輸給遠端的數據中心，實現重復數據的合并.

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

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

2.2 勤奮指紋查找算法

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

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

輸入：指紋數據流；

輸出：指紋是否重復并進行存儲.

1) 輸入指紋進行Bloom Filter初次篩選，被判斷為不存在于Bloom Filter的指紋說明為非重復指紋，存入外存；判斷為重復的指紋，進行下面的環節繼續查找.

2) 指紋進入DRAM的Cache進行查找，如果查找該指紋，說明指紋是重復的；否則，進入第3環節進行外存查找.

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

2.3 懶惰指紋查找算法

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

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

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

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

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

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

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

Fig. 3 Local ring and rank圖3 局部性環和秩示意圖

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

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

輸入：指紋數據流；

輸出：指紋是否重復并進行存儲.

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

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

3) 指紋進入Buffer的對應散列桶中，當散列桶的指紋數量達到閾值，則將散列桶的指紋全部進行磁盤進行查找，指紋不存在，則說明非重復指紋；指紋如果存在，則說明是重復指紋.

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

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

3 研究的動機和意義

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

3.1 指紋查找算法在新型存儲設備的性能表現

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

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

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

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

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

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

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

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

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

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

4 指紋查找算法建模與優化

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

4.1 指紋查找數學建模

本節建模的目的是探究在考慮外存設備延遲等系統參數為自變量的前提下，勤奮指紋查找算法會優于懶惰指紋查找算法的條件.即，在輸入數據量相同的情況下，勤奮指紋查找算法的時間會大于懶惰指紋查找算法的時間，可表達為

Teager>Tlazy,

(1)

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

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

得到最后的比較式為

(8)

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

4.2 建模分析及優化結論

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

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

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

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

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

5 實 驗

本節針對第4節對重復數據刪除指紋查找算法建模分析得到的優化結論進行實驗驗證，探究這2種指紋查找算法在不同存儲設備上的性能如何.

5.1 實驗基本條件

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

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

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

Table 3 The Dataset Description表3 數據集描述

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

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

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

為了說明勤奮和懶惰指紋查找算法在HDD，Optane SSD和PM上的查找總時間以及2種指紋查找算法的各部分延遲.實驗統計了2種指紋查找算法的各部分時間.指紋查找大致可以分為3部分時間：外存訪問時間、Cache訪問時間和Bloom Filter查找時間，實驗結果如圖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和持久性內存上，勤奮和懶惰指紋查找算法的時間是HDD上的勤奮和懶惰指紋查找算法的總時間的10%左右，并且HDD上的指紋查找算法時間占比最大的是在外存的查找時間，懶惰指紋查找算法優于勤奮指紋查找算法也就是在外存查找上節約了時間.但是在Optane SSD和持久性內存上，2種算法的外存查找時間相差不多，而懶惰指紋查找算法增加的Post Lookup時間使得懶惰算法性能比勤奮算法的總時間更多.各部分的具體時間如表4所示.

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

5.3 局部性環大小對整體性能的影響

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

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

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

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

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

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

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

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

下面說明3種存儲設備上的最優局部性環大小和最優指紋查找時間，如表5所示.

Table 5 The Optimal Local Ring Size and Corresponding Fingerprint Lookup Time表5 局部性環最優值和對應指紋查找時間

設備速度越快，局部性環大小降低，符合第4節結論1和2.

綜合上述實驗可以得到如下結論：

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

2) 當外存存儲設備的性能越來越好時，最優局部性環的值會越來越小.

3) 當使用Optane SSD或者持久型內存時，甚至不采用局部性環的相關優化，采用勤奮指紋查找算法的效率更高.

6 結 語

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