原文地址：https://xuzx.github.io/2020/05/23/Android-Upgrade/
什么是增量更新
由于 APP 随着业务需求的不断迭代更新，功能越来越多（复杂），APK 包的体积也会越来越大，导致每次客户端升级更新操作需要占用更多的带宽流量、下载等待时间等等，因此需寻求一些更优的更新方案。
通俗讲增量更新是将一个新版本 APK 包与旧版本 APK 包进行二进制差分对比，产生一个比原本更小的增量包，再给到客户端进行下载更新，增量更新与完全更新相对，流程如图1所示。
增量更新的好处是能减少流量成本的消耗，降低客户端升级时间。
增量更新方案对比
网上有许多增量更新方案，诸如 BSDiff、Xdelta、Courgette 等。由于 Courgette 并不适用于 Android APK 更新，所以这里不对它进行对比测试。下表1是针对前两者方案进行对比。
| 对比项 | BSDiff | Xdelta3 |
|---|---|---|
| 开源公司/作者 | Colin Percival | Joshua MacDonald |
| 开源许可证 | BSD | Apache 2.0（3.x版本） |
| 当前最新版本 | 4.3（目前调研使用版本） | 3.1.0（目前调研使用版本） |
| 开源项目地址 | 项目地址 | 项目地址 |
| 编码格式 | - | VCDIFF（RFC 3284） |
| diff 动态库大小(.dll) | 300KB左右 | 300KB左右 |
| patch 动态库大小(.so) | 250KB左右 | 350KB左右 |
| 支持文件大小 | 最大2 ^ 61-1B | - |
| 差分包压缩算法 | bzip2 | Huffman、LZMA |
| 压缩等级调整 | × | √ |
| 补丁包二次压缩 | × | √ |
| 窗口大小调整 | × | √ |
| 学习成本评估 | 较高 | 高 |
| 集成难易度 | 中 | 中 |
| 文档资料 | 一般 | 少 |
| 使用热度 | 较多（微信、QQ、抖音） | 少见 |
表1 框架对比（注：[ - ]：未知；[ √ ]：表示支持；[ × ]：表示不支持）
测试对比
环境配置
- 差分生成环境：Windows 10(64位)、CPU i5-6500(3.2GHz)、RAM 16GB
- 差分合成环境：SamSung SM-P583、Android 7.0、RAM 3GB
- 差分工具：MinGW 32位编译器生成的 BSDiff(4.3)和 Xdelta(3.1.0)
注：差分生成阶段通常在服务端进行操作，而差分合成阶段通常在手机端进行操作。
第1组测试(15M 左右 APK)
这里选取 Flipboard 红板报作为测试对象，版本分别为4.3.12 (14.5MB)、4.3.13 (14.6MB)，测试对比数据如下所示。
[图片上传失败...(image-43d8b5-1590852815848)]
| BSDiff | Xdelta3 | |
|---|---|---|
| 差分生成耗时 | 19235ms | 1867ms |
| 差分生成 CPU 占用率 | 29% | 10% |
| 差分生成内存占用率 | 88～132MB | 203～209MB |
| 差分补丁大小 | 5.64MB | 5.7MB |
| 差分合成耗时 | 3941ms | 271ms |
| 差分合成 CPU 占有率 | 12% | 1%~8.8% |
| 差分合成内存占用率 | 32.8MB | 28.4MB |
表2 15M 左右 APK 实验数据结果
第2组测试(100M 左右 APK)
这里选取微信作为测试对象，版本分别为6.7.3 (75.5MB)、7.0.3 (104MB)，测试对比数据如下所示。
| BSDiff | Xdelta3 | |
|---|---|---|
| 差分生成耗时 | 375472ms | 36517ms |
| 差分生成 CPU 占用率 | 29% | 29% |
| 差分生成内存占用率 | 480～681MB | 201～212MB |
| 差分补丁大小 | 76.5MB | 76.4MB |
| 差分合成耗时 | 48539ms | 2915ms |
| 差分合成 CPU 占有率 | 12% | 1%~12% |
| 差分合成内存占用率 | 81.3~186.4MB | 94.3MB |
表3 100M 左右 APK 实验数据结果
第3组测试(500M 左右 APK)
这里选取游戏包乱世王者作为测试对象，版本分别为1.6.8.25 (532MB)、1.6.12.26 (560MB)，测试对比数据如下所示。
| BSDiff | Xdelta3 | |
|---|---|---|
| 差分生成耗时 | × | 68538ms |
| 差分生成 CPU 占用率 | × | 30% |
| 差分生成内存占用率 | × | 203～212MB |
| 差分补丁大小 | × | 144MB |
| 差分合成耗时 | × | 14443ms |
| 差分合成 CPU 占有率 | × | 1%~12% |
| 差分合成内存占用率 | × | 82.7~87.5MB |
表4 500M 左右 APK 实验数据结果
第4组测试(1.8GB 左右 APK)
这里选取游戏包绝地求生作为测试对象，版本分别为0.13.5(1.79GB)、0.14.5 (1.86GB)，测试对比数据如下所示。
| BSDiff | Xdelta3 | |
|---|---|---|
| 差分生成耗时 | × | 514286ms |
| 差分生成 CPU 占用率 | × | 31% |
| 差分生成内存占用率 | × | 203～212MB |
| 差分补丁大小 | × | 0.99GB |
| 差分合成耗时 | × | 117527ms |
| 差分合成 CPU 占有率 | × | 1%~12% |
| 差分合成内存占用率 | × | 83.7~94.9 MB |
表5 1.8G 左右 APK 实验数据结果
注：数据来源于5次实验数据平均值
结论
由前面几组测试实验结合相关源码，可以得出如下结论：
1）从差分耗时方面，Xdelta3 在差分生成和差分合成都优于 BSDiff，两者的差距约10倍左右。两者的差分合成都优于差分生成；
2）从内存消耗方面，随着 APK 包的大小增大，BSDiff 的内存也会翻倍增大占用，而 Xdelta3 却是稳定一定范围；
3）当 APK 包达到一定大小时，BSDiff(编译器为32位)会出现差分失败，从 C 的源代码可以分析出，差分时进行大量动态申请内存空间导致，也是占用内存大的主要原因，而 Xdelta 依旧可以差分；
4）另外，BSDiff 需将新旧文件一次性读进内存形成字符串字典，进行排序(qsufsort)、搜索(search)对比等等，产生相关 diffstring 和 extra string 块，最后进行 bzip2 压缩生成增量包（patch），同时也发现排序、搜索等差异对比操作与 bzip2 压缩生成操作各占一半时间；而 Xdelta3 应用相关窗口算法对新旧文件分块读进内存，进行差异对比生成增量包；
5）需要注意的是，两个加固包产生的增量包不能与无加固包进行合成;
6）Xdelta 3.1.1 版本相对 3.1.0 版本在耗时、内存等方面有稍微的优化；
7）另外，发现不同的编译器编译生成的 Xdelta 可执行文件对差分耗时有相关影响，例如 Mingw-w64 编译器和 CL 编译器生成执行文件，在进行差分生成操作耗时会相差一半左右（前者更优）。
提示：本文为博主原创文章，如发现文中有误，欢迎批评指正，谢谢您支持！
