4.4 CTZ Skip-List——文件数据的COW结构
一个链表的四次进化
你现在要设计一个存储文件数据的盘上结构。你有这些约束：
- 必须支持COW（Copy-On-Write）——因为需要掉电安全
- 追加写入必须是O(1)——因为嵌入式最常见的用例是日志追加
- 随机读取必须比O(n)快——因为用户有时候需要跳转到文件中间
- 内存使用必须是O(1)——不能像btrfs那样构建整棵B树到内存
- 元数据开销要小——不能每个数据块都配一个独立的inode
让我们依次看看你有哪些选项，以及为什么每一个都被否决了。
第一代：单向链表。
单向链表：数据块按顺序链接
=========================================
┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐
│ data 0 │─>│ data 1 │─>│ data 2 │─>│ data 4 │─>│ data 5 │
│ │ │ │ │ │ │ │ │ │
└─────────┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘
追加一个块 → 需要更新倒数第二个块的指针 → 触发COW → 需要更新倒数第三个块的指针 → 一直传播到第一个块。这是O(n)的追加操作——对于日志文件是灾难。
第二代：反向链表。
反向链表：从现在往回指
=========================================
┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐
│ data 0 │<─│ data 1 │<─│ data 2 │<─│ data 4 │<─│ data 5 │
│ │ │ │ │ │ │ │ │ │
└─────────┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘
追加一个块→只需要创建新块，让新块指向旧尾块。O(1)！完美。
但读取呢？如果要读data 0，你得从data 5开始，沿着反向指针一路走回data 0——O(n)的读取。你可以从head开始正着读，但head只知道最后一个块——你需要反向遍历才能找到第一个块。O(n²)的读取操作不可接受。
第三代：反向跳表（Skip-List）。
跳表的经典定义是：在链表的某些节点上增加额外的指针，跳过若干个中间节点，让查找可以“跳跃前进“。LittleFS把它倒过来用——指针是反向的，但跳跃的逻辑相同。
CTZ 反向跳表
=========================================
┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐
│ data 0 │<─│ data 1 │<─│ data 2 │<─│ data 3 │<─│ data 4 │<─│ data 5 │
│ │<─│ │──│ │<─│ │──│ │ │ │
│ │<─│ │──│ │──│ │──│ │ │ │
└─────────┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘
从block 5到block 1的路程：block 5 → 跳过block 4直接跳到block 3 → 跳过block 2跳到block 1。两次跳跃。
从block 5到block 0的路程：block 5 → 跳过block 4、3、2直接跳到block 1 → 从block 1跳到block 0。也是两次跳跃。
这个跳表的关键问题是：每个块应该有多少个指针？指针各自跳多远？
一种方案是“随机的“（经典跳表），但在无动态内存分配的环境下不可行。另一种方案是“固定步长的“，但那样会退化到O(√n)的查询复杂度。
LittleFS的方案——也是这个数据结构的核心创新——是用“Count Trailing Zeros（CTZ）“指令来决定每个块的指针数目和跳跃步长。
CTZ指令与跳表的邂逅
Count Trailing Zeros（CTZ）是一个CPU指令，功能是：返回一个整数的二进制表示中，末尾连续0的个数。
CTZ 示例：
ctz(1) = ctz(0b0001) = 0
ctz(2) = ctz(0b0010) = 1
ctz(3) = ctz(0b0011) = 0
ctz(4) = ctz(0b0100) = 2
ctz(5) = ctz(0b0101) = 0
ctz(6) = ctz(0b0110) = 1
ctz(7) = ctz(0b0111) = 0
ctz(8) = ctz(0b1000) = 3
CTZ跳表的规则极其简单：对于第n个数据块（n从0开始），它包含 ctz(n) + 1 个指向前面的块的指针。这 ctz(n)+1 个指针分别跳过 2^0, 2^1, 2^2, …, 2^ctz(n) 个块。
让我们把它画出来（以6个数据块为例）：
n=0: ctz(0)=0 → 1个指针 → 没有前面的块可指 → 数据块0的特殊情况
n=1: ctz(1)=0 → 1个指针 → 跳过2^0=1个块 → 指向块0 长度=1
n=2: ctz(2)=1 → 2个指针 → 跳过2^0=1 指向块1 长度=1
→ 跳过2^1=2 指向块0 长度=2
n=3: ctz(3)=0 → 1个指针 → 跳过2^0=1 指向块2 长度=1
n=4: ctz(4)=2 → 3个指针 → 跳过2^0=1 指向块3 长度=1
→ 跳过2^1=2 指向块2 长度=2
→ 跳过2^2=4 指向块0 长度=4
n=5: ctz(5)=0 → 1个指针 → 跳过2^0=1 指向块4 长度=1
完整结构：
┌────────┬────────┬────────┬────────┬────────┬────────┐
│ block0 │ block1 │ block2 │ block3 │ block4 │ block5 │
│ │──>b0 1 │──>b1 1 │──>b2 1 │──>b3 1 │──>b4 1 │
│ │ │──>b0 2 │ │──>b2 2 │ │
│ │ │ │ │──>b0 4 │ │
└────────┴────────┴────────┴────────┴────────┴────────┘
解读：block2有两个指针——跳过1个块到b1，跳过2个块到b0
block4有三个指针——跳过1个到b3，跳过2个到b2，跳过4个到b0
这个结构的优雅之处在于：每个块的指针数量恰好在平均值上是2。 推导：在所有n个块中，CTZ值 = 0的有n/2个，CTZ值 = 1的有n/4个，CTZ值 = 2的有n/8个……无穷级数求和：
平均指针数 = lim(n→∞) (1/n) × Σ(ctz(i)+1) = Σ(1/2^i) = 2
每个数据块平均只多占用8字节（2个32位指针）的元数据空间。 对于一个4KB的块，开销是0.2%——几乎可以忽略。
从size反推位置：一个OEIS巧合
CTZ跳表还有一个隐藏的杀手特性：给定一个文件大小，你可以用O(1)的时间算出最后一个数据块的索引和偏移。 这意味着在目录中存储一个文件时，你只需要两个数值：head（最后一个块的地址）和size（文件总大小）——而不需要存储“最后一个块的索引“和“块内偏移“这两个冗余信息。
推导过程：
每个数据块n的有效数据容量是：block_size - 4×(ctz(n)+1) ——因为块中的ctz(n)+1个指针占用了前置空间。
那么大小为N的文件占用了从0到某个n_max的块：
N = Σ(i=0→n) [B - (w/8)×(ctz(i)+1)]
其中：
B = block_size（块大小，字节）
w = 字宽（32位）
这个累加可以在O(n)内计算。但LittleFS的作者在OEIS（Online Encyclopedia of Integer Sequences）上发现了一个惊人的巧合：
Σ(i=0→n) (ctz(i)+1) = 2n - popcount(n)
其中popcount(n)是n的二进制表示中1的个数。
验证几个值：
- n=0: Σctz+1 = 0, 2×0-popcount(0) = 0-0 = 0 ✓
- n=3: Σctz+1 = 1+2+1 = 4, 2×3-popcount(3=0b11)=6-2=4 ✓
- n=5: Σctz+1 = 1+2+1+3+1 = 8, 2×5-popcount(5=0b101)=10-2=8 ✓
将这个等式代入文件大小公式：
N = B×n - (w/8)×(2n - popcount(n))
= B×n - (w/8)×2n + (w/8)×popcount(n)
= (B - w/4)×n + (w/8)×popcount(n)
从中解出n：
n = floor((N - (w/8)×popcount(N/(B-w/4))) / (B - w/4))
这是一个不需要循环、不需要查表的纯公式计算。 在LittleFS的32位环境中（w=32），它非常快。
这就是lfs_ctz_index的实现：
// lfs.c:2873-2884 — 从文件偏移算出block索引
static int lfs_ctz_index(lfs_t *lfs, lfs_off_t *off) {
lfs_off_t size = *off;
lfs_off_t b = lfs->cfg->block_size - 2*4; // B - w/4 = B - 8
lfs_off_t i = size / b; // 近似索引
if (i == 0) {
return 0;
}
i = (size - 4*(lfs_popc(i-1)+2)) / b; // 精确索引公式
*off = size - b*i - 4*lfs_popc(i); // 块内偏移
return i; // 返回block索引
}
这个函数接收一个文件偏移量，返回该偏移所在的block索引，同时把*off修改为块内偏移。整个过程只有几个整数运算——O(1)时间。
lfs_ctz_find：沿着跳表快速定位
有了lfs_ctz_index，从一个文件中的任意位置读取数据就很简单了。lfs_ctz_find从head开始，利用CTZ跳表的跳跃能力，贪婪地选择能覆盖最大距离而不越过目标的指针。
// lfs.c:2886-2918 — 在CTZ跳表中找到目标偏移所在的block
static int lfs_ctz_find(lfs_t *lfs,
const lfs_cache_t *pcache, lfs_cache_t *rcache,
lfs_block_t head, lfs_size_t size,
lfs_size_t pos, lfs_block_t *block, lfs_off_t *off) {
if (size == 0) {
*block = LFS_BLOCK_NULL;
*off = 0;
return 0;
}
lfs_off_t current = lfs_ctz_index(lfs, &(lfs_off_t){size-1});
lfs_off_t target = lfs_ctz_index(lfs, &pos);
while (current > target) {
lfs_size_t skip = lfs_min(
lfs_npw2(current-target+1) - 1,
lfs_ctz(current));
int err = lfs_bd_read(lfs,
pcache, rcache, sizeof(head),
head, 4*skip, &head, sizeof(head));
head = lfs_fromle32(head);
if (err) {
return err;
}
current -= 1 << skip;
}
*block = head;
*off = pos;
return 0;
}
核心逻辑：从最后一个块开始，每次选择能跳越的最大步数（不超过目标），读取那个指针，跳到更前面的块。因为每次跳跃至少把到目标的距离减半（类似于二分搜索），最坏情况下的跳数是O(log n)。 结合每次跳跃需要从Flash读取（O(1)），总读取复杂度是O(log n)。
lfs_ctz_extend：COW追加
文件写入的另一个关键操作是追加。在CTZ跳表中，追加一个新块的流程是：
// lfs.c:2921-3017 — lfs_ctz_extend（简化版）
static int lfs_ctz_extend(lfs_t *lfs,
lfs_cache_t *pcache, lfs_cache_t *rcache,
lfs_block_t head, lfs_size_t size,
lfs_block_t *block, lfs_off_t *off) {
while (true) {
// 1. 分配一个新块
lfs_block_t nblock;
int err = lfs_alloc(lfs, &nblock);
if (err) return err;
// 2. 擦除新块
err = lfs_bd_erase(lfs, nblock);
if (err) {
if (err == LFS_ERR_CORRUPT) goto relocate;
return err;
}
if (size == 0) {
// 文件为空：新块就是第一个块
*block = nblock;
*off = 0;
return 0;
}
lfs_size_t noff = size - 1;
lfs_off_t index = lfs_ctz_index(lfs, &noff);
noff = noff + 1;
// 3. 如果上一个块不满（非整块），复制数据到新块
if (noff != lfs->cfg->block_size) {
for (lfs_off_t i = 0; i < noff; i++) {
uint8_t data;
err = lfs_bd_read(lfs, NULL, rcache, noff-i,
head, i, &data, 1);
// 写入新块
err = lfs_bd_prog(lfs, pcache, rcache, true,
nblock, i, &data, 1);
}
*block = nblock;
*off = noff;
return 0;
}
// 4. 上一个块满了：创建新块，写入跳表指针
index += 1;
lfs_size_t skips = lfs_ctz(index) + 1;
lfs_block_t nhead = head;
for (lfs_off_t i = 0; i < skips; i++) {
// 写入第i个指针（指向2^i个block之前）
nhead = lfs_tole32(nhead);
err = lfs_bd_prog(lfs, pcache, rcache, true,
nblock, 4*i, &nhead, 4);
nhead = lfs_fromle32(nhead);
if (i != skips-1) {
// 读取下一个要写入的指针值
err = lfs_bd_read(lfs, NULL, rcache, sizeof(nhead),
nhead, 4*i, &nhead, sizeof(nhead));
nhead = lfs_fromle32(nhead);
}
}
*block = nblock;
*off = 4*skips; // 数据从指针区后面开始
return 0;
relocate:
LFS_DEBUG("Bad block at 0x%"PRIx32, nblock);
lfs_cache_drop(lfs, pcache); // 重试
}
}
关键步骤：
- 分配一个新块（通过块分配器）
- 如果上一个块没有完全填满（比如文件在非块边界结束），把数据从旧块coalesce（合并）到新块
- 写入ctz(n)+1个跳表指针
- 数据区域从指针区域之后开始
追加是O(1)的： 分配块、擦除块、写入指针、返回。与之前的块无关——不需要修改任何旧数据。
COW的写入安全
CTZ跳表实现了真正的Copy-On-Write文件数据存储。修改文件中途数据的过程如下：
CTZ跳表的COW写入流程
=========================================
原始状态：
┌──────────┐
┌│metadata │
││ │
││ │
│└──────────┘
│ │
│ v
┌────────┐ ┌────────┐ ┌────────┐ ┌───────┐
│ data 0 │<│ data 1 │<│ data 2 │<│data 3 │
│ │<│ │─│ │ │ │
│ │ │ │ │ │ │ │
└────────┘ └────────┘ └────────┘ └───────┘
写入新数据到文件末尾：
┌──────────┐
┌│metadata │ ← 还没有更新
││ │
││ │
│└──────────┘
│ │
│ v
┌────────┐ ┌────────┐ ┌────────┐ ┌───────┐
│ data 0 │<│ data 1 │<│ data 2 │<│data 3 │ ← 旧数据还在
│ │<│ │─│ │ │ │
│ │ │ │ │ │ │ │
└────────┘ └────────┘ └────────┘ └───────┘
^ ^ ^
│ │ │ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐
│ │ └────│ new │<│ new │<│ new │<│ new │
│ └────────────────│data 2 │<│data 3 │─│data 4 │ │data 5 │
└──────────────────│ │─│ │─│ │ │ │
└────────┘ └────────┘ └────────┘ └────────┘
提交到metadata pair：
┌──────────┐
┌│new │
││metadata │
││ │
│└──────────┘
│ │
│ │
│ v
┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐
│ new │<│ new │<│ new │<│ new │
│data 2 │<│data 3 │─│data 4 │ │data 5 │
│ │─│ │─│ │ │ │
└────────┘ └────────┘ └────────┘ └────────┘
- 创建新的数据块链（COW）——旧数据块原封不动。
- 更新metadata pair中的文件记录——指向新的head块。
- 旧数据块变成垃圾——等待后续compaction回收。
如果在任何一步掉电：旧metadata pair（指向旧数据块链）仍然完好。挂载后恢复到写入前状态。这就是COW+Metadata Pair的组合威力。
与KnotFS的对比
KnotFS（第三章）的文件数据管理采用的是更简单直接的方案：每个文件有一个固定大小的indirect block（4KB），内嵌一个块地址数组——最多8个块地址。 文件大小上限为8×4KB = 32KB。
KnotFS Indirect Block vs LittleFS CTZ Skip-List
=============================================================
特性 KnotFS LittleFS
─────────────────────────────────────────────────────────────
数据块索引 直接的块地址数组 CTZ跳表
块数上限 8（固定） 无限制（理论2^32）
随机访问 O(1)（直接数组索引） O(log n)
追加写入 O(1)（写入新块+更新FT） O(1)
随机写入（修改中途） 需要COW整个indirect block O(n)（需要重建后续链）
元数据大小 每个文件4KB（整个 每个文件无额外block
indirect block） （信息存在目录项中）
─────────────────────────────────────────────────────────────
KnotFS的设计假设“文件很小且数量有限“（8个文件 × 每个最多32KB = 256KB 总数据量）。在这个约束下，固定数组是最优选择——简单、快速、内存占用确定。
LittleFS的设计假设“文件和设备大小都不确定“。它需要支持从512KB到GB级的设备，需要支持从几个字节到几百MB的文件。CTZ跳表是这种伸缩性需求下的最优解。
文件系统的收缩与内联优化
LittleFS的CTZ跳表还有一个灵活的变体：小文件内联（inline）。 当一个文件小于block_size/4时（对于4KB块，小于1KB），LittleFS直接把文件内容存在目录的metadata pair中，不创建CTZ跳表。
内联文件存储
=========================================
┌──────────────────────┐
│ revision │
│──────────────────────│
│ file.txt 名字 │
│ file.txt 数据 │ ← 直接存在metadata pair中
│ (≤1KB) │ 不需要CTZ跳表
│──────────────────────│
│ CRC │
└──────────────────────┘
文件存储成本对比：
内联文件（≤1KB）： ~16 bytes（名字+数据+tag）
小文件（>1KB, 1个块）： ~4KB（一个CTZ数据块）
大文件（n个块）： ~n × 4KB（每个块有平均2个指针的开销）
这确保了一个文件的存储开销永远不会超过4x实际大小——随文件增长，开销从100%（1byte的文件占用4KB块）下降到接近0%（大文件下指针开销几乎忽略）。
这是LittleFS又一次展示了“有界思想“的力量：不仅RAM增长有界，存储开销增长也有界。
KnotFS 的 CoW 走了一条更简单的路：没有 CTZ 跳表，没有反向块号映射——每个文件最多 8 个直接块，直接存在文件条目里的 blocks[8] 数组中。这样做的好处是代码量极低（不需要 CTZ 公式和跳表导航），代价是文件最大只能到 32KB。LittleFS 的 CTZ 是为了“支持任意大文件且不牺牲读性能“而设计的；KnotFS 的简化版 CoW 是为了“在 64KB 总空间中管理最多 8 个文件“而设计的。同样叫 CoW，约束不同，实现的复杂度量级可以差出两个数量级。
下集预告
CTZ跳表让我们能高效地存储和读取文件数据——但每一次分配数据块，都依赖于块分配器告诉你“下一个空闲块在哪里“。在128个块的小设备上，扫描一遍全盘只需要毫秒。但在1024块甚至更多的设备上，全盘扫描是不可接受的。LittleFS用一个固定大小的lookahead缓冲区解决了这个问题——它就像一个移动的窗口，在空闲块的空间上滑动，找到一批、用光一批、再找一批。而在这个看似简单的分配过程中，悄然实现了动态磨损均衡。
悬念留给：为什么LittleFS的块分配器在每次上电时需要一个随机数？这个随机数又是从哪来的——从文件系统自己的CRC异或出来的。