暴力撬死锁！rsync 算法是如何被“逼”出来的？

我们设想一个问题：你在北京的服务器改了一个 10GB 的文件，为什么敲下 rsync 之后，几秒钟就同步到上海的服务器上了？

10GB。几秒钟。

按常理，10GB 的数据，就算你家是千兆宽带，满速下载也得跑一分多钟。而服务器之间的链路，往往比你家宽带慢得多、卡得多。所以这里一定发生了什么“不正常”的事。

很多人会脱口而出：“因为 rsync 只传差异嘛，增量同步。”

对。但问题是——它怎么知道差异在哪？

你把“只传差异”这四个字说出口只需要半秒，但如果你停下来想一秒钟，一个让人细思极恐的问题就会浮上来：

要找出两个文件的差异，你得先把两个文件放在一起比对吧？可一个文件在北京，一个文件在上海，你怎么比？

把上海的文件传到北京来比？那你已经传了一遍了，还“只传差异”干什么——你都已经把整个文件搬过来了啊。

这是一个经典的死锁：要省带宽，你得知道差异；要知道差异，你得先花带宽。

而 rsync 的天才之处，就是用一个你绝对想不到的方式，把这个死锁暴力撬开了。

一、先把问题翻译成一个你能摸到的场景

先扔掉服务器，我们来想象一个更肉身的设定。

你在北京的一家档案馆工作，你的同事小王在上海分部。你们各自保管着一本《中国工业年鉴 2026》，每本 2400 页，重得像一块砖头。今天馆长告诉你：北京这本出了修订版，加了三章新内容，改了一百多处数据，删了五十页过时的政策文件。现在，你必须在今晚让小王手上那本变得和你这本一模一样。

但你们之间只有一样东西可以用：一台老式电报机。 每发一个字，收费一毛钱。

你想了想，2400 页的书，按一页 800 字算，全文发电报过去——将近两百万字。二十万块钱。馆长会杀了你。

好，现在你坐在这台电报机前，手心出汗。小王在两千公里外等着。你手上是全世界唯一一本新版年鉴，他手上是全世界唯一一本旧版年鉴。你们不能见面，不能拍照，不能传真。你只能用电报机发文字给他，而且每一个字都要算钱。

你怎么办？

二、人类第一反应：让上海那边自己算

你可能会说：简单啊，让小王把旧版的内容告诉我，我来告诉他改哪。

来，算个账。

小王把他的旧版年鉴一字一字用电报发给你，又是两百万字。二十万块钱。然后你比对完，把差异发回去。假设差异只有全书的 5%，十万字，一万块钱。总计二十一万。

比直接发新版还贵。

你发现没有，“让对端把文件发过来比对”这件事，本质上就等于已经传输了整个文件。一旦传完了，你还比对什么？你直接把新版发过去不就完了？

这就是问题的核心。在 rsync 诞生之前，所有人面对这个场景，能做的事只有一件：认命，传整个文件。 压缩一下，省个两三倍，仅此而已。

但 1996 年，澳大利亚国立大学的两个博士生：Andrew Tridgell 和 Paul Mackerras，坐在实验室里盯着这个问题，突然问了一个让所有人愣了一下然后猛拍大腿的问题：

“谁说比对差异，需要看到整个文件？”

三、第一个脑洞：只问“你有没有第 X 页”，不问“你第 X 页写了什么”

让我们回到你和电报机的那个夜晚。

你突然想到一个取巧的办法。

你不让小王把整本旧版发给你。你只让他做一件事：把旧版年鉴每一页的第一个字和最后一个字，用电报发给你。

2400 页，每页两个字，一共 4800 个字。四百八十块钱。 这个代价，馆长是可以接受的。

你收到这份”索引”之后，翻开你的新版年鉴，从第一页开始，逐页检查：新版第一页的第一个字和最后一个字，和旧版第一页的一样吗？

• 一样？那这一页大概率没改。你只需要发电报告诉小王：“第一页，保留。”
• 不一样？那这一页肯定改了。你把新版这一页的全文发过去。

最后你发现，新版 2400 页里，有 2280 页的首尾字和旧版对得上，只有 120 页变了。你需要全文发送的，只有这 120 页。

电报费：索引 4800 字 + 变更页 96000 字 ≈ 一万块钱。 从二十万降到一万，直接打骨折。

你很得意。馆长很满意。

但就在这时，一个尖锐的问题戳破了你的好心情——

“万一改的那一页，刚好第一个字和最后一个字没变呢？”

比如旧版第 347 页写的是”2023 年全国粗钢产量 10.13 亿 吨”，新版改成了”2023 年全国粗钢产量 10.19 亿 吨”。改了中间个数字，但首尾字一模一样——”2”和”吨”。

你的首尾字索引法会判定这一页“没变”。小王就会把旧版那一页原封不动地留下来。

然后上海档案馆里的年鉴就错了一个数据。

你倒吸一口气。这不是开玩笑的——年鉴是给决策者看的，一个数字错了，可能就是一座钢厂的产能误判。

你得想一个绝对不会漏掉任何改动的办法。

四、第二个脑洞：把每一页变成一个“数字指纹”

你坐在电报机前，盯着天花板看了很久。然后你想起了大学里学过的一个概念——哈希。

你不需要发每一页的首尾字。你可以让小王把旧版每一页的全部内容做一个“数字指纹”发给你。

什么叫数字指纹？就是一串短小的数字，但这串数字和那一页的全部内容有极强的绑定关系——只要那一页改了一个标点符号，这串数字就彻底变脸。

比如 MD5 值，128 位，只有 16 个字节。一页 800 字，原本需要 800 字来”描述”它，现在只需要 16 个字节。压缩了 50 倍。

于是你的新方案变成了这样：

小王把旧版年鉴每一页的 MD5 值发给你——2400 页 × 16 字节 = 38400 字节。还是几百块钱的量级。

你拿到这份“指纹清单”后，计算新版年鉴每一页的 MD5，然后逐页比对：

• 指纹对上了 → 这一页没变。你发电报：“第 X 页，用你旧版的。”
• 指纹对不上 → 这一页改了。你把新版这一页全文发过去。

完美。

……吗？

你还没有来得及庆祝，又一个问题从阴影里浮了上来——这次的打击比上一次更狠：

如果新版不是“改了一页”，而是“在中间插入了一章”呢？

想象一下。新版年鉴在第 200 页和第 201 页之间，插入了一整章——“新能源汽车产业十年回顾”，一共 60 页。

从第 201 页开始，旧版和新版的页码完全错位了。旧版第 201 页是“石油化工”，新版第 201 页变成了“新能源汽车”。旧版第 201 页的内容，现在跑到了新版第 261 页。

但你手上只有一列按页码对齐的 MD5 清单。你会拿旧版第 201 页的指纹去对比新版第 201 页的指纹——啪，不匹配。旧版第 202 页对新版第 202 页——啪，又不匹配。从第 201 页到第 2400 页，全部不匹配！

你的算法会判定：后面 2200 页全改了。全文发送。电报费又回到解放前。

你瘫坐在椅子上。明明有 2200 页是原封不动搬到后面的，但你的”逐页比对”完全看不到这件事。

因为你把每一页当成了一座孤岛。你看不到页面之间的“位移关系”。

五、天才一击：从”逐页比对”到”逐字滑窗”

现在是凌晨三点。电报机发出微弱的电流声。小王在上海已经趴在桌上睡着了。你还醒着。

你在想一个问题：为什么人类翻两本书，一眼就能看出“从第 201 页开始内容往后挪了”？

因为人类不是在逐页比对。人类是在任意位置寻找熟悉的段落。你翻开新版第 201 页，看到“新能源汽车……”，你觉得陌生。你继续往后翻，翻到第 261 页，看到”石油化工……”，你立刻认出来：”这不是旧版第 201 页吗！”

你需要的不是“逐页指纹”。你需要的是：把新版年鉴切成无数个重叠的小片段，然后去旧版年鉴里问——“这个片段，你见过吗？”

但问题来了。如果每一页切一刀，那碰到“插入一章”的情况你还是死——因为你的切分位置和内容边界错位了。

你必须切得足够密，才能让任何一段连续内容都至少能在你的切割网格里找到一个能对上的片段。

于是你做出了一个疯狂的决定：不按页切。按“每 500 个字”切成一个块，而且每一个字的位置都切一刀。

2400 页 × 800 字 = 192 万个字。每一个字的位置都取后面 500 个字作为一个“块”——这就是接近两百万个块。

两百万个块，每个块要算一个强指纹（MD5），然后拿每一个块去旧版的指纹清单里查找是否匹配。

这计算量大得不像话。

但这不是最可怕的。最可怕的是，每一个块的 MD5 都要从头算一遍，两百万次 MD5 计算。在 1996 年的 CPU 上，这可能需要跑几个小时。馆长不会给你这么长时间。

你觉得这个思路是对的，但实现不了。你卡住了。

六、那层窗户纸：会“滑动”的校验和

现在，让我们从年鉴的故事里跳出来，看看 Tridgell 和 Mackerras 到底做了什么。

他们的处境和你一模一样。他们也知道，要解决”插入/删除导致全部错位”的问题，必须在源文件上以每一个字节为起点切块、计算指纹、然后去目标文件的指纹清单里查。这在逻辑上是完美的——任何一段连续内容，只要长度够一个块，就一定会被某个起点位置捕捉到。

但计算量是灾难。一个 10MB 的文件，按 500 字节的块大小，就是大约一千万个块。一千万次强指纹计算——MD4（他们用的 MD4，比 MD5 更早也更轻量），在当年的机器上跑起来，黄花菜都凉了。

他们需要一个可以在“滑窗”过程中几乎零成本更新的校验和。

这就是整个 rsync 算法中最天才的那一笔。

他们设计了一个校验和，它不是对固定窗口“重新计算”，而是可以在窗口滑动一个字节时，用上一次的计算结果，加减两个字节，就立刻得到新的值。

我来试着把这件事说清楚。

先忘掉 MD5 那类强校验。我们先用一个极度简化的版本理解这个思路。

假设一个“窗口”里只有三个数字：[3, 7, 2]。最简单的校验和就是求和：3 + 7 + 2 = 12。

现在窗口向右滑动一格，进来一个新数字 5，出去了 3：窗口变成 [7, 2, 5]。

笨办法：重新算，7 + 2 + 5 = 14。

聪明的办法：用上一次的和 12，减去出去的 3，加上进来的 5——12 - 3 + 5 = 14。

无论窗口有多大，更新只需要两次加减法。

这就是“滚动校验和”的核心思想。当然，rsync 实际用的不是简单求和（太容易碰撞了），而是一个受 adler-32 启发的校验和，它由两部分组成：

• a 部分：所有字节的累加和（模一个数）
• b 部分：每个字节乘以它在窗口中的位置权重再累加（模同一个数）

这个设计的精妙之处在于，a 和 b 都能在滑窗时用常数时间更新。

具体来说，窗口从位置 k..l 滑到 k+1..l+1 时：

• a_new = a_old - X_k + X_{l+1}（减掉出去的，加上进来的）
• b_new = b_old - (窗口长度) × X_k + a_new（这个稍复杂一点，但也是 O(1)）

不是重新计算。是更新。 就像你的银行账户余额，你不需要每次都把过去三年的流水重新加一遍，你只需要在上一笔余额的基础上，减去支出，加上收入。

一千万次”重新计算”变成了一千万次“更新”。前者每步需要遍历 500 个字节，后者每步只需要两次减法一次加法。 这是几千倍的差距。

一夜之间，逐字节滑窗从”理论上很美但算不动”变成了”算得动而且算得飞快”。

七、双层指纹：为什么需要“弱校验 + 强校验”

读到这里，你可能已经嗅到一个小问题：

这个滚动校验和只有 32 位，也就是大约 40 亿种可能的值。听起来很多，但你想一下，一个 10MB 的文件切出两千万个块，每个块都有一个 32 位的校验和。根据鸽巢原理，必定有大量不同的块拥有相同的校验和。

这就是“碰撞”：两个内容完全不同的块，校验和却碰巧一样。如果你只看这个 32 位校验和就判定”匹配”，你就会把错误的旧块保留下来，文件就会损坏。

Tridgell 和 Mackerras 怎么解决这个问题？

他们用了一个双层过滤器的思路。这个思路本身，就是一个漂亮的工程设计故事。

第一层：滚动校验和（弱校验）——极快计算，但会误报。它的任务是做初筛：在滑窗的每一位置，滚算出 32 位值，然后去一个哈希表里查——旧文件的那些块里，有没有哪个块的弱校验和我一样？

绝大多数位置在这一步就被淘汰了。因为 32 位虽然会有碰撞，但对于“随机碰上一个匹配”这件事，概率是 40 亿分之一。绝大多数不匹配的块，在第一层就被筛掉了。

第二层：MD4（强校验）——只有弱校验匹配的那些极少数的位置，才触发强校验计算。128 位的 MD4，碰撞概率小到在工程上可以视为零。只有强校验也匹配，才真正判定为”这两个块内容一致”。

在测试数据里，这个双层设计的效率惊人：对于 Linux 内核源码的 tar 包（24MB），使用 500 字节的块大小，弱校验触发了 62 万次“疑似匹配”，但最终只有 4.7 万次是真匹配，而强校验排除假匹配的次数，只有 64 次。

64 次误报，对 4.7 万次真匹配。弱校验的筛选准确率高得离谱。这意味着：强校验几乎不需要被调用，而弱校验因为可以滚动更新，算起来根本不费力。

他把计算资源精确地投在“最需要的地方”，其他地方能省则省。 这就是工程之美。

八、回到那台电报机前

现在让我们回到你和电报机的故事。rsync 的实际流程，翻译成你的年鉴任务，是这样的：

第一步：小王那边（接收方 / β 端）

小王把旧版年鉴按每 500 个字切成固定大小的块（最后一块可能短一些）。2400 页 × 800 字 ÷ 500 = 3840 个块。

对每一个块，他计算两个指纹：

• 一个“弱指纹”——32 位的滚动校验和，4 个字节。便宜，但偶尔会误报。
• 一个“强指纹”——128 位的 MD4，16 个字节。贵，但几乎从不出错。

3840 个块 × 20 字节 = 76800 字节。他用电报发给你。几千块钱。

第二步：你这边（发送方 / α 端）

你拿到这份“指纹清单”后，不是逐页去对，而是从新版年鉴的第一个字开始，以每一个字为起点，取后面 500 个字作为一个块。

第一个块：第 1 到第 500 个字。第二个块：第 2 到第 501 个字。第三个块：第 3 到第 502 个字……一路滚下去，滚过 192 万个起点。

对每一个起点位置的块，你计算弱指纹，然后去那份清单里查——“有没有哪个旧块的弱指纹和我一样？”

• 没有 → 这个起点位置在旧版里不存在匹配。窗口向前滚动一个字，弱指纹 O(1) 更新，下一个。
• 有 → 触发警觉。你计算这个块的强指纹（MD4），和清单里那个“嫌疑块”的强指纹对比。

• 强指纹不匹配 → 误报。 虚惊一场，继续滚。
• 强指纹匹配 → 找到了！ 新版这一段的的确确和旧版的某个块一模一样。

找到匹配之后，你把从上一个匹配结束位置到当前匹配开始位置之间的”新内容”全文发给小王，然后告诉他：“接下来这一段，用你旧版的第 N 号块。”

然后你从匹配块的末尾继续往后滚。

第三步：小王那边

小王收到你的指令流，像拼乐高一样重建新版：

• “这是新内容，你收着” → 他把这段文字写入新文件。
• “用你旧版的第 N 号块” → 他去旧版年鉴里把那个块抠出来，拼上去。

最终，小王手上出现了一本完整的、和你一模一样的《中国工业年鉴 2026》。

而你实际通过电报发送的，只有：

• 旧块指纹清单：约 7.7 万字节.
• 新版独有的新内容：在 Linux 内核测试中，约是原文件的 5%。

从 20 万块钱，降到几千块钱。

九、慢着，还有一个漂亮的细节——流水线

你可能觉得上面这套流程已经够聪明了。但 Tridgell 和 Mackerras 还在上面叠了一层优化。

上面的流程是串行的：小王先算完全部指纹发给你 → 你算完全部匹配把指令发回去 → 小王再组装。这中间有大量的等待时间。在跨国链路上，延迟可能高达几百毫秒，等待就是浪费。

于是他们让 β 端（小王）同时跑两个独立进程：

• 进程一：不停地计算旧块的指纹，发给你。
• 进程二：不停地接收你发回来的指令，一边收一边组装。

两个进程互不阻塞。你这边还在滚校验和，他那边已经开始组装文件了。 链路在两个方向上被同时填满。

这个设计不改变算法本身，但它让 rsync 在真实网络中更快——而且是在那个时代（1996 年，拨号上网，延迟巨大）就已经考虑到了。这个工程意识，怎么说呢，超前得有点过分。

十、所以，到底什么才叫“天才的设计”

很多人了解完 rsync 会有一个感受：所有步骤拆开看，每一步都不难理解。 滚动校验和？就是加减法。哈希表查找？数据结构课本里就有。MD4？现成的。

但这就是最妙的地方：它用的全是“现成的砖”，但搭出了一个从来没人想到过的建筑。

在 rsync 之前，“远程文件同步”这件事的解法大致只有两种：

• 传整个文件（简单粗暴，但贵）。
• 传 diff/patch（需要两个文件都在同一端，实际上自相矛盾）。

rsync 开辟了第三种路径：只传指纹清单 + 不匹配的碎片，让远端自己拼回去。 这个思路在今天看来理所当然，但在 1996 年之前，全球互联网上没有任何工具这样做。

而让它能跑起来的”发动机”：滚动校验和，更是一个教科书级别的”换个角度看问题”：

别人看到的是“我需要算两百万次校验和，每次 O(n)，太慢了”。他们看到的是“校验和可以不是’算’出来的，而是’更新’出来的”。

不是更努力地算，而是换一种不需要算的方法。

结尾

今天，rsync 已经快 30 岁了。它躺在每一台 Linux 服务器里，躺在每一个 MacOS 的备份流程里，躺在无数云存储的同步引擎里。每天有数以亿计的文件通过它的算法思想完成传输。而它只需要传输平均 5% 的数据。

没有提出任何新的数学定理，没有发明任何新的密码学原语。它只是把几个已有的工具——滚动校验和、MD4、哈希表——以一种前人从未尝试过的方式组合在一起，解决了互联网时代最基础的一个工程问题：

如何在两个彼此看不到完整真相的节点之间，用最小的代价达成一致。

而 rsync 做的，就是把这句话翻译成了校验和。

后记：rsync 的作者 Andrew Tridgell 后来还做了另一件大事——他逆向工程了微软的 SMB 协议，写出了 Samba，让 Linux 和 Windows 可以在同一个网络里共享文件。他的风格一以贯之：在所有人都认为“这不可能”或者“只能传整个文件”的地方，他蹲下来看了看，说：不对，我们可以只传校验和。

作者丨最后的绅士

来源丨网址：
https://zhuanlan.zhihu.com/p/2040205763549851895

dbaplus社群欢迎广大技术人员投稿，投稿邮箱：editor@dbaplus.cn