本文首发于微信公众号“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 与业界其余计划的比照
4.1 Google 的 archive-patcher
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 资源增量更新的最佳实际。