分类：
2010-10-13 13:56:01
上周接触到rsync这个工具，因为之前不知道（我是土人 -_-|||...），所以自己查了下。下面做个简单地总结。
【rsync算法】
rsync是一个开源工具，提供快速地文件增量传输，其核心是“rsync算法”。该算法解释如下：
现有两台机器a与b。a上有文件A，b上有文件B，且文件A与B非常相似(可能来自同一份源文件，只各自做了少量修改)。则rsync算法由如下若干步骤组成：
b通过以上步骤，最终同步B文件。
【弱滚动校验和】
“rsync算法”的第4步中，a要对以1为步进值的所有s字节块频繁地计算弱“滚动”校验和。这就要求该校验和的算法应该尽可能的计算量小。下面是具体的算法：
s(k,l)是字节块Xk...Xl的滚动校验和，该算法的优势如下：
可见当已知字节块X1...Xn的滚动校验和以及X1、Xn+1的值时，使用该算法可以很方便地计算出X2...Xn+1的滚动校验和。
以上只是一个简要的介绍，具体内容因篇幅有限，就不写出来了。这个算弱“滚动”校验和的算法挺巧妙的，所以就多写了些。其实这个算法是脱胎于Adler-32校验和算法的，有兴趣的童鞋可以再去看看。
【校验和查找】
“rsync算法” 的第4步中，关于机器a如何查找相同校验和的字节块的过程如下。
当机器a接收到机器b计算出的文件B的校验和列表后，会搜索文件A中任一偏移量的s字节块，以找出相同内容的字节块。该搜索过程的基本策略是a顺序计算每个s字节块（偏移量的步进值为1）的32位滚动校验和，然后用该校验和在b发送的校验和列表中寻找匹配值。Rsync的算法通过一个简单的3层查询机制来实现该过程。
第一层查询中，机器a首先为b传过来的校验和列表中每个32位弱滚动校验和，计算一个对应的16位哈希值，并据此对b传过来的校验和列表进行排序。同时机器a创建一个容量为2的16次方的哈希表。在该哈希表中，每条记录均指向排序后的校验和列表中第一个与该16位哈希值相等的元素。如果排序后的校验和列表中没有与该16位哈希值相等的元素，则该条记录指向null。
机器a对文件A中每个偏移量的s字节块，都计算出32位滚动校验和与16位哈希值。如果容量为2的16次方的哈希表中，对应该16位哈希值的记录指向不是null，则进入第二层查询。
在第二层查询中，机器a会从哈希表中对应记录指向的位置，开始扫描排序后的校验和列表。该过程一直扫描到某个32位滚动校验和的16位哈希值，与哈希表中对应哈希值不同时结束。如果发现有相同滚动校验和，则进入第三层查询。
在第三层查询中，要比较该s字节块的MD4强校验和与对应校验和列表元素的MD4强校验和是否相等。如果相等，则我们假设找到了相同的字节块。其实存在这种可能性：弱滚动校验和与强MD4校验和均相同的两个字节块，其内容有可能不同。不过这种可能性非常小，所以rsync算法忽略不计这种情况。
当发现相同字节块后，机器a会发送当前偏移量到上次相同字节块偏移量+s之间的这段数据给机器b，然后是相同字节块在文件B中的索引。这些数据会在匹配成功后立即发送，这样机器a的校验和查询过程与机器b的文件同步过程可以并行进行。
在第二层查询中，如果最终没有发现相同滚动校验和，则机器a会步进到下一个s字节块进行滚动校验和计算（这一次的步进值是1），并重新执行上面的第一层查询。如果机器a最终找到相同校验和的字节块，则从该字节块后面重新开始新的搜索过程（这一次的步进值是s）。这个小技巧在A与B两个文件十分相似时，可以减少大量不必要的计算（查找字符串的子串时，这个技巧也经常使用）。
下面是3张图示，大家将就着看吧 -_-|||…
说明一下，我没有看rsynce算法的源码。所以这三张图只是个示意，可能存在出入。
【总结一下】
Rsync算法是Andrew Tridgell与Paul Mackerras在1998年的论文中介绍的。该算法主要针对当时网络情况的不稳定、窄带宽、高延时做出的。rsync算法很适合对一些小尺寸、相似度高的文件进行同步，但不适合大尺寸、路径结构深、文件数量庞大的文件群进行同步。原因从rsync算法可以看出，它需要对所有文件的全部弱“滚动”校验和与强MD4校验和进行计算、传递、比较，不管文件是否修改过。
那如果我们能够标示出已经改变的文件，并只对这些文件做rsync同步，效率应该会大大提高。关于如何标示出修改过的文件，网上其实已经有许多解决办法，我就不当祥林嫂了。引用比较多的是：把某个需要同步的文件夹做成一个hash tree，使用修改时间作为hash值。因为linux下文件的修改，只会反映到该文件所在目录的修改时间，而不会反映到更上层的目录中，所以需要使用inotify接口自己写一个更新以上目录修改时间的同步程序(这个inotify我从没有用过，只是人云亦云罢了)。
