版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、基于内容分块的Rsync核心算法改进 刘彦,张茹作者简介:刘彦(1987-),男,硕士,主要研究方向:网络与信息安全通信联系人:张茹(1976-),女,副教授,主要研究方向:数字内容安全. E-mail: 1.51.51.51.51.51.51.51.51.51.51.51.51.5School of Computer Science,BeiJing 100876;School of Computer Science,BeiJing 100876北京邮电大学计算机学院,北京 100876;北京邮电大学计算机学院,北京 100876100876;100876;北京市海淀区西土城路10号北京邮电大
2、学学十公寓;北京市海淀区西土城路10号北京邮电大学信息安全中心;刘彦(1987-),男,硕士,主要研究方向:网络与信息安全;张茹(1976-),女,副教授,主要研究方向:数字内容安全刘彦;张茹LIU Yan;ZHANG Ru张茹1.51.51.51.51.51.51.51.51.51.51.51.51*|*期刊*|*赵云,陈阿林. 基于rsync的备份方案研究与实现J. 电脑知识与技术,2012,8(5):984-987<CR>2*|*期刊*|*Utku Irmak Svilen Mihaylov Torsten Suel. Improved Single-Round Protoc
3、ols for Remote Files SynchronizationJ. INFOCOM,2005,24(3)(1665-1676).<CR>3*|*期刊*|*孙继忠,马永强,李玉华. 基于字节指纹极值特征的数据分块算法J. 软件技术与数据库,2010,36(8):69-73.<CR>4*|*论文集*|*Muthitacharoen A,Chen Bin,Mazieres D. A Low-bandwidth Network File SystemA. Vancouver. Proc. of the 18th ACM Symposium on Operating S
4、ystems PrinciplesC. Canada:ACM Press,2001. 174-187.<CR>5*|*技术报告*|*Rabin M O. Fingerprinting by Random PolynomialsR. Harvard Univ.:Center for Research in Computing Technology,TR-15-81,1981.|1|刘彦|LIU Yan|北京邮电大学计算机学院,北京 100876|School of Computer Science,BeiJing 100876|刘彦(1987-),男,硕士,主要研究方向:网络与信息安
5、全|北京市海淀区西土城路10号北京邮电大学学十公寓|100876|<CR>*|2|张茹|ZHANG Ru|北京邮电大学计算机学院,北京 100876|School of Computer Science,BeiJing 100876|张茹(1976-),女,副教授,主要研究方向:数字内容安全|北京市海淀区西土城路10号北京邮电大学信息安全中心|100876|基于内容分块的Rsync核心算法改进|An improvement for core algorithm of Rsync based on the content-based chunked algorithm|(北京邮电大学
6、计算机学院,北京 100876)摘要:Rsync是一个在unix/linux下用于同步文件的高效算法,它能同步更新两处计算机的文件与目录,并且能通过查找出文件中的不同块来减少数据传输。但Rsync的核心算法对目标文件的分块采取了固定长度分块,在某些情况下,比如只插入了一个字符,会导致同步效率的降低。随着基于内容分块算法的研究深入,对Rsync核心算法进行改进,是一次新的尝试,对灾备研究的数据恢复工作有着重要的意义。关键词:Rsync;固定长度分块;基于内容分块算法;数据恢复;中图分类号:TP393.0An improvement for core algorithm of Rsync base
7、d on the content-based chunked algorithmLIU Yan, ZHANG Ru(School of Computer Science,BeiJing 100876)Abstract: Rsync is an efficient algorithm for file synchronization on unix/linux, it can synchronize update files and directories in two computers, and find out different blocks to reduce the data er,
8、 the core algorithm of Rsync use the Fixed-Sized Partitioning for the chunk of destination file,sometimes,for example,only one character is inserted,could reduce the synchronization efficiency. With the research of the content-based chunked algorithm is deep, the improvement for core algorithm of Rs
9、ync is a attempt, it is important to data recovery from disaster research.Key words: Rsync; Fixed-Sized Partitioning; the content-based chunked algorithm;data recovery;0 引言随着全球信息化程度的加深,数据的备份问题变得越来越重要。如何进行数据恢复,更好的满足容灾备份的需要,是企业等单位不得不关心的重点问题。Rsync是一个使用广泛的远程同步工具。从unix开始,到对类unix系统的支持,再到对windows的支持,Rsync几
10、乎覆盖了所有需要进行远程同步的系统和平台。Rsync的核心算法决定了Rsync对带宽的要求不高,同时由于传输的数据量减少,也使得同步速度大大提高。Rsync的基本特点1如下:1.可以镜像保存整个目录树和文件系统;2.可以很容易做到保持原来文件的权限、时间、软硬链接等;3.无须特殊权限即可安装;4.优化的流程,文件传输效率高;5.可以使用rcp、ssh等方式来传输文件,当然也可以通过直接的socket连接;6.支持匿名传输。但Rsync的核心算法对目标文件的分块采取了固定长度分块,在某些情况下,比如只插入了一个字符,会导致同步效率的降低。为了解决这个问题,对Rsync的核心算法做了改进。1 Rs
11、ync的核心算法简介Rsync核心算法的主要步骤2是:1)在目标端,将目标文件B划分为相等大小为b字节的数据块Bi=Bib,(i+1)b-1。2)针对每个数据块Bi,计算两种校验码:l rolling checksum,为弱checksum,32位,使用的是Mark Adler发明的adler-32算法。l MD5值,为强checksum,128位,使用MD5算法。由rolling checksum来确定数据块是否相同,由于弱checksum碰撞概率太高,所以用MD5来确定数据块相同。3)目标端将目标文件B的一个checksum列表传给源端,列表包括三个值:rolling checksum(3
12、2bits),md5 checksume(128bits),文件块编号。4)源端拿到B的checksum列表后,将数据存到hash table中,用rolling checksum做hash。这个hash table是16bits的,所以,hash table的尺寸是2的16次方,对rolling checksum做hash会把列表每组数据散列到0 到 216-1中的某个整数值位置。在碰撞的情况下,做一个链表。5)在源端,将源文件A的第一个b字节长度的数据块A0,b-1取出来后做rolling checksum计算。然后到hash表中查。l 如果查到了,说明发现在B中有潜在相同的数据块,于是就
13、再比较 md5值这个强checksum。如果md5相同,这说明在B中有相同的块,我们需要记下这一块在B下的文件编号。l 如果查不到。表示这一块中有不同的信息。此时,在源端,Rsync会住后跳1个字节,取A中数据块A1,b继续做rolling checksum。6)经过如上的匹配,可以找到A中B没有的数据内容,然后发给B,B就能和A进行同步。2 数据分块算法简介在很多数据存储的应用中,都常常需要把文件划分为不同的数据块,然后计算各个数据块的哈希值,计算结果用来唯一表示该数据块,对文件的处理以分块的形式进行3。最常用的文件分块算法是FSP4,即固定长度分块(Fixed-Sized Partitio
14、ning)算法,如Rsync核心算法。固定长度分块算法是将文件划分为长度相同的数据块的算法。其基本做法是从文件内容的第一个字节开始,取事先规定好的字节长度的数据作为一个数据块,如此反复,一直到文件的末尾,若文件末尾不足实现规定好的字节长度,用空字节补齐。固定长度分块算法的不足在于,对于文件修改的反应不足。最简单的可以看到,后面数据分块的内容和前面数据分块内容是有联系的。如果前面数据分块内容发生了长度上的改变,那么后面的所有数据分块内容都会变化。所以,对同一个文件修改前后做同样长度的固定长度分块,得到的相同数据分块会很少。这是固定长度分块算法的不稳定性所在。基于内容的分块方算法解决了这个问题。从
15、上面的分析可以看到,如果文件修改可以独立于分块边界存在,就可以使得分块稳定。基于内容的分块算法,突破了固定长度的限制,对文件修改的反应更好。从分块上来说,可以极大的减少由于文件修改而改变的数据块内容。基于内容的分块算法的基础是通过一种算法来确定分块的分界点。通常的做法是,取一个字节,按照给定方式取该字节相关的一段数据进行计算,检查计算结果是否符合事先设定的边界点要求,如果符合,则这个字节为一个边界;如果不符合,则取一个字节进行计算。重复以上计算,直到文件结束。由上可以看到,数据分块的两个边界只和边界数据的内容相关,只要修改内容没有发生在影响边界计算的两端,就不会影响其他数据分块。以上称为分块的
16、稳定性。对同一个文件进行修改,在修改前后分别进行固定长度分块和基于内容的分块,可以发现后者在修改前后有大量相同的数据分块内容。3 基于内容的分块算法在改进的Rsync核心算法中,本文采取了BSW算法4,即基本滑动窗口算法 (Basic Sliding Window)。基本滑动窗口算法是典型的基于内容的分块算法。正如前文所言,对文件内容的某一个字节,往后取w字节长度的数据内容,对这块字节长度为w的数据内容做指纹函数(如Rabin指纹5)计算,得到计算结果H,这个时候要检验H是不是符合我们事先设定的边界点要求。边界点要求的算法是,看HmodD的结果是不是等于r。D和r是事先选择好的两个整数,且D大
17、于r。如果HmodD等于r,则该字节是一个数据块的分界点。依次往下进行,直到确定所有的分界点。可以看到,基于内容的分块算法的数据块长度是不同的。事实上,对于基于内容的分块算法而言,通常有个对数据块长度的期望大小。由上可知,字节长度w,选择的两个整数D和r,是影响数据块长度的期望大小的,需要进行合适的选择。与固定长度分块算法相比,基本滑动窗口算法的各个数据块的分界是独立的,基本不受该数据块中间内容变化的影响,不也会影响下一个分界点,符合分块稳定性的要求。4 改进的Rsync核心算法基于内容分块的Rsync核心算法的主要步骤是:1) 在目标端,将目标文件B用BSW算法划分为大小不等的各数据块Bi。
18、2) 针对每个数据块Bi,计算两种校验码:rolling checksum和MD5值。3) 目标端将目标文件B的一个checksum列表传给源端,列表包括三个值:rolling checksum(32bits),md5 checksume(128bits),文件块编号。列表示例:<Bi;rolling checksum;md5>。4) 源端拿到B的checksum列表后,将数据存到hash table中,用rolling checksum做hash。这个hash table是16bits的,所以,hash table的尺寸是2的16次方,对rolling checksum做hash
19、会把列表每组数据散列到0 到 216-1中的某个整数值位置。在碰撞的情况下,做一个链表。5) 在源端,将源文件A用BSW算法划分为大小不等的各数据块Ai。然后计算Ai的两个校验码,用rolling checksum去哈希表里查:如果查到了,说明发现在B中有潜在相同的数据块,于是就再比较 md5值这个强checksum。如果md5相同,这说明在B中有相同的块,我们需要记下这一块在B下的文件编号。如果查不到。表示这一块是不同的内容。此时,在源端,Rsync对下一个A中的数据块继续做rolling checksum。6) 经过如上的匹配,可以找到A中B没有的数据内容,然后发给B,B就能和A进行同步。
20、我们现在假设源文件A在目标文件B的基础上只插入了一个字符,使用BSW分组后有下图所示三种情况:(Bi分别代表强弱校验不全相同的数据块)目标文件B的分块:B1B2B3B4B5B6B7图1 目标文件分块示意图源文件A的分块:1.插入字符未改变边界。肯定会改变了它所位于的数据块内容,导致校验值改变。B1A1B3B4B5B6B7图2 源文件分块示意图a2.插入字符形成了新的边界:B1A2A3B3B4B5B6B7图3 源文件分块示意图b3.插入字符导致边界消失:B1B2A4B5B6B7图4 源文件分块示意图c由上可知:不论是那种情况都只需要传1-2个数据块的内容覆盖原内容即可。对比校验过程来说,所需要的
21、计算量仅为数据块的数目。而对于改进前的算法来说,需要的计算量最大可能为块长度+数据块数目。如果进行了多处改动,可能得到以上三种结果的结合;但由于边界值的稳定性,所以多数情况下得到的是1类结果,而且很多相邻处的改动只导致一个数据块的变化。综上所述,改进后的算法主要解决了原算法的两点不足:1) 基于内容分块取代固定长度分块,使得算法对数据变化的适应能力加强了;2) 原算法中源端和目标端两端的计算量不对等,源端计算量偏大,需要对每个数据块进行反复的扫描和查找匹配;改进后,两端的计算量比较均衡,源端的计算量大大降低了。5 实验分析:在模拟环境下,选择了如下4组样本数据,分别存储在源端和目的端:表1 样
22、本数据样本编号文件个数文件总大小(k)46507978322C502489164D22801500241然后对源端的数据进行修改后,存储相同的两份修改后数据,分别用于改进前的Rsync和模拟的改进后Rsync算法进行了数据恢复;原Rsync算法:表2 原Rsync算法实验数据样本编号文件总大小(k)实际传输数据(k)恢复时间(s)A16193760371114B978322387059386C891643728443D500241296893191平均值432416195402184改进后的Rsync算法:表3 改进的Rsync算法实验数据样本编号文件总大小(k)实际传输数据(k)恢复时间(s)A1619373370492B978322328006347C891642893344D500241244157172平均值432416158700164由以上两组数据对比得出,改进后的Rsyn
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学一年级心理健康教学设计 我喜欢我自己自我认知启蒙课
- 关于重庆市废旧电池回收项目战略融资投资回报测算
- 双碳约束下智能制造安全装备能否成为重化工的第二曲线
- 十五五期间:智能台式洗碗机在预制菜零售业的落地实践
- 药品管理法培训课件
- 关于2026年营销活动费用预算调整的回复函(6篇)
- 网络设备安全配置网络安全专家预案
- 办公桌椅配置与使用标准手册
- 催促2026年度对账截止日期执行催办函(3篇范文)
- 关于2026年电商平台订单处理流程优化的确认函(5篇)
- 糖尿病医学营养治疗中国专家共识(2026版)
- TCCEAS 008-2026 建设工程造价咨询成果文件质量标准
- 2026年保安员押运勤务规范题含答案
- 2026届高三语文理解性默写60篇(教师版)
- 2026儿童益智玩具市场发展分析与发展趋势及投资前景预测报告
- 余额宝相关课件
- (重点)采购师(中级)职业能力等级认证近年考试真题题库-含答案
- 智驭未来:AI工具辅助高效学习与科研(天津师范大学)学习通网课章节测试答案
- 2025年医学生物化学基础知识综合测试卷答案及解析
- 工会经费审计条例课件
- 保安督察管理办法
评论
0/150
提交评论