手上有个 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 包如果你能拆成一个个条目分别差分效果会比整包差分好上一大截。以我自己跑过的数据做粗略参考具体数字高度依赖数据本身只当量级看数据类型补丁 / 新文件体积原因纯文本、配置、SQL 导出1% ~ 5%改动局部化重复串极多未压缩二进制、固件裸镜像5% ~ 20%代码段相似但地址位移会拉高已压缩包、图片、视频60% ~ 100%修改导致字节流大面积重排加密数据、随机数表~100%完全没有可复用的参考价值看到最后两行你就明白了差分不是压缩算法的升级版它只是一个更聪明的字典压缩前提是字典和原文确实长得像。1.3 BSDiff 在整条更新链路里站在哪个位置很多人把 bsdiff 和更新系统混为一谈其实它只占整条链路里非常小的一块。一个完整的增量更新链路大致长这样版本管理服务端保留最近 N 个版本的安装包每个版本有唯一标识通常是文件哈希。补丁生成离线或准实时地把旧版本 → 新版本的差分跑出来结果落盘并缓存。补丁分发客户端上报自己当前的版本号服务端返回匹配的补丁地址如果没有匹配补丁就回落到全量。客户端合并下载补丁校验补丁完整性用本地旧文件还原新文件。结果校验与回滚对还原出来的新文件做哈希校验不一致就丢弃、回落全量绝对不能带着一个损坏的文件继续跑。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因为完全一样差值全是 0ctrl 记(10, 0, 0)red这一段在旧文件里没有对应extra 流里原样写redctrl 记(0, 3, 0)fox这一段diff 流再写 4 个0x00同时旧文件指针要跳回到fox的位置ctrl 记(4, 0, 6)——这个 6 就是往回跳 6 个字节。最后jumps找不到对应extra 流写jumpsctrl 记(0, 5, 0)。看到没有最终落盘的 diff 流几乎全是 0extra 流只有真正新增的那几个字节。这就是为什么补丁能比改动本身还小的原因——它存的不是数据是怎么从旧文件拼出新文件的操作说明。这里还有个容易被忽略的设计点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 里我最欣赏的一处细节——它体现的是作者把差分和压缩当成一个整体在优化而不是各干各的。补丁文件的整体头部也是同一套编码偏移长度内容08魔数BSDIFF4088ctrl 流压缩后的长度168diff 流压缩后的长度248新文件的原始大小32变长ctrl 流bzip2 压缩32 ctrl 长度变长diff 流bzip2 压缩末尾变长extra 流bzip2 压缩三个流各自独立压缩、独立解压互不依赖。这种布局带来了一个很实用的好处bspatch 可以边解压边写输出不需要把整个补丁全部解到内存里再处理。4. 补丁还原bspatch 为什么能在手机上毫秒级完成4.1 三元组驱动的两个指针逻辑简单到可以背下来bspatch 的还原逻辑比生成过程简单了不止一个量级。它只需要两个指针一个指向旧文件的当前位置一个指向新文件的写入位置。然后循环读 ctrl 三元组从 diff 流读 x 个字节从 extra 流读 y 个字节从旧文件读 x 个字节和 diff 的 x 个字节逐字节相加结果写进新文件把 extra 的 y 个字节原样追加到新文件末尾旧文件指针向前移动 zz 可以是负数表示往回跳。循环结束新文件就完整了。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 两个输出缓冲区合计约 nm。峰值出现在后缀排序阶段因为那时新旧文件和各种缓冲区都已经分配好了。所以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 分钟、内存峰值 8GB10 个补丁就是 100 分钟机时加 80GB 峰值内存。所以实际工程里几乎都会做裁剪只保留最近 N 个版本。这是最常见的做法。用户版本太老就让他先升到一个中间版本或者直接走全量。N 取多少取决于版本淘汰速度和服务器资源3 到 5 是比较舒服的区间。懒生成 缓存。不预先算好所有补丁等真的有用户请求某个版本对时再触发计算算完就缓存起来。缺点是第一个用户要等很久所以通常会配合热点版本预生成一起用。按渠道或设备分组合并。如果某个渠道的包只改了包名和签名其他内容完全一致可以先做一次去渠道归一化再差分把补丁矩阵的维度砍掉一层。有个容易忽略的成本补丁文件本身也是要占存储和带宽的。如果你的补丁平均 20MB、有 30 个版本对、每个补丁保留 3 个历史版本那就是 1.8GB 的存储还要考虑 CDN 回源。所以补丁也是需要做过期清理的不能只生成不回收。6.2 客户端校验、回滚和宁可全量的底线客户端这一侧我的经验是可以写一句口诀任何一步不确定就回全量。具体要校验的地方至少有四处补丁文件本身的完整性。下载过程中可能中断、可能被中间设备改写必须校验。原版 bsdiff 的补丁格式里只有 bzip2 每个流自带的校验没有覆盖整个文件的哈希所以工程上一般会额外带一个补丁的哈希值随下载接口一起下发。本地旧文件的身份。这是最容易被忽略的一处。用户设备上的旧文件可能因为上次升级中断而处于损坏状态也可能被其他程序修改过。打补丁之前必须先算一次旧文件的哈希和生成补丁时用的版本比对不一致就立刻回全量——千万不要先试着打一下不行再说因为打失败的中间产物可能是部分正确部分错误的文件这种文件最难排查。还原出来的新文件。打完补丁后必须对新文件算哈希和预期值比对。这一步是整个链路的安全网。磁盘空间。打补丁的过程需要同时存在旧文件、补丁文件和新文件峰值占用是三者之和。手机上这条特别容易翻车尤其是在旧文件就有几百兆的场景下。提前检查剩余空间不足就直接引导用户走全量升级或者清理。还有一点值得强调还原过程必须是原子的。先写到临时文件校验通过后再替换正式文件中途任何失败都删掉临时文件、保留旧文件。如果直接原地覆盖一旦断电或者进程被杀用户就两头不占了——旧文件被破坏、新文件没生成只能重装。6.3 高频翻车点对照表下面这些是我和团队在实际项目里真正遇到过的按出现频率排。现象真实原因处理方式补丁比全量包还大数据本身已压缩或改动引起大面积位移换成条目级差分或改用支持重定位的方案小文件正常大文件结果错乱偏移量变量用了 32 位类型全线换成 64 位类型并开启大文件支持服务端出补丁时被系统杀掉内存峰值超过容器限制串行出补丁、限制并发、或换更省内存的实现补丁打不上但旧文件哈希是对的新旧文件的行尾或编码在打包时被转换过生成和还原两端都用二进制模式读写禁止任何自动转换打补丁过程偶发失败重试就好磁盘空间不足或写入被中断提前检查空间改为临时文件 原子替换补丁生成时间从 5 分钟涨到 40 分钟新版本里塞了一个巨大的新增资源文件对超大新增文件单独走全量分发不参与差分用户升级后启动崩溃重装才好补丁打到了部分文件部分文件还是旧版本把一次升级当作一个事务全部成功才提交最后一行那个现象特别值得说。当更新涉及多个文件时有些人会做逐文件差分 逐文件替换如果一个文件成功了另一个失败了设备上就会出现新旧版本混合的状态。对于应用来说这是灾难性的——它既不是 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 左右的旧文件各自做一次小改动然后比较补丁大小数据构造改动方式补丁体积量级观察纯文本日志中间插入 200 行尾部追加 50 行百 KB 级补丁远小于改动量因为插入点前后的重复串完全对得上未压缩二进制修改常量 在函数体里加几行数 MB 级补丁比实际改动大很多因为后续代码段出现位移已压缩包zip替换其中一张小图接近新文件大小diff 流里几乎没有零字节压缩器帮不上忙第二行那个结果值得多想一会儿。很多人第一次看到我只改了 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 当成一个孤立的命令行工具而要把它当成一个模板。真正落到项目里你需要自己决定的东西比算法本身多得多用哪个压缩后端、什么时候生成补丁、保留多少个版本、客户端怎么做原子替换和校验、失败了怎么兜底。算法部分你可以信任这个二十年前就写好的设计它不会给你惊喜也不会给你意外剩下的那些取舍才是这个项目真正花时间的地方。另外一个小建议如果你准备在自己的项目里引入差分更新第一件事不是写代码而是先在真实数据上跑一次实验把补丁体积、生成耗时、峰值内存这三个数字量出来——这三个数字会直接决定你的方案能不能过评审也决定了你要不要去做那些围绕它的工程优化。
BSDiff 二进制差分与增量更新：补丁生成、还原及 OTA 工程实践
手上有个 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 包如果你能拆成一个个条目分别差分效果会比整包差分好上一大截。以我自己跑过的数据做粗略参考具体数字高度依赖数据本身只当量级看数据类型补丁 / 新文件体积原因纯文本、配置、SQL 导出1% ~ 5%改动局部化重复串极多未压缩二进制、固件裸镜像5% ~ 20%代码段相似但地址位移会拉高已压缩包、图片、视频60% ~ 100%修改导致字节流大面积重排加密数据、随机数表~100%完全没有可复用的参考价值看到最后两行你就明白了差分不是压缩算法的升级版它只是一个更聪明的字典压缩前提是字典和原文确实长得像。1.3 BSDiff 在整条更新链路里站在哪个位置很多人把 bsdiff 和更新系统混为一谈其实它只占整条链路里非常小的一块。一个完整的增量更新链路大致长这样版本管理服务端保留最近 N 个版本的安装包每个版本有唯一标识通常是文件哈希。补丁生成离线或准实时地把旧版本 → 新版本的差分跑出来结果落盘并缓存。补丁分发客户端上报自己当前的版本号服务端返回匹配的补丁地址如果没有匹配补丁就回落到全量。客户端合并下载补丁校验补丁完整性用本地旧文件还原新文件。结果校验与回滚对还原出来的新文件做哈希校验不一致就丢弃、回落全量绝对不能带着一个损坏的文件继续跑。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因为完全一样差值全是 0ctrl 记(10, 0, 0)red这一段在旧文件里没有对应extra 流里原样写redctrl 记(0, 3, 0)fox这一段diff 流再写 4 个0x00同时旧文件指针要跳回到fox的位置ctrl 记(4, 0, 6)——这个 6 就是往回跳 6 个字节。最后jumps找不到对应extra 流写jumpsctrl 记(0, 5, 0)。看到没有最终落盘的 diff 流几乎全是 0extra 流只有真正新增的那几个字节。这就是为什么补丁能比改动本身还小的原因——它存的不是数据是怎么从旧文件拼出新文件的操作说明。这里还有个容易被忽略的设计点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 里我最欣赏的一处细节——它体现的是作者把差分和压缩当成一个整体在优化而不是各干各的。补丁文件的整体头部也是同一套编码偏移长度内容08魔数BSDIFF4088ctrl 流压缩后的长度168diff 流压缩后的长度248新文件的原始大小32变长ctrl 流bzip2 压缩32 ctrl 长度变长diff 流bzip2 压缩末尾变长extra 流bzip2 压缩三个流各自独立压缩、独立解压互不依赖。这种布局带来了一个很实用的好处bspatch 可以边解压边写输出不需要把整个补丁全部解到内存里再处理。4. 补丁还原bspatch 为什么能在手机上毫秒级完成4.1 三元组驱动的两个指针逻辑简单到可以背下来bspatch 的还原逻辑比生成过程简单了不止一个量级。它只需要两个指针一个指向旧文件的当前位置一个指向新文件的写入位置。然后循环读 ctrl 三元组从 diff 流读 x 个字节从 extra 流读 y 个字节从旧文件读 x 个字节和 diff 的 x 个字节逐字节相加结果写进新文件把 extra 的 y 个字节原样追加到新文件末尾旧文件指针向前移动 zz 可以是负数表示往回跳。循环结束新文件就完整了。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 两个输出缓冲区合计约 nm。峰值出现在后缀排序阶段因为那时新旧文件和各种缓冲区都已经分配好了。所以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 分钟、内存峰值 8GB10 个补丁就是 100 分钟机时加 80GB 峰值内存。所以实际工程里几乎都会做裁剪只保留最近 N 个版本。这是最常见的做法。用户版本太老就让他先升到一个中间版本或者直接走全量。N 取多少取决于版本淘汰速度和服务器资源3 到 5 是比较舒服的区间。懒生成 缓存。不预先算好所有补丁等真的有用户请求某个版本对时再触发计算算完就缓存起来。缺点是第一个用户要等很久所以通常会配合热点版本预生成一起用。按渠道或设备分组合并。如果某个渠道的包只改了包名和签名其他内容完全一致可以先做一次去渠道归一化再差分把补丁矩阵的维度砍掉一层。有个容易忽略的成本补丁文件本身也是要占存储和带宽的。如果你的补丁平均 20MB、有 30 个版本对、每个补丁保留 3 个历史版本那就是 1.8GB 的存储还要考虑 CDN 回源。所以补丁也是需要做过期清理的不能只生成不回收。6.2 客户端校验、回滚和宁可全量的底线客户端这一侧我的经验是可以写一句口诀任何一步不确定就回全量。具体要校验的地方至少有四处补丁文件本身的完整性。下载过程中可能中断、可能被中间设备改写必须校验。原版 bsdiff 的补丁格式里只有 bzip2 每个流自带的校验没有覆盖整个文件的哈希所以工程上一般会额外带一个补丁的哈希值随下载接口一起下发。本地旧文件的身份。这是最容易被忽略的一处。用户设备上的旧文件可能因为上次升级中断而处于损坏状态也可能被其他程序修改过。打补丁之前必须先算一次旧文件的哈希和生成补丁时用的版本比对不一致就立刻回全量——千万不要先试着打一下不行再说因为打失败的中间产物可能是部分正确部分错误的文件这种文件最难排查。还原出来的新文件。打完补丁后必须对新文件算哈希和预期值比对。这一步是整个链路的安全网。磁盘空间。打补丁的过程需要同时存在旧文件、补丁文件和新文件峰值占用是三者之和。手机上这条特别容易翻车尤其是在旧文件就有几百兆的场景下。提前检查剩余空间不足就直接引导用户走全量升级或者清理。还有一点值得强调还原过程必须是原子的。先写到临时文件校验通过后再替换正式文件中途任何失败都删掉临时文件、保留旧文件。如果直接原地覆盖一旦断电或者进程被杀用户就两头不占了——旧文件被破坏、新文件没生成只能重装。6.3 高频翻车点对照表下面这些是我和团队在实际项目里真正遇到过的按出现频率排。现象真实原因处理方式补丁比全量包还大数据本身已压缩或改动引起大面积位移换成条目级差分或改用支持重定位的方案小文件正常大文件结果错乱偏移量变量用了 32 位类型全线换成 64 位类型并开启大文件支持服务端出补丁时被系统杀掉内存峰值超过容器限制串行出补丁、限制并发、或换更省内存的实现补丁打不上但旧文件哈希是对的新旧文件的行尾或编码在打包时被转换过生成和还原两端都用二进制模式读写禁止任何自动转换打补丁过程偶发失败重试就好磁盘空间不足或写入被中断提前检查空间改为临时文件 原子替换补丁生成时间从 5 分钟涨到 40 分钟新版本里塞了一个巨大的新增资源文件对超大新增文件单独走全量分发不参与差分用户升级后启动崩溃重装才好补丁打到了部分文件部分文件还是旧版本把一次升级当作一个事务全部成功才提交最后一行那个现象特别值得说。当更新涉及多个文件时有些人会做逐文件差分 逐文件替换如果一个文件成功了另一个失败了设备上就会出现新旧版本混合的状态。对于应用来说这是灾难性的——它既不是 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 左右的旧文件各自做一次小改动然后比较补丁大小数据构造改动方式补丁体积量级观察纯文本日志中间插入 200 行尾部追加 50 行百 KB 级补丁远小于改动量因为插入点前后的重复串完全对得上未压缩二进制修改常量 在函数体里加几行数 MB 级补丁比实际改动大很多因为后续代码段出现位移已压缩包zip替换其中一张小图接近新文件大小diff 流里几乎没有零字节压缩器帮不上忙第二行那个结果值得多想一会儿。很多人第一次看到我只改了 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 当成一个孤立的命令行工具而要把它当成一个模板。真正落到项目里你需要自己决定的东西比算法本身多得多用哪个压缩后端、什么时候生成补丁、保留多少个版本、客户端怎么做原子替换和校验、失败了怎么兜底。算法部分你可以信任这个二十年前就写好的设计它不会给你惊喜也不会给你意外剩下的那些取舍才是这个项目真正花时间的地方。另外一个小建议如果你准备在自己的项目里引入差分更新第一件事不是写代码而是先在真实数据上跑一次实验把补丁体积、生成耗时、峰值内存这三个数字量出来——这三个数字会直接决定你的方案能不能过评审也决定了你要不要去做那些围绕它的工程优化。
