Skip to main content

Xet 块级去重规范

概述​

块级去重是 Xet 系统中的一项基本优化技术，通过识别和共享跨文件和仓库的相同内容块（块）来消除冗余数据。 本规范详细说明了在保持数据完整性和访问控制的同时实现高效存储和传输的过程、算法和安全机制。

Xet 中的去重在块级别而不是文件级别运行，提供细粒度的去重功能，即使文件差异很大也能识别共享内容。 这种方法对于机器学习和数据科学工作流中常见的场景特别有效，例如：

  • 具有增量更改的数据集的多个版本
  • 共享共同层或参数的模型检查点
  • 具有相似内容的文档和配置文件
  • 只有部分内容在版本之间发生变化的大文件

核心概念​

块​

块是使用内容定义分块（CDC）和滚动哈希函数从文件派生的可变大小内容块。块是 Xet 中去重的基本单位。

  • 目标大小：64KB（可配置）
  • 大小范围：8KB 到 128KB（最小和最大约束）
  • 标识：每个块由其加密哈希（MerkleHash）唯一标识

详细的分块描述

Xorbs​

Xorbs 是聚合多个块以实现高效存储和传输的对象：

  • 最大大小：64MB
  • 最大块数：每个 xorb 8,192 个块
  • 目的：将多个块批处理在一起，以减少上传和下载块组时的元数据和网络开销

Shard（Xorb 列表）​

Shard 是包含可以针对其进行去重的 xorbs 列表的对象（对于去重上下文，忽略 shard 格式的文件信息部分）。

  • 最大大小：64MB
  • 目的：在全局去重请求的肯定回复上提供格式，包含有关 CAS 系统中已存在的 xorbs 的信息。

CAS（内容寻址存储）​

CAS 系统提供底层存储基础设施：

  • 内容寻址：所有对象都通过其加密哈希存储和检索
  • 不可变性：一旦存储，文件内容无法修改
  • 去重：相同内容在存储级别自动去重

去重过程​

1. 文件处理和分块​

当文件被处理以上传时，它经历以下步骤：

  1. 分块：使用 GearHash 算法的内容定义分块创建文件数据的可变大小块
  2. 哈希计算：使用加密哈希函数（基于 Blake3 的 MerkleHash）对每个块的内容进行哈希
  3. 块对象创建：块用包括哈希、大小和数据的元数据包装

2. 多级去重策略​

Xet 采用三级去重策略，以在最小化延迟的同时最大化效率：

级别 1：本地会话去重​

范围：当前上传会话 机制：内存哈希查找表 目的：消除当前文件或会话内的冗余

好处：

  • 最快的查找（内存中）
  • 零网络开销
  • 即时去重反馈

级别 2：缓存元数据去重​

范围：以前上传的文件和会话 机制：本地 shard 文件元数据缓存 目的：利用针对最近上传内容的去重

好处：

  • 快速本地磁盘访问
  • 无网络延迟
  • 跨会话持久化

级别 3：全局去重 API​

范围：整个 Xet 系统 机制：具有 HMAC 保护的全局去重服务 目的：发现跨所有用户和仓库的去重机会

3. 全局去重过程​

全局去重系统提供跨 Xet 系统管理的所有数据的去重功能：

资格标准​

并非所有块都有资格进行全局去重查询以管理系统负载：

  1. 第一个块：每个文件的第一个块始终有资格。
  2. 哈希模式匹配：如果哈希的最后 8 个字节解释为小端 64 位整数 % 1024 == 0，则块有资格。

建议： 间距约束：全局去重 API 经过优化，当有匹配时返回有关附近块的信息。考虑仅对每 ~4MB 数据中的合格块发出请求。

查询过程​

  1. 后台查询：全局去重查询应该异步运行，以避免阻塞上传
  2. HMAC 保护：使用 HMAC 密钥保护块哈希
  3. Shard 响应：找到匹配时，API 返回包含以下内容的 shard：
    • CAS 信息部分：包含有关存储块的许多 xorbs 的元数据
    • HMAC 密钥：包含在用于加密块哈希的 shard 元数据标头中
  4. 加密块匹配：返回的 shard 中的所有块哈希都已使用 HMAC 密钥加密
  5. 匹配发现过程：要查找匹配，客户端必须：
    • 使用提供的 HMAC 密钥加密其块哈希
    • 在 shard 的块列表中搜索加密的哈希
    • 对于后续块，重复加密和搜索过程
    • 跟踪原始（未加密）块哈希，同时注意哪个 xorb 包含该块
  6. 元数据缓存：客户端下载并缓存 shard 元数据以供将来去重

HMAC 安全机制​

全局去重使用 HMAC（基于哈希的消息认证码）来保护块哈希，同时启用去重。

安全属性：

原始块哈希永远不会从服务器传输到客户端；客户端必须加密其原始块哈希并找到匹配，才能知道系统中存在原始块哈希。 他们可能知道此块哈希，因为他们拥有此数据，匹配使他们知道哪个 xorb 具有此块哈希以及 xorb 中的位置，但没有透露该 xorb 或其他 xorbs 中的任何其他原始块哈希。

技术实现细节​

块哈希计算​

每个块都使用加密哈希函数（基于 Blake3 的 MerkleHash）对其内容进行哈希，以为内容寻址创建唯一标识符。 参见有关哈希的部分。

Xorb 形成​

当需要存储新块时，它们根据大小和计数限制聚合到 xorbs 中。如果添加新块会超过最大 xorb 大小或块计数，则完成并上传当前 xorb。参见有关 xorb 形成的部分

文件重建信息​

当块被去重时，系统创建文件重建信息，包括：

  • 包含块的 xorb 的哈希
  • CAS 块的标志
  • 段中的总字节数
  • Xorb 内的起始和结束索引（起始包含，结束独占）

此信息允许系统通过以下方式重建文件：

  1. 识别哪些 xorbs 包含所需的块
  2. 从每个 xorb 提取特定的块范围
  3. 按正确顺序连接块

参见有关文件重建的部分。

碎片化预防​

虽然去重对于节省空间很有价值，但过于激进地进行去重可能会导致文件碎片化——这意味着文件的块最终分散在许多不同的 xorbs 中。这会使读取文件变慢且效率降低。 为了避免这种情况，在 xet-core 中，我们的目标（并鼓励实现者）是在可能的情况下将长的连续块运行保持在同一 xorb 中。实现应该在可行时保持长的连续运行在一起。 系统有时选择引用单个 xorb 中的直接块运行，而不是总是去重每个可能的块，即使这意味着跳过几个块的去重。 这种方法平衡了去重的好处与保持文件易于快速读取的需要。 例如，考虑在最小块运行（例如至少 8 个块）中引用去重的块，或目标平均连续块运行总长度 >= 1MB。

结论​

Xet 的块级去重系统为大规模数据工作流中的高效数据存储和传输提供了全面的解决方案。 通过将本地、缓存和全局去重策略与强大的安全机制和碎片化预防相结合， 系统在保持性能和数据完整性的同时实现了显著的存储节省。

多层方法确保去重既有效又高效：

  • 本地去重在会话内提供即时好处
  • 缓存去重利用最近的上传历史
  • 全局去重在保持安全的同时实现跨仓库优化

系统的设计优先考虑效率和安全性，具有全面的错误处理、性能监控和安全措施，使其适合在数据密集型应用程序中用于生产。

Last updated on