ファイルシステムのアロケーション戦略

アロケータが解く問題：どの物理ブロックを渡すか

ファイルへ書き込むとき、ファイルシステムは「この論理オフセットに、ディスク上のどの物理ブロックを割り当てるか」を毎回決めています。この判断を担うのが ブロックアロケータ です。アロケータの良し悪しは、後のシーケンシャル読み出しがどれだけ連続ブロックで済むか、つまり 断片化 の度合いを左右します。HDDではシーク時間に、SSDでも読み出しリクエスト数とリードアンプリフィケーションに直結する、性能の根幹です。

アロケータが満たすべき目標は相反します。連続性（1ファイルを物理的に隣接させる）を最大化したいが、同時に 空き領域を使い切る 必要があり、さらに 割り当て自体を高速 に、できれば並列に行いたい。これらをどう折り合わせるかが設計判断になります。

ブロックグループ：局所性を作る分割単位

ext2/3/4 系はボリュームを ブロックグループ という固定サイズ（典型的に128MB）の区画に分割します。各グループは自分専用の block bitmap（ブロックの空き状況）、inode bitmap、inode テーブル、そして実データブロックを内部に持ちます。

ブロックグループ N の内部
  [ super block 複製 | group descriptor | block bitmap | inode bitmap |
    inode table | ........ data blocks ........ ]

この分割の狙いは 局所性 です。アロケータは「inode が属するグループの中に、そのファイルのデータブロックも置く」「同じディレクトリのファイルは同じグループへ集める」よう試みます。inode（メタデータ）とデータが物理的に近接するため、ファイルを開いて読む際のシーク距離が小さく収まります。bitmap がグループ単位で分かれていることは並列性にも効き、別グループへの割り当てはロックが競合しません。XFS の Allocation Group も同じ発想で、詳しくは ジャーナリングファイルシステムの内部 を参照してください。

遅延割当：物理位置の決定を先送りする

素朴な実装は write() のたびに即座に物理ブロックを割り当てます。しかしアプリは小さな書き込みを何度も発行することが多く、その都度割り当てると、最終的なファイルサイズが分からないまま位置を決めてしまい連続領域を確保しにくくなります。

ext4・XFS が採る 遅延割当（delayed allocation） は、write() の時点では物理ブロックを確定せず、データを ページキャッシュ に溜めて「割り当て予定（unallocated だが予約済み）」とだけ記録します。実際の物理位置は、ライトバックでディスクへ書き出す直前にまとめて決定します。

write() 連発  → ページキャッシュに蓄積（物理位置は未定）
   ...（数秒、または fsync / メモリ圧迫まで保留）...
writeback 時 → 蓄積総量が判明 → 連続エクステントを一括割り当て

この先送りには明確な利得があります。第一に、書き出し時点で 総バイト数が判明 しているので、必要なブロック数の連続空きを一発で探せます。第二に、短命な一時ファイルが書かれてすぐ消えれば、割り当てが一度も起きずに済みます。ライトバックの仕組み自体は ページキャッシュとライトバック で扱います。

エクステント：連続確保を範囲で表す

遅延割当で連続領域を取れても、それを 記録する方法 が貧弱だと意味が半減します。古い方式は1ブロックごとに物理アドレスを間接ブロックへ列挙したため、1GBのファイルで数十万エントリを要しました。

エクステント は連続ブロックを「論理オフセット＋長さ＋開始物理ブロック」の三つ組で表す範囲表現です。連続した数万ブロックをわずか1エントリで記述できます。

エクステント = (logical_offset, length, physical_start)
  (0,    8000, 50000)   ← 先頭から8000ブロックが phys 50000 から連続
  (8000, 4000, 90000)   ← 続きは別の連続領域

エクステントは連続性が高いほどエントリ数が減るので、遅延割当と組み合わせると効果が最大化されます。逆に断片化したファイルはエクステント数が膨らみ、メタデータ自体が肥大して探索コストが増えます。エクステント数はファイルの健全性を測る実用的な指標になります。

断片化の発生と対策

断片化は2種類あります。ファイル断片化 は1ファイルが多数の不連続エクステントに分かれる状態。空き領域断片化 は空きブロックが小さな穴に細分化され、大きな連続割り当てができなくなる状態です。後者がより厄介で、空きの総量は十分でも連続空きが枯渇します。これは物理メモリの外部断片化と同型の問題で、対策の発想は メモリアロケータの内部 の buddy system とも通じます。

XFS は空きエクステントを 開始ブロック順 と サイズ順 の2本のB+Treeで保持し、前者で隣接空きの結合判定、後者で最適合わせ探索を高速化します。割り当てと解放のたびに隣接空きを即座に結合（coalesce）することで、空き領域断片化の進行そのものを遅らせる設計です。

予約領域の設計判断：なぜ空けておくか

ファイルシステムは満杯まで使わせず、意図的に 予約領域 を確保します。ext4 の既定は全体の5%を root 専用に予約します。これは単なる安全マージンではなく、アロケータの性能を保つための設計判断です。

空きが極端に少ないと、連続空きが見つからずアロケータは小さな穴を寄せ集めるしかなくなり、新規ファイルが激しく断片化します。空き率が一定以上あれば「近傍に連続空きが存在する確率」が高く保たれ、最適合わせ探索が短時間で成功します。予約はこの 探索の余地 を残すための投資です。加えて、システム重要プロセスが書き込めずに停止する事態を防ぐ役割もあります。

まとめ

• ブロックグループ はディスクを区画化し、inode とデータを近接させる局所性と、グループ単位 bitmap による並列割り当てを同時に実現する。
• 遅延割当 は物理位置の決定をライトバック直前まで先送りし、総サイズ確定後に連続エクステントを一括割り当てして断片化を予防する。永続性は fsync に委ねられる。
• エクステント は連続領域を範囲で表してメタデータを削減し、遅延割当と組み合わさって連続確保の効果を最大化する。
• 断片化 はファイル断片化と空き領域断片化に分かれ、プリアロケーション・最適合わせ探索・隣接結合・オンラインデフラグで抑える。
• 予約領域 はアロケータに探索の余地を残す投資であり、容量効率との均衡を用途ごとに決める。基礎は ファイルシステム も参照してください。