跳到主要内容

Xorb 形成和序列化格式

"Xorb"（Xet Orb，发音类似 "zorb"）是一系列块以及一系列块的序列化格式。

收集块​

使用分块算法，文件被映射到一系列块，一旦找到这些块，就需要将它们收集到 Xorbs 集合中。

将一系列块收集到 Xorbs 中是有利的，这样它们可以作为整个块范围被引用。

假设文件按顺序 ABCD 被分块为块 A、B、C、D。然后创建一个 Xorb X1，按此顺序包含块 A、B、C、D（从块索引 0 开始），假设此 Xorb 的哈希是 X1。然后要重建文件，我们请求 Xorb X1 块范围 [0, 4)。

虽然 Xorb 中的块数量没有明确限制，但序列化的 Xorb 总大小限制为 64MiB。 由于某些块会被压缩，通常建议收集块直到它们的总未压缩长度接近 64 MiB，然后序列化结构。 也就是说，Xorbs 指向大约 64 MiB 的数据。 （回想一下，目标块大小是 64 KiB，因此预计每个 Xorb 大约有 ~1024 个块）。

CAS 服务器将拒绝超过 64 MiB 序列化大小限制的 Xorb 上传。

如果大小要求允许，建议将来自多个文件的块打包到一个 Xorb 中，例如文件 X 和 Y 各自产生 10 个新块，总共约 128000 字节，那么所有这些块都可以放入一个新的 Xorb。

Xorb 格式​

Xorb 是一系列"块"，按照特定格式序列化，该格式支持访问范围块并在块级别构建压缩。

┌─────────┬─────────────────────────────────┬─────────┬─────────────────────────────────┬─────────┬─────────────────────────────────┬──────────
│  Chunk  │                                 │  Chunk  │                                 │  Chunk  │                                 │
│  Header │      Compressed Chunk Data      │  Header │      Compressed Chunk Data      │  Header │      Compressed Chunk Data      │   ...
│         │                                 │         │                                 │         │                                 │
└─────────┴─────────────────────────────────┴─────────┴─────────────────────────────────┴─────────┴─────────────────────────────────┴───────────
│                 Chunk 0                   │                 Chunk 1                   │                 Chunk 2                   │   ...

块寻址​

每个块在其所在的 Xorb 内都有一个索引，从 0 开始。 块可以通过其索引单独寻址，但通常按范围寻址或获取。 块范围始终指定为起始包含和结束独占，即 [start, end)。

块格式​

块由标头后跟压缩数据组成。标头包含有关块的元数据，特别是需要知道如何反序列化块的压缩方案。

块标头结构​

块标头按以下方式序列化：

  • Version（1 字节）：协议版本，当前为 0
  • Compressed Size（3 字节）：压缩后数据的大小，作为 3 字节小端无符号整数。
  • Compression Type（1 字节）：用于压缩的算法（参见下面的映射）
  • Uncompressed Size（3 字节）：原始块数据的大小（压缩前），作为 3 字节小端无符号整数。

压缩和未压缩大小都可以容纳在 3 字节整数中，因为原始未压缩块最多可以是 128KiB， 需要 18 个二进制数字来表示。 如果使用预期的压缩方案导致压缩块更大，则块应该以未压缩形式存储， 未压缩大小也最多为 128KiB。

块标头布局​

┌─────────┬─────────────────────────────────┬──────────────┬─────────────────────────────────┐
│ Version │        Compressed Size          │ Compression  │       Uncompressed Size         │
│ 1 byte  │           3 bytes               │    Type      │           3 bytes               │
│         │      (little-endian)            │   1 byte     │      (little-endian)            │
└─────────┴─────────────────────────────────┴──────────────┴─────────────────────────────────┘
0         1                                 4              5                                 8

块压缩方案​

值名称描述
0None无压缩 - 数据按原样存储
1LZ4标准 LZ4 压缩
2ByteGrouping4LZ4字节分组，4 字节组后跟 LZ4 压缩。针对浮点数和其他结构化数据优化，其中按位置分组字节可提高压缩比

字节分组 LZ4 压缩​

字节分组 LZ4 压缩是一种优化技术，可提高结构化数据（如浮点数、整数和其他在特定位置具有相似字节模式的数据类型）的压缩比。

  1. 字节分组阶段：通过按每个 4 字节组内的位置对字节进行分组来重新组织输入数据： 创建 4 个缓冲区，对于块数据的每 4 个字节（B1, B2, B3, B4），将每个字节追加到其 respective 组，即按顺序从 1 到 4。然后按顺序连接组（1, 2, 3, 4）。

    示例：

    • 原始数据：[A1, A2, A3, A4, B1, B2, B3, B4, C1, C2, C3, C4, ...]
    • 分组数据：[A1, B1, C1, ..., A2, B2, C2, ..., A3, B3, C3, ..., A4, B4, C4, ...]

    如果块中的总字节数不是 4 的倍数，则按照模式（每个组 1 个字节）将剩余字节追加到前 1-3 个组，直到块中没有更多字节。

  2. LZ4 压缩：然后使用标准 LZ4 压缩对分组数据进行压缩。

块数据​

标头之后是压缩数据块，正好是 compressed_size 字节长。

选择压缩方案​

为 Xorb 选择块压缩方案是在上传 Xorb 时留给客户端的任务。 目标是最小化 Xorb 的整体大小以加快传输速度，代价是在接收端解压缩块需要资源。

为块选择压缩方案时，有多种策略，实现者可以自行决定如何选择压缩方案。 请注意，Xorb 可能包含使用不同压缩方案的块。

  1. 暴力方法

    尝试所有可能的压缩方案，选择最好的一个。 最好的可能是产生最小压缩块或解压缩最快的那个。

  2. 最佳努力预测

    在 xet-core 中，为了预测 BG4 是否有用，我们计算将形成的 4 个组中每个组的每字节 pop-count 分布之间的最大 KL 散度。 你可以在 bg4_prediction.rs 和配套脚本中了解更多信息。

    如果预测器没有显示 BG4 会更好，我们使用 Lz4，并且在任何情况下，如果使用的压缩方案没有显示任何好处，我们将块存储为未压缩版本。

示例块序列化​

VERSION = 0
buffer = bytes()

for chunk in xorb.chunks:
    uncompressed_length = len(chunk)
    compressed, compression_scheme = pick_compression_scheme_and_compress(chunk)
    header = Header(VERSION, len(compressed), compression_scheme, uncompressed_length)
    buffer.write(header)
    buffer.write(compressed)

Xorb 格式示例​

有关序列化 xorb 对象的示例，请参见 eea25d6ee393ccae385820daed127b96ef0ea034dfb7cf6da3a950ce334b7632.xorb。 此 xorb 的哈希是 eea25d6ee393ccae385820daed127b96ef0ea034dfb7cf6da3a950ce334b7632，它由文件 Electric_Vehicle_Population_Data_20250917.csv 的块组成。

最后于 更新