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

doi:10.7652/xjtuxb201310009

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-09

- A Grouping Prediction Method Based on Undirected Graph Traversal in De-Duplication System
- Vol. 47, Issue 10, Pages: 51-56(2013)
- 作者机构：
  
  西安交通大学电子与信息工程学院,西安,710049
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201310009
  CLC： TP333
- Online First：10 October 2013，
  
  Published：2013
- 稿件说明：
移动端阅览
A Grouping Prediction Method Based on Undirected Graph Traversal in De-Duplication System[J]. 2013, 47(10): 51-56.
DOI：

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]

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

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

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

Sensitivity Analysis of Foil Geometrical Parameters for the Third-Generation CO2 Gas Foil Bearings Based on Design of Experiments Method

Numerical Simulation of the Energy Conversion Process in Thermoacoustic Engines with Different Stack Materials

Electrothermal Coupling Research on the Evolutionary Law of Anti-Corona Performance for High-Altitude Air-Cooled Generators

Related Author

王龙翔 1

董凯 2

王鹏博 1

董小社 1

张兴军 1

朱正东 1

张利平 1

Related Institution

School of Computer Science and Technology, Xi’an Jiaotong University

⁰