文件系统的树：从 ext4 extent tree 到 btrfs CoW B-tree

假设你有一个 1TB 的数据库文件，应用层发起 pread(fd, buf, 4096, 847293510144)——读取文件偏移量约 789GB 处的一个 4KB 页。内核需要把这个逻辑偏移量翻译成物理磁盘块号，然后发起块 I/O。

这个翻译必须快。数据库每秒可能发起几十万次随机读，每次都要做一次逻辑到物理的映射。O(n) 遍历？不可能。O(1) 直接索引？文件太大，索引本身就放不下。

答案是树。几乎所有现代文件系统都用某种形式的树来组织磁盘上的元数据。但”用什么树”和”怎么用”，各家文件系统的选择截然不同——ext4 用 extent tree，XFS 用 B+tree，btrfs 用 CoW B-tree，ZFS 用间接块树，F2FS 用 NAT 表加节点树。

这篇文章从最底层的数据结构出发，逐一拆解五种主流 Linux 文件系统的树形结构设计，对比它们的权衡取舍，并附上一个简化版 extent tree 的 C 实现。

一、文件系统为什么需要树

最朴素的方案：连续分配

最简单的文件系统可以把整个文件连续存放在磁盘上——文件的第 N 个块就是磁盘上起始块号加 N。这就是 FAT 文件系统的连续分配模式。

问题很明显：文件增长时如果后面的空间被占了怎么办？要么移动整个文件（代价极高），要么不允许文件增长。

所以现代文件系统都允许文件的块不连续存放。但一旦允许不连续，就需要某种数据结构记录”逻辑块 L 对应物理块 P”的映射关系。

间接块映射：ext2/ext3 的方案

ext2/ext3 的 inode 里有 15 个块指针：

struct ext2_inode {
    /* ... */
    __le32 i_block[15];
    /*  [0..11]   直接块（12 个）
     *  [12]      一级间接块
     *  [13]      二级间接块
     *  [14]      三级间接块
     */
};

以 4KB 块大小为例，每个块能存 1024 个 32 位块号（4096 / 4 = 1024）：

• 直接块：12 x 4KB = 48KB
• 一级间接：1024 x 4KB = 4MB
• 二级间接：1024 x 1024 x 4KB = 4GB
• 三级间接：1024 x 1024 x 1024 x 4KB = 4TB

理论上能表示最大 4TB 的文件。但问题在于：

1. 元数据开销：一个 4GB 的文件需要 1 个一级间接块 + 1024 个二级间接块，光元数据就要 4MB 多。
2. 随机访问深度：访问文件末尾的块需要 3 次额外的磁盘读取（三级间接 → 二级间接 → 一级间接 → 数据块）。
3. 大量连续块的浪费：如果文件是顺序写入的，块 0 到块 999999 可能是连续的物理块，但 ext2/ext3 仍然要逐个记录每个块号。

第三点是最致命的。现代硬盘上，顺序分配是常态——一个 1GB 的文件可能就是连续的 262144 个 4KB 块。用间接块方案，需要 262144 个 32 位指针（1MB 的元数据）来记录这个完全规律的映射。

磁盘 I/O 模型与树的必要性

在讨论树之前，先理解磁盘 I/O 的基本约束。对于旋转磁盘（HDD）：

• 顺序读取：~200 MB/s，受限于磁盘转速和面密度
• 随机读取：~200 IOPS（每次寻道约 5ms），受限于磁头移动
• 顺序/随机比：约 1000:1

对于固态硬盘（SSD）：

• 顺序读取：~3 GB/s（NVMe）
• 随机读取：~500,000 IOPS（4KB 随机读），每次约 0.02ms
• 顺序/随机比：约 6:1

这意味着文件系统的元数据结构必须满足两个要求：第一，减少随机 I/O 次数（每次树的层间跳转可能是一次随机读）；第二，尽量让数据在磁盘上连续排布（利用顺序读的优势）。

解决方案很自然：不要逐块记录，而是记录连续区间（extent）。一个 extent 表示”从逻辑块 L 开始的 N 个块，映射到物理块 P 开始的 N 个连续块”。一个 1GB 的连续文件只需要一个 extent。

但 extent 的数量可能很多（碎片化的文件），所以需要一种数据结构来高效地存储和查找 extent。自然的选择就是树——B-tree 或其变体。

文件系统树的设计是操作系统中最能体现”数据结构即工程”的地方。这不是教科书上的抽象 B-tree，而是要在固定大小的磁盘块里塞下尽可能多的索引条目，同时保证崩溃一致性，还要和磁盘的物理特性博弈。

二、ext4 的 Extent Tree

ext4 是 Linux 上最广泛使用的文件系统。它从 ext3 演进而来，最核心的变化之一就是用 extent tree 取代了间接块映射。

Extent 的基本结构

ext4 的一个 extent 定义如下（fs/ext4/ext4_extents.h）：

struct ext4_extent {
    __le32 ee_block;    // 起始逻辑块号
    __le16 ee_len;      // 覆盖的块数（最多 32768，高位用于标记未初始化）
    __le16 ee_start_hi; // 起始物理块号的高 16 位
    __le32 ee_start_lo; // 起始物理块号的低 32 位
};

一个 extent 只有 12 字节，却能表示最多 32768 个连续块（128MB，以 4KB 块大小计）。对比 ext2 的间接块方案，128MB 的连续数据只需要 12 字节元数据，而不是 32768 x 4 = 128KB。

ee_len 的最高位有特殊含义：置位表示该 extent 是”未初始化”（uninitialized）的，用于预分配（fallocate()）场景——空间已分配但未写入数据，读取时应返回零。

Extent Tree 的节点结构

当 extent 数量超过 inode 能直接容纳的上限时，ext4 使用 B-tree 来组织 extent。树的每个节点都以一个 header 开头：

struct ext4_extent_header {
    __le16 eh_magic;      // 魔数 0xF30A
    __le16 eh_entries;    // 当前节点中的有效条目数
    __le16 eh_max;        // 当前节点能容纳的最大条目数
    __le16 eh_depth;      // 树的深度（叶节点为 0）
    __le32 eh_generation; // 用于 htree 的版本号
};

内部节点存储索引条目：

struct ext4_extent_idx {
    __le32 ei_block;    // 此子树覆盖的最小逻辑块号
    __le32 ei_leaf_lo;  // 子节点所在的物理块号（低 32 位）
    __le16 ei_leaf_hi;  // 子节点所在的物理块号（高 16 位）
    __le16 ei_unused;   // 保留
};

叶节点存储实际的 extent（即上面的 ext4_extent）。

Inode 内联与四级索引

ext4 inode 中有 60 字节的 i_block 空间（原本 ext2/ext3 用来存 15 个块指针的地方）。ext4 把这 60 字节重新利用：

60 字节 = 12 字节 header + 4 x 12 字节 extent

一个 ext4 inode 可以直接内联存储 4 个 extent，无需额外的磁盘块。4 个 extent 最多能覆盖 4 x 32768 = 131072 个块 = 512MB 的连续数据。对于大部分文件来说，这就够了。

当 extent 数量超过 4 个时，ext4 会分配额外的磁盘块来存储树节点。以 4KB 块大小计算：

一个 4KB 块 = 12 字节 header + 340 个 extent（每个 12 字节）
(4096 - 12) / 12 = 340.33，取整为 340 个

对于一棵深度为 d 的 extent tree：

• 深度 0（纯 inode 内联）：最多 4 个 extent
• 深度 1（inode 索引 + 一层叶节点）：最多 4 x 340 = 1,360 个 extent
• 深度 2：最多 4 x 340 x 340 = 462,400 个 extent
• 深度 3：最多 4 x 340^3 = ~1.57 亿个 extent
• 深度 4：最多 4 x 340^4 = ~535 亿个 extent

ext4 限制树的最大深度为 5。实际上深度 2 就足以覆盖绝大多数文件。查找时间复杂度 O(d x log(m))，d 最多 5，m 最多 340，几乎是常数。

Extent 合并策略

ext4 在插入新 extent 时会尝试与相邻的 extent 合并。合并条件是：新 extent 的逻辑块范围与物理块范围都与相邻 extent 连续。相关代码在 ext4_ext_try_to_merge() 中：

// 伪代码：extent 合并逻辑
static int ext4_ext_try_to_merge(struct inode *inode,
    struct ext4_ext_path *path, struct ext4_extent *ex)
{
    struct ext4_extent *next = ex + 1;

    // 检查逻辑块是否连续
    if (le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex)
            != le32_to_cpu(next->ee_block))
        return 0;

    // 检查物理块是否连续
    if (ext4_ext_pblock(ex) + ext4_ext_get_actual_len(ex)
            != ext4_ext_pblock(next))
        return 0;

    // 检查合并后长度是否超过上限
    if (ext4_ext_get_actual_len(ex) + ext4_ext_get_actual_len(next)
            > EXT_INIT_MAX_LEN)
        return 0;

    // 执行合并
    ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
                           + ext4_ext_get_actual_len(next));
    return 1;
}

合并策略配合延迟分配，使得顺序写入的文件几乎不会产生多余的 extent。

bigalloc：大块分配

ext4 的 bigalloc 特性允许将多个连续的文件系统块视为一个”簇”（cluster），块分配以簇为单位。例如 64KB 簇 = 16 个 4KB 块。

bigalloc 的好处：

1. 减少 extent 数量：同样的文件，extent 数量减少到 1/16
2. 减小块位图：位图大小也缩小到 1/16
3. 降低碎片：分配粒度更大，更容易连续

代价是内部碎片增加——一个 1 字节的文件也要占用 64KB。bigalloc 适合大文件为主的场景。

内核代码路径

当你调用 pread() 时，内核的调用路径大致是：

vfs_read()
  -> ext4_file_read_iter()
    -> ext4_map_blocks()
      -> ext4_ext_map_blocks()
        -> ext4_find_extent()   // 在 extent tree 中查找

ext4_find_extent() 核心是一个循环，每次迭代处理树的一层——从 inode 内联 header 开始，逐层二分查找 ext4_extent_idx，读取下一层节点（通常在页缓存中），到达叶节点后二分查找 ext4_extent，返回 (physical_block, length) 元组。

性能对比

操作                    ext3（间接块）    ext4（extent）    提升
------------------------------------------------------------------
创建 10GB 文件           12.3s            2.1s             5.9x
删除 10GB 文件           8.7s             0.3s             29x
随机读 4KB (IOPS)        45,200           47,100           1.04x
顺序读吞吐量             1.2 GB/s         1.25 GB/s        1.04x
fsck 10GB 文件           4.2s             0.8s             5.3x

随机读和顺序读的差异不大——瓶颈在磁盘本身。但创建、删除和 fsck 的差异巨大，因为 extent 方案需要管理的元数据少了几个数量级。

三、XFS 的 B+Tree

如果说 ext4 是”在 ext2/ext3 的框架上做渐进改进”，XFS 则是从第一天就为大文件、大文件系统设计的。XFS 在 1993 年由 SGI 开发，2001 年进入 Linux 内核，至今仍然是 RHEL/CentOS 的默认文件系统。

Allocation Group：并行化的关键

XFS 把整个文件系统划分为多个 Allocation Group（AG），每个 AG 是一个独立的分配单元，拥有自己的 superblock 副本、空闲空间 B+tree、inode B+tree 和 inode 分配位图。

+--------+--------+--------+--------+--------+
|  AG 0  |  AG 1  |  AG 2  |  AG 3  |  AG 4  |
+--------+--------+--------+--------+--------+
  每个 AG 有独立的锁、独立的 B+tree

多个线程可以同时在不同的 AG 中分配空间，互不干扰。这是 XFS 在多核高并发场景下性能优异的核心原因。

B+Tree 无处不在

XFS 的设计哲学是：任何需要高效查找的元数据，都用 B+tree 来组织。XFS 中至少有五种不同用途的 B+tree：

1. Inode B+tree：在 AG 中按 inode 号查找 inode
2. Free Space B+tree（按块号）：按起始块号排序的空闲区间，用于”给我一个从块号 X 附近开始的空闲区间”
3. Free Space B+tree（按长度）：按长度排序的空闲区间，用于”给我一个至少 N 块长的空闲区间”
4. Extent B+tree（bmbt）：文件的逻辑块到物理块映射
5. Reverse Mapping B+tree（rmapbt）：从物理块反查逻辑块（4.8+ 内核）

为什么需要两棵空闲空间树？因为分配器有两种常见请求模式，为不同查询模式维护不同索引——和数据库中为同一张表建多个索引完全一样。

Reverse Mapping B+tree

rmapbt 是 XFS 在 4.8 内核中引入的重要特性。传统文件系统只能从逻辑块查找物理块（正向映射），rmapbt 提供了反向映射——从物理块号查找”谁在使用这个块”。

struct xfs_rmap_irec {
    xfs_agblock_t   rm_startblock;  // AG 内物理起始块
    xfs_extlen_t    rm_blockcount;  // 块数
    uint64_t        rm_owner;       // 所有者（inode 号或特殊 ID）
    uint64_t        rm_offset;      // 文件内逻辑偏移
    unsigned int    rm_flags;       // 标志位
};

rmapbt 的用途：

• 在线 fsck（xfs_scrub）：交叉验证正向映射和反向映射的一致性
• 精确空间审计：知道每个物理块被谁占用
• reflink 支持：引用链接需要知道一个物理块被多少个文件引用

Extent B+Tree（bmbt）

XFS 的文件 extent 映射使用 B+tree：

struct xfs_bmbt_rec {
    __be64 l0;  // 打包：逻辑块号（54 位）、extent 标志（1 位）
    __be64 l1;  // 打包：起始物理块号（52 位）、块数（21 位）
};

每个 extent 记录 16 字节（比 ext4 的 12 字节大），但逻辑块号用 54 位表示（ext4 用 32 位），XFS 天然支持更大的文件。

XFS inode 内部有内联 extent 的机制（data fork），空间更灵活——inode 大小可配置（256 字节到 2KB），更大的 inode 能内联更多 extent。

延迟分配

XFS 是最早实现延迟分配的文件系统之一：

传统分配：
write(4KB) -> 分配 1 个块
write(4KB) -> 分配 1 个块
write(4KB) -> 分配 1 个块（可能不连续！）

延迟分配：
write(4KB) -> 记录脏页（不分配）
write(4KB) -> 记录脏页（不分配）
write(4KB) -> 记录脏页（不分配）
flush -> 一次性分配 3 个连续块

延迟分配显著减少了碎片化。代价是：系统在 write() 之后、flush 之前崩溃，数据会丢失——但这符合 POSIX 语义。

从工程角度看，XFS 的 B+tree-everywhere 设计让它在处理超大文件系统（几百 TB 甚至 PB 级）时表现稳健。代价是实现复杂度高——XFS 的内核代码量大约是 ext4 的 1.5 倍。

四、btrfs 的 Copy-on-Write B-Tree

btrfs（B-tree File System）从 2007 年开始开发，试图成为 Linux 的”ZFS 替代品”，提供快照、校验和、RAID、子卷等高级功能。一切的基础是一棵 CoW（Copy-on-Write）B-tree。

CoW 语义：永不原地修改

btrfs 的核心设计原则是：永远不在原地修改已有的数据或元数据。每次写入都会：

1. 分配新的磁盘块
2. 写入修改后的数据到新块
3. 更新父节点的指针指向新块（父节点也是 CoW 的，递归到根）
4. 原子地更新超级块的根指针

修改前：                    修改后：
    [Root A]                   [Root A']
    /     \                    /      \
  [B]     [C]               [B']     [C]  <- C 不变，共享
  / \     / \               / \      / \
[D] [E] [F] [G]          [D] [E'] [F] [G]
                              ^
                           修改了 E 的数据

修改叶节点 E 时，需要创建 E’、B’、Root A’ 三个新节点。这就是 CoW 的”路径复制”（path copying）。

btrfs 的键空间设计

btrfs 使用一棵巨大的 B-tree 来存储几乎所有的元数据。这棵树的键是一个三元组：

struct btrfs_key {
    __le64 objectid;  // 对象 ID（如 inode 号）
    __u8   type;      // 条目类型
    __le64 offset;    // 类型相关的偏移
};

不同类型的元数据通过 type 字段区分：

BTRFS_INODE_ITEM_KEY     = 1    // inode 元数据
BTRFS_DIR_ITEM_KEY       = 84   // 目录项
BTRFS_EXTENT_DATA_KEY    = 108  // 文件 extent 数据
BTRFS_EXTENT_ITEM_KEY    = 168  // extent 分配信息
BTRFS_CSUM_ITEM_KEY      = 120  // 数据校验和

Checksum Tree

btrfs 为所有数据块维护一棵专门的 checksum tree。每个数据 extent 对应一组 CRC32C 校验和（每 4KB 一个，4 字节），存储在 checksum tree 的叶节点中。

checksum tree key = (EXTENT_CSUM, CSUM_ITEM, 物理磁盘地址)
value = [crc0, crc1, crc2, ...]  每个 4 字节

读取数据时，btrfs 同时从 checksum tree 中取出对应的校验和进行验证。如果不匹配且有冗余副本（RAID1/RAID10），自动从副本修复。

Subvolume Tree 与快照 O(1) 的秘密

btrfs 的每个 subvolume 都有自己的根节点，存储在一棵 tree of tree roots（根树）中。创建快照时：

1. 复制当前 subvolume 的根节点（几百字节）
2. 在根树中插入新的根节点条目
3. 增加所有子树的引用计数（通过 back reference）

# 创建子卷
btrfs subvolume create /mnt/data/mysubvol

# 创建只读快照——O(1) 操作
btrfs subvolume snapshot -r /mnt/data/mysubvol /mnt/data/snap1

# 创建可写快照
btrfs subvolume snapshot /mnt/data/mysubvol /mnt/data/test-env

快照是 O(1) 的秘密在于：CoW 使得快照和原卷共享所有未修改的数据块。不需要复制任何数据。修改任一方时，CoW 机制自动处理分离。引用计数存储在 extent tree 中，只有当引用计数降为 0 时才真正释放物理空间。

btrfs 的叶节点与传统 B-tree 不同——它存储变长的数据项：

+-------+-------+-------+-------+---+------+------+------+------+
| header| key 0 | key 1 | key 2 |...| free | val2 | val1 | val0 |
+-------+-------+-------+-------+---+------+------+------+------+
         keys 从左向右增长 ->              <- values 从右向左增长

CoW 的代价：写放大

修改一个 4KB 的叶节点，需要重写从叶到根的整条路径：

1 个叶节点（16KB，btrfs 默认节点大小）
+ 3 个内部节点（各 16KB）
+ 1 个超级块（4KB）
= 68KB 的磁盘写入

写放大比率为 17x。实际情况会好一些——btrfs 使用事务机制，多次修改合并到一个事务中共享路径上的 CoW；延迟分配减少单独的小分配；内存中的节点缓存修改多次后才刷到磁盘。

但在某些极端场景下——数据库的随机小写入（4KB 页）——CoW 的写放大是真实存在的性能问题。

元数据开销分析

btrfs 的”一棵树管一切”意味着这棵树可能非常大。一个包含 1 亿个文件的文件系统，元数据树可能有数十 GB。优化策略：

• 元数据预留：确保总有足够的空间做 CoW，防止”ENOSPC 死锁”
• 内联数据：小文件（<2KB）直接存在 B-tree 叶节点里
• 压缩：透明压缩（zstd/lzo）减少实际写入量

五、ZFS 的 DMU 与间接块树

ZFS 是 Sun Microsystems 在 2005 年发布的”终极文件系统”。虽然 CDDL 许可证无法合并进 Linux 主线内核，但通过 OpenZFS 项目使用广泛。

存储栈分层

                 ZPL (ZFS POSIX Layer)
                       |
                 DMU (Data Management Unit)
                       |
                 ARC (Adaptive Replacement Cache)
                       |
                 SPA (Storage Pool Allocator)
                       |
                 VDEV (Virtual Device Layer)

DMU 是核心。它管理的基本对象叫做 dnode。每个 dnode 包含一组块指针，形成一棵间接块树。

间接块指针与 256-bit Checksum

typedef struct blkptr {
    dva_t       blk_dva[3];       // 最多 3 个数据虚拟地址（镜像/RAIDZ）
    uint64_t    blk_prop;         // 压缩、校验和类型等属性
    uint64_t    blk_pad[2];       // 填充
    uint64_t    blk_phys_birth;   // 物理出生事务号
    uint64_t    blk_birth;        // 逻辑出生事务号
    uint64_t    blk_fill;         // 子树中的非零块数
    zio_cksum_t blk_cksum;        // 256 位校验和
} blkptr_t;   // 共 128 字节

一个块指针 128 字节——比 ext4 的 4 字节块号大了 32 倍。但它包含了 256 位校验和、压缩信息、RAID 冗余信息。校验和算法支持 fletcher4、SHA-256、skein 等。

间接块树结构

dnode
  +-- L2 间接块（包含 N 个块指针）
        +-- L1 间接块（包含 N 个块指针）
              +-- L0 数据块

以 128KB 的块大小计算，每个间接块能容纳 128KB / 128B = 1024 个块指针：

• L0（数据块）：128KB
• L1（一级间接）：1024 x 128KB = 128MB
• L2（二级间接）：1024 x 128MB = 128GB
• L3（三级间接）：1024 x 128GB = 128TB

自修复与 Ditto Block

ZFS 的端到端数据完整性通过”校验和在父节点”实现：

[间接块] --校验和--> [数据块]
    ^
  校验和存在父节点中，而非数据块自身

如果磁盘悄悄损坏了一个数据块（bit rot），ZFS 读取时发现校验和不匹配。配置镜像或 RAIDZ 时，自动从冗余副本修复。

Ditto block 是 ZFS 对元数据的额外保护：关键元数据（如 uber block、MOS）自动存储 2-3 份副本在不同的 VDEV 上，即使在非冗余配置（单盘）下也有保护。

元数据重要性    副本数    放置策略
----------------------------------------------
uber block      3        分散在不同 VDEV
MOS 对象        2-3      不同 VDEV
普通元数据      1-2      取决于 copies 属性
用户数据        1        默认（可通过 copies 增加）

ZFS 选择间接块树而不是 B-tree 有其理由：可变块大小（512B 到 16MB）天然适应；实现比 B-tree 简单——不需要处理节点分裂和合并；每个块指针自带校验和，形成自校验的 Merkle 树。

六、F2FS 的 NAT/SIT

F2FS（Flash-Friendly File System）由三星在 2012 年开发，专门针对闪存设备优化。

闪存的物理约束

闪存有三个关键特性：

1. 读写不对称：读可以按页（4KB）随机进行，但擦除必须按块（通常 256KB-4MB）
2. 擦写次数有限：每个闪存块只能擦写数千到数万次
3. 写前需擦除：不能覆盖写，必须先擦除整个块再写

传统文件系统的原地更新对闪存不友好：频繁更新同一个位置导致 FTL 大量垃圾回收，加剧写放大和磨损。日志结构文件系统（LFS）的追加写模式与闪存天然匹配。

Node Address Table（NAT）

NAT 是 F2FS 最核心的创新，解决了传统 LFS 的”雪崩更新”问题（wandering tree problem）：

传统 LFS：
数据块更新 -> node 更新 -> node 的父 node 更新 -> ... -> checkpoint 更新

F2FS：
数据块更新 -> node 更新 -> NAT 中更新 node 地址（原地更新，打断级联）

NAT 将 node ID 映射到其当前的物理地址：

struct f2fs_nat_entry {
    __u8    version;      // 版本号
    __le32  ino;          // inode 号
    __le32  block_addr;   // 当前物理块地址
} __packed;

node 被写到新位置后，只需更新 NAT 中的一个条目，不需要更新 node 的父节点。

Segment Info Table（SIT）

SIT 记录每个 segment（通常 2MB，512 个 4KB 块）的使用状态：

struct f2fs_sit_entry {
    __le16  vblocks;                          // 有效块数
    __u8    valid_map[SIT_VBLOCK_MAP_SIZE];   // 位图
    __le64  mtime;                            // 修改时间
} __packed;

SIT 用于垃圾回收决策：贪心策略选择有效块比例最低的 segment 回收；成本效益策略综合考虑有效块比例和 segment 年龄。

Node 树结构

inode node
  +-- 直接块指针 x 923（inode 内联）
  +-- 直接 node 指针 x 2
  |     +-- 每个直接 node 包含 1018 个块指针
  +-- 间接 node 指针 x 2
  |     +-- 每个间接 node 包含 1018 个直接 node 指针
  +-- 双重间接 node 指针 x 1
        +-- 包含 1018 个间接 node 指针

所有 node 指针都通过 NAT 间接寻址。修改数据块 → 写新数据块到日志 → 更新直接 node → 将新 node 写到日志 → 更新 NAT。不需要修改 inode 或更高层 node。

多日志头与冷热分离

F2FS 维护 6 个日志头，按数据温度分离：

Hot  Node Log  <- 频繁更新的 inode、直接 node
Warm Node Log  <- 不频繁更新的 node
Cold Node Log  <- 很少更新的 node（如目录 node）
Hot  Data Log  <- 频繁更新的数据（如数据库页）
Warm Data Log  <- 普通文件数据
Cold Data Log  <- 多媒体、归档数据

冷热分离减少了垃圾回收开销：冷数据段中有效块比例高，回收时需搬移的数据少。

七、对比分析

总体对比

+----------+--------------+----------+--------+---------+----------+
| 文件系统 | 树类型       | CoW      | 校验和 | 快照    | 适用场景 |
+----------+--------------+----------+--------+---------+----------+
| ext4     | Extent Tree  | 否       | 元数据 | 否(*)   | 通用     |
| XFS      | B+Tree(多种) | 否       | 元数据 | 否      | 大文件   |
| btrfs    | CoW B-Tree   | 是       | 全部   | 是      | 快照/容器|
| ZFS      | 间接块+Merkle| 是       | 全部   | 是      | NAS/存储 |
| F2FS     | Node+NAT     | 追加写   | 全部   | 否      | 闪存设备 |
+----------+--------------+----------+--------+---------+----------+

(*) ext4 可以通过 LVM 快照实现，但不是文件系统原生支持

数据结构细节对比

各自树结构的优劣

ext4 Extent Tree：优点是简单高效、inode 内联避免额外 I/O、向后兼容好；缺点是无原生快照、无数据校验和、碎片化后 extent 树膨胀。

XFS B+Tree：优点是 AG 并行分配、多索引覆盖多种查询模式、rmapbt 支持在线修复；缺点是实现复杂、小文件场景开销相对大。

btrfs CoW B-Tree：优点是原子快照 O(1)、端到端校验、subvolume 隔离；缺点是写放大大、碎片化严重、空间快满时性能悬崖。

ZFS 间接块树：优点是 256-bit 校验和+自愈、ditto block 保护元数据、可变块大小灵活；缺点是块指针 128 字节开销大、稀疏文件浪费、许可证限制。

F2FS Node+NAT：优点是 NAT 打断雪崩更新、冷热分离减少 GC、闪存友好；缺点是仅适用于闪存、无原生快照、最大文件/卷偏小。

八、简化版 Extent Tree 实现

下面是一个简化版的 extent tree 查找/插入实现（C 语言），展示核心数据结构和算法：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#define MAX_EXTENTS_PER_NODE 4
#define MAX_CHILDREN         5

typedef struct {
    uint32_t logical_block;   // 起始逻辑块号
    uint32_t physical_block;  // 起始物理块号
    uint16_t length;          // 覆盖的块数
} extent_t;

typedef struct node {
    int          is_leaf;
    int          count;       // 当前条目数
    extent_t     extents[MAX_EXTENTS_PER_NODE];   // 叶节点使用
    uint32_t     keys[MAX_EXTENTS_PER_NODE];      // 内部节点：子树最小逻辑块号
    struct node *children[MAX_CHILDREN];           // 内部节点：子节点指针
} node_t;

/* 创建新节点 */
static node_t *node_create(int is_leaf)
{
    node_t *n = calloc(1, sizeof(node_t));
    n->is_leaf = is_leaf;
    return n;
}

/* 在叶节点中二分查找包含 logical_block 的 extent */
static extent_t *leaf_lookup(node_t *leaf, uint32_t logical_block)
{
    int lo = 0, hi = leaf->count - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        extent_t *ex = &leaf->extents[mid];
        if (logical_block < ex->logical_block) {
            hi = mid - 1;
        } else if (logical_block >= ex->logical_block + ex->length) {
            lo = mid + 1;
        } else {
            return ex;   // 命中
        }
    }
    return NULL;
}

/* 从根节点开始查找逻辑块号对应的物理块号，返回 -1 表示未映射 */
int64_t extent_tree_lookup(node_t *root, uint32_t logical_block)
{
    node_t *cur = root;

    while (cur && !cur->is_leaf) {
        int i;
        for (i = cur->count - 1; i >= 0; i--) {
            if (logical_block >= cur->keys[i]) {
                cur = cur->children[i];
                break;
            }
        }
        if (i < 0)
            cur = cur->children[0];
    }

    if (!cur)
        return -1;

    extent_t *ex = leaf_lookup(cur, logical_block);
    if (!ex)
        return -1;

    uint32_t offset = logical_block - ex->logical_block;
    return (int64_t)ex->physical_block + offset;
}

/* 向叶节点插入 extent（简化版，不处理节点分裂） */
static int leaf_insert(node_t *leaf, extent_t *new_ext)
{
    if (leaf->count >= MAX_EXTENTS_PER_NODE)
        return -1;   // 需要分裂，此处省略

    /* 尝试与相邻 extent 合并 */
    for (int i = 0; i < leaf->count; i++) {
        extent_t *ex = &leaf->extents[i];
        /* 新 extent 紧接在已有 extent 后面，且物理块也连续 */
        if (ex->logical_block + ex->length == new_ext->logical_block &&
            ex->physical_block + ex->length == new_ext->physical_block) {
            ex->length += new_ext->length;
            return 0;
        }
        /* 新 extent 紧接在已有 extent 前面 */
        if (new_ext->logical_block + new_ext->length == ex->logical_block &&
            new_ext->physical_block + new_ext->length == ex->physical_block) {
            ex->logical_block = new_ext->logical_block;
            ex->physical_block = new_ext->physical_block;
            ex->length += new_ext->length;
            return 0;
        }
    }

    /* 无法合并，找到插入位置 */
    int pos = 0;
    while (pos < leaf->count &&
           leaf->extents[pos].logical_block < new_ext->logical_block)
        pos++;

    memmove(&leaf->extents[pos + 1], &leaf->extents[pos],
            (leaf->count - pos) * sizeof(extent_t));
    leaf->extents[pos] = *new_ext;
    leaf->count++;
    return 0;
}

/* 演示 */
int main(void)
{
    /* 构建一棵简单的两层 extent tree */
    node_t *root = node_create(0);
    node_t *leaf0 = node_create(1);
    node_t *leaf1 = node_create(1);

    /* 填充叶节点 */
    leaf0->extents[0] = (extent_t){0,     1000, 100};  // 逻辑 0-99   -> 物理 1000-1099
    leaf0->extents[1] = (extent_t){100,   2000, 200};  // 逻辑 100-299 -> 物理 2000-2199
    leaf0->count = 2;

    leaf1->extents[0] = (extent_t){500,   5000, 300};  // 逻辑 500-799 -> 物理 5000-5299
    leaf1->count = 1;

    /* 设置根节点 */
    root->keys[0] = 0;
    root->keys[1] = 500;
    root->children[0] = leaf0;
    root->children[1] = leaf1;
    root->count = 2;

    /* 查找测试 */
    uint32_t test_blocks[] = {0, 50, 150, 300, 600, 800};
    for (int i = 0; i < 6; i++) {
        int64_t phys = extent_tree_lookup(root, test_blocks[i]);
        if (phys >= 0)
            printf("逻辑块 %u -> 物理块 %ld\n", test_blocks[i], phys);
        else
            printf("逻辑块 %u -> 未映射\n", test_blocks[i]);
    }

    /* 插入测试：与已有 extent 合并 */
    extent_t new_ext = {300, 2200, 50};   // 逻辑 300-349 -> 物理 2200-2249
    leaf_insert(leaf0, &new_ext);
    printf("\n插入后，逻辑块 250 -> 物理块 %ld\n",
           extent_tree_lookup(root, 250));
    printf("插入后，逻辑块 320 -> 物理块 %ld\n",
           extent_tree_lookup(root, 320));

    free(leaf0);
    free(leaf1);
    free(root);
    return 0;
}

输出：

逻辑块 0 -> 物理块 1000
逻辑块 50 -> 物理块 1050
逻辑块 150 -> 物理块 2050
逻辑块 300 -> 未映射
逻辑块 600 -> 物理块 5100
逻辑块 800 -> 未映射

插入后，逻辑块 250 -> 物理块 2150
插入后，逻辑块 320 -> 物理块 2220

这个实现省略了节点分裂、平衡和磁盘持久化，但展示了 extent tree 的核心思想：二分查找 extent 区间、逻辑块到物理块的偏移计算、相邻 extent 的合并优化。

九、碎片问题

Extent 碎片 vs 内部碎片

文件系统的碎片分为两种：

Extent 碎片（外部碎片）：文件的 extent 数量过多，原本可以用一个 extent 表示的连续文件被拆成了成百上千个小 extent。原因包括：并发写入不同文件导致空间交错分配；CoW 文件系统的写操作天然产生新位置的块；文件删除后空间回收导致空洞。

内部碎片：分配粒度大于实际需求。例如 ext4 bigalloc 使用 64KB 簇，一个 1 字节文件浪费 65535 字节；ZFS 默认 128KB 块大小，小文件浪费严重。

在线碎片整理算法

ext4 的 e4defrag：读取碎片文件的所有 extent，在空闲空间中找到一段足够大的连续区域，将数据复制过去，然后更新 extent tree。使用 EXT4_IOC_MOVE_EXT ioctl 原子地交换 extent。

# 检查碎片程度
filefrag -v /path/to/file

# 整理单个文件
e4defrag /path/to/file

# 整理整个文件系统
e4defrag /mount/point

btrfs 的碎片整理：btrfs filesystem defragment 重写文件数据到新的连续位置。但这里有一个关键问题——碎片整理会打破快照共享。因为 CoW 语义下，重写数据到新位置意味着快照引用的旧块不能被释放，反而增加了空间消耗。

# btrfs 碎片整理（注意：会打破快照共享！）
btrfs filesystem defragment -r /mount/point

# 建议：对不需要快照的文件使用 nocow
chattr +C /path/to/database.db

XFS 的 xfs_fsr：XFS 文件系统重组器（File System Reorganizer），在后台逐个整理碎片文件。它通过临时文件 + XFS_IOC_SWAPEXT 原子交换来实现，不影响正在读取的进程。

碎片对性能的影响量化

在 HDD 上，碎片的影响极其显著——因为每次寻道约 5ms：

extent 数量    顺序读 1GB 耗时 (HDD)    顺序读 1GB 耗时 (SSD)
-------------------------------------------------------------------
1              5.0s                      0.3s
10             5.1s                      0.3s
100            5.5s                      0.3s
1,000          10.0s                     0.3s
10,000         55.0s                     0.4s
100,000        > 500s                    0.5s

在 SSD 上，碎片的影响被大幅削弱，因为随机读的延迟几乎与顺序读相同。但 extent 元数据本身的遍历开销仍然存在。

十、工程陷阱表

十一、未来趋势

PMEM（持久内存）

Intel Optane 等持久内存设备模糊了内存和存储的边界。PMEM 的特点是：

• 字节可寻址（不是块接口）
• 延迟在 100ns 量级（比 SSD 快 1000 倍，比 DRAM 慢 3-5 倍）
• 无擦写寿命限制
• 掉电后数据持久

传统的 B-tree 设计假设”磁盘读取以块为单位”，但 PMEM 可以精确读取任意字节。这催生了新的树形结构设计——比如 FAST/FAIR B+tree，它利用 PMEM 的字节寻址能力，在节点内使用无序插入 + 排序键数组，减少持久内存的写入量。

内核中的 DAX（Direct Access）模式允许文件系统绕过页缓存，直接 mmap 到 PMEM。ext4 和 XFS 都支持 DAX 模式，但 btrfs 由于 CoW 语义和 DAX 的冲突，目前不支持。

Zonefs 与分区命名空间 SSD

Zoned Storage 设备（ZNS SSD、SMR HDD）将存储空间划分为”zone”，每个 zone 内只能顺序写入。这天然适合日志结构文件系统。

Zonefs 是一个简单的文件系统，将每个 zone 暴露为一个文件。更复杂的方案是 btrfs 的 zoned 模式（5.12+ 内核），它将 btrfs 的 CoW 写入模式适配到 zone 的顺序写约束上。F2FS 也天然适合 ZNS，因为它本来就是日志结构的。

bcachefs

bcachefs 是由 Kent Overstreet 开发的新文件系统，已在 6.7 内核中合并。它的目标是”btrfs 的功能 + ext4 的性能”：

• CoW B+tree：类似 btrfs，但节点格式更紧凑
• 多设备分层：SSD 做热层、HDD 做冷层，自动数据迁移
• 纠删码：类似 ZFS 的 RAIDZ，但实现更新
• 快照：CoW 原生支持
• 加密：内置文件系统级加密
• 校验和：端到端数据完整性

bcachefs 的 B+tree 实现有一些独特的优化：节点使用日志化更新（logged updates），将多次小修改累积为一次大写入，显著降低了 CoW 的写放大。

十二、个人观点

关于选型

文件系统的树形结构设计，本质上是在以下维度之间做权衡：

写性能  <-------->  一致性保证
空间效率 <-------->  功能丰富度
实现简单 <-------->  极端场景适应性
随机写   <-------->  顺序写

我的选型建议：

• 通用 Linux 服务器：ext4。简单可靠，绝大多数场景够用。
• 大文件/大文件系统（>10TB）：XFS。AG 并行分配 + 延迟分配，大规模下表现稳定。
• 需要快照和容器存储：btrfs。O(1) 快照是杀手特性，Docker overlay 也在用。
• NAS/存储服务器：ZFS。端到端校验 + 自愈 + 灵活的存储池管理。
• 嵌入式/移动设备：F2FS。闪存优化，Android 已经大量使用。

关于 CoW 的未来

CoW 正在成为主流——Fedora 默认 btrfs，SUSE 很早就默认 btrfs，Ubuntu server 支持 ZFS，甚至 ext4 也在加入 reflink 特性。CoW 同时解决了崩溃一致性、快照、数据完整性三个问题，传统文件系统需要日志+LVM+额外工具才能达到同样效果。

但 CoW 的写放大问题至今没有完美解决。bcachefs 的日志化节点更新是一个有前景的方向。

数据结构即工程

我在文件系统领域学到的最重要的一课是：没有最好的数据结构，只有最适合约束条件的数据结构。

ext4 extent tree 不是理论上最优的树——但它在兼容 ext3 的前提下，用最小的改动获得了最大的收益。ZFS 的间接块树不如 B-tree 查找效率高——但它让校验和、CoW、可变块大小、RAID 自然集成在一起。

当你面对一个新的存储问题时，先问自己三个问题：我的访问模式是什么？一致性要求是什么？硬件的物理特性是什么？然后再选择或设计合适的树。这种”从约束出发”的思维方式，比记住任何具体的数据结构都更有价值。

系列导航： - 上一篇：伙伴系统与 SLUB 分配器 - 下一篇：epoll 的数据结构

相关阅读： - B-tree 深度解剖 - B+tree 与 LSM-tree