NDK实现增量更新

一、增量更新的业务价值

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

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

商业案例：

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

1.1 增量更新的分类

增量更新在实现层面分为两大类：

1. 文件级增量：对新旧 APK 整体做 bsdiff，生成一个完整的差分包。实现简单，但差分包可能包含大量无效差异（如 ZIP 对齐填充、压缩层的变化）。
2. 文件内增量（File-by-File）：解压 APK（实质是一个 ZIP 文件），对内部每个文件分别做差分。Google Play 使用的就是这种方式。差分包更小，合成更快，但需要处理 ZIP 文件格式。

二、BSDiff 算法原理深度剖析

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

2.1 BSDiff 的核心思想

BSDiff 不是简单的逐字节差异比较（像 Unix diff 那样），而是利用后缀排序（suffix sorting）找到旧文件中与新文件相似的区域，然后编码差异。为什么逐字节比较不够？考虑这个场景：

旧文件（二进制代码段）:
  [指令A][指令B][指令C][指令D][指令E]

新文件（在中间插入了指令X）:
  [指令A][指令B][指令X][指令C][指令D][指令E]

逐字节比较从第一字节开始：A=A 匹配，B=B 匹配，C≠X 失配。之后的所有字节全部失配——即使绝大多数内容未变。BSDiff 通过后缀排序识别出 “C” 在新文件中偏移 +1 后匹配到了旧文件中的 “C”，从而减少了 diff 数据量。

BSDdiff 算法的三个步骤：

步骤一：后缀排序

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

旧文件 "ABAB" 的后缀：
后缀            起始位置    排序后
"ABAB"          0          "AB" (0)
"BAB"           1          "ABAB" (0)
"AB"            2          "B" (1)
"B"             3          "BAB" (1)
                          "AB" (2)  — 这重复了，实际上是不同的位置

步骤二：匹配

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

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

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

步骤三：生成 diff + extra + control

三部分数据：

• diff string（差异数据）：new_byte - old_byte，逐字节编码差异。使用 bzip2 压缩。注意：这里使用减法（而非 XOR）是为了与 bzip2 配合更好——减法产生的小整数分布更有利于 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 on-disk 格式

BSDiff Patch 文件的格式：
┌──────────────────────────────────────────────┐
│ Magic: "BSDIFF40" (8 bytes)                  │
├──────────────────────────────────────────────┤
│ Header (24 bytes):                           │
│   ctrl_len    (int64_t): 控制块压缩后长度     │
│   diff_len    (int64_t): diff块压缩后长度     │
│   new_size    (int64_t): 新文件大小           │
├──────────────────────────────────────────────┤
│ bzip2(control block): 解压后 = N * 24 bytes  │
│   (每个 triple: 3 个 int64_t)                │
├──────────────────────────────────────────────┤
│ bzip2(diff block)                            │
├──────────────────────────────────────────────┤
│ bzip2(extra block)                           │
└──────────────────────────────────────────────┘

这里的 int64_t 使用了大端序（big-endian），确保跨平台兼容。

2.3 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 = read_int64_bigendian(&ctrl[ctrlpos]);
        int64_t extra_len = read_int64_bigendian(&ctrl[ctrlpos + 8]);
        int64_t copy_len = read_int64_bigendian(&ctrl[ctrlpos + 16]);
        ctrlpos += 24;

        // 1. 应用差异（diff string）
        // new[i] = old[i] + diff[i]（模 256）
        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;
    }

    // 验证合成结果
    if (newpos != *newsize) {
        free(*new);
        *new = NULL;
        return -1;  // 合成大小不匹配
    }

    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 源码加入项目编译。

四、mmap 优化内存使用

BSPatch 需要将整个旧文件和新的输出文件加载到内存，对于大型 APK（200MB+）内存压力很大。可以使用 mmap 减少物理内存占用：

// 使用 mmap 读取大文件
int fd = open(old_path, O_RDONLY);
struct stat st;
fstat(fd, &st);
uint8_t *old_data = mmap(NULL, st.st_size, PROT_READ,
                         MAP_PRIVATE, fd, 0);
// 不需要 fread，直接通过 old_data 指针访问
// 内核按需加载页面（demand paging），不占用物理内存
// ...
munmap(old_data, st.st_size);
close(fd);

// 对于新文件输出，使用 MAP_SHARED 配合文件
int out_fd = open(new_path, O_RDWR | O_CREAT | O_TRUNC, 0644);
ftruncate(out_fd, new_size);
uint8_t *new_data = mmap(NULL, new_size, PROT_READ | PROT_WRITE,
                         MAP_SHARED, out_fd, 0);
// 合成过程直接写入 new_data（内存映射）
// 操作系统负责异步刷盘
msync(new_data, new_size, MS_SYNC);  // 确保写入磁盘
munmap(new_data, new_size);
close(out_fd);

五、签名验证

补丁合成后必须验证新 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 层进行 MD5/SHA256 hash 校验
// 合成完成后，计算新文件的 SHA256，与预期的值比较
bool verify_checksum(const uint8_t *data, size_t len,
                     const uint8_t *expected_sha256) {
    uint8_t computed[SHA256_DIGEST_LENGTH];
    SHA256(data, len, computed);
    return memcmp(computed, expected_sha256, SHA256_DIGEST_LENGTH) == 0;
}

也可以直接在 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 使用。自研增量更新方案仍然有重要价值（特别是面向中国市场的应用）。

6.1 Courgette 算法（Chrome 的差分方案）

Chrome 使用了比 BSDiff 更激进的差分算法Courgette：

Courgette 的核心思路：
1. 将旧文件 disassemble 为汇编指令序列
2. 将新文件 disassemble 为汇编指令序列
3. 对汇编指令做 diff（而非对原始字节）
4. 只存储差异指令 + 地址调整信息

优势：代码中插入一条指令只会改变指令的偏移，Courgette 可以识别
      这种"语义相同"的变化，差分包比 BSDiff 更小。
劣势：需要反汇编（平台相关），且只适用于原生代码。
      Courgette 生成的差分包约是 BSDiff 的 50-70% 大小。

七、性能与安全

7.1 性能优化

性能要点：

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

7.2 压缩算法对比

算法	压缩比	压缩速度	解压速度	适用场景
bzip2	高	慢	慢	BSDiff 默认，追求最小差分包
gzip	中	中	中	通用场景
zstd	中高	快	很快	推荐替代方案
lz4	低	很快	极快	速度优先场景

// 使用 zstd 替代 bzip2（需要修改 bsdiff 的压缩/解压调用）
#include <zstd.h>

// 压缩
size_t compressed_size = ZSTD_compress(dest, dest_capacity,
    src, src_size, compression_level);

// 解压
size_t decompressed_size = ZSTD_decompress(dest, dest_capacity,
    src, compressed_size);

7.3 安全要点

• 差分包必须从可信服务器下载（HTTPS + 证书固定）。
• 合成后 APK 必须签名验证（前文已述）。
• 合成过程在沙盒中进行，不修改系统分区。
• 差分包本身可以加密（AES），在合成前先解密。
• 在低端设备上的合成超时处理（设置超时阈值，超时后回退到全量下载）。

7.4 错误恢复策略

// 增量更新的完整错误恢复流程
public class PatchManager {
    public void applyPatch(String patchUrl) {
        try {
            // 1. 下载差分包（带 MD5 校验）
            File patchFile = downloadPatch(patchUrl);
            if (!verifyMD5(patchFile)) {
                fallbackToFullUpdate();
                return;
            }
            
            // 2. 合成新 APK
            File newApk = applyNativePatch(
                getOldApkPath(), patchFile);
            
            // 3. 签名验证
            if (!verifySignature(newApk)) {
                newApk.delete();
                fallbackToFullUpdate();
                return;
            }
            
            // 4. 安装
            installApk(newApk);
            
        } catch (Exception e) {
            // 任何一步失败，回退到全量下载
            fallbackToFullUpdate();
        }
    }
}

八、面试常问题目

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 个版本）的情况，通常回退到全量下载，因为多次合成的累积失败概率和时间成本不划算。更好的方案是维护一个”基准版本”（如每 5 个小版本发布一个全量包），所有差分包相对于基准版本生成。

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

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

Q5: BSPatch 合成过程中的内存优化有哪些策略？

对于 100MB+ 的 APK，同时加载旧文件和新文件到内存需要 200MB+ 的 RAM，在低端设备上可能 OOM。优化策略：(1) 使用 mmap 加载旧文件（内核按需换页，不占用物理内存）；(2) 分片合成——如果修改 bsdiff 格式支持分片，可以分批合成；(3) 使用 zstd 替代 bzip2 减少解压时的临时内存分配；(4) 合成输出也使用 mmap + 文件，写入通过 OS 异步刷盘；(5) 在合成前检查可用内存（通过 /proc/meminfo），不足时回退到全量下载。

---

参考源码路径：

• 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/