本文首发于微信公众号“Shopee技术团队” 。
作者：Pei，来自 Shopee 商家服务前端团队。
1. 背景
Shopee 的许多手机应用是原生与 React Native（下文简称 “RN”）的混合（hybrid）应用。在用户打开 App 时，客户端会发起请求查看是否有新版 RN 资源。若有，则后台静默下载最新资源，重新加载 RN，以实现 RN 更新。这样的更新过程免却了用户去 Google Play/App Store 重新下载 App 的麻烦，也能迅速把最新资源推送给所有用户。
另一方面，RN 资源虽会更新迭代，但新旧版的差异其实只占小部分，让用户下载全量资源不仅浪费用户流量，也影响用户对 App 的使用体验（因为后台静默更新仍然会挤占带宽资源）。
自然而然，我们会想到“增量（差量）更新”，客户端仅下载新旧 RN 资源的差异部分。这个差异部分汇总到一个文件里，这个文件被称之为增量包（或补丁包）。下载完成并验证补丁包的合法性后，方可与旧版本合并为新版本，以此节约流量。
考虑到 Shopee 主要市场的网络条件，数据流量的节约尤为重要。但这个增量包应该是怎样的呢？本文会以循序渐进的思路分析各种方案的优缺点，包括 Shopee 公司内的探索实践过程所产生的方案，以及业界提供的方案，最后提出 FolderBsdp 算法，对直接资源进行差分，实现增量更新。
2. 增量包实践方案进化之路
2.1 直接传输差异的（原始）文件
RN 资源包括转译后的 JavaScript 代码、各语言翻译 JSON 文件、图片等媒体资源、配置文件。我们把这些资源称为“直接资源”。它们是 RN 打包的直接产物，也是日常供客户端调用的存在形式。如果这些“直接资源（原始文件）”在 CDN 上，保留新旧资源的文件目录，即可对应下载新增的和修改的文件。
![]()
其缺点主要有两方面：
1）分散传输易出错
如果有新增图片和修改翻译文件等修改，需要发起多次 HTTP 请求到 CDN 下载文件，这样会复杂化更新的异常处理情况，比如部分文件下载过程中断的恢复问题。
2）传输量大费流量
图片和翻译 JSON 文件用原始文件传输浪费数据流量，因为这些资源本可以被压缩。翻译文件体积较大，但每个版本的修改一般是细微新增若干行，没有必要直传整个文件。因此，所谓传输“差异”的部分，文件级别的“差异”颗粒度还是太大了。
2.2 文件间的差分算法 BSDiff
为了避免 2.1 中的问题，我们引入了差分算法，以实现增量更新。
2.2.1 差分算法
文件间的差分算法是一种实现增量更新的方法。差分算法的入参是新旧两个文件，其输出是两个文件的差异部分，称为 Patch，即补丁包（也称增量包）。
一个差分算法还有与之配套的打补丁算法，其入参是旧文件和 Patch，输出是新文件。不同的差分算法各有优劣，体现在差分和打补丁操作的时空复杂度、Patch 体积、Patch 内容可读性等。
2.2.2 Bsdp（BSDiff & BSPatch）算法
BSDiff 算法是一个非常流行的差分算法，它专注于得到尽可能小的 Patch 体积（适用于 Patch 要通过网络传输的更新方式），被 Google Chrome 等软件广泛使用，非常适合代码升级这种具有局域性的稀疏的改动。
BSDiff 算法开源且免费，用 C 语言写成，源代码可以在服务端、Android/iOS 端执行。BSDiff 算法所搭配的打补丁算法 BSPatch 可以将旧文件和 Patch 结合，恢复出新文件。BSDiff 和 BSPatch 算法并称 Bsdp 算法。
![]()
2.2.3 直接使用 BSDiff 算法的优缺点
对比于“2.1 直接传输差异的（原始）文件”，如果只传输 BSDiff 所生成的差异 Patch，的确能够减少传输的数据流量，加快下载过程。但是，它没有解决频繁发起多次 HTTP 请求去下载各个文件的问题。我们需要一个方法把资源合并起来，一起下载。
2.3 压缩资源的 BSDiff
考虑到各个资源文件分散传输（2.1 与 2.2）的缺点，改进方式是在编译时把 RN 各直接资源文件放在一个文件夹里，然后用 ZIP 工具压缩为一个文件，采用 ZIP 压缩资源全量包以及压缩资源的 Patch 来实现初始安装和后续更新。
![]()
具体说来，RN 打包的直接产物包含了一定目录结构的 JS 代码、翻译 JSON、图片、配置文件。所有这些文件压缩为一个 ZIP 压缩包。在 App 初始安装时，里面有这个 ZIP 包，以及其解压的 RN 资源。
在用户使用 App 的过程中，若有新版 RN 资源，则会下载对应 Patch 文件，运用 BSPatch 算法与先前的 ZIP 压缩包（客户端打包时并不删除当时 RN 资源的 ZIP 压缩包）结合，即可得到新版本的 ZIP 压缩包，这个新版本的 ZIP 压缩包保留在用户手机里，以便下一次生成新 ZIP 包，如此反复，持续更新。ZIP 压缩包解压后得到直接资源，即可被使用。
![]()
从时间线上来看，这样的更新也就是版本迭代，形成如下图所示的更新关系，称为“RN 更新链”。
![]()
此方案的优点是克服了分列文件方案的缺点。通过 ZIP 压缩文件，多个文件合为一体，资源形式变得简单，HTTP 请求数也减少了。对于全量包来说，它减少了总体积。Shopee 某业务包未压缩时所有资源一共有 14MB，压缩后约为 4MB。
但是，此方案隐藏了一个难以发现的缺陷，使得这一方案存在很大的改进空间。这一缺陷就是 ZIP 压缩过程影响了文件的样貌，使得新旧文件的差异扩大，由此，ZIP 压缩包之间的 Patch 体积也过大。以下详细解释这一缺陷。
2.3.1 BSDiff 生成 Patch 的过程
BSDiff 属于“区块移动”算法。为了记录新旧文件的差异以便恢复出来，它使用了动态规划算法——最长公共子序列。
对于新文件的内容，它尝试从旧文件找到匹配的最长公共子序列，并记录了新文件的内容相对于旧文件的位置变化，站在新文件面向旧文件的视角，尽可能地用旧文件的内容拼装成新文件。
而对于额外的差异，它记录了差异内容以及其在新文件的位置。这些记录的内容和位置信息经过 bzip2 压缩后即得到 Patch 文件。Patch 文件包含的复制和插入信息，在运行 BSPatch 时可以把旧文件变成新文件。
![]()
简单的示意图如上。蓝色和绿色区块是相同的内容，但是它们出现在文件中的位置不一样，Patch 记录下位置信息。红色的是额外（Extra）的内容，Patch 文件记录下其在新文件的位置及其内容本身。这些记录形成的指令让我们用旧文件和 Patch 文件恢复出新文件。
由此，我们领悟到，对重复内容，记录位置偏移（蓝色、绿色区块）所需要的信息量少；对于额外区块，我们不仅要记录位置偏移，还要在 Patch 文件里留存其内容本身（尽管可以压缩）。位置偏移所占的 Patch 文件体积要远小于内容所占体积。额外内容越少（新旧文件越相似），Patch 文件体积越小。
2.3.2 压缩资源使用 BSDiff 的缺陷
Lempel-Ziv 编码算法是 ZIP 压缩算法的重要环节，它又被称为“滑动窗口压缩”。该算法的核心思想是在之前的历史数据中寻找重复字符串。
但是，并不是一路回溯到文件头，而是考虑到重复内容的局部性，它设定了一个区间（常见是 32KB）。这个 32KB 的窗口随着编码不断进行而向前滑动。理论上来说，这个滑动窗口（Sliding Window）如果更大，我们有更大概率找到重复字符串，但这样会增大计算量。32KB 是 ZIP 的折中设定。
![]()
在上图中，当编码来到 “OK.”（右侧，蓝色标记）时，在滑动窗口回溯发现有重复的 “OK.”（左侧，蓝色标记）。LZ 算法记录下左侧 “OK.” 相对于当前位置的距离（Distance）和长度（Length），然后再推进到下一个字符（Next Character）。在压缩的结果文件中，此处就会保留一个“OK.”，然后用 Distance+Length 的方式把 Sliding Window 里重复的 “OK.” 表示出来。这样就避免了 “OK.” 重复出现，节约了体积。若重复字符若更长，压缩效果会更明显。
若这段字符出现了细微修改，LZ 算法的编码结果会产生巨大的改动。
![]()
考虑上图第二行的情况，若插入了 “!”（绿色标记），则编码可能产生两个变化。
第一个变化就是编码时扫描到右侧 “OK.” 时，其对应的左侧重复字符的 Distance 发生了改变（Distance 值的变化会产生一系列其他副作用）。
第二个可能的变化是因为插入了字符，左侧的 “OK.” 已经超出了滑动窗口的左沿，因此右侧 “OK.” 无法找到此重复字符（此处当然在 32KB 滑动窗口内，仅作示意）。
考虑上图第三行的情况，若插入了 “!”（橙色标记），则原有的 “OK.” 重复字符（Literal）不复存在，编码产生了巨大的改动。
此外，在 ZIP 压缩算法中还有霍夫曼编码环节，无论是字符（Literal），距离（Distance），还是长度（Length），都不会用其真值表示，而是采用了霍夫曼编码，越常出现的就用越短的字符表示，越不常出现的就用越长的字符表示。另外再保留一张霍夫曼编码后的字符与原字符的对应表格。
上面第二行和第三行的情况，会影响到 Literal、 Distance、Length 不同值出现的频率，也就影响到了其对应的编码。这个编码的影响是全局而非局部的。
其他主流压缩算法与 ZIP 压缩算法原理本质相同，为了追求压缩比，细微的差异也会有全局的影响。
由此，我们可知：压缩不利差分性质。
压缩过的文件有可能破坏了新旧 RN 资源的字节流的相似性，基于压缩过的文件进行 BSDiff 计算所得的 Patch 体积存在进一步缩小的可能。
计算 BSDiff 基于原始 RN 资源的字节流是一个值得探讨的方向。
2.4 Store 文件的 BSDiff
为了解决 2.3 存在的缺陷（压缩不利差分性质），我们尝试把包含各文件的直接资源以不压缩的方式合并成一个大文件，让原始字节流以其原有的样貌留在文件中，它还可以“解绑”恢复原有的文件及目录结构。通过这个方法，原始的字节流特征就不会被破坏。我们把这样的文件称之为 Store 文件，即没有压缩功能的 Archive 文件。
其主流实现有 ZIP 的 Store 模式（也是使用 ZIP 工具，但是不进行 ZIP 压缩算法）以及 Tar 文件格式。ZIP Store 模式的资源执行 BSDiff 算法，（相较于压缩文件）大概 84% 的体积。但是，这一方案也有其缺陷。
2.4.1 ZIP 的 Store 模式
要生成 ZIP 的 Store 文件非常简单，所有的 ZIP 工具都有 Store 模式，一般来说是生成 ZIP 包时把入参布尔值 store 设置为 true，解压/解绑时不需要额外提供参数。考虑到使用 ZIP 的 Store 模式主要是因为 Android SDK 原生支持 ZIP 文件的生成和解压/解绑，因此对于包含许多 App 的 Shopee 公司来说是一大优势，不仅节约包体积（重要），还减少协调难度。
精简依赖考量——在客户端，我们尽可能不安装额外的依赖包。
看似是最优解，但在实践尝试中发现此方案有一个问题：ZIP Store 文件在各端并不兼容。
具体的问题是，在后端 Node.js 中，运用通用的 archiver 库所生成的 Store 文件不被 Android 原生的 ZIP 库识别，无法解绑。这一点在网上也有过广泛讨论，见 StackOverflow。
其中提出的解决建议是 Android 另外装 Oracle 的 ZIP 库，这与精简依赖考量相违背，不是优秀的选项。
那么，在 Android 客户端运用直接资源去生成 ZIP Store 文件行不行呢？答案是否定的。因为 Android 客户端生成的 Store 文件和服务端生成的不同，而服务端的 Patch 是基于服务端的 Store 文件求 BSDiff 所得。哪怕有一个字节的差异，都无法打补丁成功。所以我们不能让客户端去生成 Store 文件。哪怕我们去掉了平台所特有的 metadata，ZIP 本身也是非确定性算法（Non-deterministic Algorithm），这会让打补丁算法失效。所以：
ZIP不确定性——跨平台差异性使得 ZIP 压缩包或 ZIP Store 包不能由客户端运用直接资源去生成。
2.4.2 Tar 文件格式
Tar 文件格式在类 UNIX 系统非常流行，是不执行压缩的 Archive-only File（本文续称 Store 文件）。Tar 文件格式不可避免地包含各种平台特有的 metadata，在一部分平台的库中没有彻底去除 metadata 的选项，即便可以，Android 和 iOS 客户端也要为此安装 Tar 文件的解绑依赖包，这与精简依赖考量相违背。
2.4.3 Store 文件格式难以避免的缺点
上文讲解了 ZIP Store 文件和 Tar 文件的缺陷，假设我们寻觅到了一个优秀的 Store 文件格式，它支持跨平台统一的 Archive 操作，但还是避免不了一个难以接受的缺陷——增大了客户端存储空间的占用。
相比于 ZIP 压缩文件，Store 文件由于未压缩，体积很大。在某些情况下传输全量 Store 包的流量消耗也就变大了。如果我们对于全量 Store 包再进行压缩，则给客户端带来了新的复杂度。那就是资源包具有多种格式，有的要解压两次，有许多异常的可能性，这给客户端带来的负担太沉重。我们需要有另外的方法来差分资源。
3. 最佳实践方案：FolderBsdp
为解决上一章的问题，我们创新性地提出 FolderBsdp 方案。FolderBsdp 是以文件间的 Bsdp 算法为基础，对有目录层级结构的文件夹进行差分。具体来说，它由 FolderBSDiff（求差分）和 FolderBSPatch（打补丁）两个算法相结合。
![]()
3.1 FolderBSDiff 的具体算法
先比较新旧文件夹的目录结构和内含文件，新文件夹相对于旧文件夹所产生的变动包括五种情况：新增目录、删除目录、新增文件、删除文件、修改文件。
对于新增目录、删除目录、删除文件的情况，记录下对应的操作；对于修改文件，调用 BSDiff 函数。我们基于直接资源里的每一个文件的内容修改求 BSDiff，留下其 Patch 文件体积足够小，避开了压缩不利差分性质的困境；对于新增文件，则记录下所增文件的相对路径，并拷贝此文件。
我们把这些操作按照一定顺序（新增目录要在最前，删除目录要在最后）汇总到一个 JSON 文件里。并且把 BsDiff 求出的各个 Patch 文件和新增的文件保存下来，这些文件通过 ZIP 压缩算法为一个 ZIP 文件，即为 FolderBSDiff 的 Patch 文件。这个文件的体积与 Store 文件之间求 BSDiff 类似，也同样（相对于 ZIP 压缩包之间的 BSDiff）节约了约 84% 的体积。这个 Patch 可以用于对应的打补丁操作（FolderBSPatch）。
优点一：在客户端侧打补丁时内存占用低
在打补丁操作时，我们需要把旧文件和补丁包加载到内存里，在执行完成前，新文件也在内存里。FolderBSPatch 针对逐个资源文件，按顺序串行操作，“化整为零”，相比于 ZIP 包的 BSPatch，内存占用更低，更不影响用户体验。
根据实际测算，相比于 ZIP 包的 BSPatch，使用 FolderBSPatch 在客户端侧打补丁的内存峰值占用少了 40%。
内存考量——在客户端侧降低内存占用是一个优点。
在 RN 资源包更新这个情境中，FolderBSPatch 这一优点非常有必要，因为打补丁的过程是在 App 运行时的后台进行，与此同时用户很可能还在积极使用 App。此外，我们预期 Shopee 主要市场的用户手机内存配置较低。
优点二：节约存储空间
在客户端侧，基于 FolderBsdp 可以舍弃掉储备文件，无论是 ZIP 压缩资源包，还是上文讨论的 Store 资源包。
在之前的算法中，因为 ZIP 不确定性，我们留存 ZIP 压缩包或 Store 文件在客户端。文件留存的唯一目的就是为了打补丁，没有其他用处，非常浪费存储空间。
![]()
从时间线上来看，根据 FolderBsdp 也形成了客户端侧的 “RN 更新链”，如下图所示：
![]()
以 Shopee 内某个 App 为例，客户端总包体积 202MB，其中 RN 的 ZIP 压缩包约 8MB，使用 FolderBsdp 后，不再需要 ZIP 包，App 也就“瘦身”了。
空间考量——节约掉储备文件所占的体积是一个重要的优点，我们要尽量做到。
优点三：不需要 ZIP 库
在客户端，我们不再需要调用 ZIP 的解压算法，iOS 端也就不再需要依赖 ZIP 库或其他压缩库（Android 内置无法删除）。虽然我们需要引入 FolderBSPatch，但其代码不过一百行左右，没有大型依赖，体积远小于 ZIP 库，符合精简依赖考量。
优点四：附带更精确的 MD5 校验
我们可以把每一个新增、删除、修改文件的 MD5 值保存在 JSON 文件中，在打补丁操作时进行校验，更自信地确认我们的操作是正确无误的。
4. FolderBsdp 与业界其他方案的对比
Google 考虑到了 ZIP 压缩文件之间求 BSDiff 破坏了原始字节流相似性的缺陷（压缩不利差分性质），产生了逐个文件恢复出其原始字节流并且求差异的方案，很好地解决了这个问题。
另一方面，因为跨平台的差异性（ZIP 不确定性），此方案不可避免地需要在客户端保留 ZIP 压缩资源包。
这与我们追求尽可能节约存储空间的目标背道而驰（空间考量），因此不应该被采用。而本文提出的 FolderBsdp 方案很好地克服了 archive-patcher 的这一缺点。
4.2 其他方案
增量更新领域中有另一知名的开源项目，作者使用 C++ 自行编写算法，将目录下各文件以不压缩的状态合并起来进行差分，即本文 Store 文件思路。FolderBsdp 与此方案对比的优点是打补丁时更加节约内存（内存考量）。本文所述的 RN 资源更新，是在用户活跃使用 App 时后台静默更新，也考虑到 Shopee 主要用户群体手机内存配置较低的特点，FolderBsdp 算法这一优点很重要。
此外，有方案对差分包的压缩格式进行扩展，使其不局限于 ZIP 格式，也可以支持其他压缩库。这个灵活性在某些场景适用。但在本文情境中，App 的精简依赖考量更加重要。本文提出的 FolderBsdp 算法利用标准 bsdp 和 Android SDK 自带的 ZIP 库，不需要安装其他格式的压缩库。FolderBsdp 的补丁包体积与其他压缩格式差异不大。
5. 总结
本文所介绍的 FolderBsdp 方案降低了打补丁时的内存峰值，避免了在客户端保留多余的 ZIP 包占用空间，额外提供了逐个文件的 MD5 精准校验，无需新增依赖库，因为用各端原生开发语言实现而具有兼容性。兼具各种优点，FolderBsdp 成功实现了增量更新功能，是多番探索之下总结出来的 RN 资源增量更新的最佳实践。
