RSSで流れてきたlittlefsを読んだのとFatFsとの比較

RSSを流し見してたら littlefs の DESIGN.md が流れてきた。マイコン向けのファイルシステムで、停電耐性を本気で解こうとした設計が面白かったので読んだ。

詳細な設計の話は DESIGN.md に全部書いてあるのでそっちを読んでほしい。ここでは要点だけ。

littlefs とは

マイコン向けの組み込みファイルシステム。ターゲットは RAM 約 32KiB、ROM 約 512KiB 程度の 32bit マイコン + SPI NOR フラッシュ。

設計上の制約が 3 つある。

• 停電耐性 — 書き込み中のどのタイミングで電源が落ちても壊れないこと
• ウェアレベリング — フラッシュの特定ブロックに書き込みが集中して早死しないこと
• RAM 上限保証 — ファイルシステムのサイズが増えても RAM 使用量が増えないこと

マイコンは「シャットダウン処理」という概念がないので、停電耐性は必須要件になる。

既存 FS の問題点

DESIGN.md では既存のアプローチを 4 つ整理している。

ログ型は GC が O(n²) か O(n) RAM のどちらかになる。COW は更新がルートまで伝播して特定ブロックにウェアが集中する。どれも一長一短。

littlefs のアプローチ

ログ型と COW を合体させたアプローチを取っている。

ログ型の問題への対処: ログのサイズに上限を設ければ、O(n²) の計算量を O(1) に見せかけられる。「有界（bounded）」というのは「上限がある」という意味で、n が定数に固定されていれば O(n²) も実質 O(1) と言い張れるというハック。

COW の問題への対処: 1 回書くたびにコピーするのではなく、n 回書いたらコピーする CObW（Copy-on-Bounded-Writes） に変形する。各レベルで伝播頻度が 1/n になるので、n がブランチファクタより大きければウェアの伝播が収束する。

これを実現する 2 つのコアデータ構造がある。

Metadata Pairs（メタデータペア）

2 ブロック 1 組の小さなログ。FS 上のどこでもアトミックな更新を可能にする基盤になる。

「サーキュラーログ」というのはリングバッファのログ版で、端まで行ったら先頭に戻って使い続ける構造のこと。ただしフラッシュは上書きができない（消去がブロック単位でしかできない）ので、1 ブロックだけでは成立しない。そこで 2 ブロック交互に使う。

A: [エントリ1][エントリ2][エントリ3]  ← 満杯
B: [    空                          ]

コンパクション（Bに最新だけ詰める）
A: [エントリ1][エントリ2][エントリ3]  ← 保険として残す
B: [エントリ2'][エントリ3]            ← 現役に昇格

次が満杯になったら A を消去して A に書く → 交互に繰り返す

2 ブロット構成の理由は停電耐性のため。コンパクション中に電源が落ちても古いブロックが完全な状態で残っているので復旧できる。チェックサム（CRC）で壊れているかどうかを判定して、壊れていたら古い方を使う。

ブロックが埋まったらコンパクション（古いエントリを捨てて詰め直す）、コンパクションしてもゴミが出ないなら 2 つにスプリットして連結リストにする。コンパクションは 50% 埋まった時点でトリガーして、GC コストを平均 2x 以内に抑える（償却 O(1)）。

CTZ スキップリスト

ファイルの実データを格納する COW データ構造。

追記が多いことを前提に逆向きリンクリストにする。通常のリンクリストは先頭ポインタを持つが、逆向きは末尾ポインタだけ持って、各ブロックが「自分の前のブロック番号」を持つ構造になる。

通常:   head → A → B → C → D
逆向き: A ← B ← C ← D ← tail

追記時は新しいブロック E に「前は D だよ」というポインタを書くだけで、既存ブロックは一切触らない → O(1)。

ただし逆向き単純リストだと順方向（先頭から）に読むときに端から端までたどる必要があり O(n²) になる。これを解決するのがスキップリスト。

ブロック n は、n が 2^x で割り切れるたびに n-2^x へのショートカットポインタを追加で持つ。

0 ← 1 ← 2 ← 3 ← 4 ← 5
          ↑         ↑
     0 ←--'    0 ←--'
               1 ←--'（block4は3本のポインタを持つ）

ショートカットの実体は「ブロック番号（= フラッシュ上の物理的な位置）」なので、その番号さえわかれば直接アクセスできる。どのブロックが何本のポインタを持つかは自分のインデックスだけで決まる（外から何かを渡す必要はない）。これにより読み込みが O(n log n) になる。追記は O(1) のまま。

面白いのはポインタ数の計算で、sum(ctz(i)+1, i=0..n) = 2n - popcount(n) という恒等式が成立する。これを使うとファイルサイズからブロックインデックスを CTZ と popcount だけで O(1) 計算できる。

FatFs と比べてどうか

調べてたら FatFs という組み込み向けの定番 FS があった。ChaN 氏が個人で開発・メンテしている FAT/exFAT 実装で、世界中のマイコンで使われている。

FatFs は FAT ベースなのでブロックベース FS に分類される。

FatFs が広く使われているのは SD カードとの相性がいいから。SD カード自体がコントローラ内部でウェアレベリングと停電対策をある程度やってくれるので、FatFs 側がそれをしなくても実用上問題ない。

NOR フラッシュに直接 FatFs を使うのは本来リスクがある。そういう用途には littlefs の方が向いている。

まとめ

• FatFs: SD カードに乗せるならこれ。シンプルで枯れてる
• littlefs: NOR フラッシュ直書きで停電耐性が必要なら

設計ドキュメントは読み物として普通に面白かった。FS の教科書的なトレードオフが整理されている。 DESIGN.md / FatFs 公式