差分升级算法：bsdiff、hdiffpatch的原理与实车选型
各位做OTA的同行，今天我们来聊一个很实在的话题——差分升级。说白了，就是怎么让升级包变小。我见过太多项目，一开始觉得2GB的升级包无所谓，结果到了实车部署阶段，流量费、下载时间、失败率全成了噩梦。
嗯，这里要注意：差分算法不是万能的，但选对了，能把2GB压到200MB。怎么做到的？我们一步步拆开看。
差分升级的核心逻辑
差分升级，本质上就是只传输新旧版本之间的差异部分。你想想看，一个车载系统，这次升级可能只改了20%的代码，剩下的80%完全没动。如果每次都全量推送，那80%的流量就白白浪费了。
差分算法的任务就是：找出新旧两个二进制文件之间的最小差异，生成一个补丁包。车端收到补丁后，再和本地旧版本合并，还原出新版本。
核心公式：
补丁大小 ≈ 新版本中发生变化的字节数 + 算法元数据开销
理想情况下：补丁大小 / 全量包大小 → 5%~15%
我在项目中遇到过最夸张的一次，一个1.8GB的导航地图包，差分后只有120MB。客户当场就愣住了，说你们是不是把功能砍了？我说没有，只是把没变的部分全跳过了。
主流差分算法：bsdiff vs hdiffpatch
目前车载领域用得最多的就是bsdiff和hdiffpatch。两者思路不同，适用场景也不同。我直接上对比表，这样更清楚。
| 对比维度 | bsdiff | hdiffpatch |
|---|---|---|
| 算法原理 | 基于后缀排序（suffix sorting） | 基于哈希匹配（hash-based） |
| 压缩率 | 极高，尤其对二进制代码 | 较高，对结构化数据友好 |
| 内存消耗 | 极高（旧版本+新版本全量加载） | 较低（分块处理） |
| 生成速度 | 慢（O(n²)级别） | 快（O(n)级别） |
| 合并速度 | 快 | 快 |
| 适用场景 | 固件、内核、系统镜像 | 地图数据、媒体资源、配置文件 |
bsdiff：压缩率之王，但吃内存
bsdiff是我个人习惯用在固件升级上的首选。它的核心思路是：先对旧版本做后缀排序，然后在新版本中查找最长匹配子串。匹配到的部分用指针引用，没匹配到的部分作为新增数据写入补丁。
为什么压缩率这么高？因为它能发现非常细微的重复模式。比如两个函数，只是参数类型变了，其他逻辑完全一样，bsdiff能精准地只记录那几字节的差异。
避坑指南：
我曾经在一个项目里直接用bsdiff处理2GB的导航地图包，结果生成补丁时内存直接爆了。bsdiff需要同时加载旧版本和新版本到内存，2GB+2GB=4GB，车机芯片根本扛不住。
后来我学乖了：超过500MB的文件，不要直接用bsdiff。要么分块，要么换算法。
hdiffpatch：轻量级选手，适合大文件
hdiffpatch是后来才进入车载领域的。它的设计思路更务实：把文件分成固定大小的块，对每个块独立做哈希匹配。匹配上的块直接引用，没匹配上的块作为新增数据。
这样做的好处很明显：
- 内存可控：一次只处理一个块，不会爆内存
- 支持流式处理：边读边算，不用等全量加载
- 生成速度快：哈希查找比后缀排序快得多
但代价是压缩率不如bsdiff。我实测过，同样一个固件包，bsdiff能压到8%，hdiffpatch大概在12%~15%。不过对于地图、媒体这类大文件，这点差距可以接受。
实车选型决策树
说了这么多，到底怎么选？我画了一张决策图，你们一看就明白。
如何把2GB压缩到200MB？实战步骤
好，现在我们来解决最核心的问题。假设你有一个2GB的导航地图包，怎么压到200MB？我直接给步骤。
- 分析文件结构：先搞清楚这个2GB包里，哪些是经常变的，哪些是基本不变的。地图包通常分为索引文件（经常变）和瓦片数据（很少变）。
- 分块处理：把2GB文件按逻辑模块拆成若干块，每块不超过200MB。我习惯按城市或区域划分。
- 选择算法：对索引文件用bsdiff（因为数据量小，追求极致压缩），对瓦片数据用hdiffpatch（因为数据量大，内存优先）。
- 生成差分补丁：分别对每个块生成差分补丁，然后合并成一个补丁包。
- 二次压缩：对合并后的补丁包做gzip或zstd压缩。这一步通常能再压30%~50%。
实战数据：
我做过一个项目，2.1GB的导航地图包，按城市拆成30个块。索引块用bsdiff，瓦片块用hdiffpatch。最终差分补丁大小：186MB。加上gzip压缩后：142MB。
从2.1GB到142MB，压缩率6.7%。客户说这是他们见过最小的升级包。
避坑指南：我踩过的三个坑
做差分升级这么多年，有些坑是绕不过去的。我直接说出来，你们以后遇到能少走弯路。
坑一：版本跨度太大
我曾经尝试从V1.0直接差分到V3.0，结果补丁包比全量包还大。为什么？因为中间版本变化太多，差分算法找不到足够的匹配。后来我改成逐版本升级：V1.0→V2.0→V3.0，每个差分包都控制在合理范围内。
坑二：文件对齐问题
bsdiff对字节对齐非常敏感。有一次我升级了一个固件，新旧版本只是编译时间戳不同，其他完全一样。按理说差分包应该很小，结果生成了50MB。排查后发现是编译器的填充字节变了位置。后来我强制在编译时固定对齐策略，差分包立刻降到了2MB。
坑三：车端内存不足
这个坑最致命。bsdiff合并时需要同时加载旧版本和补丁包到内存。如果车机只有512MB内存，你生成一个300MB的补丁包，合并时直接OOM。解决方案：要么限制补丁包大小不超过车机可用内存的一半，要么改用hdiffpatch的流式合并模式。
总结：选型不是非黑即白
说了这么多，其实就一句话：没有最好的算法，只有最合适的场景。bsdiff和hdiffpatch不是对手，而是搭档。我现在的做法是：
- 固件、内核、系统镜像 → bsdiff
- 地图、媒体、配置文件 → hdiffpatch
- 超大文件 → 分块 + 混合算法
这样搭配下来，2GB压到200MB不是梦。你们回去可以试试，有问题随时交流。