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

Fingerprint Search Optimization for Deduplication on Emerging Storage Devices

指纹查找部分是I/O密集型工作负载,即外存存储设备的性能是指纹查找的性能瓶颈.因此关注重复数据删除系统的指纹查找部分,对比了传统的勤奋指纹查找算法和致力于减少磁盘访问次数的懒惰指纹查找算法,分析了2种方法在傲腾固态硬盘(Optane solid state drive,Optane SSD)和持久性内存(persistent memory,PM)两种新型存储设备上的性能表现,并给出了优化建议.对勤奋指纹查找算法和懒惰指纹查找算法的时间进行建模,分析得出了指纹查找算法在新型存储设备下的3点优化结论:1)应减少统一查找的指纹数;2)在较快设备上应减少懒惰指纹查找中局部性环的大小,并且局部性环大小存在一个最优值;3)在快速设备上,勤奋指纹查找的效果要优于懒惰指纹查找.最终,在实际机械硬盘(hard disk drive,HDD)、Optane SSD和PM模拟器上实验验证了模型的正确性.实验结果显示,快速设备上指纹查找的时间相较于HDD减少90%以上,并且采用勤奋算法要优于懒惰算法,局部性环最优值前移的现象,也与模型理论优化结果吻合.

Fingerprint search part is I/O intensive,and the performance of the external storage device is the bottleneck of fingerprint search.Therefore,this paper focuses on the fingerprint search of data deduplication system.This paper compares the traditional eager deduplication algorithm with lazy deduplication algorithms that reduce the number of disk accesses,and studies deduplication algorithm on the emerging storage devices:Optane SSD and persistent memory,and gives optimization suggestions.In this paper,we model the fingerprint search delay of the eager deduplication algorithm and the lazy deduplication algorithm,and three conclusions under the new storage device are obtained through the modeling results:1)The number of fingerprints for batched search should be reduced;2)The local ring size should be reduced on faster devices,and the local loop size has an optimal value;3)On fast devices,the eager fingerprint lookup is better than the lazy fingerprint lookup.Finally,the experimental results verify the correctness of our model on the actual HDD,Optane SSD and emulated persistent memory.The eager algorithm is better than the lazy algorithm on the emerging storage devices,and the locality ring optimal value is advanced,which basically conforms to the conclusions of the proposed model.