简介

rsync 是 Unix 下的一款应用软件，它能同步更新两处计算机的文件与目录，并适当利用差分编码以减少数据传输量。rsync 中的一项同类软件不常见的重要特性是每个目标的镜像只需发送一次。rsync 可以拷贝／显示目录内容，以及拷贝文件，并可选压缩以及递归拷贝。

在常驻模式（daemon mode）下，rsync 默认监听 TCP 端口 873，以原生 rsync 传输协议或者通过远程 shell 如 RSH 或者 SSH 提供文件。SSH 模式下，rsync 客户端运行程序必须同时在本地和远程机器上安装。

rsync 使用所谓的“rsync 算法”来使本地和远程两个主机之间的文件达到同步，这个算法只传送两个文件的不同部分，而不是每次都整份传送，因此速度相当快。

需要解决的问题

如何判断文件是否变更？ 如何找到变更的部分？ 对于二进制文件怎样处理？ 对于大文件怎样处理？

rsync 算法

按固定大小将 A 分为多块，每块都计算出一个 32 位的滚动哈希值和一个 128 位的 MD4（有些也用 MD5），发给 B 一端。 B 一端从位置 0 开始按的同样块大小的滚动哈希值，查找看是否命中 A 给的某个滚动哈希值，若匹配，则表明 B 文件中的这块内容与对应的 A 中的那块内容很可能是一致的，但由于 32 位的哈希值强度不够，因此再计算 MD4，若还是匹配，则确认是一致内容，这时 B 发给 A 端匹配的段号。对于那些不能匹配的内容，则发给 A 端原始内容。 A 端得到 B 端给的匹配信息，构造一个与 B 一致的复本，若是匹配的块，则拷贝原 A 文件中对应的块，若是不匹配内容则追加之。

分块 Checksum 算法

首先，我们会把 fileDst 的文件平均切分成若干个小块，比如每块 512 个字节（最后一块会小于这个数），然后对每块计算两个 checksum， 一个叫 rolling checksum，是弱 checksum，32 位的 checksum，其使用的是 Mark Adler 发明的 adler-32 算法， 另一个是强 checksum，128 位的，以前用 md4，现在用 md5 hash 算法。 为什么要这样？因为若干年前的硬件上跑 md4 的算法太慢了，所以，我们需要一个快算法来鉴别文件块的不同，但是弱的 adler32 算法碰撞概率太高了，所以我们还要引入强的 checksum 算法以保证两文件块是相同的。也就是说，弱的 checksum 是用来区别不同，而强的是用来确认相同。（checksum 的具体公式可以参看这篇文章）

传输算法

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

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

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

如果我 fileSrc 这边在文件中间加了一个字符，这样后面的文件块都会位移一个字符，这样就完全和 fileDst 这边的不一样了，但理论上来说，我应该只需要传一个字符就好了。这个怎么解决？ 如果这个 checksum 列表特别长，而我的两边的相同的文件块可能并不是一样的顺序，那就需要查找，线性的查找起来应该特别慢吧。这个怎么解决？ 很好，让我们来看一下同步源端的算法。

基于 rsync 的应用

Rclone…… Back In Time …

推荐阅读

rsync 原理 | ESON (opens new window)
rsync 的核心算法 | | 酷 壳 - CoolShell (opens new window)
rsync 用法教程 - 阮一峰的网络日志 (opens new window)