Bazel 新增内容定义分块

# 远程缓存 CDC：字节复用 | BuildBuddy 来源：https://www.buildbuddy.io/blog/content-defined-chunking/ 新内容被添加到已复用内容中 *目标：传输发生变化的字节，而非整个输出文件。* BuildBuddy 的远程缓存采用内容定义分块（Content-Defined Chunking，CDC），使大型构建输出更具增量性。当二进制文件、包、归档文件基本未变时，BuildBuddy 可以复用已见过的数据块，而无需重新上传或重新下载整个文件。 在我们的 Bazel 分块实现 PR（https://github.com/bazelbuild/bazel/pull/28437）中，在 BuildBuddy 自身仓库的基准测试中，观察到上传数据减少 40%，磁盘缓存缩小 40%。要使用 BuildBuddy 启用客户端 CDC，请使用 Bazel 8.7 或 9.1+，并传入参数 `--experimental_remote_cache_chunking`。 ## 场景设定（https://www.buildbuddy.io/blog/content-defined-chunking/#setting-the-scene） 构建缓存的下一个前沿并不仅仅是跳过操作，而是跳过字节。 构建缓存已经取得了长足进步。不再是每次编辑后重新构建整个世界，Bazel 和远程缓存让团队能够在不同机器和 CI 作业间复用操作输出。实际上，构建已从接近“仓库规模”向“变更规模”转变。 但“变更规模”可能具有误导性。真正重要的是编辑所影响的传递性操作的大小。一个小的源代码变更仍可能波及许多二进制文件、包、归档文件和其他大型输出，即使每个输出中只有一小部分实际发生变化。 这种失效是预期的。构建系统应在输入变更时重新运行操作。远程缓存的问题在于接下来发生的事：缓存看到一个新的摘要，然后移动整个数据块，即使该数据块与先前版本大部分字节相同。 ## 传递性操作（https://www.buildbuddy.io/blog/content-defined-chunking/#transitive-actions） 链接、打包、归档是这种情况最常见的场景。它们将许多传递性输入合并成一个输出。 这使得它们与针对少量直接文件的操作不同。一个典型的编译操作可能编译一个源文件，使用较小的直接输入集。而传递性操作则往往消耗许多依赖项的累积输出，并生成一个最终的二进制文件、包或归档文件。 在 Bazel 规则中，这通常表现为一个规则通过传递的 `depset` 收集文件，并将累积的文件集传递给单个操作。例如，一个简化的编译操作可能像这样： ``` ctx.actions.run( inputs = [src] + direct_headers, outputs = [obj], executable = compiler, arguments = ["-c", src.path, "-o", obj.path], ) ``` 而打包或归档操作则更像这样： ``` transitive_inputs = depset( direct = direct_files, transitive = [dep[MyInfo].files for dep in ctx.attr.deps], ) ctx.actions.run( inputs = transitive_inputs, outputs = [bundle], executable = bundler, arguments = ["--output", bundle.path], ) ``` 第二种模式正是小源代码变更可能扩散为大型输出变化的地方。源代码编辑可能只改变最终输出中的一小段字节序列，但输出摘要是全新的。 没有 CDC，缓存会将其视为全新的数据块，即使大部分二进制文件、包、归档文件与先前版本逐字节相同。如果多个最终输出依赖于该变更的输入，它们都会获得新的摘要。 对于远程缓存来说，昂贵之处不仅在于输出体积大，更在于输出体积大且与缓存已有的内容大部分相似，但整个数据块的摘要是全新的。 这带来了两个问题： - 上传和下载移动整个数据块，即使只有小部分发生了变化。 - 存储保留另一个完整的数据块，即使大部分字节是重复的。 一种解决方法是针对这些操作禁用远程缓存。这样可以避免在预期缓存命中不抵写入成本时上传大型输出，但这又产生了另一个问题：该操作现在每次都必须运行。同时，这也会使操作更难以迁移到远程执行，因为 RBE 依赖于高效地移动操作输入和输出。 因此，构建避免了一次昂贵的缓存写入，但完全放弃了复用。 传递性操作坍缩 *一个小源变更可能导致最终传递性操作失效。* ### 案例研究：Go 测试（https://www.buildbuddy.io/blog/content-defined-chunking/#case-study-go-tests） 一个常见示例是共享的 `go_library`，比如 `foo`，它被许多其他库导入：`bar1`、`bar2`，一直到 `barN`。每个 `bar` 库可能也有自己的 `go_test`。 对 `foo` 的仅实现变更可能只重建 `foo` 自身的 `GoCompilePkg` 操作。下游编译操作通常仍能命中缓存，因为 Go 编译依赖于直接依赖的导出数据（如 `foo.x`），而非完整的传递归档图。 链接则不同。每个 `go_test` 需要一个测试二进制文件，由 `GoLink` 操作生成，而该链接操作会消耗传递的 Go 归档集，例如 `foo.a`。如果 `foo.a` 发生变化，即使源代码和编译操作未变，许多下游测试二进制文件也可能获得新的摘要。最后，`TestRunner` 操作需要那个测试二进制文件作为输入才能运行。 这意味着一个小的源代码编辑可能产生许多新的测试二进制摘要。这些测试二进制文件通常体积很大，且其中许多与前版本字节大部分相同。没有 CDC，每个文件仍作为全新的整个数据块进行传输和存储。 ## 将其视作输出问题（https://www.buildbuddy.io/blog/content-defined-chunking/#treating-this-as-an-output-problem） 一种选择是让操作本身具有增量性：增量链接、运行时链接、更智能的打包、更智能的归档等。但这通常非常困难，需要对链接器及工具本身进行大量修改。 即使我们为某个工具解决了这个问题，仍然需要为 GoLink、C++ 链接器、JavaScript 打包器、应用打包工具、生成的归档文件以及其他所有可能产生大型输出的操作分别提供解决方案。这无法扩展。 相反，我们可以将其视为一个通用的输出问题：这些操作会创建大型文件，其中仅有少量内容发生变化。通过内容定义分块（CDC），我们可以保持操作本身不变，同时获得类似使操作增量化的诸多好处。 ## 内容定义分块（https://www.buildbuddy.io/blog/content-defined-chunking/#content-defined-chunking） CDC 是一个可重复的过程，它根据文件内容而非固定字节偏移量将文件拆分成数据块。 简单概括：在一个小字节窗口上运行滚动哈希，当哈希匹配一个稀有模式时进行分割。哈希的行为足够随机，使得这种情况只是偶尔发生，但过程仍然是确定性的：相同的内容产生相同的块边界。 如果你希望块大小平均约为 512 KiB，就选择一个大约每 512 KiB 有 1 次匹配概率的模式。如果模式不匹配，则移动窗口并重试。经过一段时间，你就能得到所需的平均块大小，同时保持边界由内容定义。 较小的块可以提高去重率，但会增加元数据开销和 RPC 成本，因此 CDC 实现需要在块大小与效率之间取得平衡。 用一个玩具示例来说明：假设滚动窗口宽度为 4 字节，每当这个 4 字节窗口的哈希值以 `00` 结尾时我们就分割。假设窗口 `bbbb` 和 `cccc` 恰好都匹配该模式（具体哈希值不重要）： ``` original: aaaabbbbccccdddd windows: bbbb cccc cuts: aaaa|bbbb|cccc|dddd ``` 如果在 `bbbb` 内部插入几个字节，附近的窗口会发生变化，因此该块会变化： ``` updated: aaaabbXXbbccccdddd ``` 但一旦滚动窗口移过插入的字节，再次到达 `cccc` 时，它会看到与之前相同的 4 字节序列。该序列产生相同的哈希值，因此算法再次找到相同的切割点。后续的块可以保持相同的边界和哈希值。 真实的 CDC 使用更大的滚动窗口和更罕见的分割模式，但原理相同。 这意味着，一个大型文件如果在某处插入或删除了几个字节，通常只会改变附近的一个（或多个）块。一旦滚动窗口移过变更的字节并再次遇到未变的内容，它就会开始看到与之前相同的字节序列，从而找到相同的未来切割点。 一种常见的 CDC 算法是 FastCDC（https://doi.org/10.1109/TPDS.2020.2984632）。FastCDC 幻灯片（https://www.usenix.org/sites/default/files/conference/protected-files/atc16_slides_xia.pdf）也提供了有用的可视化概览。 CDC 块稳定性 *只有发生变化的块需要重新上传。* ## 这对远程缓存有何好处？（https://www.buildbuddy.io/blog/content-defined-chunking/#how-does-this-benefit-remote-caching） 如果一个操作创建了一个大型输出，比如 GoLink 或 CppLink，一个小小的输入变更可能仍然产生一个新的输出，该输出与前一个输出大部分相同。 有了 CDC，缓存可以将该输出拆分成块，并发现许多块已经存在。无需重新上传整个输出，只需上传缺失的块。 这对于 CI 和开发者构建尤其有效，因为相邻的提交往往产生大部分相似的输出。一旦某个块被上传，未来的构建就可以跨相关输出复用该块。 GoLink 输出在插入后仍保持大部分稳定 *大部分输出仍能映射到缓存中已存在的块。* ## 结果（https://www.buildbuddy.io/blog/content-defined-chunking/#results） 写入去重率 *在近期的时间窗口中，CDC 对符合条件的 BuildBuddy 缓存写入的去重率约为 85%。换句话说，大部分大型输出写入时，其字节已作为可复用块存在，因此只需上传剩余变化的块。* 每小时节省的写入字节数 *在这两周的时间窗口内，CDC 在写入路径上跳过了约 300 TiB 的重复块数据上传，峰值超过每小时 4 TiB。这来自于 BuildBuddy 管理缓存写入和执行器输出上传的写入侧块去重。总的网络节省应该更大，因为这不包括当块从磁盘缓存、区域缓存或执行器文件缓存提供服务时的读取侧节省。* 在生产环境中，CDC 已经跳过了数百 TiB 的重复块上传。由于 BuildBuddy 存储的重复数据更少，有效缓存保留时间也得到了改善。 Bazel 实现 PR（https://github.com/bazelbuild/bazel/pull/28437）在 BuildBuddy 仓库上对 50 次提交进行了基准测试，结果显示上传数据减少约 40%，磁盘缓存缩小约 40%，并且在该基准测试中构建速度更快。 BuildBuddy 当前对大于 2 MiB 的数据块应用分块。在一次测试中，只有约 4.2% 的对象超过该阈值，因此大多数数据块未被分块。 在该符合条件的子集内，CDC 对写入字节的去重率约为 85%。在所有缓存流量中，总体节省通常在 20% 到 40% 之间。 经验法则：CDC 最适合那些体积大且跨版本字节稳定的输出。链接和打包通常是很好的候选，我们看到的大多数大型输出都复用了大部分字节。打包在输出未被压缩、混淆或随机化时也是很好的选择。 压缩并非完全不行，但通常会导致更多变动。像 `tar.gz` 归档文件和 Docker 镜像层这样的压缩格式通常更难以分块，因为很小的输入变动就可能重写压缩字节流中的更多内容。关键属性是字节级别的相似性，而不是文件扩展名。 ## 实现（https://www.buildbuddy.io/blog/content-defined-chunking/#implementation） 为了端到端地实现这一功能，变更分布在三个层面： - 远程 API 定义共享的 `SplitBlob` / `SpliceBlob` 协议，使客户端和缓存能够讨论数据块。 - BuildBuddy 实现服务端缓存行为以及执行器侧的分块上传和下载。 - Bazel 实现客户端侧的组合缓存路径，使本地磁盘缓存和远程缓存能够共享数据块。 ### 远程 API：Split 和 Splice（https://www.buildbuddy.io/blog/content-defined-chunking/#remote-apis-split-and-splice） 为了使 CDC 对远程缓存有用，客户端和服务器需要一种方式来讨论数据块，而不仅仅是整个数据块。当网络成为瓶颈时，这一点尤其有用：网络慢、使用 VPN 或与缓存之间延迟高的用户，不应在大多数数据块已存在于某处的情况下，仍需上传或下载整个大型输出。 相反，客户端可以发现一个数据块如何映射到各个块，检查哪些块已经在本地可用，并仅传输缺失的部分。 这就是 `SplitBlob`（https://github.com/bazelbuild/remote-apis/blob/becdd8f9ff811df88a22d3eadd6341753d51d167/build/bazel/remote/execution/v2/remote_execution.proto#L443-L500）和 `SpliceBlob`（https://github.com/bazelbuild/remote-apis/blob/becdd8f9ff811df88a22d3eadd6341753d51d167/build/bazel/remote/execution/v2/remote_execution.proto#L503-L558）的用武之地。 `SplitBlob` 是读取侧 API。给定一个大型数据块的摘要，客户端询问缓存是否已知该数据块的块布局。如果已知，客户端可以只下载尚未拥有的块。 `SpliceBlob` 是写入侧 API。操作创建大型输出后，Bazel 或执行器上传任何缺失的块，并告知缓存如何从这些块重建完整的数据块。缓存存储该重建元数据，以便将来针对同一数据块摘要的 `SplitBlob` 调用能够返回块布局。 读取路径变为： 1. 调用 `SplitBlob` 获取大型数据块的块布局。 2. 检查本地缓存中已存在的块。 3. 使用 `Read` 或 `BatchReadBlobs` 下载缺失的块。 写入路径则相反： 1. 生成大型输出后，客户端或执行器运行 CDC 算法以计算块边界和块摘要。 2. 调用 `FindMissingBlobs` 检查缓存缺失哪些块。 3. 仅使用 `Write` 或 `BatchUpdateBlobs` 上传缺失的块。 4. 调用 `SpliceBlob` 存储重建元数据。 在此模型下，块作为常规 CAS 数据块以其自身摘要存储。重建元数据以原始大型数据块摘要为键，因此未来的 `SplitBlob` 调用可以从已知的摘要开始，并发现块布局。 这也有助于更均衡地分布存储。不再将单个非常大的对象视为不可分割的缓存条目，缓存可以像对待其他任何数据块一样，在 CAS 中存储和提供较小的块。 SplitBlob 和 SpliceBlob 流程 *SplitBlob 是读取侧 API；SpliceBlob 是写入侧 API。* ### Bazel 组合缓存（https://www.buildbuddy.io/blog/content-defined-chunking/#bazel-combined-cache） Bazel 在组合缓存中实现 CDC，该缓存协调远程缓存和磁盘缓存的读写。 当远程缓存声明支持分块时，Bazel 会创建分块上传和下载路径。大于服务器提供阈值的大型数据块使用分块路径；较小的数据块继续使用正常缓存路径。 一个重要的实现细节是，Bazel 不需要在内存中保留每个块的第二个副本。输出已经存在磁盘上，因此上传器可以使用原始文件作为块数据的源，并在上传过程中流式传输所需的字节范围。 块字节范围而非块副本 *客户端可以保留字节范围而非块副本。*