RSync 算法是澳大利亚人 Andrew Tridgell （samba的作者）发明的，按照 Andrew Tridgell 自己的话，这个算法只需要半个小时就能够理解，但是花费了他几年时间才研究出来。
Rsync 算法大概原理：（目标：把 HostA 上的FileNew 同步到 HostB 上 FileOld）
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?wa=wsignin1.0&sa=739070373
Post a Comment