rsync 算法

场景：假设有两台计算机 CA和 CB ， CA 上有文件 FA ， CB 上有文件 FB ， FA 和 FB 是“相似的”。 CA 和 CB 通过低速通信链接连接，现在要把 FA 同步到 FB 上去，如何才能高效同步。

rsync 算法包含下面的步骤：

1. CB把 FB 分割成固定大小 S 字节的块，最后一块可能少于 S 字节；
2. 对于每个块，CB 计算两个校验和：一个弱的“滚动” 32 位校验和和一个强的 128 位 MD4 校验和。
3. CB把这些校验和发给 CA 。
4. CA搜索 FA 来查找 S 大小的块，这些块与 CB 的块有相同的弱和强校验和。这可以通过一次遍历来完成，通过利用滚动校验和的特殊属性。
5. CA给 CB 发送一序列指令来构建一个 FA 的拷贝。每个指令要么指向 FB 的一个块，要么是文字数据。文字数据只用于发送 FA 的那些不匹配 FB 块的区域。

最终结果是 CB有了 FA 的拷贝，但只发送了那些在 FB 里找不到的数据。
这个算法只要求一个来回，减少了网络延迟。

这个算法的最重要的细节是滚动校验和 和 associated multi-alternate search mechanism which allows the all-offsets checksum search to proceed very quickly.

这里说到的多选择搜索机制，在实现时用HashMap + List。

继续阅读 →