文件系统元数据：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 直觉(先写意图再动手)在这里第三次兑现。

目标:做出 forgefs 的元数据层 —— 一棵能被切成多片、摊在多台机器上,还能保证改名原子的目录树。这一层是纯逻辑,不碰挂载点、不碰网络,必须能脱离真集群单独测试。

行为规格:
1. 文件元数据要记的东西:结构版本号(格式定了就改不动,第一天就要留演进余地)、inode 号、类型(普通文件 / 目录 / 符号链接)、权限位、属主属组、硬链接数、大小、mtime 与 ctime,外加一个指向数据布局的引用(下一课再填);
2. 文件名当原始字节处理,不假设 UTF-8 —— POSIX 允许任意非 0 字节,哪一层擅自假设编码,以后就会出「乱码文件名删不掉」的工单;
3. 目录项按(父目录 inode 号, 文件名)索引,存放在**父目录所属的那一片**上,让列目录只查一片、不广播全集群;
4. inode 按哈希分成固定 256 片:ino 是顺序分配的整数,直接取模会让相邻文件规律地撞片,必须先做一次位混合再取模;每一片内的操作串行执行,片内不需要加锁;
5. 跨片改名必须原子:任何时刻观察,源和目标恰好存在一个,进程被 kill 也不例外。协议是三步 —— 源片先把「我要搬」这个意图落盘,目标片写入新目录项,源片再删掉旧目录项和意图记录。每一步重放任意次结果都相同;
6. 崩溃恢复:启动时扫未完成的意图记录,向目标片查这笔搬迁是否已经生效,生效就往前推完,没生效就回滚。整个过程中源目录项对查找仍然可见(返回旧值),不许出现谁都查不到的空窗;
7. 错误要分得清:不存在、已存在、不是目录、分片不可用 —— 上层要靠这几类错误翻译成 errno 给内核。

交付:实现 + 一个纯内存版本供测试使用 + 测试覆盖这几件事:同名创建冲突、列目录分页、改名之后源没了目标有了,以及三个崩溃时刻(意图落盘后崩、目标片写入后崩、源片清理前崩)各自恢复后状态合法。跑通后把测试与静态检查结果贴给我。分几个模块、用什么库、错误怎么建模你定,最后告诉我为什么。

小结

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