4、差分升级算法：bsdiff、hdiffpatch原理、差分算法选型、压缩率与性能权衡、我在项目中的踩坑记录
差分升级，说白了就是只传「变化的部分」。
你想想看，一个系统镜像动辄几百兆，每次升级都全量下载，用户流量受不了，服务器带宽也扛不住。差分算法就是来解决这个问题的——它对比新旧两个文件，生成一个很小的补丁包，车端拿到补丁后，自己「拼」出完整的新版本。
我在项目里最早用的是bsdiff，后来发现某些场景下它并不合适。嗯，这里面的门道不少，我一个个讲清楚。
4.1 bsdiff 原理：经典但「重」
bsdiff 是 Colin Percival 在 2003 年提出的算法。它的核心思路是：先找相似块，再补差异。
具体流程是这样的：
- 后缀排序：对新旧文件做后缀数组（Suffix Array）排序，找到旧文件中与新文件匹配的最长子串。
- 生成 diff 串：把匹配到的部分标记为「copy」，没匹配到的部分标记为「insert」。
- 压缩输出：用 bzip2 对 diff 串做二次压缩，进一步减小体积。
bsdiff 的优点是压缩率极高。我做过测试，两个版本之间如果改动不大（比如只改了 5% 的代码），补丁包大小通常只有全量包的 5%~10%。
但它的缺点也很明显：
- 内存消耗巨大：bsdiff 需要把新旧文件都加载到内存里做后缀排序。一个 500MB 的镜像，内存占用轻松超过 2GB。车机端的 MCU 或低配 SoC 根本扛不住。
- 生成速度慢：后缀排序的时间复杂度是 O(n log n)，文件越大越慢。我曾在服务器上跑一个 1GB 的镜像差分，等了快 20 分钟。
- 补丁应用也吃内存：车端打补丁时，需要同时持有旧文件、补丁文件和新文件（或临时空间），对存储和内存都是考验。
适用场景：服务器端生成补丁，且目标设备内存充裕（比如 2GB 以上 RAM 的座舱域控制器）。
4.2 hdiffpatch 原理：轻量级选手
hdiffpatch 是 bsdiff 的改良版，由 Google 的工程师开发。它主要做了两件事来降低资源消耗：
- 用哈希代替后缀数组：hdiffpatch 使用滚动哈希（类似 Rabin-Karp 算法）来快速定位匹配块，不再需要全量排序。内存占用从 O(n) 降到了 O(1) 级别。
- 分块处理：把大文件切成固定大小的块（默认 64KB），逐块做差分。这样即使文件很大，内存压力也始终可控。
我个人的习惯是：在车端资源受限的场景下，优先考虑 hdiffpatch。它虽然压缩率比 bsdiff 略差（大概差 5%~10%），但内存占用只有 bsdiff 的十分之一甚至更低。
举个例子：
# 生成补丁
hdiffpatch -generate old.bin new.bin patch.bin
# 应用补丁
hdiffpatch -apply old.bin patch.bin new.bin你看，命令很简单。但要注意，hdiffpatch 对文件对齐有要求。如果新旧文件的结构差异太大（比如分区表变了），它的匹配率会急剧下降，补丁包可能比全量包还大。
踩坑记录：我曾经在升级 bootloader 时用了 hdiffpatch，结果因为 bootloader 版本之间地址映射完全不同，生成的补丁包比全量包还大了 30%。后来我加了一个预检查逻辑：如果差分后的补丁包超过全量包的 80%，就自动回退到全量升级。
4.3 差分算法选型：怎么选？
选型不是拍脑袋的事。我总结了一个简单的决策矩阵：
| 场景 | 推荐算法 | 理由 |
|---|---|---|
| 座舱域（高配 SoC，2GB+ RAM） | bsdiff | 压缩率优先，带宽成本更低 |
| 智驾域（中配 SoC，1GB RAM） | hdiffpatch | 内存可控，性能均衡 |
| MCU / 低配控制器（512MB 以下） | hdiffpatch 或自定义分块差分 | 内存是硬约束，压缩率可以妥协 |
| OTA 服务器端生成补丁 | bsdiff | 服务器资源充足，追求最小补丁 |
另外，还有一个容易被忽略的点：差分算法的稳定性。bsdiff 和 hdiffpatch 都是开源项目，但维护频率不同。bsdiff 的原始代码已经很久没更新了，而 hdiffpatch 在 Google 的 repo 里还在持续维护。我建议选型时优先考虑社区活跃度高的项目，否则遇到 bug 都没人修。
4.4 压缩率与性能权衡
这里有一个经典的「不可能三角」：压缩率、生成速度、应用速度，三者很难同时做到最优。
- 追求极致压缩率：用 bsdiff + bzip2，生成慢，应用也慢。
- 追求快速生成：用 hdiffpatch + zlib，压缩率下降，但生成速度提升 10 倍以上。
- 追求快速应用：用 hdiffpatch 的快速模式（-fast），牺牲一点压缩率，换取车端更快的打补丁速度。
我在项目中做过一个对比测试：
| 算法组合 | 补丁大小（MB） | 生成时间（秒） | 应用时间（秒） |
|---|---|---|---|
| bsdiff + bzip2 | 12.3 | 187 | 8.2 |
| hdiffpatch + zlib | 14.1 | 22 | 3.5 |
| hdiffpatch + 快速模式 | 16.8 | 15 | 1.8 |
你看，bsdiff 的补丁最小，但生成时间接近 3 分钟。而 hdiffpatch 快速模式虽然补丁大了 36%，但生成时间只有 15 秒，应用时间不到 2 秒。对于量产车来说，用户更在意的是「升级要快」，而不是「补丁要小」。所以我的建议是：在车端，优先优化应用速度；在服务器端，可以适当牺牲生成速度来换取压缩率。
4.5 我在项目中的踩坑记录
做差分升级，坑真的不少。我挑几个印象深刻的说说。
坑一：文件对齐问题
我曾经在升级一个 64MB 的固件时，发现差分补丁包异常大。排查了半天，发现是编译工具链的版本变了，导致新固件里每个函数的地址都偏移了 4 字节。差分算法找不到匹配块，几乎把整个文件当成了「差异」。后来我加了一个「对齐检查」步骤：在生成补丁前，先对比新旧文件的符号表，如果偏移量超过阈值，就自动切换到全量升级。
坑二：内存不足导致升级失败
有一次在低配 MCU 上测试 bsdiff 补丁，车端打补丁时直接 OOM（内存溢出）了。原因是 bsdiff 的应用端也需要大量内存来解压和重组文件。从那以后，我定了一个规则：车端可用内存必须大于旧文件大小的 1.5 倍，才能使用差分升级。否则就回退到全量。
坑三：差分补丁的校验
差分补丁本身是二进制文件，传输过程中如果损坏一个字节，打出来的新文件就完全不可用。我早期项目里没有对补丁做完整性校验，结果有次升级后系统直接变砖。后来我强制要求：补丁包必须带 SHA256 校验，车端应用前先校验，校验不通过就放弃升级。
坑四：版本兼容性
差分算法对版本跳级支持不好。比如从 v1.0 直接升到 v1.2，如果中间有 v1.1 的改动，差分补丁会非常大。我建议的做法是：只支持相邻版本差分，跨版本升级走全量。或者维护一个「差分链」：v1.0→v1.1 的补丁 + v1.1→v1.2 的补丁，车端依次应用。
嗯，差分升级看起来简单，但真正落地时，细节决定成败。选对算法、做好校验、控制好内存，才能让 OTA 升级又快又稳。