R-dedup: A Performance Improvement Strategy for Fingerprint Calculation of Data De-Duplication

doi:10.7652/xjtuxb202101006

您当前的位置：

首页 >

文章列表页 >

R-dedup: A Performance Improvement Strategy for Fingerprint Calculation of Data De-Duplication

更新时间：2025-07-09

- R-dedup: A Performance Improvement Strategy for Fingerprint Calculation of Data De-Duplication
- Vol. 55, Issue 1, Pages: 43-51(2021)
- 作者机构：
  
  西安交通大学计算机科学与技术学院,西安,710049
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb202101006
  CLC： TP319
- Online First：10 January 2021，
  
  Published：2021
- 稿件说明：
移动端阅览
R-dedup: A Performance Improvement Strategy for Fingerprint Calculation of Data De-Duplication[J]. 2021, 55(1): 43-51.
DOI：

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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Grouping Prediction Method Based on Undirected Graph Traversal in De-Duplication System

Sparse Random Erasure Code: a Fault Tolerance Scheme for Large-Scale Storage System

Bi-Level Multi-Obj ective Optimization of a Wind-Solar Coupled Hydrogen Production System Based on the Synergy of Hybrid Electrolyzer Arrays

I/O Performance Modeling and Prediction Method for Large-Scale Parallel Applications Using Machine Learning

Research on the Electrohydrodynamic Effects of Ionic Liquid-Modified Fuels

Related Author

王龙翔

张兴军

朱国峰

朱跃光

董小社

滕鹏国 1

陈亮 1

Related Institution

School of Electronics and Information Engineering, Xi'an Jiaotong University

Chengdu Computer Applications Institute, Chinese Academy of Sciences

Chinese Academy of Sciences University

⁰