文件系统元数据：inode 与目录分片

文件系统 = 对象存储 + 一棵会并发变形的树

L3 结束时 forge 是一个对象存储:put/get/delete,key 之间互不相干。 文件系统难就难在多出来的那棵树:路径要逐级解析,目录里能 ls 出孩子, rename 要原子地把一个子树从这里搬到那里 —— 而这一切都发生在并发之下。 你运维 CephFS 时见过 MDS 在「几千个客户端同时 create」下 CPU 打满, 那不是 Ceph 写得差,是这棵树本身难伺候。

这节课在 forge-fs crate 里把树立起来:设计 inode 和目录项的结构, 按 Weka bucket 的思路把它们哈希分片到多个 forge-node,最后啃最硬的骨头 —— 跨分片 rename。

POSIX 语义盘点:先认清性能杀手

动手前把 POSIX 的账算清楚。以下操作的成本天差地别,设计时要区别对待:

inode 与目录项:盘上结构

forge-fs 的两个核心结构。注意版本号 —— L1 学过的规矩,格式定了就改不动, 所以第一天就留演进余地:

/// forge-fs: 盘上 inode,serde + bincode 编码,存入 forge-node 的元数据分片
#[derive(Serialize, Deserialize, Clone)]
pub struct Inode {
    pub version: u8,          // 结构版本,现在是 1
    pub ino: u64,
    pub kind: FileKind,       // File / Dir / Symlink
    pub mode: u32,
    pub uid: u32,
    pub gid: u32,
    pub nlink: u32,
    pub size: u64,
    pub mtime_ns: u64,
    pub ctime_ns: u64,
    /// 数据布局的根引用,下一课(条带化)填充语义
    pub extent_root: Option<ExtentRef>,
}

/// 目录项:key 是 (父目录 ino, 文件名),value 是子 inode 号
/// 存放在**父目录 ino 所属的分片**上 —— readdir 只查一个分片
#[derive(Serialize, Deserialize)]
pub struct DentryKey {
    pub parent_ino: u64,
    pub name: Vec<u8>,        // 原始字节,不假设 UTF-8(POSIX 允许任意非 0 字节)
}

两个决定值得停下来想:

1. 目录项跟着父目录走,而不是跟着子文件走 —— readdir 是一次单分片范围扫描, 不用广播全集群。代价是 create 时目录项和子 inode 可能落在不同分片,写要跨两处。
2. 文件名用 Vec<u8> 不用 String —— POSIX 文件名是字节串,不保证 UTF-8。 你运维时见过乱码文件名删不掉的工单,根源常常是某层代码擅自假设了编码。

inode 分片:哈希还是范围

元数据要摊到多个 forge-node,切法只有两派:

• 范围分片(如 HDFS federation、TiKV):ino 01M 归节点 A,1M2M 归节点 B。 局部性好,但顺序分配的 ino 会让最新创建的文件全挤在一个分片 —— 编译、解压 这类负载正是疯狂创建新文件的,热点正好砸在一个节点上。
• 哈希分片(Weka bucket 的选择):shard = hash(ino) % shard_count。 局部性没了,但负载天然均匀 —— 这正是上一课讲的「用哈希拆热点」。

forgefs 选哈希,和 Weka 同派。实现上有个细节:ino 是顺序分配的整数, 直接取模会让相邻 ino 规律地散布,要先做一次位混合:

/// forge-fs: ino -> 分片号。分片数固定 256,远大于节点数(Weka 64k bucket 的粗粒度版)
pub const SHARD_COUNT: u32 = 256;

pub fn shard_of(ino: u64) -> ShardId {
    // Fibonacci hashing:一次乘法把低位规律打散到高位
    let mixed = ino.wrapping_mul(0x9e37_79b9_7f4a_7c15);
    ShardId((mixed >> 32) as u32 % SHARD_COUNT)
}

分片到节点的映射复用 L3 的一致性哈希环:256 个分片当作 256 个 key 放上环, 节点增减时只有少量分片换主。分片内的操作串行执行(每个分片一个任务队列, 单消费者)—— 单写者模型,分片内不需要锁,和 Weka bucket 一致。

大目录:一个分片装不下怎么办

目录项跟着父目录走,意味着一个千万级条目的大目录全压在一个分片上 —— 你运维 Lustre 时见过单目录百万文件把 MDT 拖死的场景。工业级解法是目录分裂: 目录超过阈值后,按 hash(name) 把目录项二次切分到多个分片(GPFS 的可扩展哈希目录、 Weka 也是类似思路)。

forgefs 做半个:结构上预留、实现上不做。Inode 里 Dir 类型带一个 dir_layout: DirLayout 字段,现在只有 DirLayout::Single 一种取值, 分裂逻辑留作扩展。理由是诚实的工程判断:分裂 + 分裂过程中的并发 readdir 是几周的工作量,而我们的里程碑(编译真实项目)单目录最多几千个条目, 一个分片毫无压力。知道坑在哪、留好演进位,比现在就把坑填满更重要。

rename 跨分片:分布式事务的最小剂量

压轴难题。rename("/a/x", "/b/y") 里 a 和 b 的目录项可能在不同分片、不同节点, POSIX 要求这个操作原子:任何时刻观察,x 和 y 恰好存在一个,崩溃也不例外。

完整方案是 2PC 或 Percolator 式事务,但 forgefs 用不着全套 —— rename 只涉及恰好两个分片、各一条记录,可以用「意图日志 + 幂等应用」做一个 最小剂量版本:

/// forge-fs: 跨分片 rename 的三步协议。协调者 = 源分片
pub async fn rename_cross_shard(
    &self,
    src: DentryKey,
    dst: DentryKey,
    txn_id: TxnId,
) -> Result<(), FsError> {
    // 1. PREPARE:源分片持久化意图记录(txn_id, src, dst),此后源目录项进入"迁移中"
    self.shard(shard_of(src.parent_ino))
        .prepare_rename(txn_id, &src, &dst).await?;

    // 2. COMMIT:目标分片写入新目录项,携带 txn_id 保证重放幂等
    self.shard(shard_of(dst.parent_ino))
        .commit_rename(txn_id, &dst).await?;

    // 3. FINALIZE:源分片删除旧目录项和意图记录
    self.shard(shard_of(src.parent_ino))
        .finalize_rename(txn_id).await?;
    Ok(())
}

关键在崩溃恢复:分片启动时扫描未完成的意图记录,向目标分片查询 txn_id 是否已提交, 已提交则继续第 3 步,未提交则回滚意图 —— 每一步都幂等,重放任意次结果相同。 「迁移中」状态的目录项对 lookup 仍然可见(返回旧值),保证过程中无空窗。

这就是分布式事务的最小剂量:不引入全局事务管理器,靠"意图先落盘 + 幂等 + 恢复对账" 覆盖仅有的一种两分片场景。L1 的 WAL 直觉(先写意图再动手)在这里第三次兑现。

在 forge workspace 新增 crates/forge-fs(纯库,不依赖 fuser 和网络):

1. 定义 Inode(version/ino/kind/mode/uid/gid/nlink/size/mtime_ns/ctime_ns/extent_root)、DentryKey(parent_ino + name: Vec<u8>)、FileKind,serde 序列化;
2. 实现 shard_of(ino: u64) -> ShardId:Fibonacci 位混合后对 SHARD_COUNT=256 取模;
3. 定义 trait MetaShard,方法:get_inode / put_inode / lookup(parent_ino, name) / readdir(parent_ino, offset) / create(parent_ino, name, inode) / unlink,全部返回 Result,错误类型 FsError 用 thiserror 定义,含 NotFound / Exists / NotADirectory / ShardUnavailable;
4. 提供内存实现 MemShard(BTreeMap,readdir 用范围扫描)用于单元测试;
5. 实现跨分片 rename 三步协议:prepare_rename 写意图记录,commit_rename 幂等写入(同 txn_id 重放返回 Ok),finalize_rename 清理;再写恢复函数 recover_pending:扫描意图记录,向目标分片查询后决定 roll-forward 或回滚;
6. 测试必须覆盖:同名 create 冲突、readdir 分页、rename 后源不存在目标存在、以及"commit 成功后协调者崩溃、恢复后 roll-forward"的模拟(手动分步调用制造中间状态)。

生产路径不许 unwrap。完成后跑 cargo test -p forge-fs 和 cargo clippy,贴结果。

小结

• POSIX 操作成本分三档:lookup 类要快且可缓存,create/unlink 跨两处要有序,rename 跨分片是事务;atime 在设计里直接杀掉
• 目录项跟着父目录 ino 走,readdir 单分片搞定;文件名是字节串不是 UTF-8
• inode 哈希分片(256 片,位混合后取模),分片内单写者串行 —— Weka 64k bucket 的粗粒度等价物
• 大目录分裂:留好 DirLayout 演进位但不实现,里程碑负载用不上
• 跨分片 rename 用意图日志 + 幂等 + 恢复对账,是分布式事务的最小剂量;WAL 直觉第三次兑现