ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2020, Vol. 57 ›› Issue (2): 269-280.doi: 10.7544/issn1000-1239.2020.20190543

所属专题: 2020大数据与智能存储系统前沿技术专题

• 系统结构 • 上一篇    下一篇

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

何柯文, 张佳辰, 刘晓光, 王 刚   

  1. (南开大学计算机学院 天津 300350) (天津市网络与数据安全技术重点实验室(南开大学) 天津 300350) (hekw@nbjl.nankai.edu.cn)
  • 出版日期: 2020-02-01
  • 基金资助: 
    国家自然科学基金项目(U1833114,61872201,61702521,61602266);天津市自然科学基金项目(17JCYBJC15300,16JCYBJC41900);天津市人工智能重大专项项目(18ZXZNGX00140,18ZXZNGX00200);中央高校基本科研业务费专项资助项目

Fingerprint Search Optimization for Deduplication on Emerging Storage Devices

He Kewen, Zhang Jiachen, Liu Xiaoguang, and Wang Gang   

  1. (College of Computer Science, Nankai University, Tianjin 300350) (Tianjin Key Laboratory of Network and Data Security Technology (Nankai University), Tianjin 300350)
  • Online: 2020-02-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (U1833114, 61872201, 61702521, 61602266), the Natural Science Foundation of Tianjin (17JCYBJC15300, 16JCYBJC41900), the Artificial Intelligence Major Project of Tianjin (18ZXZNGX00140, 18ZXZNGX00200), and the Fundamental Research Funds for the Central Universities.

摘要: 指纹查找部分是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%以上,并且采用勤奋算法要优于懒惰算法,局部性环最优值前移的现象,也与模型理论优化结果吻合.

关键词: 重复数据删除, 持久性内存, 指纹索引, 新型存储设备, 数据空间局部性

Abstract: 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.

Key words: deduplication, persistent memory, fingerprint index, emerging storage device, data spatial locality

中图分类号: