Skip to main content

内容定义分块算法

分块的目标是将文件数据转换为较小的可变长度块，长度约为 64 KiB。 块边界必须以确定性方式计算，以便在两个不同位置对相同数据进行分块时产生可以去重的块。

        +---------+---------+---------+---------+---------+---------+---------+--------------
File -> | chunk 0 | chunk 1 | chunk 2 | chunk 3 | chunk 4 | chunk 5 | chunk 6 | chunk 7 | ...
        +---------+---------+---------+---------+---------+---------+---------+--------------

逐步算法（基于 Gearhash 的 CDC）​

常量参数​

  • target_chunk_size: 64 KiB
  • MIN_CHUNK_SIZE: 8 KiB（最小块大小）
  • MAX_CHUNK_SIZE: 128 KiB（最大块大小）
  • MASK: 0xFFFF000000000000（16 个一位 → 每字节边界概率 1/2^16）
  • TABLE[256]: 256 个 64 位常量表（rust-gearhash-table）

状态​

  • h: 64 位哈希，初始化为 0
  • start_offset: 当前块的起始偏移量，初始化为 0

每字节更新规则（Gearhash）​

对于每个输入字节 b，使用 64 位包装算术更新哈希：

h = (h << 1) + TABLE[b]

边界测试和大小约束​

在更新 h 后的每个位置，令 size = current_offset - start_offset + 1。

  • 如果 size < MIN_CHUNK_SIZE：跳过测试 MASK；继续
  • 否则如果 size >= MAX_CHUNK_SIZE：强制边界
  • 否则如果 (h & MASK) == 0：此位置为边界

当找到或采用边界时：

  • 发出块 [start_offset, current_offset + 1)
  • 设置 start_offset = current_offset + 1
  • 重置 h = 0

在文件末尾，如果 start_offset < len(data)，发出最终块 [start_offset, len(data))。

伪代码​

输入: (参见上面的常量参数)
  data: 字节数组

状态:
  h = 0
  start_offset = 0 // "当前块"的起始

if len(data) < MIN_CHUNK_SIZE:
  发出块 [0, len(data))
  完成

for i in range(0, len(data)):
  b = data[i]
  h = (h << 1) + TABLE[b]      // 64 位包装
  size = i + 1 - start_offset

  if size < MIN_CHUNK_SIZE:
    continue

  if size >= MAX_CHUNK_SIZE or (h & MASK) == 0:
    发出块 [start_offset, i + 1)
    start_offset = i + 1
    h = 0

if start_offset < len(data):
  发出块 [start_offset, len(data))

边界概率和掩码选择​

给定 MASK 有 16 个一位，对于随机 64 位哈希 h，所有这些 16 位都为零的概率是 1 / 2^16。平均而言，这意味着大约每 64 KiB 你会看到一次匹配。

属性​

  • 确定性边界：相同内容 → 相同块
  • 局部性：小编辑仅影响附近边界
  • 线性时间和恒定内存：单个 64 位状态和计数器

直觉和原理​

  • 表 TABLE[256] 为每个字节值注入伪随机性，使得演化的哈希 h 在掩码测试方面表现得像随机 64 位值。这使得边界是内容定义的，但在统计上均匀分布。
  • 左移 (h << 1) 放大最近的字节，帮助小变化影响附近位置，而不会全局移动所有边界。
  • 在每个边界将 h 重置为 0 可防止长距离传递，并保持每个块的边界决策在统计上独立。

实现注意事项​

  • 仅在发出边界时重置 h。这确保即使分片流式输入时，分块也是稳定的。
  • 仅在 size >= MIN_CHUNK_SIZE 时应用掩码测试。这减少了小块的频率并稳定了平均块大小。
  • 即使 (h & MASK) != 0，也必须在 MAX_CHUNK_SIZE 处强制边界。这保证了有界块大小，并在匹配很少时防止病态长块。
  • 对 (h << 1) + TABLE[b] 使用 64 位包装算术。这是参考实现 rust-gearhash 中的行为。

边界情况​

  • 小文件：如果 len(data) < MIN_CHUNK_SIZE，整个 data 作为单个块发出。
  • 长时间运行无匹配：如果在 MAX_CHUNK_SIZE 之前没有位置匹配 (h & MASK) == 0，则在 MAX_CHUNK_SIZE 处强制边界以限制块大小。

可移植性和确定性​

  • 使用固定的 T[256] 表和掩码，算法在跨平台上是确定性的：相同输入 → 相同块边界。
  • 字节序不影响行为，因为更新是按字节进行的，并使用标量 64 位操作。
  • SIMD 加速实现（可用时）仅是优化；它们产生与标量路径相同的边界 rust-gearhash。

最小大小跳过（切点跳过优化）​

对于大数据，在每个字节处计算和测试滚动哈希是昂贵的，并且无论如何，MIN_CHUNK_SIZE 约束禁止在块的前几个字节内进行早期测试。 我们能够通过切点跳过有意跳过测试某些数据，以加速扫描而不影响正确性。

哈希函数通过使用 64 字节整数长度和位移（(h << 1) + TABLE[b]）使得任何字节偏移处的哈希仅依赖于最后 64 个字节。 使用 64 字节的 Gear 滚动哈希窗口，第一个边界测试被推迟到块中至少 MIN_CHUNK_SIZE - 64 - 1 字节。 这确保，当可以考虑第一个边界时（在偏移 MIN_CHUNK_SIZE），来自当前块的至少一个完整哈希窗口的字节已经影响了哈希状态。

  • 效果：
    • 分布质量得以保留，因为第一个可接受的测试使用混合良好的哈希（完整窗口），避免最早字节的偏差。
    • 通过避免在不能采用边界的前缀中进行每字节哈希/判断来提高性能。
    • 正确性得以保留，因为边界不得在 MIN_CHUNK_SIZE 之前设置，并且在可测试偏移处产生的哈希与我们没有跳过任何字节时计算的哈希相同。
  • 注意事项：
    • 这只是搜索过程的优化；与简单地避免在 MIN_CHUNK_SIZE 之前采用边界的逐字节实现相比，它不会改变边界条件、掩码或发出的块集。
    • 在参考代码中，这表现为在调用掩码测试循环之前将扫描指针前进最多 MIN_CHUNK_SIZE - 64 - 1。

参考文献​

  • rust-gearhash: 用于 CDC 的快速、SIMD 加速的 GEAR 哈希 rust-gearhash
  • FastCDC 论文（CDC 的背景和设计原理）fastcdc-paper

示例参考​

xet-team/xet-spec-reference-files 仓库包含原始文件 Electric_Vehicle_Population_Data_20250917.csv。

在同一仓库的文件 Electric_Vehicle_Population_Data_20250917.csv.chunks 中列出了从 Electric_Vehicle_Population_Data_20250917.csv 产生的块。 文件中的每一行都是块哈希的 64 十六进制字符字符串版本，后跟空格，然后是该块中的字节数。

实现者应使用块长度来确定他们正在使用其分块实现为此文件生成正确的块边界。

Last updated on