个块，每个块要算一个强指纹（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 年，拨号上网，延迟巨大）就已经考虑到了。这个工程意识，怎么说呢，超前得有点过分。十、所以，到底什么才叫“