本文最初发表在微信公共帐户“ Shopee技术团队”中。
Shopee的许多移动应用程序都是混合（混合）本机和React Native的应用程序（以下称为“ RN”）。当用户打开应用程序时，客户端将启动请求以查看是否有RN资源的新版本。将最新资源推向所有用户。
另一方面，尽管RN资源将被更新和迭代，但新版本的差异实际上仅占一小部分，使用户可以下载全部资源不仅浪费用户流量，而且还会影响用户的体验该应用程序（因为背景的安静更新仍将在带宽资源中拥挤。
自然，我们会想到“增量（差异）更新”，客户只下载了新的和旧的RN资源的差异。此差异汇总到文件中，该文件称为增量软件包（或补丁程序包）。下载和验证补丁程序包的合法性，可以将其合并到新版本中，以保存流量。
考虑到Shopee主要市场的网络条件，数据流量的节省特别重要，但是这种增量软件包应该是什么样的？本文将以逐步思考分析各种计划的优势和缺点，包括探索所产生的方案Shopee的练习过程以及行业提供的计划。最后，提出了FolderBSDP算法以区分直接资源并实现增量更新。
RN资源包括翻译的JavaScript代码，各种语言，例如JSON文件，图片和其他媒体资源和配置文件。我们将这些资源称为“直接资源”。它们是RN包装的直接产品，它们也是每日客户端的存在表格呼叫。如果这些“直接资源（原始文件）”在CDN上，则保留了新的和旧资源的文件目录，并且可以下载新添加和修改的文件。
有两个主要缺点：
1）多样化的传输很容易犯错。如果有新图片和修改翻译文件，则需要向CDN下载文件启动多个HTTP请求。这将使复杂和更新异常的处理情况，例如恢复某些文件下载过程中断。
2）大型传输流量流图和翻译JSON文件使用原始文件来传输废物数据流量，因为这些资源可以被压缩。翻译文件很大，但是每个版本的修改通常是少数新行，并且那里不需要直接传递整个文件。因此，传输级别的SO称为“差异”部分仍然太大。
为了避免2.1中的问题，我们引入了差异算法以实现增量更新。
文件之间的微分算法是实现增量更新的一种方法。差分算法的输入参数是两个新文件和旧文件。输出是两个文件中的差异，即补丁程序，即补丁包（也称为增量软件包）。
差分算法还具有支持碎片。它的参数是旧文件和补丁，输出是新文件。不同的微分算法具有其自己的优点和缺点，这些算法反映在差分和修补操作的时空时间复杂性，补丁程序卷和补丁内容内容的可读性中。
BSDIFF算法是一种非常流行的差分算法。它专注于尽可能小（适合通过网络传输的更新方法）。
BSDIFF算法是开源的，免费。它是用C语言编写的。源代码可以在服务器上执行Android/iOS。BSDIFF算法BSPATCH的BSPATCH可以与旧文件和补丁结合使用以还原新文件。BSDIFF和BSPATCH算法也称为BSDP算法。
与“ 2.1直接传输差（原始）文件”相比，如果仅BSDIFF生成的补丁的差异确实可以减少传输数据流量并加速下载过程。但是，它没有解决经常启动HTTP请求的问题下载每个文件。我们需要一种合并资源并将其下载在一起的方法。
考虑到各种资源文件的分散传输（2.1和2.2）的缺点，改进方法是在编译过程中将RN直接资源文件放入文件夹中，然后使用zip工具将其压缩到文件中。用于压缩资源的patch要实现初始安装和后续更新。
具体而言，RN包装的直接乘积包含JS代码，翻译JSON，图片和配置文件的某个目录结构。所有这些文件都将压缩到ZIP压缩软件包。当应用程序最初安装时，有此ZIP软件包和其解压缩的RN资源。
在使用该应用程序的过程中，如果有新版本的RN资源，请下载相应的补丁文件，然后将BSPATCH算法与先前的ZIP压缩软件包（当时RN资源时未删除客户端）获取ZIP压缩软件包的新版本。该新版本的ZIP压缩软件包保留在用户的手机中，以便生成下一个新的ZIP软件包，重复并连续更新。ZIP压缩软件包的解压缩后，可以直接使用它。
从时间轴的角度来看，此更新也是版本迭代，形成了下图所示的更新关系，称为“ RN更新链”。
该解决方案的优点是克服分数文件方案的缺点。通过zip压缩文件，集成了多个文件，资源表格变得简单，HTTP请求的数量也减少了。对于完整的包，它减少了当Shopee的业务包没有压缩时，所有资源总共有14MB，压缩后约有4MB。
但是，该解决方案隐藏了一个缺陷的缺陷，这使该计划很大程度上可以改进。该缺陷是邮政压缩过程会影响文件的外观，并扩大了旧文件和新文件的差异。结果，邮政压缩软件包之间的贴片体积太大。详细说明了以下解释。
BSDIFF属于“块移动”算法。为了记录要恢复的旧文件和旧文件的差异，它使用动态的计划算法 - 最长的公共后续序列。
对于新文件的内容，它试图从旧文件中找到最长的公开后续序列，并记录新文件的内容相对于旧文件的位置的更改。文件的内容组装到新文件。
有关其他差异，它记录了差异及其在新文件中的位置。这些记录的内容和位置信息在被BZIP2压缩后获得的补丁文件。复制和插入包含补丁文件的副本和插入信息可以将旧文件转换为运行bspatch时的新文件。
简单的示意图如上所述。蓝色和绿色块是相同的内容，但它们以不同的方式出现在文件中。补丁记录位置信息。红色是额外的（额外），补丁文件记录了其位置和内容本身在新文件本身中。这些记录形成的指令允许我们使用旧文件和补丁还原新文件。
结果，我们意识到重复内容和记录位置（蓝色，绿色块）所需的信息量很小；对于其他块，我们不仅必须记录位置偏移量，而且还必须保留在补丁文件中。它的内容本身（尽管可以压缩）。位置偏移占用的补丁文件的体积远小于内容的量。额外内容越少（类似的新文件），补丁文件的卷越小。
编码算法的LEMPEL-ZIV是ZIP压缩算法的重要组成部分，该算法也称为“滑动窗口压缩”。该算法的核心思想是在先前的历史数据中找到重复的字符串。
但是，它不是回到文件标头，而是考虑到重复内容的局部性质，它设置了一个范围（常见为32kb）。这32KB窗口用编码向前滑动。理论上，如果此滑动窗口更大，我们就有找到重复字符串的更好机会，但这将增加计算量。32KB是ZIP的折叠设置。
在上图中，当编码到“确定”时。（对，蓝色标记），发现重复“好”。（左，蓝色标记）在向后滑动窗口中。lz算法记录了“确定”。从当前位置（距离）和长度的左侧，然后前进到下一个字符。在压缩结果文件中，“确定”。这里将保留，然后表示重复的“好”。在距离+长度的切片窗口中。这样，“好。”重复并保存卷。如果重复的字符更长，则压缩效果将更加明显。
如果此字符略微修改，则LZ算法的编码结果将产生巨大的变化。
考虑到上面的第二行中的情况，如果“！”（绿色标记）被插入，编码可能会产生两个变化。
第一个更改是扫描正确的“确定”。在编码期间，相应的左重复字符的距离发生了变化（距离值的变化将产生一系列其他副作用）。
第二个可能的更改是因为字符被插入，并且“确定”。左侧超过了滑动窗口的左侧，因此“确定”。在右边找不到。
考虑到上面的第三行中的情况，如果“！”（橙色标记）被插入，原始的“好”。重复的字符不再存在，编码产生了巨大的变化。
另外，huffman在zip压缩算法中的编码链接，无论是字符，距离还是长度，它都不会由其真实值表示，但是使用了霍夫曼编码。更常见的是，出现，较短的字符较短。由更常见的字符表示。此外，保留了字符编码和原始字符的相应表。
上面的第二行和第三行的情况会影响文字，距离和长度不同值的频率，这也影响其相应的编码。该代码的影响是全局而不是部分。
其他主流压缩算法与拉链压缩算法的原理相同。为了追求压缩比，微妙的差异也将产生全球影响。
从中，我们可以知道：
压缩文件可能会破坏新旧RN资源的字节流的相似性。通过压缩文件获得的补丁音量进一步减少。
根据原始RN资源流量计算BSDIFF是值得探索的方向。
为了求解2.3（）的缺陷，我们试图以不压缩的方式将包含每个文件的直接资源合并为大文件，以便原始字节在原始外观中流入文件中。原始文件和目录结构。通过此方法，将不会破坏原始字节流功能。我们将这样的文件称为商店文件，即没有压缩功能的存档文件。
它的主流实现具有ZIP的存储模式（还使用ZIP工具，但不执行ZIP压缩算法）和焦油文件格式。邮政编码模式的资源执行BSDIFF算法（与压缩文件相比），约为84％卷。但是，该计划也有自己的缺陷。
生成ZIP的商店文件非常简单。所有ZIP工具都有存储模式。一般而言，当生成ZIP软件包时，输入布尔值将设置为true。解压缩/UNBLOCKED时，它不需要其他参数。考虑使用ZIP的存储模式主要是因为Android SDK本来支持ZIP文件的生成和解压缩/解除zip文件，这是包含许多应用程序的Shopee公司的主要优势。它不仅节省了软件包的卷（重要），还可以减少协调不足。
- 在客户上，我们不会尽可能多地安装其他依赖项。
这似乎是最佳解决方案，但实际上，我发现该解决方案存在问题：Zip Store文件在两端不兼容。
具体的问题是，在后端node.js中，使用公共Archiver库生成的存储文件未通过Android Native Zip库标识，并且不能取消结合。此也在Internet上广泛讨论，请参见Stackoverflow。
提出的解决方案是Android还安装了Oracle的邮政编码，这彼此相反，不是一个绝佳的选择。
因此，您是否使用直接资源在Android客户端上生成ZIP Store文件？答案是负面的。因为商店文件和服务器端由Android客户端生成的侧面生成不同，并且服务器上的补丁程序基于服务器 -基于商店文件以查找BSDIFF。即使字节有差异，它就无法成功。因此，我们不能让客户端生成商店文件。定义的算法（非确定性算法），这将使迷恋算法失败。
- 跨平台差异使客户无法通过直接资源生成ZIP压缩软件包或ZIP存储软件包。
焦油文件格式在UNIX系统中非常受欢迎。这是一个仅执行压缩的仅存档文件（本文称为商店文件）。焦油文件格式不可避免地包含各种平台独有的元数据。在某些平台的库中，没有选项可以完全删除元数据。
上面说明了Zip Store文件和TAR文件的缺陷。假设我们找到了出色的商店文件格式。它支持交叉平台的统一存档操作，但仍然无法避免不可接受的缺陷 - 客户端口空间职业。
与zip压缩文件相比，商店文件很大，因为它不被压缩。在某些情况下，商店包的交通消耗变得更大。如果我们压缩了完整的商店包，我们为客户带来了新的复杂性也就是说，资源软件包具有多种格式，有些需要两次解压缩。有许多不寻常的可能性，这太重了，无法给客户带来负担。我们需要另一种方法来差异资源。
为了解决上一章的问题，我们创新提出了folderbsdp解决方案。folderBSDP基于文件之间的BSDP算法，并且具有目录级别结构的文件夹是区别的。它是由两个算法组合在一起的：folderbsdiff and fillersbspatch。
首先比较旧文件夹的目录结构和内部文件。旧文件夹的新文件夹的更改包括五个情况：新目录，删除目录，新文件，删除文件和修改文件。
对于新目录，删除目录和删除文件，请记录相应的操作；要修改文件，请调用BSDIFF函数。基于直接资源中每个文件的内容上的内容，我们修改BSDIFF，将补丁文件留下少量卷并避免其困境；对于新文件，记录附加文件的相对路径并复制此文件。
我们将以一定顺序总结这些操作（新目录在顶部，将目录删除到末尾）。这些文件是通过zip压缩算法的zip文件，即folderbsdiff的补丁文件。该文件的卷与商店文件中的BSDIFF和相同的bsdiff相似（BSDIFF与zip Compressions之间的BSDIFF相比软件包）节省了约84％的卷。此补丁可用于相应的修补操作（FolderBspatch）。
优点1：修补客户端时，记忆职业在修补操作时较低，我们需要将旧文件和补丁包加载到内存中。在执行完成之前，新文件也在内存中。folderBspatch操作以使资源文件一一并按顺序“变成零”。与ZIP软件包的BSPATCH相比，内存较低，并且不会影响用户体验。
根据实际计算，与ZIP软件包的BSPATCH相比，folderbspatch在客户端修补的内存峰值的内存峰值小于40％。
- 客户端的内存职业是一个优势。
在RN资源软件包中的这种情况下，FolderBspatch的优点非常必要，因为要在应用程序的背景下进行补丁过程。同时，用户可能会积极使用该应用程序。此外，我们希望用户的手机存储器配置在Shopee的主要市场中较低。
优点2：将存储空间保存在客户端的侧面。基于folderbsdp，您可以放弃储备文件。无论是ZIP压缩资源软件包还是上面讨论的商店资源软件包。
在上一个算法中，由于ZIP不确定性，我们将ZIP压缩软件包或存储文件保留在客户端上。文件保留的唯一目的是修补，没有其他用途，并且是浪费存储空间。
从时间轴的角度来看，根据FolderBSDP的说法，客户端的“ RN更新链”也形成了，如下图所示：
以Shopee中的某个应用程序为例，客户总包装为202MB。其中，RN的拉链压缩套件约为8MB。使用FolderBSDP后，不再需要ZIP软件包，并且该应用程序“缩小”。
- 燃烧储备文件的数量是一个重要的优势，我们必须尝试做到这一点。
优点三：客户端不需要邮政库。我们不再需要调用ZIP的解压缩算法，iOS端将不再需要依靠ZIP库或其他压缩库（无法删除Android）。尽管我们需要介绍folderbspatch，但它的代码仅大约是一个大约一个一百条线，没有大的依赖项，而且音量远远远远远远少于排队的ZIP库。
优点4：通过更准确的MD5验证，我们可以保存每个新的，删除的MD5值，并在JSON文件中修改文件，并检查修补操作。
Google认为，考虑了原始字节的原始字节的原始字节的原始字节的相似性缺陷已考虑。
另一方面，由于Cross -platform（）的差异，此解决方案不可避免地需要将ZIP压缩资源软件包保留在客户端上。
这是我们追求尽可能节省存储空间的目标（），因此不应采用。
增量更新领域中还有另一个知名的开源项目。作者使用c ++编写算法，以未压缩差异的状态在目录中合并每个文件，也就是说，商店文件对本文的思考。与此解决方案相比，folderbsdp的优势是保存内存时Patching（）。本文中描述的RN资源更新是用户主动使用该应用程序时的背景中的无声更新。它还考虑了Shopee主要用户组的较低手机存储器配置的特征。FolderBSDP算法的优点很重要。
此外，还有一个计划扩展差分软件包的压缩格式，因此它不限于ZIP格式并可以支持其他压缩库。此灵活性适用于某些场景。更重要的是。本文提出的FolderBSDP算法使用Android SDK随附的标准BSDP和ZIP库，而Android SDK不需要安装其他格式压缩库。FillbSDP的补丁程序包的音量与其他压缩格式没有太大不同。
本文中描述的FolderBSDP解决方案在修补修补时降低了内存峰，避免了客户端上的多余ZIP软件包以占用空间，并提供了准确的MD5准确验证文件。无需添加新的依赖项，因为每个端的本机都是本地的。这是通过多次探索总结RN资源逐步更新的最佳实践。
作者
PEI，来自Shopee Merchant Service的前端团队。
原始：https：//juejin.cn/post/7099686565365940261