学习 3FS。
设计
主要概括了 design notes。
需要解决的问题
OSS 方面：
- 现在的 OSS 并不支持原子地移动一系列文件或者一整个目录，或者递归地删除整个目录。而 3FS 的场景（实际上数据库的场景也是这样）涉及要创建一个临时目录，然后对这个目录写入数据，最后将这个目录 move 到最终的位置。
- 3FS 需要广泛使用 symbolic 或者 hard 链接
- 提供一个熟悉的文件接口，我理解这也是 3FS 选择 FUSE 的原因
FUSE 方面：
- 在 Fuse 学习一文中介绍了为什么 FUSE 不支持 Zero Copy。但这也是 FUSE 的缺点之一。
- FUSE 使用一个由 spin lock 保护的多线程共享的队列。3FS 团队的测试显示，400K 4KiB reads per second 的写入负载之后，因为 lock contention 的方法。
- Linux 5.x 上的 fuse 不支持对一个文件的并发写。所以很多需要更大带宽的程序会并发写多个文件。
- 对小的随机非对齐读性能不好，SSD 和 RDMA 网络的带宽没有被利用充分。
但是将 client 实现为一个 VFS 内核模块则能解决上面说的问题，但也更有挑战性。内核的 bug 更难定位和修复。此外，升级的时候需要停掉所有访问这个 fs 的进程，或者重启。
因此，3FS 选择在 FUSE daemon 里面设计一套原生的 client，由它来支持异步的 Zero copy IO。其中，File meta operation 例如 open、close 等还是被 FUSE daemon 处理。但是在 open 的时候会把拿到的 fd 通过 native API 注册。然后就可以通过 native client 去读取数据了。
这个 API 类似于 io_uring，其中关键结构如下：
- Iov
user process 和 native client 共享的内存 - Ior
user process 和 native client 通过这个 ring buffer 进行交互。具体方式类似于 io_uring。
请求会被按照 io_depth 攒批执行，不同的 batch 的执行是并行的。
Metadata 存储
chunk 的分布
文件按 chunk 为粒度，被条带化到多个 replication chain 中。
创建新文件的时候，会根据 stripe size，使用 round robin 的方式，选择一系列的 chain。选出来的这些 chain，会随机分给不同的 chunk 写入。
存储 file atributes
为什么 3FS 的 inode 里的 length 会不准确？因为写路径走的是 CRAQ，而 inode 是在 metadata service 里面的。如果每次写操作完都更新一下 metadata，那么会多一次 metadata RTT，写放大严重，吞吐和延迟都会变差。
但是如果 metadata 迟迟不更新，例如是 100mb，而客户端写到 120mb 就挂了，此时，虽然数据已经通过 CRAQ 持久化到 chunk 存储了，但因为读的时候从 metadata 获得的长度偏小，所以还是在效果上丢失数据。
一种方式是按照 interval 上报更新 metadata，但这就存在不一致窗口。不过先考虑容灾问题，大概有两个方案：
- 重启之后，从 chunk 存储中恢复数据，并由此更新 metadata。但是从 chunk 扫描数据恢复的代价很大
- 3FS 的设计是由 client 按照 interval 上报 max writer position，因为 client 上报的 position 一定是已经被 tail 提交了的，所以是安全的。但是如果 client 长期丢失，那么 gap 就得通过第一种方式补齐了。
Chunk 存储
Suppose there are 6 nodes: A, B, C, D, E, F. Each node has 1 SSD. Create 5 storage targets on each SSD: 1, 2, … 5. Then there are 30 targets in total: A1, A2, A3, …, F5. If each chunk has 3 replicas, a chain table is constructed as follows.
| Chain | Version | Target 1 (head) | Target 2 | Target 3 (tail) |
|---|---|---|---|---|
| 1 | 1 | A1 |
B1 |
C1 |
| 2 | 1 | D1 |
E1 |
F1 |
| 3 | 1 | A2 |
B2 |
C2 |
| 4 | 1 | D2 |
E2 |
F2 |
| 5 | 1 | A3 |
B3 |
C3 |
| 6 | 1 | D3 |
E3 |
F3 |
| 7 | 1 | A4 |
B4 |
C4 |
| 8 | 1 | D4 |
E4 |
F4 |
| 9 | 1 | A5 |
B5 |
C5 |
| 10 | 1 | D5 |
E5 |
F5 |
这里的 Version 是配置的 Version，节点下线会导致这个增大。
这里的一个 Chain 类似于一个 Raft Group 的概念。但是它也不是像 TiKV 一样跟某一段数据绑定的。一个 Chain 可以被多个 chain table 包含。引入 chain table 的概念，这样对于每一个 file，metadata service 就可以为它选一个 chain table，并根据这个 table 中的 Chain 去 strip 这个 file 的所有 chunk。
Balanced traffic during recovery
如果一个节点 A 故障了，就需要由 Chain 中的其他节点来承担原来 A 的流量。而之前的 Chain table 中，A 节点基本上只和 B、C 玩。
在新的架构中，A 在 Chain 2 里和 B/D 在一起，在 Chain 5 里和 C/F 在一起。
Data replication
一个 Write request 可能是从 client 或者 Chain 的前驱发送出来的。一个节点收到 Write request 后的处理：
- 校验 write request 中的 chain version。
- 通过 RDMA Read 去 pull 写入的数据。如果 client 或者前驱挂掉了，导致拿不到数据。写入就 abort。
- Once the write data is fetched into local memory buffer, a lock for the chunk to be updated is acquired from a lock manager. Concurrent writes to the same chunk are blocked. All writes are serialized at the head target.
- 读取这个 Chunk 的 committed version，对它 apply change，然后将更新后的版本存储为 pending version。版本号是单调连续递增的。
- If the service is the tail, the committed version is atomically replaced by the pending version and an acknowledgment message is sent to the predecessor. Otherwise, the write request is forwarded to the successor. When the committed version is updated, the current chain version is stored as a field in the chunk metadata.
- When an acknowledgment message arrives at a storage service, the service replaces the committed version with the pending version and continues to propagate the message to its predecessor. The local chunk lock is then released.
实现
Chain replication
CRAQ 的最大的特点是：复制链路是固定的，而 Raft 的复制链路因为存在 Quorum 是随机的。因此，对于单个 entry 的复制，Raft 的延迟可能会比 CRAQ好，但是 CRAQ 的延迟和吞吐更稳定，可以被预测。
延迟维度的对比：
- Raft 最优
a. 条件：follower 延迟几乎一致、没有网络问题
b. commit latency 约等于 RTT - Raft 最劣
a. 条件：quorum 中某个 follower 抖动，例如出现了 Write Stall
b. Throughput 约等于 1 / avg([max(follower latency)]，这里的 avg 因为抖动是不均匀的，因为多数派每次都不一定一样。 - CRAQ 最优
a. 条件：链上每个 node 的 hop_latency 相同，管道用满
b. Throughput ≈ min(hop throughput)，这个很简单，木桶效应嘛。 - CRAQ 最劣
a. 条件：链上每个 node 变慢
b. 存在木桶效应，每个 entry 的提交都被固定变慢。
吞吐维度的对比：
- Raft 最优
a. 条件：同延迟。
b. Throughput ≈ follower replication rate - Raft 最劣
a. 条件：同延迟。
b. commit latency 等于 max(quorum follower latency)，出现了木桶效应 - CRAQ 最优
a. 条件：链上每个 node 的 hop_latency 相同
b. commit latency 约等于 chain_length * hop_latency。因为 CRAQ 在 Tail 返回确认，所以 3 副本也是两次数据传输，和 Raft 的 1 个 RTT 是接近的。但是链长了，CRAQ 就会变慢。 - CRAQ 最劣
a. 条件：存在一个很慢的 node
b. 同上，但是木桶效应被放大很明显。
CRAQ 的其他特点：
- 没有 quorum 容错
- failover 不需要重新选主，但需要重构链。需要根据挂的是哪一个来讨论。
