3fs learning

1. 设计

1.1 架构

1.1.1 客户端

fuse（需要多次内核态和用户态拷贝，多线程锁抢占性能不佳）
Native client（USRBIO）
- File metadata 仍然走fuse daemon流程（例如open/close/stat）。
- 数据通路走native client：自己开发的library动态库
- 每个 USRBIO 实例使用一个 Iov 文件和一个 Ior 文件
  - Iov 文件用来作为读写数据的 buffer
    - 用户提前规划好需要使用的总容量
    - 文件创建之后 FUSE Daemon 将该其注册成 RDMA memory buffer，进而实现整个链路的零拷贝
  - Ior 文件用来实现 IoRing
    - 用户提前规划好并发度
    - 在整个文件上抽象出了提交队列和完成队列，具体布局参考上图
    - 文件的尾部是提交完成队列的信号量，FUSE Daemon 在处理完 IO 后通过这个信号量通知到用户进程
- 一个挂载点的所有 USRBIO 共享 3 个 submit sem 文件
  - 这三个文件作为 IO 提交事件的信号量（submit sem），每一个文件代表一个优先级
  - 一旦某个 USRBIO 实例有 IO 需要提交，会通过该信号量通知到 FUSE Daemon
- 所有的共享内存文件在挂载点 3fs-virt/iovs/ 目录下均建有 symlink，指向 /dev/shm 下的对应文件。

1.1.2 服务端

cluster manager：集群状态管理，使用例如etcd等保证，实际使用FoundationDB 。
meta service：使用FoundationDB存储元数据。
storage service：利用Chain Replication with Apportioned Queries保证一致性。

1.2 无缓存（针对大模型场景随机读设计，缓存失效）

在存储系统发展的早期，DRAM 缓存加 HDD 是主流方案，缓存设计弥补了硬件性能的巨大差距。随着 SSD 的引入，DRAM+SSD 的组合成为优化热点数据的利器。然而，全闪存时代的到来让复杂的缓存机制逐渐成为瓶颈。NVMe SSD 的超高性能，使得 DRAM 缓存在某些场景下反而拖慢了系统效率。

1.3 链式(CRAQ )

1.3.1 具体操作流程

CARQ标准实现写操作流程：

客户端把请求发给chain中的head target.
head target本地执行完写请求后，把请求转发给 second target， second target同样先完成本地写操作后转发tail target.
tail target 写成功后，会返回ack给前一个target，同样的ack最后返回给head target.
head target返回给client，应答客户端成功。

3FS的的具体写操作

storage service接收到write request后，需要检查request带的chain的版本是否是本地最新的版本。如果不是，拒绝该write请求。
写操作：target service数据通过RDMA Read操作实现，也就说是通过pull的方式拉取的。
不支持对同一个chunk的并发操作。在head target实现对同一个chunk的并发操作的串行访问：当数据写入到target的memory buffer中时，会对该chunk加lock锁住。
每个storage service节点上可能存在同一个chunk的两个版本：committed version和 pending version. 版本号都是单调增加的：pending version = committed version + 1
在tail target，如果写操作成功，更新commited version为最新的pending version，并返回给前一个（predecessor） target
当每个target收到后面（successor）target的成功的ack返回消息，committed version就会变为最新的pending version，并把ack信息继续返回给predecessor target，本地的chunk lock会被释放。
head target会做同样的操作：修改commited version，释放chunk lock，返回客户端写操作成功的ack消息。

3FS读操作

3FS的读操作可以发送给任意一个chunk副本：

当storage service收到读请求，检查如果对应的data chunk只有一个committed version，就把该版本的数据直接返回给client
1. NodeX 检查本地 commitVer 和 updateVer 是否相等；
  - 步骤 2.1：如果不等，说明有其它 flying 的写请求，通知 Client 重试；
  - 步骤 2.2：如果相等，则从本地 chunk 读取数据，并通过 RDMA 写给 Client；
和原始的CRAQ不同，3FS的实现并没有去tail target上去查询确认版本信息。而是提供了两个选项：
1. 直接返回给客户端一个special status code，用户等一段时间后去重试。
2. 客户端对数据一致性要求不敏感，可以直接返回pending version版本的数据给客户端。

错误处理

如果chain中的target故障，就把该target从chain中删除，然后请求重试。

3FS系统中的具体处理方法是把故障的target添加到chain链的末尾并标记为offline状态。

1.3.2 优化

写操作顺序确认（Write-All）：虽然写操作需沿链顺序传播到所有节点，但RDMA的特性显著优化了这一过程：
- RDMA的单边操作（One-Sided）：节点间通过RDMA直接写入下一节点的内存，无需目标节点CPU介入，降低写延迟。
- 流水线化传输：链中节点可并行处理RDMA写入请求，利用高带宽网络实现高效流水线，减少整体写时延。
读操作完全卸载：由于读请求由任意节点直接通过RDMA响应，主机的CPU无需处理网络协议栈，释放计算资源用于其他任务（如元数据管理或写协调）。
批量处理与高效同步：RDMA支持大规模并发数据传输，CRAQ的版本控制机制（如元数据一致性标记）可快速同步，避免传统网络协议中的ACK风暴。

1.3 小文件以及布局

FFRecord

布局

1.4 数据恢复

存储服务崩溃、重启、介质故障，对应的存储 Target 不参与数据写操作，会被移动到 chain 的末尾。

数据恢复流程

步骤 1：Local Node 向 Remote Node 发起 meta 获取，Remote Node 读取本地 meta；
步骤 2：Remote Node 向 Local Node 返回元数据信息，Local Node 比对数据差异；
步骤 3：若数据有差异，Local Node 读取本地 chunk 数据到内存；
步骤 4：Remote Node 单边读取 Local Node chunk 内存数据；
步骤 5：Remote Node 申请新 chunk，并把数据写入新 chunk。

Sync Data 原则：

如果 chunk Local Node 存在 Remote Node 不存在，需要同步；
如果 Remote Node 存在 Local Node不存在，需要删除；
如果 Local Node 的 chain version 大于Remote Node，需要同步；
如果 Local Node 和Remote Node chain version 一样大，但是 commit version 不同，需要同步；
其他情况，包括完全相同的数据，或者正在写入的请求数据，不需要同步。

2. 思考

2.1 分层kv-cache

3FS提供kv-cache的来源，本地nvme作为kv-cache的缓存，一级位于显存中。使用类似vllm的方式加载或分配kv-cache。

2.2 向量索引

使用向量数据库索引，根据索引拉取3FS的kvcache。

2.2.1 基于树的索引

KD-Tree (K-Dimensional Tree)
- 原理：递归地将数据空间沿坐标轴分割成超矩形区域，构建二叉树。
- 优点：适合低维数据（维度 < 20），支持精确搜索。
- 缺点：高维数据性能急剧下降（“维度灾难”）。
- 应用场景：小规模低维数据集（如地理坐标搜索）。
Ball Tree
- 原理：将数据划分为嵌套的超球体，减少距离计算次数。
- 优点：相比 KD-Tree，在高维数据中表现更好。
- 缺点：构建和查询成本较高，适合中等维度。
- 应用场景：中等维度数据（如特征向量分类）。
Annoy (Approximate Nearest Neighbors Oh Yeah)
- 原理：通过随机投影构建多棵树，利用投票机制提升搜索效率。
- 优点：内存占用低，支持并行查询。
- 缺点：需要调参（树的数量、搜索节点数）。
- 应用场景：中等规模高维数据（如 Spotify 音乐推荐）。

2.2.2 基于哈希的索引

LSH (Locality-Sensitive Hashing)

原理：通过哈希函数将相似向量映射到相同桶中，牺牲精度换速度。
优点：查询速度快，适合超大规模数据。
缺点：参数敏感，召回率较低。
变体：Multi-probe LSH（提升召回率）。
应用场景：海量数据快速粗筛（如去重、预过滤）。

2.2.3 基于图的索引

HNSW (Hierarchical Navigable Small World)
- 原理：构建多层图结构，上层为稀疏图用于快速导航，下层为稠密图用于精细搜索。
- 优点：高召回率、低延迟，支持动态更新。
- 缺点：内存占用较高。
- 应用场景：高性能实时搜索（如 Milvus、Elasticsearch）。
NSW (Navigable Small World)
- 原理：单层图结构，通过贪心算法逐步逼近目标节点。
- 优点：实现简单，适合中小规模数据。
- 缺点：性能随数据量增长下降明显。
- 应用场景：小规模实时搜索。

2.2.4 基于量化的索引

PQ (Product Quantization)
- 原理：将高维向量切分为子向量，分别量化并构建码本，用笛卡尔积压缩向量。
- 优点：大幅减少内存占用，适合超大规模数据。
- 缺点：量化误差可能影响精度。
- 应用场景：大规模图像检索（如 Facebook Faiss）。
IVF (Inverted File Index)
- 原理：先聚类（如 K-Means），再对每个簇构建倒排索引，搜索时仅遍历最近簇。
- 优点：结合聚类加速，适合非均匀分布数据。
- 缺点：聚类质量影响性能。
- 变体：IVF-PQ（结合量化进一步压缩）。
- 应用场景：大规模相似性搜索（如 Faiss 的 IVF 系列）。

2.3.5 混合与优化方案

SCANN (Scalable Nearest Neighbors)
- 原理：结合树、哈希和量化，动态选择最优搜索路径。
- 优点：平衡速度与精度，适合超大规模数据。
- 应用场景：Google 的大规模向量检索。
DiskANN
- 原理：结合图索引与磁盘存储优化，减少内存依赖。
- 优点：支持内存受限场景。
- 应用场景：十亿级数据检索（如微软 Bing 搜索）。