Hacker News 中文摘要

RSS订阅

rsync算法（1996年）[pdf] -- The rsync algorithm (1996) [pdf]

原文链接 | HN讨论 | 2026-01-03 13:01:51

文章摘要

该文章是1996年澳大利亚国立大学的技术报告TR-CS-96-05，介绍了Andrew Tridgell和Paul Mackerras提出的rsync算法，用于高效文件同步。报告属于计算机科学系列，包含8页内容，由该校工程与信息技术学院发布。

文章总结

技术报告：rsync算法（TR-CS-96-05）

报告基本信息

  • 标题：rsync算法
  • 作者：Andrew Tridgell与Paul Mackerras
  • 机构：澳大利亚国立大学计算机科学系
  • 发布日期：1996年6月
  • 页数：8页
  • 技术报告系列：TR-CS-96-05

摘要

本报告提出了一种高效的文件同步算法，用于在低带宽、高延迟的双向通信链路上，将目标机器上的文件更新至与源文件一致。该算法的核心思想是： 1. 识别源文件与目标文件中相同的部分 2. 仅传输无法匹配的部分 3. 通过引用目标文件已有块来重构源文件

算法在文件相似时表现最佳，但在文件差异较大时仍能保持合理效率。

算法原理

问题背景

传统文件同步方法在低带宽环境下存在局限： - 直接传输大文件效率低下 - 压缩传输通常只能提升2-4倍效率 - 差异传输需要双方文件都可用

rsync解决方案

  1. 分块处理：将目标文件B分割为固定大小块（建议500-1000字节）
  2. 双重校验：为每个块计算：
    • 32位弱滚动校验和（快速计算）
    • 128位MD4强校验和（精确匹配）
  3. 校验和传输：将校验和发送给源端
  4. 匹配搜索：源端在文件A中搜索所有可能偏移位置的匹配块
  5. 差异传输：仅传输未匹配部分和块引用

关键技术

滚动校验和

采用改进的Adler-32算法： a(k,l) = (ΣXi) mod M b(k,l) = (Σ(l-i+1)Xi) mod M s(k,l) = a(k,l) + 2^16*b(k,l) 特性： - 支持增量计算 - 计算复杂度O(1) - 使用M=2^16保证效率

三级搜索机制

  1. 16位哈希过滤：快速排除不匹配项
  2. 32位校验和匹配：中等精度筛选
  3. 128位MD4验证：最终确认

性能测试

Linux内核测试

  • 对比版本：1.99.10与2.0.0
  • 文件大小：约24MB
  • 变化情况：291/2441文件修改

| 块大小 | 匹配数 | 数据传输量 | 总写入量 | 总读取量 | |--------|--------|------------|----------|----------| | 300B | 64,247 | 5.31MB | 5.63MB | 1.63MB | | 500B | 46,989 | 1.09MB | 1.28MB | 979KB | | 700B | 33,255 | 1.31MB | 1.44MB | 700KB |

Samba代码测试

  • 总大小：1.7MB
  • 差异量：120KB

| 块大小 | 匹配数 | 数据传输量 | |--------|--------|------------| | 300B | 3,727 | 130KB | | 500B | 2,158 | 172KB |

实现与可用性

rsync已实现为类rcp命令行工具，可通过以下地址获取： ftp://samba.anu.edu.au/pub/rsync

（注：原文中的数学公式、部分技术细节及测试数据表格已作简化处理，保留核心内容）

评论总结

这篇评论主要围绕rsync工具展开讨论，包含以下观点：

  1. 对rsync实用价值的肯定

  • 认为rsync体现了计算机科学解决实际问题的本质（评论1） "Well-written, succinct...a way to make computers more efficient and smarter, to solve real problems" "写得很好，简洁...展示了计算机科学如何让计算机更高效智能地解决实际问题"

  • 用户分享实际案例展示rsync的高效性（评论2） "Blew my mind when...I had only sent 600MiBs" "当我发现...只传输了600MB时，简直震惊"

  1. 使用技巧分享

  • 指出rsync默认使用文件大小和修改时间判断文件差异（评论2） "rsync uses file size and modified time first to see if the files are identical" "rsync首先使用文件大小和修改时间判断文件是否相同"

  • 建议使用--checksum参数确保准确性（评论2） "rsync was not noticing...until I added the --checksum flag" "直到添加--checksum参数，rsync才能识别变更"

  1. 对作者的赞赏
  • 提到rsync作者Andrew Tridgell也是Samba项目的奠基人（评论4） "the author of rsync...reverse-engineered Microsoft SMB" "rsync作者...反向工程了微软SMB协议"
  1. 日常应用场景
  • 用户分享在NAS设置中使用rsync的经历（评论3） "I just used this today while setting up my NAS" "今天设置NAS时刚用过这个"