ファイルシステム 基礎

下から。ブロックは 4 KB の固定長チャンク、inode は 1 ファイル分のメタデータとオフセットからブロックへの写像、ディレクトリはデータが名前の表になっている inode にすぎない。まずカーネルが最初に見るままのパスを見てほしい。まだ何も読んでいない、名前の連なりだけだ。スライダーが 1 つずつ辿る：

ここでは何も払っていない。それがこの姿の言いたいことだ。パスは 1 回の検索ではなく検索の列で、その 1 回ごとにディレクトリ自身のデータブロックを読んで名前を見つける必要がある。同じ歩みに、その箱を 1 つだけ足すと：

名前 5 つ、ディレクトリブロック 5 つ。ただしディレクトリの中の名前は番号でしかない ——どの inode かを言うだけで中身は言わない —— から、その検索ごとにそれが名指す inode をもう 1 回読む。その箱も足し、各コンポーネントをもう一度歩いて、キャッシュを替えてほしい：

コストの在処に注目。ファイルではない。コールドなら 5 段で 10 ブロック読み、ログの 1 バイト目にはまだ触れていない。ウォームなら 0 ——dentry キャッシュが全部 RAM から返す。深いパスの open() が最初だけ高いのはこれだ。

inode の中の写像は 15 個のスロット：直接が 12 個、続いて 1 段・2 段・3 段間接。バイトがどこに座っているかが読みの値段を決める。オフセットをドラッグするか、軸上のハンドルを引いてほしい：

鎖が伸びるのを見てほしい。4 KB ブロックと 4 バイトのブロック番号なら間接ブロック 1 つに 1,024 ポインタ。到達範囲は 48 KB、4 MB、4 GB、4 TB。4 GB のバイトは 3 ブロック読み、最遠端は 4 回、うち 3 回は写像だ。深いファイルほど尻尾が高くつく。

エクステントはリストを「ひと続き」に置き換える。ext4_extent 1 本は 12 バイトで最大 128 MB の連続ブロックを記述でき、4 本なら inode に収まる。断片化を上げて、エクステントの写像がポインタのリストに近づくのを見てほしい：

1 GB は 262,144 ブロック。ポインタなら 1 MB の写像と間接ブロック。8 本のエクステントなら 96 バイト —— まだ収まらない。ee_len は 15 ビットなので 1 本の上限は 32,768 ブロック、完全に連続でも 8 本要る。i_block は 60 バイト、ヘッダ 12 と 12 バイト記録 4本。5 本目で写像はエクステントツリーの葉へ溢れ、読みが 1 回増える。

名前とファイルは別物で、inode は名前を数えている。カウントを 0 まで下げ、 symlink に切り替えてもう一度 ——名前、inode、残るもの：

inode が数えるのは参照だ。rm は unlink —— 名前を外してカウントを 1 減らす。解放は 0 のとき、開いているプロセスがあれば 0 でも解放されない。消したログが容量を食い続けるのはこれだ。symlink は何も数えず、ターゲットを消せばリンクは ENOENT を指す。

コストが隠れるもう 1 つの場所がディレクトリだ。ext4 は htree —— 1〜2 段のハッシュ B ツリー —— で索引を張る。無ければ 1 回の検索は全ブロックの線形走査だ。エントリ数を対数軸で上げ、2 本が分かれるのを見てほしい：

すぐに分かれる。100 万ファイルで htree は 3 ブロック読み、線形走査は平均 2,942 回。索引があるから誰も気づかない ——readdir のあと全エントリに stat を掛ける何かが現れるまでは。それはどんな索引も助けない。

これらはすべて mkfs の時点で敷かれ、そこで大きさが決まる。inode の密度をドラッグし、次にこれから置くファイルの大きさをその下まで下げてほしい：

16 KB ごとに inode 1 個という既定はデバイスの 1.6% —— 4 TB で 64 GB、空のままだ。（KB は 1,024 バイト。4 TB ÷ 16 KB = 268,435,456 個の inode × 256 B でちょうど 64 GB。）個数は固定される。64 KB ごとに 1 個の上へ 4 KB のファイルを置けば、容量の 6.3% で inode が尽き、df が空だと言う横で ENOSPC が返る。理由を言うのは df -i だけだ。

page cache は触られたファイルデータの写しで、(inode, オフセット) で索引される —— free -h の buff/cache だ。読みではまずここを見る：常駐するページなら memcpy 1 回、無いページならデバイスまでの往復だ。ページを横に歩き、デバイスを替えてほしい：

この差に注目。ヒットは 0.7 µs —— システムコール、検索、4 KB の memcpy。同じ読みが NVMe なら 80 µs で 114 倍、7200 rpm なら平均シーク 6 ms と平均回転 4.17 ms で 10.2 ms、14,571 倍。コードは 1 文字も変わらない。変わったのはページが在ったかだけだ。

書きは違う。カーネルはキャッシュへコピーし、ページをダーティに印を付け、戻る。メディアへ載せるのは後で誰かがやる。電源断を時間軸上でドラッグし、そのページが自分の手で失えなくなる瞬間を探してほしい：

dirty_expire_centisecs が 3000、flusher は 5 秒ごとに起きるので、書いたページが書き戻せるのは 30 秒後、RAM に居られるのは 35 秒。write() の成功はカーネルメモリにある意味で、電源断の外ではない。

ダーティページには上限があり、書いた当人に課される。dirty_background_ratio は RAM の 10%、dirty_ratio は 20%。線の下では書きは memcpy だ。ダーティの割合を両方の線の先へ押し、write() の値段を見てほしい：

段差を見てほしい。10% 未満なら書きは memcpy、20% を超えると呼び出した側が自分で書き戻しをやらされ、21% で 0.7 µs ではなく 321 µs —— この数値は実測ではなくモデルだ。閾値を越えると balance_dirty_pages が超過分に比例して書き手を眠らせるフィードバックループを回し、図はその 1 回の眠りをデバイス書き 2 回分として値付けしている。曲線の高さはカーネル版依存だが、20% の段差はそうではない。大きなコピー中の「プロセスが 2 秒固まった」の正体はこれだ。1 回の write() が全員のツケを払っただけだ。

読みには書きにない助けがある。順次に見えるとカーネルは先読みウィンドウを開き、read_ahead_kb の 128 KB まで倍々に広げる。下の帯はちょうどその窓 1 つ分、ファイルの 32 ブロックで、ストライドがそのどれを要求するかを決める：

ストライド 1 なら窓は開いていて、1 リクエストが 32 ブロック全部を覆い、使う 1 KB あたり 1.1 µs だ。ストライド 2 では閉じる。欲しいブロックが 1 つずつ自分のリクエストになり —— 実際に読む 64 KB に 16 個 —— 使える 1 KB は 20 µs、18 倍悪くなる。1 より大きいどのストライドでもそこから戻らない。払っているのはバイトではなくリクエストで、しかも 1 つずつが 4 KB のブロックを丸ごと引きずり込み、使うのはそのうち 1 フィールドだ。

O_DIRECT はキャッシュを丸ごと外す。自分のバッファからデバイスへ DMA、アライメント制約もろともだ。最適化のつもりで手が伸びやすい。読み返し回数をドラッグして、キャッシュが開けていく差を見てほしい：

ちょうど 1 回の読みまでだ。2 回目からは page cache 経由が 0.7 µs、O_DIRECT はまたデバイスへ行く —— 2 回なら 81 µs 対 159 µs。O_DIRECT が勝つのは自前のキャッシュがカーネルより賢いときだけだ。

メタデータの変更はビットマップ、inode、ディレクトリブロックに同時に触り、途中で中断されれば自分と矛盾するファイルシステムが残る。だがその前に、バイトはどこかへ行かねばならない。4 か所あって、生き残るのは最後の 1 つだけだ：自分のバッファ、page cache、デバイス自身の書き込みキャッシュ、そしてメディア。再生を押すか、手でスクラブしてほしい：

fsync が 1 段ではなく 2 段であることに注目。ブロック層へ流すだけでは足りない。ドライブは揮発性の DRAM に受理して応答するので、fsync はキャッシュフラッシュ命令も出して応答を待つ。5 段目で止まった書き込みは、電源が保つ間だけ耐久的だ。

journal はメタデータ変更を原子的にする。新しいブロックをログへ書き、次に commit ブロックを書き、それからファイルシステムに触る。電源断を動かし、各地点の判定を読んでほしい：

不変条件は一文だ。回復時、commit ブロックのあるトランザクションは再適用され、無いものは破棄される。だから常に古い方か新しい方だ。回復の上限はディスクではなくログ ——mke2fs は journal を 128 MB で頭打ちにし、順次 NVMe 読みで 38 ms。4 TB の inode テーブルを流すだけで 20 秒かかるのに対してだ。20 秒は下限で見積もりではない。実際の e2fsck はビットマップとディレクトリツリーも、順次読みではなくシークで歩く。

ext4 には 3 つのモードがあり、既定は折衷だ。data=ordered はメタデータだけを journal に載せるがデータブロックを先に書く。data=journal はデータもログに通す。data=writeback も記録するのはメタデータだけだが、データはいつ落ちてもよい。セグメントを左から右へ動かし、スライダでトランザクションを大きくしてほしい：

増幅を見てほしい。データ 1 MB で data=journal は 2.01 倍 —— 全バイトを 2 回 —— 書き、最強のクラッシュ意味論を得る。そして data=writeback が何を買っていないかを見てほしい。棒の長さは data=ordered と同じだ。書くバイトが同じだからだ。落としているのは順序で、それは事故が起きるまでは只だ —— データより先にメタデータをコミットさせうるので、クラッシュは伸ばしたばかりのファイルにそのブロックの以前の中身 —— 他人の削除済みデータかもしれない —— を見せうる。只なのに他人のバイトを渡しうるモードこそ、避けるべきものだ。

fsync は何かを約束する唯一の POSIX 呼び出しで、しかも値段はバイトではなくコミット単位だ。デバイスを選び、1 回の呼び出しの後ろにライタを増やしてほしい：

値段がフラッシュ単位なので、まとめればスループットはほぼただだ。7200 rpm でライタ 1 本なら毎秒 100 回の永続コミット —— プラッタが回る必要があり、そのうち 4.17 ms が平均回転待ちだ。16 本が 1 回の fsync を共有すれば 1,581 回 —— 1 回転あたり 16 コミットから、この図がライタ 1 本増えるごとに 8 µs と値付けした待ち行列分を引いた値だ。実測なのは回転だけで、待ち行列の項は図のモデル、きっかり 1,600 にならない理由もそれだけだ。グループコミットとはこれだ。

次の問いは避けられない。fsync が 700 µs なら、fdatasync は何を省いていて、なぜ常にそれを使わないのか。呼び出しをドラッグし、条件を切り替えてほしい：

2 列目に注目。fdatasync はデータを押し下げ、inode を飛ばす。メタデータ書きと journal コミットが浮くので 540 µs 対 700 µs だ。だがファイルが伸びたに切り替えると割引は消える。新しいサイズは読み戻しに要り、POSIX はそれをデータの一部と定めている。追記するライタ —— ログや WAL —— は何も得ない。fallocate で先に確保すれば戻る。

残る 3 行は同じ内訳の欠けたもので、欠ける項の大きさは違う。3 回のデバイス書きから flush を抜いて残りを見てほしい：

sync_file_range は読み違えられやすい行だ。データを動かすだけで、他は何も強制しない —— メタデータもなく、cache flush もない —— だから書き戻しを早めに始める手段であって、永続化の手段では決してない。man ページ自身がそう書いている。そして nobarrier は同じ削除を fsync に当てたものだ。flush を落とせばコミットは 700 µs ではなく 241 µs になる。安全なのは電源断保護のあるデバイス —— はしごの PLP の段 —— だけで、それ以外では、電源断で最後の 1 秒ぶんの書きを黙って失う 2.9 倍の高速化にすぎない。

そして fsync は失敗しうる。デバイスがエラーを返すと、カーネルの手元には書けないダーティページが残り、永久に抱えることもできないので捨てる。次の呼び出しが何を報告するか、順に踏んでほしい：

これが 2018 年に PostgreSQL で見つかった fsyncgate だ。2 回目の fsync が 0 を返すのは、エラーが消費されページがもう無いから —— 起きなかった書き込みに成功が報告される。Linux 4.13 より前は、エラーを見られるのは 1 つの fd だけだった。答えは一様だ：fsync の失敗は回復不能として扱い、panic し、ログから作り直す。

だからファイルの置き換えは write ではなく 4 段のレシピになる。レシピを選び、切断点を動かし、再起動後に何が残るかを読んでほしい：

注目。あらゆる切断点で安全なのは完全なレシピだけだ。その場で上書きすると半分古く半分新しいものが残り、控えは無い。fsync せずに rename すると、名前が未割り当てのブロックへ翻る ——0 バイトの設定ファイルで、2009 年に何千もの ext4 利用者を刺した。誤った版と正しい版は 2 行違いで、誤った方はテストに通る：

write(f, buf, n)
fsync(f)          # 誤った版はこの行が無い
close(f)
rename(tmp, dst)
fsync(dirfd)      # この行も無い

4 つのレシピの下には同じ硬い床がある。デバイスの 4 KB セクタが原子的な最大の単位で、その上には何も無い。ページ書き込みの中で切断点を動かし、ページを広げてほしい：

8 KB のページは 2 セクタにまたがるので、3 つの切断点のうち 1 つが裂けたページを残す —— 半分新しく半分古く、チェックサムは落ちる。POSIX はそれ以上を約束していない。Postgres は WAL への全ページ書き込みで、ZFS と btrfs は上書きしないことでこの隙間を埋める。

ext4 と XFS はその場で上書きし、メタデータを journal に載せる。ZFS と btrfs は生きたブロックを上書きせず、新しい場所へ書いてルートまでの経路を書き直すことで変更を公開する —— コミットはポインタ 1 本だ。4 KB の上書きを葉から superblock まで歩かせ、新しいブロックが古いブロックの隣に現れるのを見てほしい：

最後の 1 歩まで、古い木はどの段階でも完全でマウント可能であることに注目。journal がログで買う性質を、COW は書きの形から得ている。請求書は増幅 —— 4 KB の上書きが 6 ブロックに触った —— と断片化だ。

2 つ目の違いは、誰かが検査しているかどうかだ。コンシューマ向けディスクの規格は 10¹⁴ bit 読むごとに読めないセクタが 1 個未満。読んだ量をアレイ再構築の規模までドラッグしてほしい：

12 TB で 1 個に当たる確率は 62%。ext4 と XFS は自分のメタデータにしか付けないので、反転した 1 ビットはデータとしてそのまま返る。ZFS と btrfs は全ブロックにチェックサムを付け、壊れていると言える。訂正ではなく検出だ —— 訂正には 2 つ目の複製、つまりミラーが要る。

3 つ目は、割り当て器が動くときに何を知っているかだ。ext4 は割り当てを書き戻しまで遅らせるので、write() 1 回ずつではなく走り全体を一度に見る。割り当て器が選ぶ前にどれだけ溜めるかを変えてほしい：

見てほしい。4 KB 粒度なら 1 GB は 262,144 エクステントと 3 MB の写像。128 MB ずつ溜めれば 8 エクステントと 96 バイト ——i_block に入る 4 本よりまだ 2 本多いが、3 段の木ではなく葉ブロック 1 つで済む。write() 直後のクラッシュが何も割り当てられていない状態を見つけうるのも遅延割り当てのせいだ。連続にする仕掛けと空にする仕掛けは同じものだ。

もう 1 つ。いまや多くの人はコンテナ越しにファイルシステムと出会うからだ。overlayfs は読み取り専用の下位レイヤを書き込み可能な上位レイヤの下に敷き、下位のファイルへの最初の書き込みはファイル全体を上へコピーする。ファイルサイズをドラッグしてほしい：

200 MB のファイルを 1 バイト変えるとおよそ 175 ミリ秒 —— コピーは同じデバイスを読み書きして約 1.2 GB/s —— ブロックし、コンテナの書き込み可能レイヤを 200 MB 食う。イメージの中のデータベースがボリュームを欲しがる理由であり、レイヤに対する chmod -R が見た目ほど安くない理由だ。

• ループの write() で耐久性を主張。電源断 1 回で無かったことになる。
• 失敗した fsync の再試行。ページは無く、0 が返る。
• 設定を O_TRUNC で置き換える。一時ファイル、fsync、rename、ディレクトリの fsync。
• ディレクトリをキーバリューストアに。検索は安いが readdir+stat は違う。
• O_DIRECT を最適化として掴む。 2 回目の読みから、外した側のほうが安い。