跳到主要内容

文件重建：基于 Term 的表示

本文档描述了如何使用一系列 term 以紧凑、去重的形式表示和重建文件。每个 term 指定数据源（称为 xorb 的内容寻址容器）以及该容器中需要哪些块索引。

术语表​

  • Xorb：包含一系列块的内容寻址容器。由加密哈希（"xorb 哈希"）标识。
  • Chunk：Xorb 内的数据单元。块是有序的，可以单独解压缩/解码为原始字节。
  • Chunk index：块在特定 xorb 内的基于 0 的位置。
  • Term：标识 xorb 和该 xorb 内连续块索引范围的对：(xorb hash, chunk range [start, end))。
  • Reconstruction：term 列表。

核心思想​

遵循分块过程后，文件可以表示为块的排序。 然后将这些块打包到 xorbs 中，给定 xorbs 集合，我们将文件表示转换为由"term"组成的"重建"。 在形成 xorbs 时，块的排序和分组优先考虑文件中出现的连续块运行，以便在引用 xorb 时最大化 term 范围长度。

任何文件的原始字节都可以描述为由一系列 term 产生的数据的连接。 每个 term 引用特定 xorb 内的连续块范围。 通过检索这些块范围、将它们解码为原始字节并按顺序连接来重建文件。

Diagram 序列图​

A file with 4 terms. Each term is a pointer to chunk range within a xorb.

File Reconstruction

  ┌----------------------------┬┬--------------------------┬┬---------------------------┬┬-------------------------┐
  ¦ X0                         ¦¦ X1                       ¦¦ X2                        ¦¦ X3                      ¦
  ¦ start: 0                   ¦¦ start: 0                 ¦¦ start: 300                ¦¦ start: 300              ¦
  ¦ end: 1024                  ¦¦ end: 700                 ¦¦ end: 1024                 ¦¦ end: 700                ¦
  ├----------------------------++--------------------------++---------------------------++-------------------------┤
  ¦                            /¦                          /\                           /\                         /
  ¦                           / ¦                         /  \                          ¦ \                       /
  ¦                          /  ¦                    /---/    \----\                    ¦  \----\                /
  ¦                         ¦   ¦                   /               \                   ¦        \              /
  ¦                         ¦   ¦                  /                 \                  ¦         \            /
  ┌-------------------------┐   ┌-------------------------┐   ┌-------------------------┐   ┌-------------------------┐
  ¦ X0                      ¦   ¦ X1                      ¦   ¦ X2                      ¦   ¦ X3                      ¦
  ¦                         ¦   ¦                         ¦   ¦                         ¦   ¦                         ¦
  ¦0                    1024¦   ¦0                    1000¦   ¦0                    1090¦   ¦0                    870 ¦
  └-------------------------┘   └-------------------------┘   └-------------------------┘   └-------------------------┘

Term 格式​

每个 term 由以下组成：

  • Xorb 哈希：32 字节哈希值，是 CAS（内容寻址存储）中 xorb 的键。
  • 块范围：该 xorb 内块索引的半开区间 [start, end)。范围包括索引 start 处的块，不包括索引 end 处的块。

重建规则​

给定描述文件的有序 term 列表：

  1. 对于每个 term，从标识的 xorb 获取指定的块范围。
  2. 将块解码/解压缩为原始字节，保留原始顺序。
  3. 如果重建整个文件，按列出的顺序连接所有 term 的解码输出。
  4. 如果重建文件的字节子范围，可以部分使用第一个和最后一个 term：
    • 跳过第一个 term 解码输出中的字节前缀，以便文件级范围从请求的偏移量开始。
    • 截断最后一个 term 解码输出的尾部，以便文件级范围在请求的位置结束。

排序和覆盖​

  • Term 根据文件的字节顺序排序。连接它们的解码输出产生请求的文件区域。
  • 不得存在间隙。如果存在间隙，重建将不会产生连续的字节流。

每个 Xorb 的多个 Term 和合并​

  • 文件可能包含引用同一 xorb 的多个 term，可能具有不相交的块范围。这使得可以在文件的远距离部分进行去重。
  • 当多个 term 针对同一 xorb 内的重叠或相邻块范围时，实现应该将这些合并为单个检索，以减少 I/O 和请求开销，同时保留 term 级重建语义。

块和字节边界​

  • 块范围在块索引空间中指定，而不是字节偏移。每个块的解码大小不需要统一。
  • term 贡献的字节长度等于其引用块的解码大小之和，减去重建子范围时的任何初始跳过或最终截断。
  • 在 term 内切片（用于子范围重建）在寻址块序列的解码输出中以字节粒度发生。

确定性和完整性​

  • Xorb 哈希将底层块集的身份与其内容绑定。如果 xorb 哈希正确且指定的块范围按定义检索和解码，则生成的字节是确定性的。
  • 文件级身份（例如，重建字节的加密哈希）可以通过重建并哈希结果来验证。

示例（概念性）​

假设文件由以下有序 term 表示：

TermXorb 哈希（概念性）块范围
1X1[0, 5)
2X2[3, 8)
3X1[9, 12)

重建通过从 xorb X1 获取块 0,1,2,3,4，从 xorb X2 获取块 3,4,5,6,7，从 xorb X1 获取块 9,10,11，解码每个连续范围，并按 term 顺序 1 → 2 → 3 连接来进行。

序列化和反序列化​

本节总结了基于 term 的重建如何持久化和交换。

序列化到 shard（文件信息部分）​

文件的重建可以序列化到 shard 中，作为其文件信息部分的一部分。 从概念上讲，此部分编码描述文件的完整 term 集。 以这种方式存储时，表示是规范的，并且足以仅从其引用的 xorb 范围重建完整文件。

参考：shard 格式文件信息

从重建 API 反序列化（JSON）​

重建 API 可以返回携带完整重建的 JSON 对象。 此响应由名为 "QueryReconstructionResponse" 的结构表示，其中 terms 键枚举重建整个文件所需的有序 term 列表。 terms 列表包含每个 term 的 xorb 标识符和要检索的连续块索引范围。 其他字段可能提供辅助详细信息（例如偏移量或获取提示），以优化检索而不改变 terms 序列的含义。

参考：api, 下载协议

碎片化和为什么更长的范围很重要​

碎片化是指用许多非常短的、分散的范围跨多个 xorbs 表示文件。虽然这可以最大化去重机会，但它通常会损害读取性能并增加开销。

  • 碎片化的含义：文件的字节流由众多小的 term 范围组装而成，可能跨越许多 xorbs。这意味着更多的查找、更多的范围获取和更差的局部性。
  • 碎片化的成本：
    • 更大的重建对象
    • 可能更多的网络请求（每个请求的开销）
  • 为什么优先考虑更长的范围：
    • 更少、更长的范围减少往返次数并启用更多顺序读取
    • 重建期间更简单的调度和写入模式

实际上存在平衡：更长的范围提高重建性能，而更细的粒度可以增加去重节省。 优先考虑同一 xorb 内更长的连续块范围，并在可行时合并相邻或重叠范围，有助于保持良好的读取性能而不牺牲正确性。 在 xet-core 中，我们使用碎片化预防机制，目标是平均 term 包含 8 个块。

最后于 更新