新型存储设备上重复数据删除指纹查找优化

何柯文 张佳辰 刘晓光 王 刚

(南开大学计算机学院 天津 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点优化结论.