"手上有个 2.3GB 的固件包，这个版本只改了一个 40KB 的动态库和一个配置项，用户到底要不要重新下 2.3GB？"这是我第一次接手 OTA 升级链路时被问到的问题，也是增量更新这个需求最原始的形态。解决它的核心工具之一就是 BSDiff——一个 2003 年写出来、至今还在手机、浏览器、车机、游戏资源热更里默默干活的老家伙。它对外只暴露两个命令：bsdiff 负责把"旧文件 + 新文件"榨成一个小补丁，bspatch 负责在客户端把补丁打回去。整套东西没有参数、没有配置文件、没有服务端概念，但它背后的差分算法思想影响了一整代更新系统。这篇文章适合三类人看：正在设计客户端更新链路的工程师、被"补丁打不上/补丁比全量还大"折磨过的同学，以及想搞清楚后缀数组、贪心匹配、bzip2 这三样东西是怎么拼成一台机器的好奇者。

1. 先算清楚增量更新到底在省什么：从场景到成本账

1.1 一个 5MB 的改动让用户下 300MB，痛在哪里

先把这个需求放回真实场景里。假设你维护一个 Android 应用，APK 大小 300MB，其中 280MB 是美术资源和地图瓦片。这个版本策划改了三张图、修了两个 bug，代码改动不到 5MB。如果走全量更新，用户要从 CDN 拉 300MB，服务端要扛 300MB 的带宽，移动网络下用户可能直接放弃更新，最后你得到的是"版本覆盖率上不去、老版本 bug 一直有人报"。

增量更新的思路很朴素：既然新旧版本的差异只有 1.7%，那能不能只把"差异"传过去？于是整条链路变成三步：服务端把旧版本和新版本喂给差分算法，产出一个几百 KB 到几 MB 的补丁文件；客户端下载这个补丁，再把它和本地已经存在的旧文件合并，还原出完整的新版本。

这里有个容易被忽略但很关键的事实：客户端本来就有旧文件，这是增量更新能成立的前提。旧文件不是白占空间的垃圾，它是一份免费的高质量"参考数据"。差分算法本质上就是在利用这份参考数据做字典压缩——这也是为什么差分补丁能比普通的"新文件压缩包"小得多。同样是把新版本发给用户，直接 gzip 新文件可能得到 250MB，而用旧文件做参考得到 3MB，差距是数量级的。

代价也很明确，而且必须提前讲清楚：服务端要多花 CPU 和时间去生成补丁；客户端要多花一次合并运算；你要维护补丁和版本之间的对应关系。这三笔账没有一笔是白来的。

1.2 别指望差分是万能钥匙：数据的"熵"决定天花板

我见过最常见的误解，是有人拿着一个已经压缩过的 zip 包去做 bsdiff，然后发现补丁大小几乎等于新文件大小，跑来问"是不是参数没调对"。

不是参数问题，是数据本身的问题。差分算法的压缩率取决于"新旧文件之间到底有多少字节是相同的"，而这些相同字节又必须能被算法识别出来。压缩包、JPEG 照片、MP4 视频、加密后的数据块，它们的字节序列是刻意打散的——改了一个像素，压缩后的字节流可能整段都不一样。这种情况下差分算法看到的不是"改了一点点"，而是"整块全是新东西"。

所以判断一个更新场景适不适合用 BSDiff，有个不用跑代码的快速办法：

• 看新旧版本里相同结构的数据占比。代码段、文本、数据库文件、未压缩的位图、日志，这些"人写的、未压缩的"数据，差分效果都很好。
• 看改动是否会引起全局位移。比如在一个可执行文件头部插入了一段代码，后面所有函数的地址都会偏移，机器码里的跳转指令和重定位表会大面积变化，字节层面看起来"到处都是差异"，但语义上只改了一处。这是 BSDiff 最大的一块短板，后面第 2 章会讲它是怎么被后人补上的。
• 看压缩时机。先解压、再差分、最后重新压缩，是处理压缩型数据的标准套路。同一个 zip 包，如果你能拆成一个个条目分别差分，效果会比整包差分好上一大截。

以我自己跑过的数据做粗略参考（具体数字高度依赖数据本身，只当量级看）：

看到最后两行你就明白了：差分不是压缩算法的升级版，它只是一个更聪明的字典压缩，前提是字典和原文确实长得像。

1.3 BSDiff 在整条更新链路里站在哪个位置

很多人把 bsdiff 和"更新系统"混为一谈，其实它只占整条链路里非常小的一块。一个完整的增量更新链路大致长这样：

1. 版本管理：服务端保留最近 N 个版本的安装包，每个版本有唯一标识（通常是文件哈希）。
2. 补丁生成：离线或准实时地把"旧版本 → 新版本"的差分跑出来，结果落盘并缓存。
3. 补丁分发：客户端上报自己当前的版本号，服务端返回匹配的补丁地址；如果没有匹配补丁，就回落到全量。
4. 客户端合并：下载补丁，校验补丁完整性，用本地旧文件还原新文件。
5. 结果校验与回滚：对还原出来的新文件做哈希校验，不一致就丢弃、回落全量，绝对不能带着一个损坏的文件继续跑。

BSDiff 只负责第 2 步和第 4 步里的算法部分。第 3 步和第 5 步恰恰是最容易翻车的地方，第 6 章会专门讲。把这个边界认清之后，你就不会指望"换个更牛的差分算法"能解决所有问题了。

2. BSDiff 的来路：一个 FreeBSD 开发者顺手写出来的小工具

2.1 需求起点是"怎么把二进制安全更新发出去"

要理解 BSDiff 的设计取舍，得先回到它诞生的场景。2003 年前后，Colin Percival 在做 FreeBSD 的二进制更新工作。当时的痛点是：安全补丁经常只改了一个库文件里的几十行代码，但用户为了拿到这个补丁，必须下载整份二进制包。

这不是"用户体验不好"这么轻描淡写的问题，而是直接影响安全补丁的普及率——补丁包越大，愿意及时更新的机器越少，暴露在风险里的时间越长。所以他的目标是：做一个能把二进制文件之间的差异压到极小的工具，而且是纯命令行的、不依赖系统状态、可以直接塞进更新脚本里的那种。

这个目标决定了 BSDiff 的性格：它不关心文件格式、不解析 ELF、不做反汇编，只把文件当成字节流。这种方法论的代价是"看不懂语义"，好处是通用——同样的代码可以处理可执行文件、文档、数据库文件、磁盘镜像，什么都能吃。这个"字节流万能论"既是它二十多年不倒的原因，也是它被 Courgette 这类后继者超越的原因。

同年，他写了一份技术报告《Naive Differences of Executable Code》，把整套方法和动机讲清楚了。报告标题里的 "Naive" 用得很诚实——作者自己就承认这是一种朴素的做法，不去理解代码结构，只在字节层面找最长公共子串。这个词后来也成了很多人评价 BSDiff 时的第一反应，但朴素不等于低效，它的压缩率在同类工具里长期是第一梯队。

顺便说一句，这位作者后来还写了一个在密码学圈子里非常有名的东西——scrypt 密钥派生函数。能在两个完全不同的领域都留下被广泛使用的作品，这种"顺手写个小工具结果被全世界用了二十年"的故事，在开源圈子里还挺浪漫的。

2.2 那份报告里真正被固化下来的三个决定

报告不长，但里面有几个决定一直保留到了今天，理解它们比背算法细节更重要。

第一个决定：压缩和差分分成两步，先差分再压缩。BSDiff 不试图设计一个"能同时做差分和压缩"的编码，而是先用差分把新文件表示成"参考旧文件的一堆指令"，再把这个指令流丢给通用压缩器 bzip2。这个分层设计非常聪明：差分层只负责把数据变成"低熵"的形式，压缩层只负责吃掉剩下的冗余。想换压缩器，只动压缩层就行——这也是今天各种 bsdiff 变体能轻松替换成 zstd、brotli 的原因。

第二个决定：用后缀数组找最长匹配，而不是滚哈希。滚哈希（类似 rsync 的做法）只能找固定长度或有限长度窗口的匹配，而且需要一个预先选好的块大小；后缀数组则能在 O(log n) 的时间里找到"以当前位置开头、在旧文件里出现过的最长前缀"，不管它是 10 字节还是 10MB。代价是内存开销大，这个账后面第 5 章细算。

第三个决定：补丁是单向的，只支持"旧 → 新"。没有"反向打补丁"的概念，也没有把新旧文件都当成参考。这让格式简单了很多，但也意味着回滚要走另一条链路。实战中这是个需要额外设计的点，很多团队第一次上线增量更新时都会漏掉。

2.3 二十多年里它被塞进了哪些地方

BSDiff 的传播路径挺有意思，它几乎从没做过市场推广，全靠"谁有需求谁就把它搬过去"。

Android 的 OTA 升级包是最典型的用户。Google 在 recovery 里内置了一套基于 bsdiff 的差分工具，同时针对 zip 包和稀疏镜像做了变体 imgdiff——它会先把 zip 的各个条目拆开、把稀疏镜像的填充块处理掉，再对每个条目分别调用 bsdiff。这就是前面说的"先解压再差分"思路的工程化落地，比整包 bsdiff 的补丁小得多。

浏览器和客户端软件的自动更新、各种系统的固件升级、游戏的热更新资源包、车机 OTA、机顶盒固件、嵌入式设备的现场升级，都曾经或正在用这类工具。移动应用商店也做过大规模的文件级差分更新，把应用拆成一个个文件分别差分再打包，公开过的平均值是能砍掉一半以上的下载体积。

我印象最深的一次是给一个资源包做热更，新版本只改了 UI 描述文件和一个脚本，1.2GB 的包里补丁只有 200 多 KB。当时团队里有人怀疑"是不是补丁生成错了"，专门写了个脚本逐字节对比还原结果——完全一致。这件事之后，我们才真正接受了"补丁比改动本身还小"这个反直觉但合理的结果，因为它把参考文件当成了字典。

2.4 被现实逼出来的那几个"后代"

BSDiff 有个硬伤在长期使用中逐渐暴露：它不理解代码结构。在可执行文件前面插入一段函数，后面所有函数的地址都会平移，机器码里的相对跳转、绝对地址、重定位表全部变化。即使逻辑上只改了一个函数，字节层面看起来也像"全文件重写"。

针对这个问题，Google 在 Chromium 的更新里做了 Courgette：先用反汇编器把可执行文件拆成指令，识别出哪些差异其实只是地址偏移，把地址"归一化"之后再做差分。这一步预处理让补丁体积又降了一个数量级，代价是必须针对每一种 CPU 架构写反汇编支持，通用性大幅下降。

另一类改进方向是工程可用性。原版 bsdiff 对超大文件不友好、内存吃得多、只支持 bzip2。后来出现的 hdiffpatch 这类工具，重新设计了后缀排序和匹配策略，支持更大的文件、可选的流式处理、多种压缩后端（zstd / lzma 等），还提供了补丁内嵌校验信息，在游戏行业的资源热更里用得很多。另外 zstd 自带的--patch-from也提供了一种"用旧文件当字典"的差分能力，思路相近，但走的是字典压缩路线而不是指令流路线。

这些后代的出现并不说明 BSDiff 过时了，而是说明同一个问题在不同约束下有不同的最优解：字节流通用性优先选它，补丁体积极致优先考虑 Courgette，超大文件和工程集成优先考虑 hdiffpatch。

3. 三个工序咬合成一台机器：后缀排序、贪心匹配、bzip2 压缩

3.1 第一道工序：qsufsort 把旧文件的每个后缀排好队

理解 BSDiff 的第一个门槛是"后缀数组"这个词。别被它吓到，用一句话说清楚：把旧文件的每个位置当作起点，一直取到文件结尾，会得到 n 个"后缀串"（n 是旧文件字节数）；把这 n 个后缀串按字典序从小到大排好序，把它们的起始位置存成一个数组，这个数组就是后缀数组。

拿banana举例，它的后缀有banana、anana、nana、ana、na、a，按字典序排完是a、ana、anana、banana、na、nana，对应的起始位置就是[5, 3, 1, 0, 4, 2]。就这么多。

为什么要有这个东西？因为有了它，"以某个字节串开头的所有出现位置"就变成了连续的一段。你想知道新文件里的anana在旧文件里出现过没有、出现在哪，只要在排好序的后缀数组上做二分查找，找到后再逐个比对字符就能拿到最长匹配长度。如果没有后缀数组，你就得对旧文件的每个位置暴力比对，复杂度直接爆炸。

BSDiff 用的是 Larsson-Sadakane 的倍增构造法（实现里叫 qsufsort），时间大约 O(n log n)，并且只需要两个off_t类型的大数组来滚动计算。关于算法本身我先不展开，记住结论就够了：它是"预处理旧文件"这一步的全部开销所在，也是内存占用的主要来源。

这里有个实战细节值得提前说：后缀数组一旦建好，就可以对任意多个新文件复用。也就是说，如果你要同时生成"旧版本 → 版本 A""旧版本 → 版本 B""旧版本 → 版本 C"三个补丁，理想情况下旧文件的后缀数组只需要建一次。可惜原版 bsdiff 的命令行工具不支持这个模式，每次调用都会从头重建。真要批量出补丁，得自己改代码或者在流程上做取舍，这是个很实际的性能改造点。

3.2 第二道工序：scan 循环如何判断"这里该匹配还是该直传"

拿到后缀数组之后，bsdiff 从新文件的第 0 个字节开始往里走，每一步问一个问题：以新文件当前位置开头的这段内容，在旧文件里能匹配多长？

如果匹配长度大于 0，通常意味着"这段内容在旧版本里出现过"，那就可以用"参考旧文件的这一段 + 少量修正字节"来表示，非常省地方。但这里有个陷阱：匹配到了不等于值得匹配。假设匹配长度只有 3 个字节，但这 3 个字节在旧文件里的位置离当前位置十万八千里，那么记录"跳到那里"需要存储一个跳转量，存储修正字节也要 3 个字节，加起来可能比直接把这 3 个字节原样塞进补丁还贵。

所以 bsdiff 的 scan 循环里藏着一套评分启发式，核心思想是：只有当匹配区域内的相同字节密度足够高时，才值得把它抽成一次匹配。实现上它用一个2 * 相同字节数 - 区域长度的形式来打分，并且会沿着匹配的边界向前向后各扫一段，找一个让总收益最大的切分点。这个"前后双向扩展"的细节很关键，它决定了相邻匹配块之间的边界落在哪，直接影响到 diff 流里非零字节的数量。

另一个能显著提升速度的细节是：一次匹配成功之后，扫描指针直接跳过整个匹配长度，而不是一个字节一个字节地前进。所以 bsdiff 并不会对新文件的每一个位置都发起一次二分查找——大部分位置都被跳过了。这也是它虽然算法看起来复杂，实际跑起来没慢到不可接受的原因之一。

3.3 第三道工序：ctrl、diff、extra 三个流各管什么

这是整个算法里最需要记清楚的部分。bsdiff 把新文件重新表达成三个流：

• ctrl 流：一串三元组(x, y, z)。语义是"从 diff 流取 x 个字节，从 extra 流取 y 个字节，然后把旧文件指针移动 z"。
• diff 流：与旧文件对应位置的字节差，用来描述"相似但不相同"的内容。
• extra 流：完全找不到参考的新增内容，原样存放。

举个具体例子你就明白了。假设旧文件是The quick brown fox，新文件是The quick red fox jumps。算法会发现The quick和fox这两段在旧文件里有对应，于是：

• The quick这一段：diff 流里写入 10 个0x00（因为完全一样，差值全是 0），ctrl 记(10, 0, 0)；
• red这一段在旧文件里没有对应：extra 流里原样写red，ctrl 记(0, 3, 0)；
• fox这一段：diff 流再写 4 个0x00，同时旧文件指针要跳回到fox的位置，ctrl 记(4, 0, 6)——这个 6 就是"往回跳 6 个字节"。
• 最后jumps找不到对应：extra 流写jumps，ctrl 记(0, 5, 0)。

看到没有，最终落盘的 diff 流几乎全是 0，extra 流只有真正新增的那几个字节。这就是为什么补丁能比改动本身还小的原因——它存的不是数据，是"怎么从旧文件拼出新文件"的操作说明。

这里还有个容易被忽略的设计点：ctrl 三元组里的 z 是有符号的，可以为负。这意味着匹配块在新旧文件里的顺序可以完全不一致——新文件的第 100 行可能对应旧文件的第 10000 行，后面又跳回第 50 行。这种"乱序引用"能力是 bsdiff 比一些简单差分工具强的关键，因为真实的文件改动经常涉及代码块的移动（重构、函数重排），而不是单纯的插入删除。

3.4 8 字节的符号位把戏：一个专门为压缩率服务的小心机

三元组最终要以某种形式写进补丁文件。最直觉的做法是每个数字用变长编码或者固定 4 字节整数，但 bsdiff 用的是固定 8 字节的符号-数值表示。

具体写出来是这样的：把一个数取绝对值，按小端序逐字节写入 8 个字节的缓冲区；如果原数是负数，就把第 8 个字节的最高位（0x80）置位。这样做的效果是：

• 数值的绝对部分集中在低字节，高字节大量为 0；
• 符号信息只占 1 个 bit，而且是单独放在最高字节的顶部；
• 所有的小数值（0、1、2、-1 这类在 ctrl 流里最常出现的）都会呈现为"一堆 0x00 后面跟一个小数"，bzip2 处理这种模式几乎没有成本。

如果换成普通的二进制补码表示，负数会变成0xFF 0xFF 0xFF ...的形态，虽然也能压，但和 0x00 混杂的时候模式会变得没那么规整。这种"为了让下游压缩器舒服一点而在编码上做妥协"的做法，是整个 BSDiff 里我最欣赏的一处细节——它体现的是作者把"差分"和"压缩"当成一个整体在优化，而不是各干各的。

补丁文件的整体头部也是同一套编码：

三个流各自独立压缩、独立解压，互不依赖。这种布局带来了一个很实用的好处：bspatch 可以边解压边写输出，不需要把整个补丁全部解到内存里再处理。

4. 补丁还原：bspatch 为什么能在手机上毫秒级完成

4.1 三元组驱动的两个指针，逻辑简单到可以背下来

bspatch 的还原逻辑，比生成过程简单了不止一个量级。它只需要两个指针：一个指向旧文件的当前位置，一个指向新文件的写入位置。然后循环读 ctrl 三元组：

1. 从 diff 流读 x 个字节；
2. 从 extra 流读 y 个字节；
3. 从旧文件读 x 个字节，和 diff 的 x 个字节逐字节相加，结果写进新文件；
4. 把 extra 的 y 个字节原样追加到新文件末尾；
5. 旧文件指针向前移动 z（z 可以是负数，表示往回跳）。

循环结束，新文件就完整了。off_t类型的三元组在文件里固定 8 字节，所以解析 ctrl 流的工作本质上就是"每 24 字节切一刀，按符号-数值规则解码"，连分支预测都不用担心。

这解释了为什么客户端侧的体验往往很好：用户点一下更新按钮，几百毫秒就装好了，感觉像没下载一样。因为它的计算量基本就是把新文件大小的字节读写一遍，加上几百次内存拷贝。1GB 的目标文件在手机上通常也就一两秒的量级，瓶颈往往是磁盘 I/O 而不是 CPU。

4.2 字节级模加：diff 流为什么天然适合压缩

第 3 章提到 diff 流存的是"字节差"，这里要补充一个关键细节：这个差是无符号字节的模 256 加法，也就是新字节 = （旧字节 + diff字节）& 0xFF。

为什么用加法不用异或？因为加法产生的值分布"更像真实差异"。两个字节相同，差值是 0；相差 1，差值是 1；相差 -1，差值是 255。在真实文件里，改动往往集中在低位的小范围波动（比如一个递增的计数器、一个稍微调大一点的常量），产生的 diff 值就是 0x01、0x02 这类小数字，扎堆出现，压缩器最喜欢。用异或的话，改动一个 bit 就会产生 0x01，改动两个 bit 产生 0x03，模式上没有加法那么"聚集"。

更妙的是，大片完全相同的区域会产生大片的 0x00。bzip2 处理超长重复字节串的效率极高，一个 100MB 的全零块压缩后可能只有几百字节。所以你会看到 bsdiff 的补丁体积波动很大：如果新旧版本之间大部分内容没动，补丁极小；如果改动导致大片区域重排，补丁立刻膨胀。这不是算法不稳，而是它在忠实地反映数据的变化程度。

4.3 用 40 行 Python 把这套机制跑通

光看文字描述容易有种"懂了但又没完全懂"的感觉，所以我写了一个极简版本，把 ctrl / diff / extra 三个流的语义完整复现出来。注意它不是bsdiff 的实现——它用固定长度的哈希索引代替后缀数组，用简单的贪心代替评分启发式，压缩率会差很多。它的唯一目的是让你把三个流的结构看得清清楚楚。

BLOCK = 16 def make_patch(old, new): # 极简索引：记录每个 BLOCK 长度片段第一次出现的位置 idx = {} for i in range(len(old) - BLOCK + 1): idx.setdefault(bytes(old[i:i + BLOCK]), i) ctrl, diff, extra = [], bytearray(), bytearray() lit = bytearray() # 暂存还没匹配上的字面量 oldpos, i, n = 0, 0, len(new) while i < n: hit = -1 if i + BLOCK <= n: hit = idx.get(bytes(new[i:i + BLOCK]), -1) if hit < 0: lit.append(new[i]) # 没命中，攒起来当字面量 i += 1 continue L = BLOCK # 命中后向后扩展，尽量延长匹配 while i + L < n and hit + L < len(old) and new[i + L] == old[hit + L]: L += 1 if lit: # 先吐之前的字面量 extra.extend(lit) ctrl.append((0, len(lit), 0)) lit = bytearray() if hit != oldpos: # 需要跳转就单独发一条 seek 指令 ctrl.append((0, 0, hit - oldpos)) oldpos = hit diff.extend((new[i + k] - old[hit + k]) & 0xFF for k in range(L)) ctrl.append((L, 0, 0)) oldpos += L i += L if lit: extra.extend(lit) ctrl.append((0, len(lit), 0)) return ctrl, bytes(diff), bytes(extra) def apply_patch(old, ctrl, diff, extra): out = bytearray() oldpos = dpos = epos = 0 for x, y, z in ctrl: for k in range(x): # 旧文件 + diff，模 256 out.append((old[oldpos + k] + diff[dpos + k]) & 0xFF) oldpos += x dpos += x out += extra[epos:epos + y] # extra 原样追加 epos += y oldpos += z # 指针按 z 移动，可为负 return bytes(out)

跑一遍就能验证apply_patch(old, *make_patch(old, new)) == new。真实 bsdiff 里，seek 是和复制指令合并在同一个三元组里的（靠x + z的组合完成指针调整），这里为了看清语义拆成了独立指令；它的匹配靠后缀数组找全局最长匹配，这里只能找固定锚点的匹配。但三个流的骨架、指针的走法、模加的语义，和原版是完全一致的。

把这段代码跑通之后，你再看任何"补丁打不上"的报错，排查方向都会立刻清晰：要么是旧文件和生成补丁时用的不是同一份（三元组指向了错误的偏移），要么是补丁在传输中损坏（diff 或 extra 被截断），要么是新文件的长度和 ctrl 流描述的对不上。这三个方向基本覆盖了现场九成以上的问题。

5. 时间与内存账单：17n 这个数字是怎么算出来的

5.1 内存主要吃在后缀数组那两个大数组上

BSDiff 有个在圈子里流传很广的说法：它需要大约 17 倍于旧文件大小的内存。这个数字不是吓唬人的，具体拆开来看是这样的。

构造后缀数组时需要两个和旧文件等长的索引数组（一个存排序结果，一个存中间排名），如果编译成 64 位程序、下标用 8 字节表示，这两个数组就是 16n。除此之外还有旧文件本身（n）、新文件（m）、以及 diff 和 extra 两个输出缓冲区（合计约 n+m）。峰值出现在后缀排序阶段，因为那时新旧文件和各种缓冲区都已经分配好了。

所以"17 倍"这个经验值是有前提的：它大致对应 32 位下标、以及实际文件大小落在某个范围内的情形。用 64 位编译，实际峰值会更高一些；而且排序结束后那个中间排名数组就可以释放了，之后的内存占用会明显回落。真正致命的场景是你在一个 4GB 内存的构建机上跑两个 1.5GB 文件的差分——那基本上是把机器按在地上摩擦。

我踩过这个坑。当时给一个 1.2GB 的固件做差分，本机 16GB 内存，跑是能跑，但同一时间只敢开一个任务；后来为了批量出 8 个版本的补丁，写了个队列串行跑，整体出包时间从"并行 20 分钟"变成"串行 3 小时"。这里没有取巧空间，要么加机器，要么换算法，要么减少需要差分的版本数量。

5.2 时间都花在哪了，跟直觉可能不一样

很多人以为最大的时间开销是后缀排序，实际多跑几次就会发现，压缩往往占了大头。

后缀排序是 O(n log n)，但每一步都是紧凑的数组操作，局部性不错，现代 CPU 跑起来效率还行。而 bzip2 是出了名的慢——它用的是 Burrows-Wheeler 变换加霍夫曼编码，压缩比好但速度一般，而且 bsdiff 默认是最高块大小，对几百 MB 的数据流压缩起来相当耗时。

这就给了一个很现实的优化方向：如果出包时间不可接受，先考虑换掉压缩后端，而不是换掉差分算法。很多 bsdiff 的分支版本支持把 bzip2 换成 zstd 或 brotli，压缩率可能略微下降几个百分点，但压缩耗时能快好几倍，整体出包时间立刻下来了。而且客户端侧的解压速度也跟着提升——对手机这种设备来说，解压速度往往比补丁体积更重要，因为用户能感知到的只有安装时的等待。

反过来，客户端侧真正的时间开销是"读旧文件 + 写新文件"这两次 I/O。如果你在一个机械硬盘或者低速存储上打 1GB 的补丁，瓶颈一定在磁盘上，这时候再怎么优化算法都没用，能做的只有减少 I/O 次数（比如边解压边写，不把所有流先解到内存）。

5.3 32 位下标和 2GB 天花板这个经典坑

原版 bsdiff 4.3 有一个被讨论了很多年的问题：在 32 位平台上，由于off_t只有 4 字节，它无法正确处理超过 2GB 的文件（严格的说是单文件超过2^31 - 1字节时会溢出，出现段错误或者生成错误的补丁）。在 64 位平台上，只要编译时正确启用了大文件支持，这个问题就不存在了。

但这里有个隐蔽的连带影响：即使你的程序是 64 位编译的，如果数据流中间某处的中间变量仍然用了 32 位整数，大文件依然会出问题。所以碰到"小文件一切正常，大文件出诡异结果"的情况，第一件事就是检查所有和文件长度、偏移量相关的变量类型是不是 64 位的off_t或int64_t，而不是int或long（注意在 Windows 上long是 32 位的，这个坑非常经典）。

另外一个和版本相关的现实问题：原版最后一个正式版本是 4.3，之后很多年没有再发布新版本。你在不同系统上通过包管理器装到的bsdiff，可能来自不同的分支或者经过了各种补丁。这意味着"我这边能跑通"和"线上环境能跑通"不一定等价——出包环境最好固定一个版本，把源码和编译参数一起纳入版本管理，别指望apt install装到的和同事机器上的是同一份。

6. 落到工程里：出包链路、版本矩阵与翻车清单

6.1 服务端：补丁矩阵和它的成本曲线

补丁是有方向的，这一点决定了服务端要做选择。假设当前线上有 v1 到 v10 十个版本，最新的 v11 发布后，理论上你需要生成 10 个补丁（v1→v11、v2→v11 …… v10→v11），这就是"补丁矩阵"。

全量生成的成本非常高。假设每个补丁平均要跑 10 分钟、内存峰值 8GB，10 个补丁就是 100 分钟机时加 80GB 峰值内存。所以实际工程里几乎都会做裁剪：

• 只保留最近 N 个版本。这是最常见的做法。用户版本太老，就让他先升到一个中间版本，或者直接走全量。N 取多少取决于版本淘汰速度和服务器资源，3 到 5 是比较舒服的区间。
• 懒生成 + 缓存。不预先算好所有补丁，等真的有用户请求某个版本对时再触发计算，算完就缓存起来。缺点是第一个用户要等很久，所以通常会配合"热点版本预生成"一起用。
• 按渠道或设备分组合并。如果某个渠道的包只改了包名和签名，其他内容完全一致，可以先做一次"去渠道"归一化再差分，把补丁矩阵的维度砍掉一层。

有个容易忽略的成本：补丁文件本身也是要占存储和带宽的。如果你的补丁平均 20MB、有 30 个版本对、每个补丁保留 3 个历史版本，那就是 1.8GB 的存储，还要考虑 CDN 回源。所以补丁也是需要做过期清理的，不能只生成不回收。

6.2 客户端：校验、回滚，和"宁可全量"的底线

客户端这一侧，我的经验是可以写一句口诀：任何一步不确定，就回全量。

具体要校验的地方至少有四处：

1. 补丁文件本身的完整性。下载过程中可能中断、可能被中间设备改写，必须校验。原版 bsdiff 的补丁格式里只有 bzip2 每个流自带的校验，没有覆盖整个文件的哈希，所以工程上一般会额外带一个补丁的哈希值随下载接口一起下发。
2. 本地旧文件的身份。这是最容易被忽略的一处。用户设备上的旧文件可能因为上次升级中断而处于损坏状态，也可能被其他程序修改过。打补丁之前必须先算一次旧文件的哈希，和生成补丁时用的版本比对，不一致就立刻回全量——千万不要"先试着打一下，不行再说"，因为打失败的中间产物可能是部分正确部分错误的文件，这种文件最难排查。
3. 还原出来的新文件。打完补丁后必须对新文件算哈希，和预期值比对。这一步是整个链路的安全网。
4. 磁盘空间。打补丁的过程需要同时存在旧文件、补丁文件和新文件，峰值占用是三者之和。手机上这条特别容易翻车，尤其是在旧文件就有几百兆的场景下。提前检查剩余空间，不足就直接引导用户走全量升级或者清理。

还有一点值得强调：还原过程必须是原子的。先写到临时文件，校验通过后再替换正式文件；中途任何失败都删掉临时文件、保留旧文件。如果直接原地覆盖，一旦断电或者进程被杀，用户就两头不占了——旧文件被破坏、新文件没生成，只能重装。

6.3 高频翻车点对照表

下面这些是我和团队在实际项目里真正遇到过的，按出现频率排。

最后一行那个现象特别值得说。当更新涉及多个文件时，有些人会做"逐文件差分 + 逐文件替换"，如果一个文件成功了另一个失败了，设备上就会出现"新旧版本混合"的状态。对于应用来说这是灾难性的——它既不是 v1 也不是 v2，任何针对特定版本的逻辑分支都可能失效。要么整体成功，要么整体回退，中间态一定不能落地。

6.4 什么情况下应该果断放弃 BSDiff

不是所有场景都值得上差分。以下几种情况我建议直接放弃：

• 更新频率极低、包体又小。一个一年更新两次、包体 30MB 的内部工具，做差分的工程成本远大于省下来的那点流量。
• 数据本身不可复用。前面说过的压缩包、加密数据、随机生成的内容，差分的收益几乎为零。
• 客户端算力或存储极其紧张。有些设备连同时容纳新旧两个文件的空间都没有，差分反而让升级变得不可能。
• 可执行文件频繁重构但逻辑改动很小。这种情况下字节层面的差分看不到语义，补丁会大得离谱，应该考虑支持重定位的专用方案。
• 需要频繁回滚。BSDiff 只支持单向，如果你需要"随时退回任意历史版本"，就要重新设计成"每个版本都保留全量 + 补丁只用于前进"的结构。

我个人的判断标准很简单：先算一笔账，看看差分能省下多少带宽，再算算要投入多少工程人力去维护它。省下的带宽乘以用户数、乘以未来的更新次数，如果这个数字比不上一到两个人月的开发维护成本，就别做。

7. 手工实验：把 BSDiff 跑出感觉来

7.1 编译与最小实验

原版工具的编译非常简单，但这里有个老生常谈的小问题值得提醒：Makefile 里对 bzip2 的链接参数处理得比较随意，在某些编译器版本下会报undefined reference to BZ2_bzWriteOpen之类的错。解决办法是把-lbz2放到链接命令的末尾，或者干脆手动指定：

# 拿到源码解压后 make CFLAGS="-O2 -Wall -lbz2" # 如果报链接错误，手动编译一遍 cc -O2 -o bsdiff bsdiff.c -lbz2 cc -O2 -o bspatch bspatch.c -lbz2

两个命令的用法都极其简单，没有任何选项，就是三个位置参数：

# 生成补丁：旧文件 新文件 输出补丁 bsdiff old.bin new.bin patch.bin # 应用补丁：旧文件 输出文件 补丁 bspatch old.bin rebuilt.bin patch.bin # 验证 cmp new.bin rebuilt.bin && echo "还原一致"

cmp这一步千万别省。它是最便宜、最可靠的验证手段，几秒钟就能跑完，比事后排查线上问题便宜一万倍。

7.2 三类数据实测下来差别有多大

我在自己的环境里跑过一组对照，不是严格的基准测试，但结论方向很明确。做法是准备三份 100MB 左右的"旧文件"，各自做一次小改动，然后比较补丁大小：

第二行那个结果值得多想一会儿。很多人第一次看到"我只改了 20 个字节，为什么补丁有 5MB"会觉得算法有问题，其实是因为在文件中间插入了内容，导致后面所有字节的位置都变了。字节流层面的差分看不见"这只是位置变了"，它只能忠实地记录"后面这几兆字节全都和以前不一样"。这也解释了为什么工程上对可执行文件做差分时，往往要先用工具做结构对齐或者干脆用支持重定位的方案。

7.3 换掉压缩后端会发生什么

最后一个实验思路，也是最能帮你建立直觉的一个：把补丁文件当成普通文件，用不同的压缩器再压一遍，看看还能压掉多少。

# 原版补丁已经是 bzip2 压缩过的三个流拼起来的 ls -l patch.bin # 再压一次，观察已压缩数据的"不可压性" bzip2 -k -9 patch.bin && ls -l patch.bin.bz2 zstd -19 patch.bin -o patch.zst && ls -l patch.zst

大概率你会发现再压缩的收益很小，这验证了前面说的"diff 和 extra 流本身已经是被压缩过的高质量数据"。真正有意思的是反过来做：拿一份完全相同的旧文件和补丁，换用支持 zstd 后端的差分工具跑一遍，比较补丁体积和生成耗时。

我在自己的场景里得到过的结论是：补丁体积可能增加一到两个百分点，但生成时间能降到原来的三分之一到五分之一。对一个每天要出几十个补丁的团队来说，这个交换几乎是必然要做的——出包流水线的耗时是实打实的开发效率成本，而那一两个百分点的体积差异在大多数业务里感知不到。

我个人在实际操作中的体会是，不要把 BSDiff 当成一个孤立的命令行工具，而要把它当成一个"模板"。真正落到项目里，你需要自己决定的东西比算法本身多得多：用哪个压缩后端、什么时候生成补丁、保留多少个版本、客户端怎么做原子替换和校验、失败了怎么兜底。算法部分你可以信任这个二十年前就写好的设计，它不会给你惊喜也不会给你意外；剩下的那些取舍，才是这个项目真正花时间的地方。另外一个小建议，如果你准备在自己的项目里引入差分更新，第一件事不是写代码，而是先在真实数据上跑一次实验，把补丁体积、生成耗时、峰值内存这三个数字量出来——这三个数字会直接决定你的方案能不能过评审，也决定了你要不要去做那些围绕它的工程优化。