rsync 的核心算法

        rsync 是 unix/linux 下同步文件的一个高效算法，它能同步更新两处计算机的文件与目录，并适当利用查找文件中的不同块以减少数据传输。rsync 中一项与其他大部分类似程序或协定中所未见的重要特性是镜像是只对有变更的部分进行传送。rsync 可拷贝／显示目录属性，以及拷贝文件，并可选择性的压缩以及递归拷贝。rsync 利用由 Andrew Tridgell 发明的算法。这里不介绍其使用方法，只介绍其核心算法。我们可以看到，Unix 下的东西，一个命令，一个工具都有很多很精妙的东西，怎么学也学不完，这就是 Unix 的文化啊。

        本来不想写这篇文章的，因为原先发现有很多中文 blog 都说了这个算法，但是看了一下，发现这些中文 blog 要么翻译国外文章翻译地非常烂，要么就是介绍这个算法介绍得很乱让人看不懂，还有错误，误人不浅，所以让我觉得有必要写篇 rsync 算法介绍的文章。（当然，我成文比较仓促，可能会有一些错误，请指正）

        问题

        首先， 我们先来想一下 rsync 要解决的问题，如果我们要同步的文件只想传不同的部分，我们就需要对两边的文件做 diff，但是这两个问题在两台不同的机器上，无法做 diff。如果我们做 diff，就要把一个文件传到另一台机器上做 diff，但这样一来，我们就传了整个文件，这与我们只想传输不同部的初衷相背。

        于是我们就要想一个办法，让这两边的文件见不到面，但还能知道它们间有什么不同。这就出现了 rsync 的算法。

        算法

        rsync 的算法如下：（假设我们同步源文件名为 fileSrc，同步目的文件叫 fileDst）

        1）分块 Checksum 算法。首先，我们会把 fileDst 的文件平均切分成若干个小块，比如每块 512 个字节（最后一块会小于这个数），然后对每块计算两个 checksum，

• 一个叫 rolling checksum，是弱 checksum，32位的 checksum，其使用的是 Mark Adler 发明的 adler-32算法，
• 另一个是强 checksum，128位的，以前用 md4，现在用 md5 hash 算法。

        为什么要这样？因为若干年前的硬件上跑 md4 的算法太慢了，所以，我们需要一个快算法来鉴别文件块的不同，但是弱的 adler32 算法碰撞概率太高了，所以我们还要引入强的 checksum 算法以保证两文件块是相同的。也就是说，弱的 checksum 是用来区别不同，而强的是用来确认相同。（checksum 的具体公式可能看这篇文章）

        2）传输算法。同步目标端会把 fileDst 的一个 checksum 列表传给同步源，这个列表里包括了三个东西，rolling checksum (32bits)，md5 checksume (128bits)，文件块编号。

        我估计你猜到了同步源机器拿到了这个列表后，会对 fileSrc 做同样的 checksum，然后和 fileDst 的 checksum 做对比，这样就知道哪些文件块改变了。

        但是，聪明的你一定会有以下两个疑问：

• 如果我 fileSrc 这边在文件中间加了一个字符，这样后面的文件块都会位移一个字符，这样就完全和 fileDst 这边的不一样了，但理论上来说，我应该只需要传一个字符就好了。这个怎么解决？

• 如果这个 checksum 列表特别长，而我的两边的相同的文件块可能并不是一样的顺序，那就需要查找，线性的查找起来应该特别慢吧。这个怎么解决？

        很好，让我们来看一下同步源端的算法。

        3）checksum 查找算法。同步源端拿到 fileDst 的 checksum 数组后，会把这个数据存到一个 hash table 中，用 rolling checksum 做 hash，以便获得O(1)时间复杂度的查找性能。这个 hash table 是 16bits 的，所以，hash table 的尺寸是 2 的 16 次方，对 rolling checksum 的 hash 会被散列到 0 – 2^16 – 1 中的某个值。（对于 hash table，如果你不清楚，请回去看你大学时的数据结构那本教科书）

        顺便说一下，我在网上看到很多文章说，“要对 rolling checksum 做排序”（比如这篇和这篇），这两篇文章都引用并翻译了原版的这篇文章，但是他们都理解错了，不是排序，就只是把 fileDst 的 checksum 数据，按 rolling checksum 做存到2^16的 hash table 中，当然会发生碰撞，把碰撞的做成一个链接就好了。这就是原文中所说的第二步。

        4）比对算法。这是最关键的算法，细节如下：

        4. 1）取 fileSrc 的第一个文件块（我们假设的是 512 个长度），也就是从 fileSrc 的第 1 个字节到第 512 个字节，取出来后做 rolling checksum 计算。计算好的值到 hash 表中查。

        4. 2）如果查到了，说明发现在 fileDst 中有潜在相同的文件块，于是就再比较 md5 的 checksum，因为 rolling checksume 太弱了，可能发生碰撞。于是还要算 md5 的 128bits 的 checksum，这样一来，我们就有 2^-(32+128) = 2^-160的概率发生碰撞，这太小了可以忽略。如果 rolling checksum 和 md5 checksum 都相同，这说明在 fileDst 中有相同的块，我们需要记下这一块在 fileDst 下的文件编号。

        4. 3）如果 fileSrc 的 rolling checksum 没有在 hash table 中找到，那就不用算 md5 checksum 了。表示这一块中有不同的信息。总之，只要 rolling checksum 或 md5 checksum 其中有一个在 fileDst 的 checksum hash 表中找不到匹配项，那么就会触发算法对 fileSrc 的 rolling 动作。于是，算法会住后 step 1 个字节，取 fileSrc 中字节2-513的文件块要做 checksum，go to (4.1) - 现在你明白什么叫 rolling checksum 了吧。

        4. 4）这样，我们就可以找出 fileSrc 相邻两次匹配中的那些文本字符，这些就是我们要往同步目标端传的文件内容了。

        图示

        怎么，你没看懂？ 好吧，我送佛送上西，画个示意图给你看看（对图中的东西我就不再解释了）。

        这样，最终，在同步源这端，我们的 rsync 算法可能会得到下面这个样子的一个数据数组，图中，红色块表示在目标端已匹配上，不用传输（注：我专门在其中显示了两块 chunk #5，相信你会懂的），而白色的地方就是需要传输的内容（注意：这些白色的块是不定长的），这样，同步源这端把这个数组（白色的就是实际内容，红色的就放 一个标号）压缩传到目的端，在目的端的 rsync 会根据这个表重新生成文件，这样，同步完成。

        最后想说一下，对于某些压缩文件使用 rsync 传输可能会传得更多，因为被压缩后的文件可能会非常的不同。对此，对于 gzip 和 bzip2 这样的命令，记得开启 “rsyncalbe” 模式。