何柯文 張佳辰 劉曉光 王 剛

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

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

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

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

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

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

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

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

1 相關(guān)工作

面對(duì)全世界的數(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ù)塊或者文件級(jí)別的重復(fù)數(shù)據(jù)刪除[8]，處理的重復(fù)數(shù)據(jù)的量越來(lái)越大，對(duì)于處理重復(fù)數(shù)據(jù)的帶寬、延遲要求也越來(lái)越高.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 勤奮指紋查找算法

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

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

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

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

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

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

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

2.3 懶惰指紋查找算法

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

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

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

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

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

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

同時(shí)，Buffer中的指紋還保留每個(gè)指紋的秩，即指紋到來(lái)的順序.在局部性環(huán)中，第1個(gè)到來(lái)的指紋的秩為0，后面的指紋依次進(jìn)行遞增(0,1,2,…).由于指紋的秩目的是為了保持指紋的相對(duì)位置關(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)行存儲(chǔ).

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

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

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

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

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

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

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

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

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

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

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

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

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

Fig. 5 The fingerprint lookup time圖5 指紋查找時(shí)間

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

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

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

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

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

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

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

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

Teager>Tlazy,

(1)

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

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

得到最后的比較式為

(8)

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

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

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

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

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

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

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

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

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

5.1 實(shí)驗(yàn)基本條件

本文實(shí)驗(yàn)平臺(tái)的基本配置如表2所示:

Table 2 The Configuration of the Experimental Platform表2 實(shí)驗(yàn)平臺(tái)配置情況

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

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

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

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

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

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

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

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

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

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

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

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

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

首先分析理論上能夠增加Cache命中率的局部性環(huán)取值.因?yàn)樵赑ost Lookup的過(guò)程是查找到一個(gè)指紋，然后在將這個(gè)指紋的局部性環(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é)相同.查看對(duì)于指紋查找時(shí)間的影響.實(shí)驗(yàn)結(jié)果如圖7、圖8所示.

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

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

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

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

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

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

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

綜合上述實(shí)驗(yàn)可以得到如下結(jié)論：

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

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

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

6 結(jié) 語(yǔ)

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