您的位置: 首页 > 技术文档 > 网络编程 > 数据同步算法研究
vs 2010 web部署 回到列表 25个最佳最闪亮的Eclipse开发项目
 数据同步算法研究

作者:刘爱贵 时间: 2010-08-12 文档类型:转载 来自:CSDN

第 1 页 数据同步算法研究 [1]
第 2 页 数据同步算法研究 [2]
第 3 页 数据同步算法研究 [3]
第 4 页 数据同步算法研究 [4]

1、引言

基于LAN或WAN的网络应用之间进行数据传输或者同步非常普遍,比如远程数据镜像、备份、复制、同步,数据下载、上传、共享等等,最为简单的做法自然就是对数据进行完全复制。然而,数据在网络上来回被复制多次后就会存在大量副本,很多情形下这些文件副本之间仅有很小的差异,很可能是从同一个文件版本演化而来。如果对文件进行完全复制,在文件较大的情况下,会占用大量网络带宽,同步时间也会较长。

目前,广域网WAN的带宽与访问延迟仍然是急需解决的问题,完全复制使得很多网络应用无法提供良好的服务质量,比如分布式文件系统(DFS)、云存储(Cloud Storage)。Rsync与RDC(Remote Differential Compression)是两种最为常见的数据同步算法,它们仅传输差异数据,从而节省网络带宽并提高效率。本文基于这两种算法思想并借助重复数据删除(De-duplication)技术,对数据同步算法进行深入研究与分析,并研发了原型系统。首先介绍rsync与RDC算法,然后详细描述算法设计与相应的数据结构,并重点分析文件分块、差异编码、文件同步算法,最后简介推拉两种应用模式。

2、相关工作

Rsync是类Unix环境下的一个高效的远程文件复制(同步)工具,它通过著名的Rsync算法来优化流程,减少了数据通信量并提高文件传输效率。假设现在有两台计算机Alpha和Beta ,计算机Alpha能够访问A文件,计算机Beta能够访问B文件,文件A和B非常相似,计算机Alpha和Beta通过低速网络互联。它的大致流程如下(详细过程请参考Rsync作者Andrew Tridgell的tech_report.ps):

1、Beta将文件B分割成连续不重叠的固定大小数据块S,最后一个数据块上可能会小于S字节;

2、Beta对于每一个数据块,计算出两个校验值,一个32位的弱滚动校验和一个128位的MD4校验;

3、Beta将校验值发送给Alpha;

4、Alpha通过搜索文件A的所有大小为S的数据块(偏移量可以任意,不一定非要是S的倍数),来寻找与文件B的某一块有着相同的弱校验码和强校验码的数据块。这主要由滚动校验Rolling checksum快速完成;

5、Alpha给Beta发送重构A文件的指令,每一条指令是一个文件B数据块引用(匹配)或者是文件A数据块(未匹配)。

Rsync是一个非常优秀的工具,但它仍然存在一些不足之处。

1、Rolling checksum虽然可以节省大量checksum校验计算量,也对checksum搜索作了优化,但多出一倍以上的hash查找,这个消耗不小;

2、Rsync算法中,Alpha和Beta计算量是不对等的,Alpha计算量非常大,而Bete计算量非常小。通常Alpha是服务器,因此压力较大;

3、Rsync中数据块大小是固定的,对数据变化的适应能力有限。

RDC算法的典型代表是微软DFS中的DFSR(Distributed File System Replication),它与Rsync不同之处在于采用一致的分块规则对复制的源文件和目标文件进行切分。因此,RDC对于源端和目标端的计算量是对等的。RDC和RSync算法在设重点上有所不同,Rsync追求更高的重复数据发现而不惜计算量;RDC在两者之间作了一个折衷,目标是以少量的计算快速发现数据差异,当然重复数据发现不及Rsync。另外,Rsync是定长分块策略,而RDC是变长分块策略。

3、重复数据删除技术

De-duplication,即重复数据删除,它是一种非常新的且流行度很高的存储技术,可以大大减少数据的数量。重复数据删除技术,通过数据集中重复的数据,从而消除冗余数据。借助dedup技术,可以提高存储系统的效率,有效节约成本、减少传输过程中的网络带宽。同时它也是一种绿色存储技术,能有效降低能耗。

Dedupe按照消重的粒度可以分为文件级和数据块级。文件级的dedup技术也称为单一实例存储(SIS, Single Instance Store),数据块级的重复数据删除,其消重粒度更小,可以达到4-24KB之间。显然,数据块级的可以提供更高的数据消重率,因此目前主流的 dedup产品都是数据块级的。将文件都分割成数据块(定长或变长的数据块),采用MD5或SHA1等Hash算法 (可以同时使用两种或以上hash算法或CRC校验等,以获得非常小概率的数据碰撞发生)为数据块计算指纹(FP, Fingerprint)。具有相同FP指纹的数据块即可认为是相同的数据块,存储系统中仅需要保留一份。这样,一个物理文件在存储系统就对应一个逻辑表示,由一组FP组成的元数据。当进行读取文件时,先读取逻辑文件,然后根据FP序列,从存储系统中取出相应数据块,还原物理文件副本。

出处:CSDN
责任编辑:bluehearts

上一页 下一页 数据同步算法研究 [2]

◎进入论坛网络编程版块参加讨论

热门搜索:CSS Fireworks 设计比赛 网页制作 web标准 用户体验 UE photoshop Dreamweaver Studio8 Flash 手绘 CG
站点最新 站点最新列表
周大福“敬•自然”设计大赛开启
国际体验设计大会7月将在京举行
中国国防科技信息中心标志征集
云计算如何让安全问题可控
云计算是多数企业唯一拥抱互联网的机会
阿里行云
云手机年终巨献,送礼标配299起
阿里巴巴CTO王坚的"云和互联网观"
1499元买真八核 云OS双蛋大促
首届COCO桌面手机主题设计大赛
栏目最新 栏目最新列表
浅谈JavaScript编程语言的编码规范
如何在illustrator中绘制台历
Ps简单绘制一个可爱的铅笔图标
数据同步算法研究
用ps作简单的作品展示页面
CSS定位机制之一:普通流
25个最佳最闪亮的Eclipse开发项目
Illustrator中制作针线缝制文字效果
Photoshop制作印刷凹凸字体
VS2010中创建自定义SQL Rule
>> 分页 首页 前页 后页 尾页 页次:1/41个记录/页 转到 页 共4个记录 分享按钮

蓝色理想版权申明:除部分特别声明不要转载,或者授权我站独家播发的文章外,大家可以自由转载我站点的原创文章,但原作者和来自我站的链接必须保留(非我站原创的,按照原来自一节,自行链接)。文章版权归我站和作者共有。

转载要求:转载之图片、文件,链接请不要盗链到本站,且不准打上各自站点的水印,亦不能抹去我站点水印。

特别注意:本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有,文章若有侵犯作者版权,请与我们联系,我们将立即删除修改。

您的评论
用户名:  口令:
说明:输入正确的用户名和密码才能参与评论。如果您不是本站会员,你可以注册 为本站会员。
注意:文章中的链接、内容等需要修改的错误,请用报告错误,以利文档及时修改。
不评分 1 2 3 4 5
注意:请不要在评论中含与内容无关的广告链接,违者封ID
请您注意:
·不良评论请用报告管理员,以利管理员及时删除。
·尊重网上道德,遵守中华人民共和国的各项有关法律法规
·承担一切因您的行为而直接或间接导致的民事或刑事法律责任
·本站评论管理人员有权保留或删除其管辖评论中的任意内容
·您在本站发表的作品,本站有权在网站内转载或引用
·参与本评论即表明您已经阅读并接受上述条款
推荐文档 | 打印文档 | 评论文档 | 报告错误  
专业书推荐 更多内容
网站可用性测试及优化指南
《写给大家看的色彩书1》
《跟我去香港》
众妙之门—网站UI 设计之道
《Flex 4.0 RIA开发宝典》
《赢在设计》
犀利开发—jQuery内核详解与实践
作品集 更多内容

杂⑦杂⑧ Gold NORMANA V2