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

王龙翔; 张兴军; 朱国峰; 朱跃光; 董小社

doi:10.7652/xjtuxb201310009

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-09

- 重复数据删除中的无向图遍历分组预测方法
- A Grouping Prediction Method Based on Undirected Graph Traversal in De-Duplication System
- 西安交通大学学报 2013年47卷第10期页码：51-56
- 作者机构：
  
  西安交通大学电子与信息工程学院,西安,710049
- 作者简介：
- 基金信息：
  
  : 2012-12-20。作者简介: 王龙翔(1988—),男,博士生;张兴军(通信作者),男,副教授,博士生导师。基金项目: 国家科技支撑计划资助项目(2011BAH04B03);国家自然科学基金资助项目(61173039);国家高技术研究发展计划资助项目(2011AA01A204)
- DOI：10.7652/xjtuxb201310009
  中图分类号： TP333
- 网络首发：2013-10-10，
  
  纸质出版：2013
- 稿件说明：
移动端阅览
王龙翔, 张兴军, 朱国峰, 等. 重复数据删除中的无向图遍历分组预测方法[J]. 西安交通大学学报, 2013,47(10):51-56.

A Grouping Prediction Method Based on Undirected Graph Traversal in De-Duplication System[J]. 2013, 47(10): 51-56.
王龙翔, 张兴军, 朱国峰, 等. 重复数据删除中的无向图遍历分组预测方法[J]. 西安交通大学学报, 2013,47(10):51-56. DOI： 10.7652/xjtuxb201310009.

A Grouping Prediction Method Based on Undirected Graph Traversal in De-Duplication System[J]. 2013, 47(10): 51-56. DOI： 10.7652/xjtuxb201310009.

摘要

针对重复数据删除系统中存储容量受内存限制难以进行扩展的问题

提出了一种基于无向图遍历的重复数据删除分组预测方法。该方法将索引表保存在磁盘中

并在内存中维护索引表缓存

以此提高系统最大可支持的存储容量。对于索引表缓存命中率低、系统性能差的问题

采用了图遍历分组方法予以解决

根据数据块访问序列特征信息建立无向图并进行分析

基于分析结果对索引项进行分组

并以组进行缓存替换

从而提高缓存命中率和系统性能。实验结果表明

基于缓存预取原理和无向图遍历分组

在将缓存设置为索引表大小的10%时

重复数据删除存储系统最大存储容量比原有方法提高了7.5倍

缓存命中率由不进行索引项分组时的47%提高到87.6%。

Abstract

An index table grouping prediction method is proposed based on undirected graph traversal to solve the problem that the data storage capacity of the de-duplication system is limited by the memory and is difficult to expand into large-scale. The method saves the index in a disk and maintains the cache of index in memory to expand the maximum storage capacity of system. The hit rate of the grouping prediction and the system performance are improved by grouping index entries based on undirected graph traversal. The method sets up and analyzes the undirected graph based on the features of data chunk sequences

and the groups generated by analyzing the graph is used in cache replacement. Experimental results show that since the proposed method bases on the cache prefetching and the hash table grouping

the index table cache hit rate of the method increases from 47% to 87.6%

and the maximum storage capacity of IDSMS system is 7.5 times higher than that of the existing method for the cache consuming only 10% of the index table size.

关键词

Keywords

references

DUBOIS L, AMALDAS M, SHEPPARD E. Key considerations as deduplication evolves into primary storage, White Paper 223310 [R]. Framingham, MA, USA: IDC, 2011.

顾瑜, 刘川意, 孙林春, 等. 带重复数据删除的大规模存储系统可靠性保证 [J]. 清华大学学报:自然科学版, 2010, 50(5): 739-744.

GU Yu, LIU Chuanyi, SUN Linchun, et al. Reliability provision mechanism for large-scale de-duplication storage systems [J]. Journal of Tsinghua University: Science and Technology, 2010, 50(5): 739-744.

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

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

ZHU B, LI Kai, PATTERSON H. Avoiding the disk bottleneck in the data domain deduplication file system [C]∥Proceedings of the 6th USENIX Conference on File and Storage Technologies. Berkeley, CA, USA: USENIX, 2008: 269-282.

BHAGWAT D, ESHGHI K, LONG D D E, et al. Extreme binning: scalable, parallel deduplication for chunk-based file backup [C]∥Proceedings of the IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems. Piscataway, USA: IEEE, 2009: 1-9.

LILLIBRIDGE M, ESHGHI K, BHAGWAT D, et al. Sparse indexing: large scale, inline deduplication using sampling and locality [C]∥Proceedings of the 7th Conference on File and Storage Technologies. Berkeley, CA, USA: USENIX, 2009: 111-123.

MIN J, YOON D, WON Y. Efficient deduplication techniques for modern backup operation [J]. IEEE Transactions on Computers, 2011, 60(6): 824-840.

BOBBARJUNG D R, JAGANNATHAN S, DUBNICKI C. Improving duplicate elimination in storage systems [J]. ACM Transactions on Storage, 2006, 2(4): 424-448.

TSUCHIYA Y, WATANABE T. DBLK: deduplication for primary block storage [C]∥Proceedings of the 27th IEEE Symposium on Mass Storage Systems and Technologies. Piscataway, USA: IEEE, 2011: 1-5.

TOMAZIC S, PAVLOVIC V, MILOVANOVIC J, et al. Fast file existence checking in archiving systems [J]. ACM Transactions on Storage, 2011, 7(1): 24-44.

WILDANI A, MILLER E L, RODEH O. Hands: a heuristically arranged non-backup in-line deduplication system, UCSC-SSRC-12-03 [R]. Piscataway, USA: IEEE, 2012.

WILDANI A, MILLER E, WARD L. Efficiently identifying working sets in block I/O streams [C]∥Proceedings of the 4th Annual International Conference on Systems and Storage. New York, USA: ACM, 2011: 46-57.

ZHU Guofeng, ZHANG Xingjun, WANG Longxiang, et al. An intelligent data de-duplication based backup system [C]∥Proceedings of the 15th International Conference on Network-Based Information Systems. Piscataway, USA: IEEE, 2012: 771-776.

吕正,陈昊,陈峰,等.一种ARM存储模型的快速检测方法.2013,47(6):68-72.[doi:10.7652/xjtuxb201306012]

边根庆,高松,邵必林,等.面向分散式存储的云存储安全架构.2011,45(4):41-45.[doi:10.7652/xjtuxb201104008]

余思,桂小林,黄汝维,等.一种提高云存储中小文件存储效率的方案.2011,45(6):177-181.[doi:10.7652/xjtuxb 2011 06011]

黄汝维,桂小林,余思,等.支持隐私保护的云存储框架设计.2011,45(10):1-6.[doi:10.7652/xjtuxb201110001]

颜秉珩,钱德沛.一种支持负载均衡的存储调度算法.2009,43(10):61-65.[doi:10.7652/xjtuxb200910013]

颜秉珩,钱德沛.面向存储资源管理的多协议存储系统.2009,43(6):10-14.[doi:10.7652/xjtuxb200906003]

浏览量

下载量

CSCD

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

提交

工具集

关联资源

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

融合物理信息与深度算子网络的变压器绕组热-流场快速计算方法

三塔合一间接空冷系统结构参数对夏季运行特性的影响研究

张角凹坑气膜孔对双层壁气膜冷却特性的影响

水蒸气掺混对氨裂解气旋流燃烧与排放特性的影响研究