Deepseek 3FS（ Fire-Flyer File System）设计笔记

本文是对 3FS 设计笔记的翻译，建议可以通过本文先快速了解，然后请阅读英文原版（后续会不断更新），然后对比代码深入学习。

原文：https://github.com/deepseek-ai/3FS/blob/main/docs/design_notes.md

3FS 设计笔记

设计与实现

3FS系统有四个组件：集群管理器（cluster manager）、元数据服务（metadata service）、存储服务（storage service）和客户端（client）。 所有组件都连接在一个RDMA网络中（InfiniBand或RoCE）。

元数据和存储服务向集群管理器发送心跳。集群管理器处理成员变更并将集群配置分发给其他服务和客户端。一个系统部署有多个集群管理器，并其中一个将被选举作为主管理器。当主管理器失败时，另一个管理器被提升为主管理器。集群配置通常存储在可靠的分布式协调服务中，例如ZooKeeper或etcd。 在我们的生产环境中，我们使用相同的键值存储作为文件元数据，以减少依赖。

文件元数据操作（例如打开或创建文件/目录）被发送到元数据服务，这些服务实现文件系统语义。元数据服务是无状态的，因为文件元数据存储在一个事务性键值存储中（例如 FoundationDB）。客户端可以连接到任何元数据服务。

译者：文件系统语义通常指 POSIX 文件接口（或者它的子集）

每个存储服务管理几个本地 SSD，并提供一个块存储接口。 存储服务实现了带有分配查询（Chain Replication with Apportioned Queries，CRAQ）的链式复制，以确保强一致性。CRAQ的**全写-任读（write-all-read-any）**方法有助于释放SSD和RDMA网络的吞吐量。 一个3FS文件被分割成大小相等的块，这些块在多个SSD上进行复制。

为应用程序开发了两个客户端：FUSE客户端和本地客户端。大多数应用程序使用FUSE客户端，该客户端具有较低的采用门槛。对性能要求严格的应用程序与本地客户端集成。

文件系统接口

对象存储正成为数据分析和机器学习的热门选择。 然而，文件系统语义和统一命名空间（文件在目录中组织）为应用程序提供了更大的灵活性。

• • 原子目录操作 对象存储可以通过在对象键中使用斜杠（/）来近似层次目录结构。然而，它并不原生支持像原子移动文件/目录或递归删除整个目录这样的操作。实际上，我们内部应用程序中的一个常见模式涉及创建一个临时目录，将文件写入其中，然后将目录移动到其最终位置。在处理大量小文件时，目录的递归删除至关重要。如果没有它，应用程序必须遍历每个目录并逐个删除文件。
• • 符号链接和硬链接 我们的应用程序利用符号链接和硬链接创建动态更新数据集的轻量级快照，其中新数据作为单独的文件附加。
• • 熟悉的接口 文件接口是众所周知并且无处不在的。 无需学习新的存储 API。许多数据集以 CSV/Parquet 文件格式存储。 将基于文件的数据加载器适配为使用 3FS FUSE 客户端或本地客户端是简单直接的。

FUSE 的局限性

FUSE（用户空间文件系统）通过将 I/O 操作重定向到用户空间进程，简化了文件系统客户端的开发，使用 FUSE 内核模块。 它创造了一个幻觉，使应用程序能够像访问本地文件系统一样访问远程文件系统。 然而，它存在性能限制：

• • 内存复制开销 用户空间文件系统守护进程无法访问应用程序内存。 内核与用户空间之间的数据传输消耗内存带宽并增加端到端延迟。
• • 原始多线程支持 当应用程序发起I/O请求时，FUSE将这些请求放入一个由自旋锁保护的多线程共享队列中。 用户空间文件系统守护进程随后从该队列中检索并处理请求。 由于锁争用，FUSE的I/O处理能力无法随着线程数量的增加而扩展。 我们的基准测试结果表明，FUSE每秒仅处理大约400K的4KiB读取。 进一步增加并发性并不会改善性能，因为锁争用加剧。 perf分析显示，内核空间自旋锁消耗了大量的CPU时间。

大多数应用程序，例如数据分析，在3FS上执行大块写入，或者它们可以在内存中缓冲数据，并在写入缓冲区满时将其刷新到3FS。然而，Linux 5.x 上的 FUSE 不支持对同一文件的并发写入[^1]。应用程序通过并发写入多个文件来克服这一限制，从而最大化总吞吐量。

读取操作表现出更复杂的模式。一些训练任务需要对数据集样本进行随机访问，读取大小从几千字节到每个样本几兆字节不等。而且样本通常在文件中不是 4K 对齐的。数据加载器专门设计用于获取样本批次。但在处理 FUSE 挂载的 3FS 上的小随机读取时，它们的表现较差。SSD 和 RDMA 网络的带宽未得到充分利用。

异步零拷贝 API

将文件系统客户端实现为 VFS 内核模块可以避免上述性能问题。但内核模块开发显著比用户空间系统编程更具挑战性。错误难以诊断，可能导致生产环境中的灾难性故障。例如，机器可能崩溃并且没有日志消息供调试。在升级内核模块时，必须干净地停止所有使用该文件系统的进程；否则，需要重启机器。

基于这些原因，我们选择在FUSE守护进程中实现一个本地客户端。 该客户端提供了一个支持**异步零拷贝I/O**操作的接口。文件元操作仍由FUSE守护进程处理（例如，打开/关闭/状态文件）。应用程序调用open()以获取文件描述符（fd），并通过本地API注册它。然后，它们可以在文件上使用本地客户端执行I/O操作。这种方法确保了元数据操作与POSIX API的一致性，使现有代码的迁移变得更加容易。

异步零拷贝API的灵感来自Linux的io_uring。 以下是API中的关键数据结构：

• • Iov 一个用于零拷贝读/写操作的大内存区域，在用户进程和本地客户端之间共享。InfiniBand内存注册由客户端管理。在本地API中，所有读取的数据将被读入Iov，所有写入的数据应在调用API之前写入Iov。
• • Ior 一个用于用户进程与本地客户端之间通信的小型共享环形缓冲区。Ior的使用类似于 Linux 的 io_uring，用户进程将读/写请求入队，而本地客户端则将这些请求出队以完成。请求以批处理的方式执行，其大小由 io_depth 参数控制。无论来自不同的环还是同一个环，多个批次都是并行处理的。然而，对于多线程应用程序，仍然建议使用多个环，因为共享一个环需要同步，这可能会影响性能。

在本地客户端中，多个线程被创建以从 Iors 中获取 I/O 请求。这些请求被批处理并分发到存储服务，从而减少因小型读请求而产生的 RPC 开销。

文件元数据存储

文件块的位置

3FS 将文件数据划分为相等大小的块，并将其条带化到多个复制链中（复制链和链表在**数据放置部分中定义）。用户可以为每个目录指定链表**、块大小和条带大小。每个块独立存储在多个存储服务上，其块 ID 通过连接文件的 inode id 和块索引生成。

在创建新文件时，元数据服务根据条带大小采用轮询策略从指定的链表中选择连续的复制链。接下来，生成一个随机种子以打乱所选链。这种分配策略确保了数据在链和 SSD 之间的均衡分布。

当应用程序打开文件时，客户端联系元服务以获取文件的数据布局信息。然后客户端可以独立计算块 ID 和数据操作的链，最小化元服务在关键路径中的参与。

译者：将部分决策（计算）下放到客户中。

事务性键值存储上的文件元数据

3FS使用FoundationDB作为其元数据的分布式存储系统。FoundationDB提供了一个键值存储接口，并支持具有可串行快照隔离（Serializable Snapshot Isolation, SSI）的事务。3FS将所有元数据作为键值对存储在FoundationDB中。元服务遵循无状态架构，极大地增强了可维护性，使管理员能够无缝升级或重启服务而不造成中断。当客户端遇到请求失败或超时时，它们可以自动切换到其他可用服务。

文件系统元数据主要由两个核心结构组成：inode和目录条目。Inode存储文件、目录和符号链接的属性信息，每个都由一个全球唯一的64位标识符标识，该标识符单调递增。Inode键通过将**"INOD"**前缀与inode id连接构成，inode id以小端字节顺序编码，以便在多个FoundationDB节点上分散inode。 Inode值根据其类型而异：

• • 所有inode类型包含基本属性：所有权、权限、访问/修改/变更时间。
• • 文件 inode 的附加属性：文件长度、块大小、链表中选择的范围、shuffle 种子。
• • 目录 inode 的附加属性：父目录的 inode ID、子目录/文件的默认布局配置（链表、块大小、条带大小）。父目录的 inode ID 是检测移动目录时循环所必需的。当将 dir_a/dir_b 移动到 dir_c/ 时，我们需要确保 dir_c 不是 dir_b 的后代，这可以通过向上检查 dir_c 的所有祖先来实现。
• • 符号链接 inode 的附加属性：目标路径字符串。

目录项键由 "DENT" 前缀、父 inode ID和条目名称组成。目录项值存储目标 inode ID 和 inode 类型。目录中的所有条目自然形成一个连续的键范围，允许通过范围查询高效列出目录。

元操作利用 FoundationDB 的事务：

• • 用于元数据查询的只读事务：fstat、lookup、listdir 等。
• • 用于元数据更新的读写事务：创建、链接、取消链接、重命名等。

对于写事务，FoundationDB 跟踪读/写键集以形成冲突检测集。当检测到并发事务冲突时，元服务会自动重试该事务。该设计使多个元服务能够并行处理请求，同时保持文件系统元数据的一致性。

动态文件属性

在大多数本地文件系统中，删除已打开的文件会延迟，直到所有相关的文件描述符关闭。因此，有必要跟踪该文件的所有文件描述符。训练作业在启动期间会打开大量文件。存储所有文件描述符会对元服务和 FoundationDB 施加很大负担。由于训练作业不依赖于此功能，3FS不跟踪以只读模式打开的文件描述符。

3FS 为每个以写模式打开的文件描述符（fd）维护一个文件会话，因为删除以写模式打开的文件可能导致来自并发写入的不可回收垃圾块。当删除具有活动写会话的文件时，元服务会延迟删除，直到所有其文件描述符关闭。为了防止离线客户端的会话持续存在，3FS元服务定期检查客户端的存活状态，并清理离线客户端的会话。

文件长度存储在inode中。对于正在积极更新的文件，存储在inode中的长度可能与实际长度不一致。客户端定期（默认每5秒）向元服务报告以写模式打开的每个文件的最大写入位置。如果该位置超过inode中的长度，并且没有并发的截断操作，则该位置被采用为新的文件长度。

由于多个客户端可能进行并发写入，上述方法仅确保文件长度的最终一致性。在处理关闭/fsync操作时，元服务通过查询存储服务中最后一个块的ID和长度来获取精确的文件长度。由于文件数据分布在多个链上，此操作会产生不可忽视的开销。

多个元服务对同一文件长度的并发更新可能导致事务冲突，并导致文件长度计算的重复。为了解决这个问题，元服务使用inode ID和汇合哈希算法将文件长度更新任务分配到多个元服务。

我们的生产环境使用较大的条带大小：200。对于小文件，包含文件块的链的数量远低于这个数字。潜在使用的链的数量存储在文件inode中，并在更新长度时作为提示使用。它以16的初始值开始，每次向更多链写入额外的文件块时翻倍。这使我们能够在更新小文件的长度时避免查询所有200条链。这个优化也可以扩展到小文件的删除。

块存储系统

块存储系统的设计目标是即使在存储介质发生故障时也能实现尽可能高的带宽。3FS的读/写吞吐量应与SSD的数量和客户端与存储服务之间的双向网络带宽线性扩展。 应用程序以无关位置的方式访问存储服务。

数据放置

每个文件块使用分配查询（CRAQ）的链式复制在一系列存储目标上进行复制。在CRAQ中，写请求被发送到头目标并沿着链传播。读取请求可以发送到任何存储目标。通常，读取流量在链中的所有目标之间均匀分配，以实现更好的负载平衡。在每个SSD上创建多个存储目标，这些目标加入不同的链。

假设有6个节点：A、B、C、D、E、F。每个节点有1个SSD。在每个SSD上创建5个存储目标：1、2、... 5。 那么总共有30个目标：A1、A2、A3、...、F5。如果每个块有3个副本，则构建链表如下。

每个链都有一个版本号。如果链发生变化（例如，存储目标离线），则版本号会递增。只有主集群管理器才能对链表进行更改。

可以构建几个链表以支持不同的数据放置需求。例如，可以创建两个链表，一个用于批处理/离线作业，另一个用于在线服务。 这两个表由位于互斥节点和SSD上的存储目标组成。

从逻辑上讲，每个链的状态独立变化。每个链可以包含在多个链表中。链表的概念是为了让元数据服务为每个文件选择一个表，并在表中的链上划分文件块。

恢复期间的流量平衡

假设读取流量在上述链表中的所有存储目标之间均匀分布。当A失败时，其读取请求将被重定向到B和C。在重负载下，B和C的读取带宽会立即饱和，B和C成为整个系统的瓶颈。更换故障的SSD并将数据同步到新的SSD可能需要几个小时。在此期间，读取吞吐量受到影响。

为了减少性能影响，我们可以让更多的SSD共享重定向的流量。在以下链表中，A与其他每个SSD配对。当A失败时，其他每个SSD接收A的读取流量的1/5。

为了在恢复期间实现最大读取吞吐量，负载平衡问题可以被表述为一个平衡的不完全区组设计。最优解是通过使用整数规划求解器获得的。

数据复制

CRAQ是一种针对读取密集型工作负载优化的写全读任意复制协议。利用所有副本的读取带宽对于在全闪存存储系统中实现最高读取吞吐量至关重要。

当存储服务接收到写请求时，它会经过以下步骤：

1. 1. 服务检查写请求中的链版本是否与最新已知版本匹配；如果不匹配，则拒绝请求。写请求可以由客户端或链中的前驱发送。
2. 2. 服务发出RDMA读取操作以提取写入数据。如果客户端/前驱失败，RDMA读取操作可能会超时，写入将被中止。
3. 3. 一旦写入数据被提取到本地内存缓冲区，将从锁管理器获取要更新的块的锁。对同一块的并发写入被阻塞。 所有写入在头目标处被序列化。
4. 4. 服务将块的已提交版本读取到内存中，应用更新，并将更新后的块存储为待处理版本。存储目标可以存储块的两个版本：已提交版本和待处理版本。 每个版本都有一个单调递增的版本号。 已提交版本和待处理版本的版本号分别为 v 和 u，并满足 u = v + 1。
5. 5. 如果服务是尾部，则已提交版本被原子地替换为待处理版本，并向前驱发送确认消息。否则，写请求将被转发到后继者。 当已提交版本被更新时，当前链版本作为一个字段存储在块元数据中。
6. 6. 当确认消息到达存储服务时，该服务用待处理版本替换已提交版本，并继续将消息传播给其前驱。然后释放本地块锁。

假设链中有3个目标：A, B, C。写请求刚刚在A的第5步进入。A将请求转发给后继者B。然后B瞬间失败，转发的写请求丢失。当集群管理器检测到B的失败时，它将B标记为离线，并将其移动到链的末尾，并广播更新后的链表。 一旦A接收到最新的链表，它将写请求转发给新的后继者C。C可能尚未接收到最新的链表，并拒绝该请求。但是A可以继续将请求转发给C。最终，C 获取最新的链表并接受请求。

当读取请求到达存储服务时：

1. 1. 当服务仅拥有已提交版本的块时，该版本将返回给客户端。
2. 2. 与 CRAQ 不同，我们的实现不会向尾部目标发出版本查询。当同时存在已提交版本和待处理版本时，服务会回复一个特殊状态码以通知客户端。客户端可以等待短暂的时间并重试。或者客户端可以发出一个放宽的读取请求以获取待处理版本。

故障检测

集群管理器依赖心跳来检测故障停止故障。 如果集群管理器在可配置的时间间隔内（例如 T 秒）未收到来自服务的心跳，则声明该服务失败。如果服务无法与集群管理器通信超过 T/2 秒，则停止处理请求并退出。心跳可以视为向管理器续租的请求。

元数据服务是无状态的。集群管理器提供的在线元服务列表是一个简单的服务发现机制，帮助客户端与元数据服务建立连接。 如果一个元服务出现故障，客户端可以切换到任何其他元数据服务。

集群管理器在存储服务的成员变更中扮演着更为关键的角色。 它维护着链表和存储目标状态的全局视图。每个存储目标都有一个公共状态和一个本地状态。

公共状态指示它是否准备好处理读取请求，以及写请求是否会被传播到它。公共状态与链表一起存储，并分发给服务和客户端。

本地状态仅由存储服务和集群管理器知道，并存储在集群管理器的内存中。 如果存储目标发生介质故障，相关服务将在心跳中将目标的本地状态设置为离线。 如果存储服务宕机，由该服务管理的存储目标将被标记为离线。

存储目标可以根据最新的本地状态在不同的公共状态之间变化。本地状态充当触发事件的角色。集群管理器定期扫描每个链，并根据状态转换表更新链上目标的公共状态。

• • 如果链被更新，链版本将递增。
• • 如果存储目标被标记为离线，它将被移动到链的末尾。
• • 如果存储服务发现任何本地存储目标的公共状态为lastsrv或离线，它将立即退出。服务可能因网络分区错误而与集群管理器隔离。
• • 一旦同步状态下存储目标的数据恢复完成，存储服务将在发送给集群管理器的后续心跳消息中将目标的本地状态设置为最新。

数据恢复

当存储服务退出（例如，进程崩溃或在升级期间重启）或发生存储介质故障时，所有相关的存储目标将被标记为离线，并由集群管理器移动到链的末尾。一旦服务重启，服务上的每个目标将独立进入恢复过程。整个恢复过程与正常活动重叠，并最小化任何中断。

当之前离线的存储服务启动时：

1. 1. 服务定期从集群管理器拉取最新的链表。但在所有存储目标在最新链表中被标记为离线之前，它不会发送心跳。 这确保了所有目标都会经过数据恢复过程。
2. 2. 当写请求在恢复期间到达时，请求始终是全块替换写入。本地已提交版本被更新，任何现有的待处理版本被放弃。 由于当前服务是尾部，确认消息被发送给前驱。前驱的完整状态通过连续的全块替换写入流复制到返回服务。
3. 3. 在存储目标的数据恢复开始之前，前驱向返回服务发送一个转储块元数据请求。然后服务迭代本地块元数据存储，以收集目标上所有块的ID、链版本和已提交/待处理版本号，并将收集到的元数据回复给前驱。
4. 4. 当同步完成消息到达时，服务知道存储目标是最新的。它在发送给集群管理器的心跳消息中将目标的本地状态设置为最新。

当存储服务发现之前离线的后继者上线时：

1. 1. 服务开始将正常的写请求转发给后继者。客户端可能只更新块的一部分，但转发的写请求应包含整个块，即全块替换写入。
2. 2. 服务向后继者发送一个转储块元数据请求。一旦接收到后继目标上所有块的元数据，它会在本地目标上收集块元数据。然后，它比较两份块元数据，以决定哪些块应该被转移。
3. 3. 选定的块通过发出全块替换写请求转移到后继者。

• • 首先为每个块获取块锁。
• • 链版本、已提交版本号和块内容被读取并通过发送全块替换请求转移到后继者。
• • 块锁被释放。

用于决定哪些块应该被转移的规则是：

• • 如果一个块仅存在于本地目标上，则应该被转移。
• • 如果一个块仅存在于远程目标上，则应将其删除。
• • 如果本地块副本的链版本大于远程块副本的链版本，则应进行传输。
• • 如果本地/远程块副本的链版本相同，但本地已提交版本号不等于远程待处理版本号，则应进行传输。
• • 否则，两个块副本要么是相同的，要么正在被进行中的写请求更新。

块和元数据

文件块存储在块引擎中。 在每个SSD上，块引擎的持久存储由固定数量的数据文件组成，用于存储块数据，以及一个RocksDB实例，用于维护块元数据和其他系统信息。此外，块引擎维护一个内存中的块元数据缓存，以提高查询性能。 实现了一个块分配器，以快速分配新块。块引擎接口通过以下操作提供线程安全的访问：

1. 1. open/close 通过从RocksDB加载元数据并重建块分配器状态来初始化引擎。
2. 2. get 通过哈希映射缓存检索块元数据和引用计数句柄，支持以 O(1) 的平均复杂度进行并发访问。
3. 3. update 通过在修改数据之前分配新块来实现写时复制 (COW) 语义。 旧块在所有句柄释放之前仍然可读。
4. 4. commit 通过写入批次将更新的块元数据提交到 RocksDB，以确保原子更新；同步刷新块元数据缓存。

块数据最终将存储在物理块上。物理块大小范围从 64KiB 到 64MiB，按二的幂次递增，总共有 11 种不同的大小。分配器将分配与实际块大小最接近的物理块。为每种物理块大小构建一个资源池，每个池包含 256 个物理文件。物理块的使用状态通过位图在内存中维护。当物理块被回收时，其位图标志被设置为 0。 块的实际存储空间保持不变，并将优先用于后续分配。当没有可用的物理块时，fallocate() 将用于在物理文件中分配一个连续的大空间，创建256个新的物理块——这种方法有助于减少磁盘碎片。

在对一个块执行写操作时，分配器首先分配一个新的物理块。系统随后将现有块数据读取到缓冲区，应用更新，并将更新后的缓冲区写入新分配的块。对于追加操作，实施了一种优化的过程，其中数据直接在现有块的末尾就地添加。从新块的位置和现有块元数据构建一个新的元数据副本。随后，新的块元数据和新旧物理块的状态在RocksDB中原子性地更新。