月度归档:2012年11月

rsync 核心算法的Java实现

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。

继续阅读