4.3 Metadata Pair——两页互为备份的原子提交
两个块为什么就够了？
现在你面对一个问题：如何在一个只能整块擦除的NOR Flash上，实现一个能够原子提交的“小日志“？
日志的经典定义是一个环形缓冲区——你不断往后追加记录，当到达末端时回到开头。但在Flash上，“到达末端时擦除“意味着你要擦除一个整块——如果擦除操作在中途掉电，这个块就变成了半擦除的垃圾状态。所以你需要至少两个块：在一块活跃写入时，另一块要么是空的（刚被擦除）、要么保存着历史数据。
这就是Metadata Pair的根本原因：两块Flash，一块活跃，一块备用。 不是三块，不是四块——两块是维持“原子性+不丢数据“的最小配置。
Metadata Pair 的基本结构
=========================================
pair[0] pair[1]
┌──────────────┐ ┌──────────────┐
│ revision: 3 │ │ revision: 2 │
│──────────────│ │──────────────│
│ entry A' │ ← 最新 │ entry A │ ← 旧数据
│──────────────│ │──────────────│
│ entry B' │ │ entry B │
│──────────────│ │──────────────│
│ entry C │ │ entry C │
│──────────────│ │──────────────│
│ checksum │ │ checksum │
└──────────────┘ └──────────────┘
↑ 活跃 ↑ 非活跃
revision更大 revision较小
每个metadata pair由两个block地址组成：pair[0]和pair[1]。通过比较两个block中的revision计数（使用序列号算术来防止整数溢出导致的问题），LittleFS知道哪一个是“最新“的。revision本质上是这个metadata pair经历的compaction次数——每次compact时revision+1。
在LittleFS中，metadata pair的结构体是lfs_mdir_t：
// lfs.h:377-386 — metadata directory 运行时状态
typedef struct lfs_mdir {
lfs_block_t pair[2]; // 两个block的地址
uint32_t rev; // 当前revision（RAM中的值）
lfs_off_t off; // 当前读取/写入偏移
uint32_t etag; // end tag：最后一个有效tag
uint16_t count; // 分裂计数（目录分裂后的子块数）
bool erased; // 备用块是否已擦除
bool split; // 是否已分裂（有tail指向下一个metadata pair）
lfs_block_t tail[2]; // 分裂后的尾部地址
} lfs_mdir_t;
而盘上，每个metadata block的格式极其简单：
Metadata Block 盘上格式
=========================================
偏移 0: revision (4 bytes, little-endian)
┌──────────────────────────────┐
│ entry 1: tag + data │
│ entry 2: tag + data │
│ entry 3: tag + data │
│ ... │
│ entry N: tag + data │
│ padding │
│ CRC (4 bytes, little-endian)│ ← 最后一个32位字
└──────────────────────────────┘
注意：条目是从block开头向末尾增长的
CRC总是在block的最末尾
block中未被entry覆盖的区域是0xFF（擦除态）
每个entry由tag（4字节）和随后的data组成。tag编码了类型、ID和data大小。当LittleFS读到data末尾时检查CRC——如果CRC匹配，整个block的内容就是可信的。
原子提交三步曲
Metadata pair的“原子提交“在数学上是这样保证的：在任何时刻断电，两个block中至少有一个包含完整且CRC校验通过的数据。
这个保证通过三种操作模式的精心编排来实现：
模式一：追加（Append）——block未满时
这是最理想的情况。活跃block还有空间，你直接在已有entry后面追加新entry。追加过程中断电的后果是：CRC覆盖不到未写完的entry，所以旧CRC仍然有效。挂载时LittleFS读到旧CRC，忽略不完整的尾部，回到上一个完整状态。
追加操作中的掉电安全性
=========================================
commit A:
┌──────────────┬──────────────┐ ┌──────────────┬──────────────┐
│ rev=1 │ rev=0 │ │ rev=1 │ rev=0 │
│──────────────│ │ │──────────────│ │
│ │ │ ==> │ A │ │
│ │ │ │──────────────│ │
│ │ │ │ CRC(ok) │ │
└──────────────┴──────────────┘ └──────────────┴──────────────┘
commit B and A':
┌──────────────┬──────────────┐ ┌──────────────┬──────────────┐
│ rev=1 │ rev=0 │ │ rev=1 │ rev=0 │
│──────────────│ │ │──────────────│ │
│ A │ │ │ A │ │
│──────────────│ │ │──────────────│ │
│ CRC(ok) │ │ │ B │ │
│ │ │ ==> │──────────────│ │
│ │ │ │ A' │ │
│ │ │ │──────────────│ │
│ │ │ │ CRC(ok) │ │
└──────────────┴──────────────┘ └──────────────┴──────────────┘
如果在写入B或A'的过程中断电：
→ 新的CRC不存在 → 旧CRC仍然有效 → 回到只有A的状态
→ 安全！
模式二：紧凑化（Compaction）——block满了但没有过期的entry
当活跃block满了的时候，LittleFS需要把仍然有效的entry复制到备用block上（擦除后变成干净的空白区），然后擦除旧活跃块。这个过程叫compaction（紧凑化）。
Compaction 中的掉电安全性
=========================================
commit B', need to compact:
┌──────────────┬──────────────┐ ┌──────────────┬──────────────┐
│ rev=1 │ rev=0 │ │ rev=1 │ rev=2 │
│──────────────│ │ │──────────────│──────────────│
│ A │ │ │ A │ A' │
│──────────────│ │ │──────────────│──────────────│
│ CRC(ok) │ │ │ CRC(ok) │ B' │
│──────────────│ │ │──────────────│──────────────│
│ B │ │ ==> │ B │ CRC(ok) │
│──────────────│ │ │──────────────│ │
│ A' │ │ │ A' │ │
│──────────────│ │ │──────────────│ │
│ CRC(ok) │ │ │ CRC(ok) │ │
└──────────────┴──────────────┘ └──────────────┴──────────────┘
如果在compaction过程中断电：
→ pair[1]的新CRC还没写 → pair[0]的旧CRC仍然有效
→ 回到compaction之前的状态
→ 安全！
在代码层面，lfs_dir_compact（lfs.c:1952）精确实现了这个过程：
// lfs.c:1952-2064 — lfs_dir_compact 的核心流程（简化版）
static int lfs_dir_compact(lfs_t *lfs,
lfs_mdir_t *dir, const struct lfs_mattr *attrs, int attrcount,
lfs_mdir_t *source, uint16_t begin, uint16_t end) {
dir->rev += 1; // 递增revision
while (true) {
// 1. 初始化提交状态，目标是pair[1]（备用块）
struct lfs_commit commit = {
.block = dir->pair[1],
.off = 0,
.crc = 0xffffffff,
};
// 2. 擦除备用块
int err = lfs_bd_erase(lfs, dir->pair[1]);
if (err) {
if (err == LFS_ERR_CORRUPT) goto relocate;
return err;
}
// 3. 写入新的revision
err = lfs_dir_commitprog(lfs, &commit,
&dir->rev, sizeof(dir->rev));
// 4. 遍历旧数据，把仍然有效的entry复制过来
err = lfs_dir_traverse(lfs, source, 0, 0xffffffff,
attrs, attrcount,
LFS_MKTAG(0x400, 0x3ff, 0),
LFS_MKTAG(LFS_TYPE_NAME, 0, 0),
begin, end, -begin,
lfs_dir_commit_commit, &commit_data);
// 5. 如果有tail，写入tail指针
if (!lfs_pair_isnull(dir->tail)) {
err = lfs_dir_commitattr(lfs, &commit,
LFS_MKTAG(LFS_TYPE_TAIL + dir->split, 0x3ff, 8),
dir->tail);
}
// 6. 写入global state的delta
// ...
// 7. 写入CRC（这是原子性的关键！）
err = lfs_dir_commitcrc(lfs, &commit);
if (err) {
if (err == LFS_ERR_CORRUPT) goto relocate;
return err;
}
// 8. CRC写入成功 → 翻转pair，旧活跃块降级为备用块
dir->erased = false;
lfs_pair_swap(dir->pair); // pair[0] ↔ pair[1]
dir->off = commit.off;
dir->etag = commit.ptag;
return 0;
relocate:
// 坏块处理：尝试用一个新的block替换pair[1]
lfs_cache_drop(lfs, &lfs->pcache);
lfs_block_t bad = dir->pair[1];
int err = lfs_alloc(lfs, &dir->pair[1]);
if (err) return err;
// 标记坏块为"已使用"，防止后续分配
// 进入下一轮循环重试
}
}
模式三：分裂（Split）——block满了且无法compact
如果block满了，但经过遍历发现没有可以清理的过期entry（所有entry都是活跃的），这意味着这个目录的元数据量需要超过一个block的容量。此时LittleFS的做法不是增大block——而是把metadata pair分拆成两个，用链表连接。
Split：一个metadata pair 分成两个
=========================================
commit C and D, need to split:
┌──────────────┬──────────────┐ ┌──────────────┬──────────────┐
│ rev=1 │ rev=2 │ │ rev=3 │ rev=2 │
│──────────────│──────────────│ │──────────────│──────────────│
│ A │ A' │ │ A' │ A' │
│──────────────│──────────────│ │──────────────│──────────────│
│ CRC(ok) │ B' │ │ B' │ B' │
│──────────────│──────────────│ │──────────────│──────────────│
│ B │ CRC(ok) │ ==> │ tail ───┐ │
│──────────────│ │ │──────────────│──────────────│
│ A' │ │ │ CRC(ok) │ │
│──────────────│ │ │──────────────│ │
│ CRC(ok) │ │ │ │ │
└──────────────┴──────────────┘ └────────┬─────┴──────────────┘
│
┌─────────────┘
v
┌──────────────┬──────────────┐
│ rev=1 │ rev=0 │
│──────────────│ │
│ C │ │
│──────────────│ │
│ D │ │
│──────────────│ │
│ CRC(ok) │ │
└──────────────┴──────────────┘
注意split过程的两步原子性：
- 先准备新metadata pair——分配两个新block，写入一半的entry，写入CRC。
- 再在原metadata pair中插入tail指针——指向新分配的那个pair。这一步本身是一次原子的目录提交（追加模式）。
如果在第1步后第2步前断电：新metadata pair是孤儿——它在链表里没有parent引用。但LittleFS的孤儿恢复机制会在下次挂载时发现它，并把它正确插入目录树。
这就是“有界日志的链表“——每个metadata pair有界（最多容纳约半个block的有效数据），但通过链表可以无限扩展。 这保证了目录可以包含任意数量的文件，同时每次操作的时间复杂度仍然是O(1)。
50%分裂阈值——为什么不在100%时才分裂？
这里有一个容易混淆的地方：LittleFS 的 compact 触发条件并不是 50%。compact 的真正触发条件是 block 写满（没有空间容纳下一次 commit 了）或者 block_cycles 到期强制搬迁。50% 是 compact 过程中的分裂决策阈值。
当 compact 发生时，LittleFS 检查当前 metadata pair 中有效数据（静态条目）的占比：
- 如果有效数据 ≤ 50% → 原地 compact，不分裂
- 如果有效数据 > 50% → 分裂成两个 metadata pair，用 tail 指针串联
为什么要 50%？从数学上看：
假设每个 entry 是 100 字节，一个 block 是 4KB（4096 字节）：
- 当有效数据占 25% 时，每次 compact 成本 ≈ 1.3n
- 当有效数据占 50% 时，每次 compact 成本 ≈ 2n
- 当有效数据占 75% 时，每次 compact 成本 ≈ 4n
- 当有效数据占 90% 时，成本 ≈ 10n
成本曲线是指数增长的。在 DESIGN.md 中，LittleFS 的作者用平摊分析证明了：在 50% 时分裂，能把 compact 的平摊成本限制在 2x 以内，保证 O(1) 的操作复杂度。
所以 LittleFS 的做法是：平时不管，block 写满才 compact。compact 时如果发现有效条目超过一半，就分裂。“50%“是判别条件，不是触发条件。
与KnotFS的SB Log对比
如果你已经读过第三章（KnotFS的设计），你可能会发现这里有一个有趣的对照：
Metadata Pair vs KnotFS的SB双槽位设计
=======================================================
特性 LittleFS Metadata Pair KnotFS SB双槽位
───────────────────────────────────────────────────────
块数量 2个（pair[0] + pair[1]） SB: 2块（SB0/SB1）
文件表嵌入在SB Header中
原子提交 追加+compact+split 追加+compact（写入备用槽位）
活跃识别 比较revision计数 比较sequence number
Compact触发 block写满 或 block_cycles Log区达到50%容量
分裂阈值 有效数据超过50%时分裂 不分裂（固定8文件槽位）
分裂机制 是（tail指针链表） 否（文件表固定8槽位）
CRC保护 每次commit一个CRC 每个log record一个CRC
───────────────────────────────────────────────────────
两种设计的核心思想相似——都是“两块交替+序列号仲裁+日志追加“。但细节差异反映了两者不同的设计目标：
- KnotFS是“知道上限的“： 最多8个文件，最多8个块的文件——所以superblock（含文件表）的大小是固定的，compact只是把内存中的完整状态写入备用SB槽位，不需要分裂。
- LittleFS是“不知道上限的“： 文件数量、目录深度、文件大小——都不受限制（除了文件大小有2GB上限）。所以它需要tail链表来支持metadata pair的无界扩展。
revision计数与序列号算术
Metadata pair依赖revision计数来判断哪一个block是“最新的“。但revision是一个uint32_t——它最终会溢出。如果revision从0xFFFFFFFF翻转到0x00000000，简单的大小比较就会出错。
LittleFS使用序列号算术（Sequence Number Arithmetic） 来解决这个问题。核心思路是：我们不是比较“哪个数字大“，而是比较“从A到B需要加多少次“——这个“距离“在二进制补码下是不受溢出影响的。
用代码来理解更直观：
// 判断 rev_a 是否比 rev_b 更新
// 不是简单的 a > b，而是检查顺时针距离
bool is_newer(uint32_t rev_a, uint32_t rev_b) {
return (int32_t)(rev_a - rev_b) > 0;
}
为什么这样可以？因为uint32_t的加减在计算机中本身就是模2³²的运算。(int32_t)(a - b) > 0等价于“从b顺时针走到a的距离小于2³¹“——这恰好是我们需要的“a比b更新“的条件。
前提条件是你不会连续执行超过2³¹次compaction而不检查revision——在Flash的物理寿命内（10万次擦除 × 两个block = 20万次），这个条件永远满足。
lfs_dir_commit：一次提交的完整路径
我们从顶层看一次目录提交的完整调用链：
// lfs.c:2601 — lfs_dir_commit 的顶层逻辑
static int lfs_dir_commit(lfs_t *lfs, lfs_mdir_t *dir,
const struct lfs_mattr *attrs, int attrcount) {
// 第一步：尝试追加
int orphans = lfs_dir_orphaningcommit(lfs, dir, attrs, attrcount);
// 第二步：如果有孤儿产生，清理孤儿
if (orphans) {
int err = lfs_fs_deorphan(lfs, false);
if (err) return err;
}
return 0;
}
而lfs_dir_orphaningcommit内部会调用lfs_dir_relocatingcommit，后者调用lfs_dir_splittingcompact：
lfs_dir_commit
└─ lfs_dir_orphaningcommit ← 处理孤儿逻辑
└─ lfs_dir_relocatingcommit ← 如果需要搬迁block
└─ lfs_dir_splittingcompact ← 处理compaction/split
├─ 尝试追加（如果当前block有空间）
├─ 尝试compact（如果当前block满了）
└─ 尝试split（如果compact后仍然超50%）
这个调用链展示了metadata pair设计的全面性：无论当前处于什么状态，总有一条路径可以让提交成功——或者因为空间不足而触发更高级的处理。
掉电保证的最终验证
让我们做一个思想实验。你在一个metadata pair处于任意状态时拔掉电源。可能的情况：
情况1：正在追加entry，追加未完成。 → 旧CRC仍然有效 → 挂载时读到旧CRC → 忽略不完整的尾部 → 回到追加前状态。
情况2：正在compact，旧数据已复制到pair[1]，但CRC未写入。 → pair[1]没有有效CRC → pair[0]的旧CRC仍然有效 → 回到compact前状态。
情况3：正在compact，CRC已写入，但pair尚未swap。 → pair[1]有新的有效CRC → pair[0]有旧的有效CRC → 比较revision → 发现pair[1]的revision更新 → 使用pair[1]作为数据源 → compact完成！
情况4：正在split，新pair已准备，但tail指针未在原pair中写入。 → 两个pair独立存在 → 新pair是孤儿 → 孤儿恢复机制会处理。
在所有可能的状态下，文件系统要么回到前一个一致状态，要么前进到下一个一致状态。不存在“部分写入“的中间态。
这就是LittleFS的Strong Guarantee在metadata pair层面的具体实现。
KnotFS 的双 SB 槽位（SB0/SB1）借鉴了 Metadata Pair 的双块交替思想——SB Log 往活跃槽位追加，Compact 往非活跃槽位覆盖，sequence 奇偶性决定谁是当前有效副本。但关键区别在于：LittleFS 的 Metadata Pair 存储的是目录条目（任意多），可以动态分裂成 tail 链；KnotFS 的 SB 存储的是文件表（固定 8 个槽位），Compact 就是整体重写——更简单，但也更“费 Flash“。这就是教学版刻意砍掉的复杂度：当你只需要管理 8 个文件时，不需要 metadata pair 的泛型框架。
下集预告
Metadata pair解决了“元数据如何安全落地“的问题——但它只存了目录结构。文件的真正数据呢？4KB的metadata block存不下一张照片。LittleFS用了一个你可能没见过的数据结构——CTZ跳表——让文件的每个数据块既是一个COW链表节点，又是一个跳表节点。追加在O(1)时间内完成，随机访问在O(log n)时间内完成。而这背后的数学，涉及二进制的count trailing zeros指令和OEIS数列大全中的一个惊人巧合。
悬念留给：为什么一个文件只需要两个数字（head指针 + size）就能描述？你是怎么从一个文件大小反推出它在跳表中的精确位置的？