NDK实现增量更新

一、增量更新的业务价值

传统 APK 更新需要用户下载完整的安装包（少则几十 MB，大则数百 MB），这对用户的流量和时间是巨大的浪费。增量更新（也叫差量更新、省流量更新）的核心思路是：用户只需下载新旧版本之间的差异数据（差分包），在本地与旧版本合成出新版本。

实际收益：以一个 100MB 的 APK 为例，如果两次版本间只有 5MB 的代码和数据发生变化，差分包可能仅 6-8MB（含差分算法开销），节省 90% 以上的下载流量。

商业案例：

• 腾讯应用宝：日均节省带宽数十 TB。
• 各大手游：版本更新时优先推送增量包，减少用户等待时间。
• Google Play：内置了 File-by-File patching（基于 bsdiff 算法），称为 Smart Updates（2012 年引入，2016 年升级）。

二、BSDiff 算法原理

BSDiff 是由 Colin Percival 于 2003 年发表的二进制差分算法，最初用于 FreeBSD 的系统更新。论文题目：*”Naive Differences of Executable Code”*。

2.1 BSDiff 的核心思想

BSDiff 不是简单的逐字节差异比较（像 Unix diff 那样），而是利用后缀排序（suffix sorting）找到旧文件中与新文件相似的区域，然后编码差异。

BSDdiff 算法的三个步骤：

步骤一：后缀排序

对旧文件的所有后缀进行排序（使用 qsufsort，基于 Larsson-Sadakane 算法的后缀数组构造），时间复杂度 O(n log n)。后缀数组使得可以快速在旧文件中找到与新文件中某段字节最匹配的位置。

旧文件后缀示例：
"abcdef" → 后缀: "abcdef", "bcdef", "cdef", "def", "ef", "f"
排序后:  "abcdef"(0), "bcdef"(1), "cdef"(2), "def"(3), "ef"(4), "f"(5)

步骤二：匹配

使用后缀数组，在新文件中遍历，找到在旧文件中最长的匹配段。匹配段长度至少为 8 字节（参数可调）。不匹配的部分记录为差异（diff）或额外数据（extra）。

旧文件: [A][B][C][D][E][F][G][H]
新文件: [A][B][X][X][D][E][Y][H]

匹配结果:
- "AB" → 匹配（从旧文件偏移 0，长度 2）
- "XX" → 不匹配 → 记录为 diff（新-旧字节值）或 extra（新增数据）
- "DE" → 匹配（从旧文件偏移 3，长度 2）
- "Y"  → 不匹配 → extra
- "H"  → 匹配（从旧文件偏移 7，长度 1）

步骤三：生成 diff + extra + control

三部分数据：

• diff string（差异数据）：new_byte - old_byte，逐字节编码差异。使用 bzip2 压缩。
• extra string（额外数据）：新文件中在旧文件中找不到匹配的部分。使用 bzip2 压缩。
• control triples（控制三元组）：三个 int64 值：(diff_pos, extra_pos, copy_len)，控制合成的过程。

control 三元组编码了合成指令：

对于每个三元组 (x, y, z):
  1. 从 diff string 位置读取 x 字节 → 与 old 文件中对应字节相加 → 写入 new 文件
  2. 从 extra string 位置读取 y 字节 → 直接写入 new 文件
  3. 从 old 文件中复制 z 字节 → 写入 new 文件（匹配段）

2.2 BSPatch 合成算法

// bspatch.c 核心逻辑（简化）
int bspatch(const uint8_t *old, int64_t oldsize,
            uint8_t **new, int64_t *newsize,
            const uint8_t *patch) {
    // 读取 patch 头
    // Header: "BSDIFF40" + control_len + diff_len + newsize
    if (memcmp(patch, "BSDIFF40", 8) != 0) {
        return -1;  // 不是 BSDiff 格式
    }

    int64_t ctrllen, difflen, extrasize;
    // ... 解析 header ...

    // 解压 patch 的三部分
    uint8_t *ctrl = bzip2_decompress(patch + header_size, ctrllen);
    uint8_t *diff = bzip2_decompress(patch + header_size + ctrllen_compr, difflen);
    uint8_t *extra = bzip2_decompress(patch + header_size + ctrllen_compr + difflen_compr, extrasize);

    // 分配新文件内存
    *new = malloc(*newsize);
    if (*new == NULL) return -1;

    // 合成循环
    int64_t oldpos = 0, newpos = 0;
    int64_t ctrlpos = 0, diffpos = 0, extrapos = 0;

    while (newpos < *newsize) {
        // 读取 control 三元组
        int64_t diff_len, extra_len, copy_len;
        // diff_len  = ctrl[ctrlpos..ctrlpos+7] (解压后的 int64)
        // extra_len = ctrl[ctrlpos+8..ctrlpos+15]
        // copy_len  = ctrl[ctrlpos+16..ctrlpos+23]
        ctrlpos += 24;

        // 1. 应用差异（diff string）
        for (int i = 0; i < diff_len; i++) {
            int64_t new_byte = old[oldpos + i] + diff[diffpos + i];
            (*new)[newpos + i] = (uint8_t)(new_byte & 0xFF);  // 加法可能溢出
        }
        newpos += diff_len;
        oldpos += diff_len;
        diffpos += diff_len;

        // 2. 复制额外数据（extra string）
        memcpy(&(*new)[newpos], &extra[extrapos], extra_len);
        newpos += extra_len;
        extrapos += extra_len;

        // 3. 从旧文件复制匹配段
        memcpy(&(*new)[newpos], &old[oldpos], copy_len);
        newpos += copy_len;
        oldpos += copy_len;
    }

    free(ctrl); free(diff); free(extra);
    return 0;
}

BSDiff 的实际 C 代码在 AOSP 源码中的 external/bsdiff/ 目录（后移到了 bootable/recovery/applypatch/）。

三、Android NDK 实现增量更新的架构

3.1 服务端：差分生成

# 服务端（Python 示例，或使用 C/Go 实现）
import bsdiff4   # Python binding for bsdiff

def generate_patch(old_apk: bytes, new_apk: bytes) -> bytes:
    return bsdiff4.diff(old_apk, new_apk)

# 服务端存储逻辑
# 1. 保留最近 N 个版本的全量 APK
# 2. 对每个旧版本 → 新版本，预计算差分包
# 3. 客户端携带来版本号 → 返回对应的差分包

3.2 客户端：补丁合成（NDK C 代码）

// jni_bspatch.c —— 通过 JNI 暴露给 Java/Kotlin 层

#include <jni.h>
#include <string.h>
#include <bzlib.h>  // bzip2 解压

// BSPatch 合成函数（集成到 NDK 模块中）
JNIEXPORT jint JNICALL Java_com_example_patch_PatchManager_nativeApplyPatch(
        JNIEnv *env, jclass clazz,
        jstring oldFilePath,
        jstring patchFilePath,
        jstring newFilePath) {

    const char *oldFile = (*env)->GetStringUTFChars(env, oldFilePath, NULL);
    const char *patchFile = (*env)->GetStringUTFChars(env, patchFilePath, NULL);
    const char *newFile = (*env)->GetStringUTFChars(env, newFilePath, NULL);

    // 1. 读取旧文件到内存
    FILE *fp_o = fopen(oldFile, "rb");
    fseek(fp_o, 0, SEEK_END);
    off_t old_size = ftello(fp_o);
    fseek(fp_o, 0, SEEK_SET);
    uint8_t *old_data = malloc(old_size);
    fread(old_data, 1, old_size, fp_o);
    fclose(fp_o);

    // 2. 读取差分包到内存
    FILE *fp_p = fopen(patchFile, "rb");
    fseek(fp_p, 0, SEEK_END);
    off_t patch_size = ftello(fp_p);
    fseek(fp_p, 0, SEEK_SET);
    uint8_t *patch_data = malloc(patch_size);
    fread(patch_data, 1, patch_size, fp_p);
    fclose(fp_p);

    // 3. 执行 BSPatch 合成
    uint8_t *new_data = NULL;
    off_t new_size = 0;
    int result = apply_bsdiff(old_data, old_size, &new_data, &new_size,
                               patch_data, patch_size);

    if (result != 0) {
        free(old_data);
        free(patch_data);
        // 抛 Java 异常
        jclass ex = (*env)->FindClass(env, "java/io/IOException");
        (*env)->ThrowNew(env, ex, "BSPatch failed");
        return -1;
    }

    // 4. 写入新文件
    FILE *fp_n = fopen(newFile, "wb");
    fwrite(new_data, 1, new_size, fp_n);
    fclose(fp_n);

    // 5. 释放内存
    free(old_data);
    free(patch_data);
    free(new_data);

    (*env)->ReleaseStringUTFChars(env, oldFilePath, oldFile);
    (*env)->ReleaseStringUTFChars(env, patchFilePath, patchFile);
    (*env)->ReleaseStringUTFChars(env, newFilePath, newFile);

    return 0;  // 成功
}

3.3 bzip2 依赖处理

bsdiff 使用 bzip2 进行 compression，需要在 CMakeLists.txt 中链接：

# CMakeLists.txt
find_library(bz2-lib bz2)  # Android NDK 内置 libbz2.so

target_link_libraries(nativepatch
    ${bz2-lib}
    ${log-lib}
)

Android NDK 的 libbz2.so 位于 $NDK/sysroot/usr/lib/<abi>/ 目录下。如果没有，也可以将 bzip2 源码加入项目编译。

四、签名验证

补丁合成后必须验证新 APK 的签名，确保没有被篡改：

// 在 Java 层验证签名
public boolean verifyPatch(String newApkPath, String originalPackageName) {
    PackageManager pm = context.getPackageManager();
    PackageInfo originalInfo = pm.getPackageInfo(originalPackageName,
        PackageManager.GET_SIGNATURES);
    PackageInfo newInfo = pm.getPackageArchiveInfo(newApkPath,
        PackageManager.GET_SIGNATURES);

    if (originalInfo.signatures.length != newInfo.signatures.length) {
        return false;
    }
    for (int i = 0; i < originalInfo.signatures.length; i++) {
        if (!originalInfo.signatures[i].equals(newInfo.signatures[i])) {
            return false;  // 签名不匹配！
        }
    }
    return true;
}

也可以直接在 C 层验证签名（解析 APK 的 META-INF/CERT.RSA 文件），但复杂度较高。实际的增量更新流程中，合成后的 APK 再完整走一次系统的 PackageInstaller 签名验证流程。

五、与 Google Play In-Place Update 的对比

Google Play 的更新机制演进：

机制	描述	时间
Smart Updates	bsdiff 差分，下载差分包后合成	2012年
File-by-File Patching	对 APK 内每个文件做差分，而非整体	2016年
In-Place Update	不解压 APK 直接修改内部文件（更省磁盘空间）	2020年+

File-by-File 相比传统的整体差分优势：

• 差分包更小（APK 内部的压缩文件变化时，整体差分会因为对齐填充产生大量无用差异）。
• 合成更快（只修改变化的文件，不需要重建整个 APK）。
• 需要使用 APK 文件格式知识（ZIP 文件结构修改）。

Google 的方案是封闭的，仅限 Google Play 使用。自研增量更新方案仍然有重要价值（特别是面向中国市场的应用）。

六、性能与安全

性能要点：

• 合成操作是 I/O 和 CPU 混合密集型（解压 bzip2 + 大量 memcpy）。在低端设备上，合成 100MB APK 可能耗时 10-30 秒。需要后台 Service 执行，配合通知栏进度显示。
• 内存使用：需要同时加载旧文件和新文件的完整内容到内存（对于大型 APK 可能需要数百 MB RAM）。可以使用内存映射（mmap）减少物理内存占用。
• bzip2 的解压速度较慢（~5-10 MB/s），在大型 APK 上可能成为瓶颈。可以考虑使用 lz4/zstd 等更快的压缩算法替换 bzip2。

安全要点：

• 差分包必须从可信服务器下载（HTTPS + 证书固定）。
• 合成后 APK 必须签名验证（前文已述）。
• 合成过程在沙盒中进行，不修改系统分区。
• 差分包本身可以加密（AES），在合成前先解密。

七、面试常问题目

Q1: BSDiff 算法为什么比简单的逐字节 diff 效率高？

简单的逐字节 diff 对代码段的变化几乎失效——代码中的一个指令变化（如插入一条 nop 指令）会导致后续所有指令的地址都偏移，逐字节比较全部不匹配。BSDiff 使用后缀数组，可以在旧文件中找到与新文件最相似的区域，即使有插入/删除导致偏移也能识别出匹配段。匹配段不需要存储差异数据，只需在 control triple 中记录”从旧文件复制 N 字节”。

Q2: 为什么增量更新需要 bzip2 压缩？可以用 zstd 替代吗？

bzip2 提供了很高的压缩比（比 gzip 高 10-20%），这对差分包的大小至关重要。但 bzip2 解压较慢。可以用 zstd 替代——zstd 提供了与 bzip2 相当的压缩比，但解压速度快 3-5 倍，且支持字典训练（针对特定 APK 模式优化）。Chrome 的 Courgette 差分算法使用了更激进的策略：反汇编 x86/ARM 代码，对汇编指令做差异，进一步缩小了差分包。

Q3: 如果用户跳过了多个版本（如从 v1 直接升级到 v5），增量更新如何处理？

两种策略：(1) 服务器预存所有版本的链式差分包（v1→v2, v2→v3, v3→v4, v4→v5），客户端依次合成——合成次数多但每个差分包小。(2) 服务器预存跨版本差分包（v1→v3, v1→v4, v1→v5），客户端一次合成——差分包较大但合成次数少。实际项目中，对于跳版本过多（如超过 5 个版本）的情况，通常回退到全量下载，因为多次合成的累积失败概率和时间成本不划算。

Q4: 合成后的 APK 为什么必须验证签名？

防止中间人攻击——攻击者替换差分包，合成出包含恶意代码的 APK。签名验证确保合成后的 APK 是由原开发者签名的。Android 系统还会在安装时进行额外的签名验证（PackageManagerService.installPackage），但客户端提前验证可以更早发现问题，避免浪费用户等待时间。

---

参考源码路径：

• BSDiff 论文：*”Naive Differences of Executable Code”* by Colin Percival, 2003
• AOSP bsdiff：external/bsdiff/ (已移除，历史版本: bootable/recovery/applypatch/)
• AOSP bspatch：bootable/recovery/updater/blockimg.cpp
• Google Play File-by-File：https://android-developers.googleblog.com/2016/07/improvements-for-smaller-app-downloads.html
• Courgette (Chrome)：https://www.chromium.org/developers/design-documents/software-updates-courgette/