2、差分算法基础：bsdiff、hdiffpatch、xdelta3 原理
聊差分算法之前，我先问个问题：你给用户发一个 200MB 的 APK，每次版本更新都让用户重新下载全量包，这体验能好吗？
肯定不行。所以我们需要差分算法——只计算新旧版本之间的“差异”，然后把这个差异打包成差分包。客户端拿到差分包，再和本地旧版本合并，就能还原出新版本。
目前业界主流的差分算法有三个：bsdiff、hdiffpatch、xdelta3。它们各有各的脾气。我一个个说。
2.1 bsdiff 算法原理
bsdiff 是 Colin Percival 在 2003 年提出的。它的核心思路是：先找相似块，再补差异数据。
具体怎么做？
- 后缀排序：对旧文件的所有后缀进行排序，构建一个后缀数组。这一步是为了快速找到新旧文件中相同的子串。
- 匹配扫描：用新文件去旧文件的后缀数组里做匹配，找到最长的相同子串。匹配上的部分，记录它在旧文件中的位置和长度。
- 生成 diff 串：匹配上的部分，用旧文件的数据直接复制；没匹配上的部分，就是新文件独有的新增数据。
- 生成 extra 串：对于匹配位置有偏差的情况，bsdiff 会额外记录一个“控制块”，告诉合并器：这里要复制旧文件的哪一段，然后跳过多少字节，再插入多少新数据。
bsdiff 的压缩率很高，尤其对二进制文件（比如 .so 库、DEX 文件）效果很好。但它的缺点也很明显——内存占用大。旧文件越大，后缀数组就越大。我记得有一次处理一个 500MB 的固件，bsdiff 直接吃掉了 2GB 内存，差点把构建机搞崩。
适用场景：APK 差分、固件差分、对压缩率要求高的场景。
避坑：内存敏感的环境慎用。我曾经在 32 位系统上跑 bsdiff，文件超过 2GB 直接报错——因为后缀数组索引用了 32 位整数。
2.2 hdiffpatch 算法原理
hdiffpatch 是腾讯在 bsdiff 基础上改进的算法。说白了，它解决了 bsdiff 的两个痛点：内存占用高和不支持大文件。
hdiffpatch 的核心改进点：
- 分块处理：把旧文件切成固定大小的块（默认 64KB），每块独立做后缀排序。这样内存占用就降下来了。
- 哈希索引：用哈希表代替全量后缀数组，匹配速度更快，内存更省。
- 支持 64 位文件偏移：文件大小不再受 2GB 限制。
我实际测试过，同样一个 200MB 的 APK，bsdiff 需要 1.2GB 内存，hdiffpatch 只需要 300MB 左右。差距很明显。
但 hdiffpatch 也有代价——压缩率略低于 bsdiff。因为分块之后，跨块的匹配会被打断，导致一些重复数据没被利用上。不过对于大多数场景，这个差距在 1%~3% 以内，完全可以接受。
个人建议：如果你的构建环境内存有限（比如 CI 机器只有 2GB），优先选 hdiffpatch。我在腾讯云的时候，内部 OTA 差分用的就是 hdiffpatch，稳定跑了两年没出过问题。
2.3 xdelta3 算法原理
xdelta3 走的是另一条路——它基于 VCDIFF 标准（RFC 3284）。核心思想是：滑动窗口 + 哈希匹配。
流程是这样的：
- 把旧文件作为“字典”，加载到内存中。
- 用滑动窗口扫描新文件，窗口大小默认 64KB。
- 对窗口内的数据计算哈希值，去字典里找匹配。
- 匹配上的部分，记录偏移和长度；没匹配上的，直接输出原始字节。
- 最终输出一个 VCDIFF 格式的差分文件。
xdelta3 最大的优势是流式处理。它不需要一次性加载整个旧文件，可以边读边处理。这意味着你可以用它处理超大文件——比如几十 GB 的虚拟机镜像。
但 xdelta3 的压缩率一般不如 bsdiff。因为它用的是固定窗口，窗口外的匹配就找不到了。不过它的速度很快，CPU 占用也低。
| 算法 | 压缩率 | 内存占用 | 处理速度 | 最大文件 | 典型场景 |
|---|---|---|---|---|---|
| bsdiff | 高 | 高（约 5x 旧文件） | 慢 | 2GB（32 位限制） | APK、固件差分 |
| hdiffpatch | 中高 | 中（约 1.5x 旧文件） | 中 | 无限制（64 位） | OTA 更新、大文件差分 |
| xdelta3 | 中 | 低（固定窗口） | 快 | 无限制（流式） | 虚拟机镜像、数据库备份 |
注意：xdelta3 的差分包格式是 VCDIFF，不是所有客户端都原生支持。如果你要做 Android 端的差分更新，需要自己集成 xdelta3 的 C 库或者用 Java 封装。bsdiff 和 hdiffpatch 在 Android 端有现成的 Java/Kotlin 实现，集成起来更方便。
2.4 三种算法的选择建议
你可能会问：那我到底该用哪个？
我的经验是这样的：
- 做 APK 差分更新：首选 hdiffpatch。压缩率接近 bsdiff，内存可控，社区活跃。
- 做固件/系统 OTA：如果构建机内存够大，用 bsdiff 拿最高压缩率；如果内存紧张，换 hdiffpatch。
- 做超大文件差分（比如数据库、镜像）：xdelta3 是唯一选择。流式处理，不爆内存。
- 跨平台需求：xdelta3 有 C 库，几乎能编译到任何平台；bsdiff 和 hdiffpatch 在 Windows 上编译稍微麻烦点。
嗯，这里还要提一句：不要迷信压缩率。差分包小 1MB，但构建时间多了 10 分钟，用户端合并时 CPU 飙到 100%，这划算吗？我见过不少团队为了省那几百 KB 的流量，把构建流水线拖慢了一倍。你想想看，值不值？
最后说一句：没有银弹。我见过有人用 bsdiff 处理 10GB 的数据库文件，结果内存爆了；也见过有人用 xdelta3 差分 APK，结果差分包比全量包还大。选算法之前，先搞清楚你的文件类型、大小、构建环境和用户端能力。拿不准的话，三种算法各跑一次，对比一下差分包大小和构建时间，数据会告诉你答案。