R-dedup: 一种重复数据删除指纹计算的优化方法

王龙翔 1; 董凯 2; 王鹏博 1; 董小社 1; 张兴军 1; 朱正东 1; 张利平 1

doi:10.7652/xjtuxb202101006

您当前的位置：

首页 >

文章列表页 >

R-dedup: 一种重复数据删除指纹计算的优化方法

更新时间：2025-07-09

- R-dedup: 一种重复数据删除指纹计算的优化方法
- R-dedup: A Performance Improvement Strategy for Fingerprint Calculation of Data De-Duplication
- 西安交通大学学报 2021年55卷第1期页码：43-51
- 作者机构：
  
  西安交通大学计算机科学与技术学院,西安,710049
- 作者简介：
- 基金信息：
  
  : 2020-06-19。作者简介: 王龙翔(1988—),男,工程师;董小社(通信作者),男,教授,博士生导师。基金项目: 国家重点研发计划资助项目(2018YFB0203902)
- DOI：10.7652/xjtuxb202101006
  中图分类号： TP319
- 网络首发：2021-01-10，
  
  纸质出版：2021
- 稿件说明：
移动端阅览
王龙翔 1, 董凯 2, 王鹏博 1, 等. R-dedup: 一种重复数据删除指纹计算的优化方法[J]. 西安交通大学学报, 2021,55(1):43-51.

R-dedup: A Performance Improvement Strategy for Fingerprint Calculation of Data De-Duplication[J]. 2021, 55(1): 43-51.
王龙翔 1, 董凯 2, 王鹏博 1, 等. R-dedup: 一种重复数据删除指纹计算的优化方法[J]. 西安交通大学学报, 2021,55(1):43-51. DOI： 10.7652/xjtuxb202101006.

R-dedup: A Performance Improvement Strategy for Fingerprint Calculation of Data De-Duplication[J]. 2021, 55(1): 43-51. DOI： 10.7652/xjtuxb202101006.

摘要

为减缓存储系统中传统重复数据删除方法在高性能固态存储盘中存在的指纹计算性能瓶颈

提出了重复数据删除指纹计算的性能优化方法R-dedup。在基于内容分块算法基础上

将切分后形成的所有数据块进一步切分为更小粒度的48 B等长数据片。基于Rabin哈希长度小于原始数据、多个Rabin哈希同时发生碰撞概率极低、数据片的Rabin哈希可以重复利用基于内容分块算法在滑动窗口过程中产生的计算结果的基础

利用数据片的Rabin哈希替代原始数据

并将其作为数据块的SHA-1指纹输入

减少SHA-1函数数据计算量

提高指纹计算性能。选取Linux内核、Imagenet等5组具有代表性的数据集

对R-dedup和标准基于内容分块的重复数据删除方法在数据分块性能、指纹计算性能、索引表检索性能和I/O性能方面分别进行了比较。结果表明:R-dedup的数据分块性能、索引表检索性能、I/O性能与对比方法具有4%左右的误差波动

性能基本一致; R-dedup的指纹计算吞吐率是对比方法的165%～422%

总体吞吐率是对比方法的6%～54%。

Abstract

To alleviate the performance bottleneck of SHA-1 fingerprint computing of data de-duplication in high-performance solid-state storage system

we propose an improvement strategy for fingerprint calculation of data de-duplication

R-dedup

which uses Rabin hash instead of original data to reduce SHA-1 fingerprint calculation. Based on content defined chunking algorithm

R-dedup further divides each data chunk formed after segmentation into smaller 48-byte length data slices. Owing to the shorter length of Rabin hash than the original data slice

the collision probability of multiple Rabin hashes is very low

and the Rabin hash of data slice can be obtained from the intermediate calculation results of sliding window of content defined chunking algorithm. The Rabin hash of data slice is used to replace the original data as the SHA-1 fingerprint input value of the data chunk

so as to reduce the data calculation amount of SHA-1 function and improve the performance. Five representative datasets

including Linux kernel and imagenet

are selected to compare the data chunking performance

SHA-1 computing performance

index table retrieval performance and I/O performance between R-dedup and standard content defined chunking of data de-duplication. The results show that R-dedup has only about 4% error fluctuation compared with the standard content defined chunking method in terms of data chunking performance

I/O performance and index retrieval performance. Compared with the standard content defined chunking strategy

R-dedup can improve the performance of SHA-1 fingerprint computing by 165% - 422% and the overall system throughput by 6% - 54%.

关键词

Keywords

references

付印金, 肖侬, 刘芳, 等. 基于重复数据删除的虚拟桌面存储优化技术 [J]. 计算机研究与发展, 2012, 49(Z1): 125-130.

FU Yinjin, XIAO Nong, LIU Fang, et al. Deduplication based storage optimization technique for virtual desktop [J]. Journal of Computer Research and Development, 2012, 49(Z1): 125-130.

LIU Jian, CHAI Yunpeng, QIN Xiao, et al. PLC-cache: endurable SSD cache for deduplication-based primary storage [C]∥Proceedings of the 2014 30th Symposium on Mass Storage Systems and Technologies(MSST). Piscataway, NJ, USA: IEEE, 2014: 1-12.

DEBNATH B, SENGUPTA S, LI J. ChunkStash: speeding up inline storage deduplication using flash memory [C]∥Proceedings of the 2010 USENIX Annual Technical Conference. Berkeley, CA, USA: USENIX Association, 2010: 215-229.

MAO Bo, JIANG Hong, WU Suzhen, et al. SAR: SSD assisted restore optimization for deduplication-based storage systems in the cloud [C]∥Proceedings of the 2012 IEEE 7th International Conference on Networking, Architecture, and Storage. Piscataway, NJ, USA: IEEE, 2012: 328-337.

MEISTER D, BRINKMANN A. Dedupv1: improving deduplication throughput using solid state drives(SSD)[C]∥Proceedings of the 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies(MSST). Piscataway, NJ, USA: IEEE, 2010: 1-6.

GUPTA A, PISOLKAR R, URGAONKAR B, et al. Leveraging value locality in optimizing NAND flash-based SSDs [C]∥Proceedings of the 9th USENIX Conference on File and Storage Technologies. Berkeley, CA, USA: USENIX Association, 2011: 91-103.

CHEN Feng, LUO Tian, ZHANG Xiaodong. CaFTL: a content-aware flash translation layer enhancing the lifespan of flash memory based solid state drives [C]∥Proceedings of the 9th USENIX Conference on File and Storage Technologies. Berkeley, CA, USA: USENIX Association, 2011: 77-90.

WANG Chundong, WEI Qingsong, YANG J, et al. NV-Dedup: high-performance inline deduplication for non-volatile memory [J]. IEEE Transactions on Computers, 2018, 67(5): 658-671.

CHEN Zhengguo, CHEN Zhiguang, XIAO Nong, et al. NF-Dedupe: a novel no-fingerprint deduplication scheme for flash-based SSDs [C]∥Proceedings of the 2015 IEEE Symposium on Computers and Communication(ISCC). Piscataway, NJ, USA: IEEE, 2015: 588-594.

王龙翔, 董小社, 张兴军, 等. 内容分块算法中预期分块长度对重复数据删除率的影响 [J]. 西安交通大学学报, 2016, 50(12): 73-78.

WANG Longxiang, DONG Xiaoshe, ZHANG Xingjun, et al. Influence of expected chunk size on deduplication ratio in content defined chunking algorithm [J]. Journal of Xi’an Jiaotong University, 2016, 50(12): 73-78.

MUTHITACHAROEN A, CHEN Benjie, MAZIèRES D. A low-bandwidth network file system [C]∥Proceedings of the 18th ACM Symposium on Operating Systems Principles. New York, USA: ACM, 2001: 174-187.

ESHGHI K, TANG H K. A framework for analyzing and improving content-based chunking algorithms [EB/OL]. [2020-05-01]. http: ∥www.hpl.hp.com/techreports/2005/HPL-2005-30R1.pdf.

KRUUS E, UNGUREANU C, DUBNICKI C. Bimodal content defined chunking for backup streams [C]∥Proceedings of the 8th USENIX Conference on File and Storage Technologies. Berkeley, CA, USA: USENIX Association, 2010: 239-252.

WEN X, DAN F, YU H, et al. FastCDC: a fast and efficient content-defined chunking approach for data deduplication [C]∥Proceedings of the 2016 USENIX Annual Technical Conference. Berkeley, CA, USA: USENIX Association, 2016: 101-114.

RABIN M O. Fingerprint by random polynomials: TR-15-81 [R]. Cambridge, USA: Havard University, 1981: 1-6.

QUINLAN S, DORWARD S. Venti: a new approach to archival data storage [C]∥Proceedings of the 1st USENIX Conference on File and Storage Technologies. Berkeley, CA, USA: USENIX Association, 2002: 89-101.

BRODER A Z. On the resemblance and containment of documents [C]∥Proceedings of the Compression and Complexity of Sequences. Piscataway, NJ, USA: IEEE, 1997: 21-29.

Linux Kernel Organization. The Linux kernel archives [EB/OL]. [2020-05-20]. http: ∥kernel.org/.

ELESAWY M. Real life violence situations dataset [EB/OL]. [2020-05-01]. https: ∥www.kaggle.com /mohamedmustafa/real-life-violence-situations-dataset.

PLUMMER B A, WANG Liwei, CERVANTES C M, et al. Flickr30k entities: collecting region-to-phrase correspondences for richer image-to-sentence models [C]∥Proceedings of the 2015 IEEE International Conference on Computer Vision(ICCV). Piscataway, NJ, USA: IEEE, 2015: 2641-2649.

ROBICQUET A, ALAHI A, SADEGHIAN A, et al. Forecasting social navigation in crowded complex scenes [EB/OL]. [2020-05-04]. https: ∥arxiv.org/abs/160100998.

DENG J, DONG W, SOCHER R, et al. ImageNet: a large-scale hierarchical image database [C]∥Proceedings of the 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR). Piscataway, NJ, USA: IEEE, 2009: 10836047.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

重复数据删除中的无向图遍历分组预测方法

稀疏随机纠删码:一种大规模数据存储容灾方法

超临界水异常区域热力学特性研究

隧道内燃料电池汽车氢气泄漏扩散特性及影响因素

EBSILON软件在热电联产系统优化中的应用综述