ログ構造化ファイルシステムとF2FS

なぜ書き込みを追記ログにするのか

従来のファイルシステムは、ブロックを その場で上書き します。inode を更新すれば inode のある位置へ、データを書き換えれば元のブロックへシークして書き込みます。HDDではこのシークが支配的コストで、小さな更新が散らばるほどヘッド移動で遅くなりました。

LFS（Log-Structured File System、Rosenblum と Ousterhout が1991年に提案）の発想は単純です。いっさい上書きせず、すべての書き込みをディスク末尾へ追記する。データもメタデータも、変更があれば常に新しい場所へ順番に書く。これによりディスクへの書き込みは理論上すべて シーケンシャル になり、シークがほぼ消えます。

前提は「読み出しの多くはキャッシュで吸収できるので、ディスクは書き込み性能で律速される」という観測でした。ページキャッシュが効くほど、ディスクI/Oは書き込みに偏る——だから書き込みをひたすら速くする、という設計判断です。書き込みの集約は ページキャッシュとライトバック の仕組みと相性が良く、溜めた更新をまとめて1本のログとして流します。

セグメントとログ構造

追記といっても1ブロックずつ書くわけではありません。LFSはディスクを セグメント（典型的には数MBの固定長領域）に分割し、メモリ上で1セグメント分の更新を組み立ててから一括で書き出します。これで個々の書き込みもセグメント境界に整列したシーケンシャルI/Oになります。

問題は inode の位置が固定でなくなる ことです。inode も追記されるたびに移動するため、「inode番号 → ディスク上の位置」を引く表が要ります。LFSはこれを inode map（imap） で解決します。

ファイル参照の経路（純LFS）
  inode番号 ──imap──▶ inodeの現在位置 ──▶ データブロック
                 ▲
                 imap 自体もログへ追記され、
                 最新位置は固定の「チェックポイント領域」が指す

imap も追記対象ですが、その断片の最新位置だけは固定位置の チェックポイント領域 に記録します。起動時はここを起点に最新の imap をたどれば全体が復元できます。これは ジャーナリングファイルシステム のような別建てのログを持つのではなく、ファイルシステム全体がそのままログである という違いです。クラッシュ復旧はログ末尾から有効なチェックポイントを探し、その先の不完全な書き込みを切り捨てる ロールフォワード で行います。

セグメントクリーニング：追記の代償

上書きしないということは、ファイルを更新するたびに 古いブロックが無効データとして残り続ける ことを意味します。放置すればディスクは無効ブロックで埋まり、新規追記に使える連続空き領域が枯渇します。これを回収するのが セグメントクリーニング、すなわちガベージコレクション（GC）です。

クリーニングは次のように動きます。

1. 回収候補のセグメントを選ぶ
2. その中の「まだ有効な」ブロックだけを読み出す
3. 有効ブロックを別の新しいセグメントへ追記する（＝また書き込み）
4. 元のセグメント全体を空き領域として解放する

ここで本質的なコストが発生します。有効ブロックの移動それ自体が追加の書き込み だという点です。ユーザーが1だけ書いても、GCが背後で有効データを動かせば実際のディスク書き込みは増える——これが 書き込み増幅（write amplification） です。

あるブロックが有効か無効かを判定するには、各セグメントに セグメントサマリ（このブロックがどのファイルの論理ブロックに対応するか）を持たせ、現在の imap/inode が指す位置と一致するかで確認します。一致すれば有効、しなければ既に上書き済みの無効データです。

クリーニング方針：どのセグメントを、いつ

GCの効率はセグメント選択ポリシーで大きく変わります。古典的な指標が以下です。

cost-benefit が要点です。直感は「すぐまた無効化されそうな新しいデータは、回収せず放っておけばタダで無効になる。長く生き残っている冷たいデータは、動かしても無駄が少ない」というもの。有効率の低さ（回収量）と age（その状態が続く見込み）を掛けて評価します。

さらに実行タイミングにも前景・背景の別があります。バックグラウンドGC はアイドル時に静かに進め、フォアグラウンドGC は空き枯渇時に書き込みを止めてでも実行します。後者が走るとユーザーI/Oが待たされ、レイテンシのテール（最悪値）が悪化します。GC由来のI/Oと通常I/Oの調停は I/Oスケジューラ の優先制御とも絡む問題です。

F2FS：フラッシュのための再設計

LFSの原理はSSD/eMMCに極めて好都合です。NANDフラッシュは 消去してからでないと書けず、消去単位（ブロック）は書き込み単位（ページ）より大きい。だから追記中心でシーケンシャルに書くLFSは、フラッシュ内部の都合と自然に噛み合います。これを正面から狙ったのが F2FS（Flash-Friendly File System、Linux 3.8 で導入）です。F2FSは純LFSの弱点を次のように手当てします。

1. wandering tree の抑制（固定マッピングのNAT） 純LFSではデータを更新すると inode が移動し、inode が移動すると imap が更新され……と参照が上流へ波及します。F2FSは NAT（Node Address Table） という固定位置のテーブルを置き、「ノードID → 物理位置」をここで一括解決します。データ更新でノードの中身は変わっても、NATの該当エントリを書き換えるだけで済み、親へ連鎖する更新（wandering tree）が止まります。

F2FSのアドレス解決
  inode/直接ノード/間接ノードはすべて「ノード」
  各ノードは node ID を持つ
    node ID ──NAT──▶ 物理ブロック位置
  データ更新 → そのノードを追記 → NATの1エントリだけ更新（上流に波及しない）

2. 多重ログによるホット／コールド分離 F2FSは単一のログではなく 複数のアクティブセグメント を同時に開き、データの寿命予測で書き分けます。頻繁に変わる ホットデータ（ディレクトリエントリ、よく更新されるファイル）と、めったに変わらない コールドデータ を別セグメントに集約します。同じ寿命のブロックが固まるほど、GC時にセグメントごと一括無効化されやすく、有効ブロックの移動が減ります。

3. FTLを意識した整列とトリム SSD内部の FTL（Flash Translation Layer） が論理↔物理を再マッピングし、独自のGCとウェアレベリング（消去回数の平準化）を行います。F2FSはセグメントをフラッシュの消去ブロック境界に整列させ、解放領域を discard（TRIM）でFTLへ通知します。FS層とFTL層の二重GCが互いに足を引っ張る現象を、整列とヒント提供で緩和する設計です。

GCコストをどう捉えるか

LFS系の性能は、結局 「追記でシークを消した利得」と「GCの書き込み増幅で失う分」の差 で決まります。要点を整理します。

• 書き込み増幅は 空き容量に強く依存 する。容量に余裕がある間はGCが軽く利得が大きいが、満杯近くで有効率が上がると急激に重くなる。プロビジョニング（予約領域）を多めに取るほどGCは楽になる。
• ホット／コールドが 混在するほどGCは無駄に有効ブロックを動かす。寿命で分離できればセグメント単位の一括無効化が増え、移動が減る。F2FSの多重ログはこの分離を狙う。
• フォアグラウンドGCは テールレイテンシの主因 になる。空きが尽きる前にバックグラウンドで先回り回収しておけるか、空き容量の余裕を保てるかが運用上の鍵になる。

まとめ

• LFSは上書きを捨て、データもメタデータも巨大セグメントへ 追記 してランダム書き込みをシーケンシャル化する。inode の移動は imap とチェックポイントで解決する。
• 上書きしない代償が無効ブロックの蓄積であり、セグメントクリーニング（GC） が有効ブロックを移動して回収する。この移動が 書き込み増幅 を生み、空き容量が減るほど重くなる。
• クリーニングは cost-benefit で有効率と age を評価し、冷たいデータを温存して変動領域を優先回収するのが定石。フォアグラウンドGCはテールレイテンシを悪化させる。
• F2FS は固定マッピングの NAT で wandering tree を断ち、多重ログ でホット／コールドを分離し、FTL整列とTRIM で二重GCを緩和する、フラッシュ前提のハイブリッド設計である。基礎は ファイルシステム も参照してください。