基于位串内容感知的数据分块算法

计算机工程与科学

基于位串内容感知的数据分块算法

周斌1，朱容波1，张莹2

（1.中南民族大学计算机学院，湖北武汉 430074；2.华中科技大学外国语学院，湖北武汉 430074）

收稿日期:2016-03-18 修回日期:2016-05-03 出版日期:2016-10-25 发布日期:2016-10-25
基金资助:
国家自然科学基金（61272497）；湖北省自然科学基金（2013CFB447）

A bit string contentaware data chunking algorithm

ZHOU Bin1, ZHU Rongbo1, ZHANG Ying2

（1.College of Computer Science, SouthCentral University For Nationalities, Wuhan 430074；

2. School of Foreign Languages, Huazhong University of Science and Technology, Wuhan 430074, China）

Received:2016-03-18 Revised:2016-05-03 Online:2016-10-25 Published:2016-10-25

摘要/Abstract

摘要：

针对基于内容的可变长度的分块CDC算法中数字签名计算需要耗费大量CPU开销的问题，提出了一种基于位串内容感知的数据块分块算法。算法利用每一次失败匹配尝试所带来的位特征信息，最大限度地排除不能匹配的位置，从而获得最大的跳跃长度，减少中间计算和比较的开销。实验结果表明，本算法减小了数据分块过程中数字签名计算的开销，降低了确定块边界时的CPU资源消耗，从而优化了数据分块的时间性能。

关键词: 位串内容感知, 数据分块, 数字签名

Abstract:

Aiming at the problem of a large amount of overhead introduced by the content defined chunking algorithm (CDC) in calculating the digital signature, we present a novel data chunking algorithm based on bit string content awareness.The proposed algorithm eliminates unmatched positions to the utmost by taking advantage of the bit feature information acquired through each failure matching.Since the maximum jump length is obtained, intermediate calculation and comparison cost are reduced.Experimental results show that the algorithm can reduce the overhead of digital signature calculation in the process of data chunking, cut down CPU resource consumption for chunk boundary determination, and optimize the time performance of data chunking.

Key words: bit string contentaware, data chunking, digital signature

周斌1，朱容波1，张莹2. 基于位串内容感知的数据分块算法[J]. 计算机工程与科学.

ZHOU Bin1, ZHU Rongbo1, ZHANG Ying2. A bit string contentaware data chunking algorithm[J]. Computer Engineering & Science.

参考文献

［1］You L,Pollack T,Long E.Deep store: An archival storage system architecture［C］∥Proc of the 21stth International Conference on Data Engineering (ICDE’05),2005:804815.

［2］Guo L,Efstathopoulos P.Building a highperformance deduplication system［C］∥ Proc of the 2011 USENIX Annual Technical Conference (USENIX’11),2011:25.

［3］Meyer D,Bolosky J.A study of practical deduplication［C］∥ Proc of the 9th USENIX Conference on File and Stroage Technologies (FAST’11),2011:114.

［4］Xie F,Condict M,Shete S.Estimating duplication by contentbased sampling［C］∥ Proc of the 2013 USENIX Conference on Annual Technical Conference (ATC’13),2013:181186.

［5］Ao Li,Shu Jiwu,Li Mingqiang.Data deduplication techniques［J］.Journal of Software,
2010,21(5):916929.(in Chinese)

［6］Sun Ailing,Ran Luchun.Design and implementation of a data deduplicationbased network file backup system［J］.Computer Applications and Software,
2014,31(10):8690.(in Chinese)

［7］Zheng Yaguang,Pan Jiuhui.A duplicate data detection algorithm based on sliding blocking［J］.Computer Engineering,
2016,42(2):3844.(in Chinese)

［8］Muthitacharoen A,Chen B,Mazières D.A lowbandwidth network file system［C］∥ Proc of Symposium on Operating Systems Principles (SOSP’01),2001:174187.

［9］Min J,Yoon D,Won Y.Efficient deduplication techniques for modern backup operation［J］.IEEE Transactions on Computers,2011,6(6):824840.

［10］Jain N,Dahlin M,Tewari R.Taper:Tiered approach for eliminating redundancy in replica synchronization［C］∥Proc of the 4th Conference on USENIX Conference on File and Storage Technologies (FAST’05),2005:21.

附中文参考文献：

［5］敖莉，舒继武，李明强．重复数据删除技术［J］.软件学报， 2010， 21(5) : 916929．

［6］孙爱玲，冉禄纯．一种基于重复数据删除的网络文件备份系统设计与实现［J］.计算机应用与软件，2014，31(10):8690．

［7］郑亚光，潘久辉.一种基于滑动分块的重复数据检测算法［J］.计算机工程，2016,42(2):3844.

[1]	阮鸥, 陈吉晨, 毛浩. 一种高效的SM2数字签名批量验证算法[J]. 计算机工程与科学, 2021, 43(07): 1236-1242.
[2]	魏亮1,2，黄振杰1，陈群山2. 去中心基于属性不可否认签名[J]. 计算机工程与科学, 2020, 42(06): 1003-1011.
[3]	左黎明1,2，张婷婷1,2，郭红丽1,2，陈祚松1,2. 对一个基于身份的部分盲签名方案的攻击与改进[J]. 计算机工程与科学, 2017, 39(10): 1832-1836.
[4]	李丽娟，郭亚杰. 一种改进的ElGamal数字签名方案[J]. J4, 2016, 38(06): 1097-1102.
[5]	张佳佳1，姜卫东1，李宽2. 基于OpenMP的包络对齐并行方法研究与实现[J]. J4, 2015, 37(11): 2025-2029.
[6]	许德武. 电子商务签密方案的改进与安全性分析[J]. J4, 2013, 35(7): 77-81.
[7]	高博1，李彦2. 一种基于硬件特征和动态许可证的服务器端软件授权认证模型[J]. J4, 2013, 35(2): 56-61.
[8]	俞波1，陈建平1，顾翔2. 一种基于数字签名的实用电子投票系统[J]. J4, 2012, 34(5): 40-44.
[9]	赵鑫，王晓东. 无线传感器网络快速广播认证协议研究[J]. J4, 2010, 32(4): 106-109.
[10]	明德廷,李娟,杨珺. 对加密的XML数据查询算法的研究与实现[J]. J4, 2010, 32(4): 142-145.
[11]	阚元平. 基于椭圆曲线的具有消息恢复特性的签名方案[J]. J4, 2010, 32(2): 58-59.
[12]	余胜生陈本初夏涛周敬利. SSL VPN系统服务器端的分布式解密／数字签名[J]. J4, 2007, 29(8): 30-32.
[13]	郭伟青[1] 求伟[2] 童华章[3]. 一种基于身份证书的数字签名方案设计[J]. J4, 2007, 29(7): 4-5.
[14]	李顺吉[1,2] 徐秋亮[1] 蒋翰[1]. 基于双线性映射的前向安全签名方案研究[J]. J4, 2007, 29(3): 19-22.
[15]	宁竞钟诚. 一种具有前向安全的椭圆曲线（t,n）门限数字签名方案[J]. J4, 2007, 29(2): 29-31.