1.Android Studio NDK 编译 Bsdiff 库
2.ReactNative资源更新增量包的官方优化实践

Android Studio NDK 编译 Bsdiff 库

       在构建web离线包时，需要实现增量更新来优化用户体验。源码c源增量更新通过对比新旧文件，官方生成差分文件，源码c源让客户端仅下载差异部分，官方从而节省带宽流量。源码c源linux显卡驱动源码分析

       bsdiff算法是官方实现增量更新的一种常用技术。为了集成bsdiff库，源码c源首先需要下载相关源代码，官方包括bsdiff和依赖的源码c源bzip2库。在Android Studio中，官方需要配置对C和C++代码的源码c源支持，为生成.so文件做准备。官方创建一个专门用于.so生成的源码c源子module，并制定清晰的官方代码结构。

       在代码实现中，将bsdiff源码和bzip2源码分别置于cpp和bzip2目录下。注意调整头文件引用路径和屏蔽主函数入口。通过关联CMake文件和编写对应的CMakeLists.txt，配置Android Studio环境以生成.so文件。在Java层，创建工具类调用Native方法，并实现差分和合并功能的实现。生成.so文件后，其他项目可直接引用。

       搭建完成后，通过测试验证功能的正确性。测试页面提供差分和合并按钮，模拟实际应用过程。通过测试，确保增量更新功能按照预期工作。

       在完成这些步骤后，基于Android Studio和CMake搭建的环境能够成功编译bsdiff.so库，并在项目中实现增量更新功能。此过程提供了完整的集成和测试流程，确保了功能的正确性和效率。相关源码已上传至GitHub，可供参考和使用。

ReactNative资源更新增量包的优化实践

       本文首发于微信公众号“Shopee技术团队”。

1.背景

       Shopee的许多手机应用是原生与ReactNative（下文简称“RN”）的混合（hybrid）应用。在用户打开App时，客户端会发起请求查看是否有新版RN资源。若有，则后台静默下载最新资源，重新加载RN，以实现RN更新。这样的ubuntu下阅读源码更新过程免却了用户去GooglePlay/AppStore重新下载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中的问题，我们引入了差分算法，单车app系统源码以实现增量更新。

2.2.1差分算法

       文件间的差分算法是一种实现增量更新的方法。差分算法的入参是新旧两个文件，其输出是两个文件的差异部分，称为Patch，即补丁包（也称增量包）。

       一个差分算法还有与之配套的打补丁算法，其入参是旧文件和Patch，输出是新文件。不同的差分算法各有优劣，体现在差分和打补丁操作的时空复杂度、Patch体积、Patch内容可读性等。

2.2.2Bsdp（BSDiff&BSPatch）算法

       BSDiff算法是一个非常流行的差分算法，它专注于得到尽可能小的Patch体积（适用于Patch要通过网络传输的更新方式），被GoogleChrome等软件广泛使用，非常适合代码升级这种具有局域性的稀疏的改动。

       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某业务包未压缩时所有资源一共有MB，压缩后约为4MB。

       但是，此方案隐藏了一个难以发现的缺陷，使得这一方案存在很大的改进空间。这一缺陷就是ZIP压缩过程影响了文件的样貌，使得新旧文件的差异扩大，由此，ZIP压缩包之间的Patch体积也过大。以下详细解释这一缺陷。

2.3.1BSDiff生成Patch的过程

       BSDiff属于“区块移动”算法。为了记录新旧文件的差异以便恢复出来，它使用了动态规划算法——最长公共子序列。

       对于新文件的内容，它尝试从旧文件找到匹配的最长公共子序列，并记录了新文件的内容相对于旧文件的位置变化，站在新文件面向旧文件的视角，尽可能地用旧文件的内容拼装成新文件。

       而对于额外的差异，它记录了差异内容以及其在新文件的位置。这些记录的内容和位置信息经过bzip2压缩后即得到Patch文件。Patch文件包含的复制和插入信息，在运行BSPatch时可以把旧文件变成新文件。

       简单的示意图如上。蓝色和绿色区块是vc 线程注入 源码相同的内容，但是它们出现在文件中的位置不一样，Patch记录下位置信息。红色的是额外（Extra）的内容，Patch文件记录下其在新文件的位置及其内容本身。这些记录形成的指令让我们用旧文件和Patch文件恢复出新文件。

       由此，我们领悟到，对重复内容，记录位置偏移（蓝色、绿色区块）所需要的信息量少；对于额外区块，我们不仅要记录位置偏移，还要在Patch文件里留存其内容本身（尽管可以压缩）。位置偏移所占的Patch文件体积要远小于内容所占体积。额外内容越少（新旧文件越相似），Patch文件体积越小。

2.3.2压缩资源使用BSDiff的缺陷

       Lempel-Ziv编码算法是ZIP压缩算法的重要环节，它又被称为“滑动窗口压缩”。该算法的核心思想是在之前的历史数据中寻找重复字符串。

       但是，并不是一路回溯到文件头，而是考虑到重复内容的局部性，它设定了一个区间（常见是KB）。这个KB的窗口随着编码不断进行而向前滑动。理论上来说，这个滑动窗口（SlidingWindow）如果更大，我们有更大概率找到重复字符串，但这样会增大计算量。KB是ZIP的折中设定。

       在上图中，当编码来到“OK.”（右侧，蓝色标记）时，在滑动窗口回溯发现有重复的“OK.”（左侧，蓝色标记）。LZ算法记录下左侧“OK.”相对于当前位置的距离（Distance）和长度（Length），然后再推进到下一个字符（NextCharacter）。在压缩的结果文件中，此处就会保留一个“OK.”，然后用Distance+Length的方式把SlidingWindow里重复的“OK.”表示出来。这样就避免了“OK.”重复出现，节约了体积。若重复字符若更长，压缩效果会更明显。

       若这段字符出现了细微修改，LZ算法的编码结果会产生巨大的改动。

       考虑上图第二行的情况，若插入了“!”（绿色标记），则编码可能产生两个变化。

       第一个变化就是编码时扫描到右侧“OK.”时，其对应的左侧重复字符的Distance发生了改变（Distance值的变化会产生一系列其他副作用）。

       第二个可能的变化是因为插入了字符，左侧的“OK.”已经超出了滑动窗口的左沿，因此右侧“OK.”无法找到此重复字符（此处当然在KB滑动窗口内，仅作示意）。

       考虑上图第三行的情况，若插入了“!”（橙色标记），则原有的“OK.”重复字符（Literal）不复存在，编码产生了巨大的改动。

       此外，在ZIP压缩算法中还有霍夫曼编码环节，无论是字符（Literal），距离（Distance），还是长度（Length），都不会用其真值表示，而是采用了霍夫曼编码，越常出现的就用越短的字符表示，越不常出现的就用越长的字符表示。另外再保留一张霍夫曼编码后的字符与原字符的对应表格。

       上面第二行和第三行的情况，会影响到Literal、Distance、Length不同值出现的频率，也就影响到了其对应的编码。这个编码的影响是全局而非局部的。

       其他主流压缩算法与ZIP压缩算法原理本质相同，为了追求压缩比，细微的差异也会有全局的影响。

       由此，我们可知：压缩不利差分性质。

       压缩过的文件有可能破坏了新旧RN资源的字节流的相似性，基于压缩过的文件进行BSDiff计算所得的Patch体积存在进一步缩小的可能。

       计算BSDiff基于原始RN资源的字节流是一个值得探讨的方向。

2.4Store文件的BSDiff

       为了解决2.3存在的缺陷（压缩不利差分性质），我们尝试把包含各文件的直接资源以不压缩的方式合并成一个大文件，让原始字节流以其原有的样貌留在文件中，它还可以“解绑”恢复原有的文件及目录结构。通过这个方法，原始的字节流特征就不会被破坏。我们把这样的文件称之为Store文件，即没有压缩功能的Archive文件。

       其主流实现有ZIP的Store模式（也是使用ZIP工具，但是不进行ZIP压缩算法）以及Tar文件格式。ZIPStore模式的资源执行BSDiff算法，（相较于压缩文件）大概%的体积。但是，这一方案也有其缺陷。

2.4.1ZIP的Store模式

       要生成ZIP的Store文件非常简单，所有的ZIP工具都有Store模式，一般来说是生成ZIP包时把入参布尔值store设置为true，解压/解绑时不需要额外提供参数。考虑到使用ZIP的Store模式主要是因为AndroidSDK原生支持ZIP文件的生成和解压/解绑，因此对于包含许多App的Shopee公司来说是一大优势，不仅节约包体积（重要），还减少协调难度。

       精简依赖考量——在客户端，我们尽可能不安装额外的依赖包。

       看似是最优解，但在实践尝试中发现此方案有一个问题：ZIPStore文件在各端并不兼容。

       具体的问题是，在后端Node.js中，运用通用的archiver库所生成的Store文件不被Android原生的ZIP库识别，无法解绑。这一点在网上也有过广泛讨论，见StackOverflow。

       其中提出的解决建议是Android另外装Oracle的ZIP库，这与精简依赖考量相违背，不是优秀的选项。

       那么，在Android客户端运用直接资源去生成ZIPStore文件行不行呢？答案是否定的。因为Android客户端生成的Store文件和服务端生成的不同，而服务端的Patch是基于服务端的Store文件求BSDiff所得。哪怕有一个字节的差异，都无法打补丁成功。所以我们不能让客户端去生成Store文件。哪怕我们去掉了平台所特有的metadata，ZIP本身也是非确定性算法（Non-deterministicAlgorithm），这会让打补丁算法失效。所以：

       ZIP不确定性——跨平台差异性使得ZIP压缩包或ZIPStore包不能由客户端运用直接资源去生成。

2.4.2Tar文件格式

       Tar文件格式在类UNIX系统非常流行，是不执行压缩的Archive-onlyFile（本文续称Store文件）。Tar文件格式不可避免地包含各种平台特有的metadata，在一部分平台的库中没有彻底去除metadata的选项，即便可以，Android和iOS客户端也要为此安装Tar文件的解绑依赖包，这与精简依赖考量相违背。

2.4.3Store文件格式难以避免的缺点

       上文讲解了ZIPStore文件和Tar文件的缺陷，假设我们寻觅到了一个优秀的Store文件格式，它支持跨平台统一的Archive操作，但还是避免不了一个难以接受的缺陷——增大了客户端存储空间的占用。

       相比于ZIP压缩文件，Store文件由于未压缩，体积很大。在某些情况下传输全量Store包的流量消耗也就变大了。如果我们对于全量Store包再进行压缩，则给客户端带来了新的复杂度。那就是资源包具有多种格式，有的要解压两次，有许多异常的可能性，这给客户端带来的负担太沉重。我们需要有另外的方法来差分资源。

3.最佳实践方案：FolderBsdp

       为解决上一章的问题，我们创新性地提出FolderBsdp方案。FolderBsdp是以文件间的Bsdp算法为基础，对有目录层级结构的文件夹进行差分。具体来说，它由FolderBSDiff（求差分）和FolderBSPatch（打补丁）两个算法相结合。

3.1FolderBSDiff的具体算法

       先比较新旧文件夹的目录结构和内含文件，新文件夹相对于旧文件夹所产生的变动包括五种情况：新增目录、删除目录、新增文件、删除文件、修改文件。

       对于新增目录、删除目录、删除文件的情况，记录下对应的操作；对于修改文件，调用BSDiff函数。我们基于直接资源里的每一个文件的内容修改求BSDiff，留下其Patch文件体积足够小，避开了压缩不利差分性质的困境；对于新增文件，则记录下所增文件的相对路径，并拷贝此文件。

       我们把这些操作按照一定顺序（新增目录要在最前，删除目录要在最后）汇总到一个JSON文件里。并且把BsDiff求出的各个Patch文件和新增的文件保存下来，这些文件通过ZIP压缩算法为一个ZIP文件，即为FolderBSDiff的Patch文件。这个文件的体积与Store文件之间求BSDiff类似，也同样（相对于ZIP压缩包之间的BSDiff）节约了约%的体积。这个Patch可以用于对应的打补丁操作（FolderBSPatch）。

优点一：在客户端侧打补丁时内存占用低

       在打补丁操作时，我们需要把旧文件和补丁包加载到内存里，在执行完成前，新文件也在内存里。FolderBSPatch针对逐个资源文件，按顺序串行操作，“化整为零”，相比于ZIP包的BSPatch，内存占用更低，更不影响用户体验。

       根据实际测算，相比于ZIP包的BSPatch，使用FolderBSPatch在客户端侧打补丁的内存峰值占用少了%。

       内存考量——在客户端侧降低内存占用是一个优点。

       在RN资源包更新这个情境中，FolderBSPatch这一优点非常有必要，因为打补丁的过程是在App运行时的后台进行，与此同时用户很可能还在积极使用App。此外，我们预期Shopee主要市场的用户手机内存配置较低。

优点二：节约存储空间

       在客户端侧，基于FolderBsdp可以舍弃掉储备文件，无论是ZIP压缩资源包，还是上文讨论的Store资源包。

       在之前的算法中，因为ZIP不确定性，我们留存ZIP压缩包或Store文件在客户端。文件留存的唯一目的就是为了打补丁，没有其他用处，非常浪费存储空间。

       从时间线上来看，根据FolderBsdp也形成了客户端侧的“RN更新链”，如下图所示：

       以Shopee内某个App为例，客户端总包体积MB，其中RN的ZIP压缩包约8MB，使用FolderBsdp后，不再需要ZIP包，App也就“瘦身”了。

       空间考量——节约掉储备文件所占的体积是一个重要的优点，我们要尽量做到。

优点三：不需要ZIP库

       在客户端，我们不再需要调用ZIP的解压算法，iOS端也就不再需要依赖ZIP库或其他压缩库（Android内置无法删除）。虽然我们需要引入FolderBSPatch，但其代码不过一百行左右，没有大型依赖，体积远小于ZIP库，符合精简依赖考量。

优点四：附带更精确的MD5校验

       我们可以把每一个新增、删除、修改文件的MD5值保存在JSON文件中，在打补丁操作时进行校验，更自信地确认我们的操作是正确无误的。

4.FolderBsdp与业界其他方案的对比4.1Google的archive-patcher

       Google考虑到了ZIP压缩文件之间求BSDiff破坏了原始字节流相似性的缺陷（压缩不利差分性质），产生了逐个文件恢复出其原始字节流并且求差异的方案，很好地解决了这个问题。

       另一方面，因为跨平台的差异性（ZIP不确定性），此方案不可避免地需要在客户端保留ZIP压缩资源包。

       这与我们追求尽可能节约存储空间的目标背道而驰（空间考量），因此不应该被采用。而本文提出的FolderBsdp方案很好地克服了archive-patcher的这一缺点。

4.2其他方案

       增量更新领域中有另一知名的开源项目，作者使用C++自行编写算法，将目录下各文件以不压缩的状态合并起来进行差分，即本文Store文件思路。FolderBsdp与此方案对比的优点是打补丁时更加节约内存（内存考量）。本文所述的RN资源更新，是在用户活跃使用App时后台静默更新，也考虑到Shopee主要用户群体手机内存配置较低的特点，FolderBsdp算法这一优点很重要。

       此外，有方案对差分包的压缩格式进行扩展，使其不局限于ZIP格式，也可以支持其他压缩库。这个灵活性在某些场景适用。但在本文情境中，App的精简依赖考量更加重要。本文提出的FolderBsdp算法利用标准bsdp和AndroidSDK自带的ZIP库，不需要安装其他格式的压缩库。FolderBsdp的补丁包体积与其他压缩格式差异不大。

5.总结

       本文所介绍的FolderBsdp方案降低了打补丁时的内存峰值，避免了在客户端保留多余的ZIP包占用空间，额外提供了逐个文件的MD5精准校验，无需新增依赖库，因为用各端原生开发语言实现而具有兼容性。兼具各种优点，FolderBsdp成功实现了增量更新功能，是多番探索之下总结出来的RN资源增量更新的最佳实践。

       本文作者

       Pei，来自Shopee商家服务前端团队。

原文：/post/