作者 | Sapan Bhatia

翻译者 | 张健欣

策画 | 褚杏娟

在 Facebook 上管理插件的大小不一是一个独特的挑战：合作开发人员每天都要检查和大量的标识符，第一行标识符最终单厢转化为人们浏览到手机上的插件中的附带位。如果不加检查和，那些加进的标识符会使插件越来越大，直到浏览插件所需的时间变得不可接受。

填充是他们用来维持插件大小不一最强化的方式之一。那些填充过的文件挤占更慢的内部空间，这意味着更小的插件浏览地更快，全球数千万使用者采用更慢的频宽。在终端光纤非常有限的地区，这样的节约尤其重要，因为非常有限的频宽会使浏览小型插件的耗费极高。但仅靠填充还足以跟得上他们所做的所有预览和加进到插件中各种功能的脚步。因而，他们合作开发了一种称为“Superpack”的控制技术，它将C++分析和统计数据填充并重，拓展出胜过传统填充工具能力的强化。Superpack 冲破了填充无限大，实现了比原有填充工具更好的填充率。

在过去两年中，Superpack 已经能控制合作开发人员导致的插件大小不一增长，并维持他们的 Android 插件模组化。Superpack 的填充有利于增大他们的 Android 插件群的大小不一，这与常规性 Android APK 填充较之要大得多，与 Android 的预设 Zip 填充较之节约了 20% 以上内部空间。采用 Superpack 的插件包括 Facebook、Instagram、WhatsApp 和 Messenger。那些插件由于 Superpack 而增大的大小不一如下表所示表右图。

Superpack：C+++统计数据填充

虽然原有的填充演算法，例如 Zip 的 Deflat 和 Xz 的 LZMA，能较好地处理小型乙烯统计数据，但它们足以抵销他们在插件中看到的发展速度，因而他们开始合作开发自己的软件系统。填充是一个成熟的应用领域，他们合作开发的控制技术横跨了整个填充应用领域，从统计数据填充和 Lempel-Ziv（LZ）导出到统计代码。

Superpack 的优势在于填充代码，如机器语言和二进制码，以及其他类型的形式化统计数据。Superpack 的下层方式是如前所述 Kolmogorov 的演算法复杂程度测度 的设想，将一段统计数据的网页内容表述为聚合该统计数据的最短流程的宽度。换言之，能通过将统计Luzy成能聚合这段统计数据的流程来填充统计数据。当统计数据是标识符时，能将其转化成更小的填充后的表示。聚合斐波异或有理数及其检索条目的流程，是包含那些有理数的文件的高度填充表示。降低 Kolmogorov 复杂程度本身的设想对于填充应用领域并不新鲜。Superpack 的新方式涉及将C++方式与现代填充控制技术并重来实现这一目标。

将聚合小型流程的聚合过程作为填充的形式有很大的好处。这为统计数据填充工程师提供了一系列成熟的编译工具和控制技术，那些工具和控制技术能更改用途进行填充。Superpack 填充利用常见的C++控制技术，例如导出和标识符聚合，以及最近的创新，例如 Satisfiability modulo theories (SMT) 求解器，来找到最小的流程。

能将那些C++控制技术与主流统计数据填充中采用的控制技术结合起来，这是 Superpack 有效性的一个重要组成部分。来自C++的语义知识占了 Superpack 的一半，造就增强的 LZ 导出（消除冗余的填充步骤），以及改进的熵代码（为频繁的信息片段聚合短代码的步骤）。

改进的 LZ 导出

填充器通常采用从 LZ 家族中选择的演算法来识别重复的二进制序列。大体上，每一个这样的演算法都试图用指向以前出现的统计数据的指针来替换重复出现的统计数据序列。这个指针由上一次出现的距离（二进制数）和序列宽度组成。如果这个指针能用比实际统计数据更慢的位表示，则能用之替换作为填充大小不一。Superpack 通过发现更长重复序列，同时减少表示指针的位数，从而改进了 LZ 导出过程。

在被填充的流程中，Superpack 通过如前所述 AST 对统计数据进行分组来实现那些改进。例如，在以下指令序列中，最长重复序列的宽度为 2。然而，当根据 AST 类型（即操作码和寄存器，小表中的组 1）和立即数（下表中的组 2）进行分组时，宽度增加到 4。在原始统计数据的原始导出中，重复序列之间的距离是 2 条指令。但在分组后的版本中，距离为 0。更小的距离通常采用更慢的位数，更长的序列匹配通过在给定指针中捕获更多的输入统计数据来节约内部空间。因而，Superpack 聚合的指针比简单计算的指针要小。

但是，他们如何决定何时分隔标识符流以及何时维持原封不动？Superpack 最近的工作中引入了分层填充，这将此决策合并到 LZ 导出的强化组件中，称为最优导出。在下面编辑过的标识符中，最好将标识符段的最后一段保留为原始形式，并聚合一个指向前五条指令的指针的匹配项，同时拆分标识符段的其余部分。在拆分余数中，利用寄存器组合的稀疏性来聚合更长的匹配。以这种方式对标识符进行分组还能通过计算重复序列之间的逻辑单元数量（沿 AST 测量）而不是测量二进制数，来进一步缩短距离。

改进的熵代码

重复的二进制序列被指向上一次出现的序列的指针有效地替换。但是填充器对非重复序列或比指针表示更短的短序列能做些什么呢？在这种情况下，填充器通过对统计数据中的值进行代码来表示统计数据。用来表示序列的位数，利用了序列能假定的值的分布。熵代码是用统计数据中的值的熵的位数来表示一个值的过程。压缩器为此目的采用的一些众所周知的控制技术包括哈夫曼代码、算术代码、距离代码和非对称数字系统（asymmetircal numberal systems，ANS）。

Superpack 有一个内置的 ANS 代码器，还有一个可插拔的架构，支持多个这样的代码后端。Superpack 通过识别上下文（其中要表示的序列由较低的熵）来改进熵代码。与 LZ 导出类似，那些上下文是从 Superpack 对通过C++分析提取的统计数据结构的了解中派生出来的。在下面简化的指令序列中，有七个不同的地址，每个地址都有前缀 0x。在该代码的大量不同排列中，常规性代码器用于表示地址字段的位数将接近 3。

然而，他们注意到，七个地址中有三个与 BL 操作码配对，而另外三个与 B 操作码关联。只有一个地址与两者都耦合。如果这个模式在整个标识符体中都成立，那么操作码能用作代码上下文。在这种情况下，表示这七个地址的位数接近 2 而不是 3。下表显示了带上下文和不带上下文的代码。在第三列中的 Superpack 填充情况下，能将操作码视为预测丢失的位。这个简单的示例旨在说明如何采用C++上下文来改进代码。在实际统计数据中，获得的位数通常是分数，上下文和统计数据之间的映射很少像本例中那样直接。

作为填充表示的流程

他们解释了当被填充的统计数据由标识符组成时，Superpack 如何改进 LZ 导出和熵代码。但当统计数据包含非形式化值时会发生什么？在这种情况下，Superpack 试图通过在填充时将值转换为流程来加进值结构。然后，在解压时，将流程进行导出来恢复原始统计数据。这种控制技术的一个例子是 Dex 检索的填充，Dex 检索是 Dex 代码中已知值的标签。Dex 检索具有高度的局部性。为了利用这种局部性，他们将检索转换为一种将最近的值存储在逻辑寄存器中的语言，并将即将出现的值作为固定值的增量发布。

为这种表示编写一个高效的填充器会导致C++中常见的寄存器分配问题，该问题决定何时从寄存器中收回旧值来加载新值。虽然这种减少是针对检索二进制码的，但一个通用的设想适用于任何二进制码表示，即，聚合的标识符符合前两节中概述的强化。在本例中，LZ 导出通过将操作码、MOV 和 PIN 放在一个组中、在第二个组中收集增量、以及在第三个组中收集最近的检索而得到改进。

如前所述真实统计数据的 Superpack

Superpack 有 3 个主要的有效载荷目标。第一个是 Dex 二进制码，在 Android 插件中 Java 被编译成的格式。第二个是 ARM 机器语言，这是针对 ARM 处理器编译的标识符。第三个是 Hermes 二进制码，它是在 Facebook 创建的 JavaScript 的专用高性能二进制码表示。所有这三种表示都采用了全方位的 Superpack 控制技术，那些控制技术由如前所述标识符语法和语法知识的C++分析提供支持。在这三种情况下，有一组填充转换应用于指令流，另一组填充转换应用于元统计数据。

应用于标识符的转换都是相似的。元统计数据转换有两部分。第一部分通过按类型进行分组来利用统计数据的结构。第二部分利用元统计数据规范中的组织规则，例如导致对统计数据进行排序或公开可用于上下文距离和序列项之间的相关性的规则。

Zip、Xz 和 Superpack 针对这三种格式的填充率如下表所示表右图。

Superpack架构和实现

Superpack 是填充应用领域的一个独特玩家，因为它包含有关填充统计数据的类型知识。为了在 Facebook 推广 Superpack 的合作开发和采用，他们合作开发了一个模块化设计，其中的抽象能跨不同的填充格式采用。Superpack 的架构类似于操作系统，其内核实现分页内存分配、文档和归档抽象、用于转换和操作指令的抽象，以及可插拔模块的接口。

面向C++的机制属于专门的C++层。每种格式都实现为一个可插拔的驱动流程。驱动流程利用被填充统计数据的属性，并在标识符中标记相关性，最终被填充层利用。导出输入标识符的机器采用如前所述 SMT 导出器的自动推理。他们如何采用 SMT 求解器来帮助填充超出了本文的范围，将成为未来一篇博文的有趣话题。

填充层还包括可插拔模块。其中一个模块是 Superpack 自己的填充器，包括一个定制的 LZ 引擎和一个熵代码后端。在他们构建这个填充器的过程中，他们插入了利用原有填充工具进行填充工作的模块。在该装置中，Superpack 的角色简化为将统计数据重新组织为不相关的流。随后，原有工具会尽最大努力进行填充，这是有效的，但在识别和采用C++信息的粒度上受到限制。Superpack 的定制填充后端通过统计数据的内部表示的细粒度视图解决了这个问题，这使它能利用单个位的细粒度的逻辑相关性。将用于执行填充工作的机制抽象为一个模块，能让他们在填充率和解压速度之间选择一些平衡。

Superpack 的实现包含用 OCaml 编程语言编写的标识符和 C 语言标识符的混合。OCaml 在填充端用于操作复杂的面向C++的统计数据结构，并与 SMT 求解器进行接口对接。C 语言是解压逻辑的自然选择，因为它往往很简单，同时对解压标识符运行的处理器的参数高度敏感，例如一级缓存的大小不一。

限制和相关工作

Superpack 是一个非对称填充器，这意味着解压速度很快，而填充速度能很慢。流式填充，即统计数据以其传输速率进行填充，一直不是 Superpack 的目标。Superpack 无法满足流式填充的约束条件，因为其当前的填充速度跟不上现代统计数据传输速率。Superpack 已经应用于形式化统计数据、标识符、整数和字符串统计数据。Superpack 当前不以图像、视频或音频文件为目标。

在 Android 平台上，在采用填充来减少浏览时间和可能增加磁盘挤占和预览大小不一之间存在一种平衡。这种平衡不是 Superpack 的限制，而是 Facebook 采用的打包工具和 Android 上采用的分发工具之间尚未建立互操作性。例如，在 Android 上，插件预览是作为插件连续版本内容之间的增量发布的。但这种增量只能由能解压和重新填充插件内容的工具聚合。由于当前工具中实现的差异对比过程无法导出 Superpack 文档，因而对于包含此类文件的插件，增量会变得更大。他们相信，这类问题能通过 Superpack 和 Android 工具之间更细粒度的接口、Android 分发机制中更高的可定制性以及 Superpack 文件格式和填充方式的公开文档来解决。Facebook 的插件主要由 Superpack 擅长填充的标识符组成，其填充方式远远超过了 Android 上 Google Play 实现的原有填充方式。因而，就目前来说，他们的填充对他们的使用者来说是有益的，尽管存在权衡。

Superpack 利用 Jarek Duda 在非对称数字化系统上的工作作为其熵代码后端。Superpack 借鉴了其“超强化（superoptimization）”思想，以及过去在标识符填充方面的工作。它利用 Xz、Zstd 和 Brotli 填充器作为可选后端来完成填充工作。最后，Superpack 采用微软的 Z3 SMT 求解器来自动导出和重构各种标识符格式。

下一步计划

Superpack 结合了C++和统计数据填充控制技术，以一种特别适用于标识符（例如，Dex 二进制码和 ARM 机器语言）的方式增加打包统计数据的密度。Superpack 大幅缩减了 Android 插件的大小不一，从而为全球数千万使用者节约了浏览时间。他们已经描述了 Superpack 背后的一些核心思想，但只触及了他们在不对称填充方面的工作的表面。

他们的旅程才刚刚开始。Superpack 通过对其C++和填充组件的增强来不断改进。Superpack 最初是作为一种工具来减少终端插件的大小不一，但他们在提高各种统计数据类型的填充率方面的成功，使他们将目标对准了非对称填充的其他用例。他们正在合作开发一种新的按需可执行文件格式，通过在加载时保留填充和解压共享的库来节约磁盘内部空间。他们正在评估采用 Superpack 对标识符进行增量填充来减少软件预览的大小不一。他们还在研究将 Superpack 用作冷存储填充器，以填充很少采用的日志统计数据和文件。

到目前为止，他们的终端部署仅限于 Android 插件。然而，他们的工作也同样适用于其他平台，例如 iOS，而且他们也正在考虑将他们的实现移植到那些平台。目前，只有他们的工程师能采用 Superpack，但他们渴望将 Superpack 的好处带给每一个人。为此，他们正在探索提高他们的填充工作与 Android 生态系统兼容性的方式。这篇博文是朝着这个方向迈出的一步。有朝一日他们可能考虑将 Superpack 开源。

他们要特别感谢 Alfredo Altaminaro、Nikhil Prakash、Mauricio Nunes 和所有为 Superpack 做出贡献的人。

原文链接：

https://engineering.fb.com/2021/09/13/core-data/superpack/