ITPub博客

首页 > Linux操作系统 > Linux操作系统 > Sync Algorithm: RSync vs. RDC [转]

Sync Algorithm: RSync vs. RDC [转]

原创 Linux操作系统 作者:friendshao 时间:2009-05-07 11:04:03 0 删除 编辑

Sync Algorithm: RSync vs. RDC

数据同步(Sync)是很多网络应用需要的解决的问题,比如文件镜像。这里就以文件同步为例,问题模型:网络中两个主机Host-A和Host-B,都有同一文件File-Old的拷贝,现在这个文件在Host-A上做了一些改变成为了File-New,需要通过同步让Host-B也获得F-New。
 
让我们想想怎么处理这个问题,最简单的方法,把所有数据都传输一遍,这样是简单,但是显得浪费,因为File-New相对于File-Old只是有些小改变,全部copy代价太大。如果我们能够只传输发生改变的部分,也就是增、删、改的文件部分,那就太好了。这样,我们要解决的问题变成,如何得到File-Old和File-New的差别。
 
如果Host-A上面保留有一个File-Old,那用普通的diff算法求一下和File-New的差别就行了,但是实际应用中,Host-A往往不会保留File-Old;或者文件格式本身有很强的版本控制功能,Host-B告诉Host-A它手上文件的版本,Host-A就能够计算出差别;更多情况下,文件就是一串bytes,没有版本控制信息,没有历史拷贝,Rsync和RDC就是解决这种情况的同步的。
 
RSync算法是澳大利亚人Andrew  Tridgell发明的,我看懂这个算法之后的第一感觉是:“嘿,这算法我也应该能想出来!”的确,按照Andrew  Tridgell  自己的话,这个算法只需要半个小时就能够理解,但是花费了他几年时间研究出来。
 
这里大概介绍一下Rsync算法大概原理
1) Host-B把File-Old划分成不重合的大小为K字节的若干块,不足K字节的结尾部分加上Padding,然后对每一块求弱Hash和强Hash。弱Hash就是说很有可能两个不同的块Hash值相同,但是计算起来快,而且这里要求这个若Hash能够Rolling,也就是说已知字节1到字节K这个块的Hash值,能够很快的计算出字节2到字节K+1这个块的Hash值,往前Roll一个字节,计算很快;强Hash就是可以认为不同块肯定有不同Hash值,Rsync用的是MD4。我们让WH表示弱Hash,SH表示强Hash。
2) Host-B把每个块的WH和SH值发送给Host-A。
3) 该Host-A上场了,他的运算量比较大。Host-A对File-New每一个长度为K的块(也就是以每个字节开头的长度为K的块)计算WH,计算出来之后和Host-B发送过来的WH匹配,如果发现有相同的,再计算这个块的SH进行匹配,如果还是相符,说明这个块在File-Old里面也存在。假如File-New长度为N,那么Host-A要处理大约(N-K)个块,这里可见用两个Hash算法的作用,WH用来做初步比较,而且因为它可以Rolling,所以能够很快筛选掉大多数不匹配,对于漏网之鱼,也躲不过SH的筛选。
4) 通过上面的计算,Host-A可知道,File-New中哪些块和File-Old中的块相同,这样自然也可以计算出哪些不同,Host-A把这些不同encode一下送给Host-B。
5) Host-B收到Host-A送来的数据,decode,就得到了File-New相对于File-Old的改变,于是获得了File-New。
 
整个过程只需要一个round-trip,而且可以精确的得到一个字节级别的差别,Host-A的运算量相对要大一些。
 
Rsync的实现已经是*inx上面的一个重要工具,所以,当Microsoft在Windows 2003 Server上推出DFSR(Distributed File System Replication)时,Open Source Community颇有嘘声。其实DFSR采用的是RDC(Remote Differential Compression)算法,和RSync相差很大,并没有抄袭RSync。
 
我感觉,RSync有学院气息(这个算法本来就是Andrew  Tridgell的博士论文),结果很完美,File-New和File-Old每一个字节的差别都计算出来了,但是Host-A和Host-B的计算量不对等,大部分的计算都集中在Host-A上。RDC和RSync相比方向上有点不同,RDC并不追求计算出字节级别的diff,而是用较少的运算求出数据块级别的diff。
 
RDC算法要求Host-A和Host-B通过一致的规则对File-New和File-Old分别进行分块,然后对每个块计算SH,Host-B把每个块的SH值发给Host-A,Host-A对两组SH进行diff,就可以知道有哪些块不同,哪些块被删掉了,哪些块被添加了。RDC的关键在于分块规则,也使用WH,要让同一规则应用于File-Old和File-New的时候,分出来的块能够尽量体现出区别。
 
比如File-Old包含“I Love Playing Basketball”,
File-New是“I Like Playing Football"。
如果是RSync算法,Host-A能够计算出准确的差别,“I Like Playing Football" 黄色部分修改了,绿色部分是增加的,精确到每个字符,Host-A主要告诉Host-B:“把第4-6号字符换成'ike',把16-21号字符去掉,插入'Foot'”。
 
如果是RDC算法,可能得到下面的结果:
File-Old分块的结果,分成3块。
I Love Playing Basketball
File-New分块的结果,分成3块。
I Like Playing Football"
Host-A经过比对,发现只有File-Old的第2块和File-New的第2块匹配,于是就告诉Host-B:“把你的第一块换成‘I Like’,把你的第3块换成‘Football’”。
 
如上面看到,RDC相对而言比较浪费,相比RSync,要多传输一些数据,但是Host-A和Host-B的计算量比较平均。为了让RDC发挥好的性能,一定要制定一个好的分块机制,让包含Diff的块尽量少包含没有Diff的数据,怎么做到这一点呢,还要靠WH,通过rolling checksum来从数据中快速挖掘出数据的性质。
 
注意一点就是RSync的分块策略是每块都是固定长度的,而RDC则每块长度可能不一样。
 
虽然RDC相对浪费一点,但是传送的大部分还是Delta数据,而且计算量相对平均而且较少,目前Window 2003 Server R2上的DFS使用的就是RDC算法,还有一个应用就是Live Messenger的Shared Folder功能,用一用,就知道效率不差了:)
 
 
 
【转自http://morganchengmo.spaces.live.com/blog/cns!9950CE918939932E!521.entry

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7201003/viewspace-594394/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 该死的DELL M1210
请登录后发表评论 登录
全部评论

注册时间:2008-04-22

  • 博文量
    50
  • 访问量
    80407