一种基于内容分块的层次化去冗优化策略

doi:10.3969/j.issn.0372-2112.2019.05.017

电子学报 ›› 2019, Vol. 47 ›› Issue (5): 1094-1100.DOI: 10.3969/j.issn.0372-2112.2019.05.017

一种基于内容分块的层次化去冗优化策略

李建江, 马占宁, 张凯

北京科技大学计算机科学与技术系, 北京 100083

收稿日期:2017-12-26 修回日期:2018-07-13 出版日期:2019-05-25
- 通讯作者:
- 张凯
- 作者简介:
- 李建江 男,1971年出生,四川人,2005年毕业于清华大学计算机科学与技术系,获博士学位.于2014年1月至2015年1月在天普大学以访问学者的身份进行学术交流.现为北京科技大学计算机与通信工程学院副教授.主要研究方向为并行计算、云计算、并行编译和大数据.E-mail:jianjiangli@163.com;马占宁 男,1988年出生,山东人,2016年毕业于北京科技大学计算机科学与技术系,获硕士学位.主要研究方向为分布式存储和数据冗余去除.
- 基金资助:
- 国家重点研发计划课题 (No.2017YFB0202104，No.2017YFB0202003）

An Optimal Hierarchical Deduplication Strategy Based on Content Defined Chunking

LI Jian-jiang, MA Zhan-ning, ZHANG Kai

Department of Computer Science and Technology, University of Science and Technology Beijing, Beijing 100083, China

Received:2017-12-26 Revised:2018-07-13 Online:2019-05-25 Published:2019-05-25

摘要/Abstract

摘要： 在过去的数十年中，信息数据量呈现指数级增长，如何存储和保护这些大量信息数据成为一个难题.云存储和冗余去重技术成为解决上述难题的主要技术.去冗技术在云存储系统中得到广泛应用，但主流的云存储系统存在索引信息的膨胀以及数据分块的不确定性等不足，而这些弊端会导致内存空间的浪费和数据分块的不可预知性.针对这些问题，提出了一种基于内容分块的层次化去冗优化策略，并构建了对应的算法，解决了云存储系统中索引信息表过大和数据分块过大或过小的问题.并且选取CNN新闻的页面内容作为测试集进行实际测试，通过比较去冗比和去冗时间可以看出，相比于目前主流的去冗策略，本文提出的基于内容分块的层次化去冗优化策略能够提升3%左右的去冗比，同时降低2%左右的去冗时间.

关键词: 云存储, 冗余去重技术, 数据分块, 层次化, 去冗比

Abstract: In the past decades,the amount of information data is growing in an unexpected speed and how to store and protect these large amounts of data becomes a problem.Cloud storage and data deduplication technology are the principal technology to solve the above problem.Deduplication technology is widely used in cloud storage systems.However,there are some shortcomings such as the expansion of the index information and the uncertainty of the data block in the current mainstream cloud storage technology,which lead to the waste of space and a big difference in the length of the data block.To overcome these shortcomings,through the study of cloud storage and data deduplication,this paper presents an optimal hierarchical deduplication strategy based on content defined chunking and proposes the corresponding algorithm,and achieves the purpose of saving memory space and obtaining better compression performance.Finally,this paper selects the content of the CNN news as a test set.By comparing the compression ratio and the compression time,the optimal hierarchical deduplication strategy has increased compression ratio by 3% and reduced compression time by 2% compared with the current mainstream deduplication strategy.

Key words: cloud storage, data deduplication, data block partition, hierarchical, compression ratio

中图分类号:

TP312

李建江, 马占宁, 张凯. 一种基于内容分块的层次化去冗优化策略[J]. 电子学报, 2019, 47(5): 1094-1100.

LI Jian-jiang, MA Zhan-ning, ZHANG Kai. An Optimal Hierarchical Deduplication Strategy Based on Content Defined Chunking[J]. Acta Electronica Sinica, 2019, 47(5): 1094-1100.

参考文献

[1] Reinsel G D,Gantz J.The digital universe decade-are you ready?[R].IDC White Paper,2010.1-16.
[2] Reinsel D.Our expanding digital world:Can we contain it? Can we manage it?[A].Intelligent Storage Workshop (ISW)[C].USA:University of Minnesota,2008.13-14.
[3] Nath P,Urgaonkar B,Sivasubramaniam A.Evaluating the usefulness of content addressable storage for high-performance data intensive applications[A].Proc of the 17th Int Symp on High Performance Distributed Computing[C].New York:ACM,2008.35-44.
[4] Gantz J,Reinsel D.As the economy contracts,the digital universe expands[R].IDC Multimedia White Paper,2009.1-10.
[5] Sapuntzakis C P,Chandra R,Pfaff B,et al.Optimizing the migration of virtual computers[J].ACM SIGOPS Operating Systems Review,2002,36(SI):377-390.
[6] Kumar N,Rawat R,Jain S C.Bucket based data deduplication technique for big data storage system[A].Reliability,Infocom Technologies and Optimization (Trends and Future Directions)(ICRITO),20165th International Conference on.IEEE[C].USA:IEEE Press,2016.267-271.
[7] Bobbarjung D R,Jagannathan S,Dubnicki C.Improving duplicate elimination in storage systems[J].ACM Transactions on Storage (TOS),2006,2(4):424-448.
[8] Muthitacharoen A,Chen B,Mazieres D.A low-bandwidth network file system[A].ACM SIGOPS Operating Systems Review[C].New York:ACM,2001,35(5):174-187.
[9] Broder A Z.Some Applications of Rabin's Fingerprinting method[M].Berlin:Springer,1993.143-152.
[10] Widodo R N S,Lim H,Atiquzzaman M.A new content-defined chunking algorithm for data deduplication in cloud storage[J].Future Generation Computer Systems,2017,71:145-156.
[11] Eshghi K,Lillibridge M,Wilcock L,et al.Jumbo store:providing efficient incremental upload and versioning for a utility rendering service[A].USENIX Conference on File and Storage Technologies[C].California:USENI,2007.123-138.
[12] Zhang X,Zhu G,Wang E,et al.Data de-duplication with adaptive chunking and accelerated modification identifying[J].Computing and Informatics,2016,35(3):586-614.
[13] 吕石磊,余顺争.一种基于中间件的RFID系统阅读器去冗余算法[J].电子学报,2012,40(5):965-970. LÜ S L,YU S Z.A middleware-based algorithm for redundant reader elimination in RFID systems[J].Acta Electronica Sinica,2012,40(5):965-970.(in Chinese)

[1]	任正伟, 李雪婷, 王丽娜, 童言, 徐士伟, 丁炜. 云存储中外包数据确定性删除研究综述[J]. 电子学报, 2022, 50(10): 2542-2560.
[2]	叶俊民, 罗达雄, 陈曙. 基于层次化修正框架的文本纠错模型[J]. 电子学报, 2021, 49(2): 401-407.
[3]	杜怡然, 李伟, 戴紫彬. PVHArray:一种流水可伸缩的层次化可重构密码逻辑阵列结构[J]. 电子学报, 2020, 48(4): 781-789.
[4]	王亚文, 郭云飞, 刘文彦, 霍树民, 杨超. 面向云存储安全的可自愈拜占庭Quorum系统[J]. 电子学报, 2020, 48(4): 675-681.
[5]	杜瑞忠, 石朋亮, 田俊峰. 基于DDCT表的多副本完整性审计方案[J]. 电子学报, 2020, 48(1): 164-171.
[6]	王小峰, 陈培鑫, 周寰, 苏金树. 一种可信安全的层次式基于身份加密系统[J]. 电子学报, 2016, 44(7): 1521-1529.
[7]	周洪丞, 杨超, 马建峰, 张俊伟. 云端数据异地容灾验证方案研究[J]. 电子学报, 2016, 44(10): 2485-2494.
[8]	李春林, 廖丹, 熊玲, 黄月江. 一种基于QoE量化评估的服务选择算法[J]. 电子学报, 2015, 43(11): 2145-2150.
[9]	谢显中, 黄倩, 王柳苏, 马彬. 一种云存储中基于干扰对齐的多节点精确修复方法[J]. 电子学报, 2014, 42(10): 1873-1881.
[10]	王宁, 杨扬, 孟坤, 陈宇, 王磊, 季青. 云计算环境下基于用户体验的成本最优存储策略研究[J]. 电子学报, 2014, 42(1): 20-27.
[11]	周恩光, 李舟军, 郭华, 贾仰理. 一个改进的云存储数据完整性验证方案[J]. 电子学报, 2014, 42(1): 150-154.
[12]	邓立宝;乔立岩;俞洋;彭喜元. 一种改进的层次化SOCs并行测试封装扫描单元[J]. 电子学报, 2012, 40(5): 949-954.
[13]	王丽娜;;任正伟;余荣威;韩凤;董永峰. 一种适于云存储的数据确定性删除方法[J]. 电子学报, 2012, 40(2): 266-272.
[14]	祝永志, 张丹丹, 曹宝香, 禹继国. 基于SMP机群的层次化并行编程技术的研究[J]. 电子学报, 2012, 40(11): 2206-2210.
[15]	李建敦, 彭俊杰, 张武. 云存储中一种基于布局的虚拟磁盘节能调度方法[J]. 电子学报, 2012, 40(11): 2247-2254.

一种基于内容分块的层次化去冗优化策略

An Optimal Hierarchical Deduplication Strategy Based on Content Defined Chunking

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics