バッファプールとページ置換

なぜバッファプールが必要か

DB のデータはディスク上に固定サイズのページ（PostgreSQL なら 8KB、InnoDB なら 16KB）として並びます。ディスクへのランダムアクセスはメモリ参照より桁違いに遅いため、毎回ページをディスクから読み直していてはまともな速度が出ません。そこで DBMS は専用のメモリ領域に最近使ったページを保持し、再アクセスをメモリヒットで返します。これがバッファプール（buffer pool / buffer cache）です。

バッファプールは固定サイズのフレーム（ページ1枚ぶんの枠）の配列です。ページを読むときは、まず「そのページが既にプールに載っているか」を調べ、載っていれば（ヒット）そのフレームを返し、載っていなければ（ミス）空きフレーム、なければ犠牲フレームを選んでディスクから読み込みます。OS のページキャッシュに任せず DBMS が自前で持つのは、アクセスパターンと書き戻し順序（WAL 規律）を DBMS だけが正しく制御できるからです。

ページテーブルと pin/unpin

「ページ番号からフレームを引く」ための索引がページテーブル（buffer table）です。一般にハッシュテーブルで実装され、ページ番号 → フレーム番号 を O(1) で引きます。各フレームには次のメタデータが付随します。

ページを使う側は、利用前に pin（ピン留め）して pin カウントを増やし、使い終わったら unpin して減らします。pin されている間、そのフレームは置換アルゴリズムの候補から外れます。読み出し中・更新中のページを足元から追い出されては困るからです。unpin 時に「内容を変更したか」を伝え、変更していれば dirty ビットを立てます。dirty なページは、追い出す前に必ずディスクへ書き戻さねばなりません（これを怠ると変更が消えます）。

単純 LRU とその弱点

犠牲をどう選ぶか――最も素直なのが LRU（Least Recently Used、最も長く使われていないものを追い出す）です。「最近使ったものは近いうちにまた使われる」という参照の局所性を仮定する、合理的な戦略です。アクセスのたびにそのページを使用順リストの先頭へ移し、追い出すときは末尾を選びます。

しかし DB のワークロードでは LRU が致命的に外れる場面があります。代表がシーケンシャルフラッディング（sequential flooding）です。大きなテーブルの全件スキャンを1回行うと、二度と使わないページが次々とプールに流れ込み、本当にホットだったページ（よく引かれる索引上位ノードなど）を全部押し出してしまいます。一度しか使わないページに、頻繁に使うページが負けるのです。LRU は直近性しか見ず、アクセス頻度を区別しないため、この一過性スキャンに弱いというのが根本原因です。

LRU-K――K 回目の直近アクセスで頻度を見抜く

LRU-K は、各ページの「直近 K 回ぶんのアクセス時刻」を覚えておき、K 回前のアクセス時刻（backward K-distance）が最も古いページを追い出します。K=1 が通常の LRU に一致します。実用上は LRU-2（K=2）がよく使われます。

肝は、犠牲選びに使うのが「最後のアクセス」ではなく「K 回前のアクセス」だという点です。一過性スキャンで1回だけ触れたページは、2回目のアクセス（K=2 の基準）が存在しないため無限遠の過去として扱われ、真っ先に追い出し候補になります。逆に何度も引かれるページは2回目アクセスが新しく、生き残ります。こうして LRU-2 は**「1回もの」と「常連」を分離**し、シーケンシャルフラッディングに強くなります。

ページ A: アクセス時刻 [..., t=90, t=92]   → 直近 = 92, 2回前 = 90（常連）
ページ B: アクセス時刻 [t=95]（初回のみ） → 直近 = 95, 2回前 = -∞（無限の過去）
LRU-2: 2回前で比較 → A=90, B=-∞。B が最も古いので B を追い出す（正しい）。
単純 LRU: 直近で比較 → A=92, B=95。A の方が古いので常連の A を追い出す（誤り）。

CLOCK／Second-Chance――近似 LRU を安く

LRU を厳密に保つには、ヒットのたびにリスト先頭への付け替え（連結リスト操作とロック）が要り、高並行下では競合点になります。これを避けるのが CLOCK（Second-Chance）です。フレームを円環状に並べ、各フレームに1ビットの参照ビット（reference bit）を持たせます。

• ページにアクセス（ヒット）したら、そのフレームの参照ビットを 1 にするだけ。リスト操作は不要。
• 犠牲を選ぶときは「時計の針」を回し、指したフレームの参照ビットを見る。
  • 1 なら「もう一度チャンス」を与えて 0 にクリアし、針を次へ進める。
  • 0 なら、それを犠牲に選ぶ（pin されていればスキップ）。

参照ビットが1で一周回ってきたページは、その間に再アクセスが無かったということなので、次に回ってきたときは0で追い出される。こうして厳密な使用順リストを持たずに「最近使われたか否か」だけで近似 LRU を実現します。コストはビット操作と針の前進のみで、ロック競合が小さいのが利点です。

ダーティページのフラッシュ戦略

変更されたページ（ダーティページ）をいつディスクへ書き戻すか――ここがバッファ管理とリカバリの接点です。素直に「コミット時に全部書き戻す（Force）」「未コミットページは決して追い出さない（No-Steal）」とすれば話は単純ですが、性能が出ません。実用 DBMS はほぼ No-Force / Steal を採ります。

• No-Force: コミット時にデータページの書き戻しを強制しない。コミットで永続化するのはシーケンシャルなログ（WAL（先行書き込みログ）の仕組み）だけで済み、ランダムなページ書き戻しを後回しにできる。代償として、コミット済み変更がディスク未着地のままクラッシュし得るので、復旧時に redo が要る。
• Steal: バッファが逼迫したら、未コミットのダーティページでも追い出してよい。これでメモリ制約下でも大トランザクションを回せる。代償として、追い出した未コミット変更がディスクに残ったままロールバックされ得るので、undo が要る。

この自由を安全にする土台が WAL 規律です。ダーティページを書き戻す前に、その変更を記述したログを先に永続化する（Write-Ahead 規則）。各ページの pageLSN とログの flushedLSN を比較し、flushedLSN がそのページの pageLSN 以上であることを確認してから書き戻します。

ダーティページ P を犠牲化・書き戻しする直前の判定:
  if flushedLSN < P.pageLSN:        # P を変えたログがまだ未永続
      WAL を P.pageLSN まで fsync   # 先にログを永続化
  ディスクへ P を書き戻す            # その後でデータページを書く

チェックポイントとバックグラウンド書き出し

No-Force だとダーティページがプール内に溜まり続け、復旧時に redo すべきログ範囲が無限に伸びます。これを区切るのがチェックポイントで、その時点のダーティページをまとめて書き戻し、「ここまで反映済み」という基準点をログに刻みます（WAL の記事参照）。ただしチェックポイントで一斉に書き戻すと I/O が突発的に跳ね、スループットが波打ちます。

そこで多くの実装は、専用のバックグラウンド書き出しプロセス（PostgreSQL の background writer、InnoDB の page cleaner 相当）が、ダーティページを平常時から少しずつ先回りで書き戻します。狙いは「犠牲に選んだフレームが dirty で、その場で書き戻し I/O が要る」状況を減らすこと。犠牲化の同期パスからフラッシュ I/O を外し、ミス処理を読み込みだけに近づけるわけです。書き戻しを時間的に分散（spread checkpoint）し、I/O のピークをならす設計も併用されます。

まとめ

バッファプールは「ホットなページをメモリに留め、ディスク I/O を最小化する」という一点を、ページテーブル・pin/unpin・dirty 管理という地味な仕組みで支えています。置換アルゴリズムは、単純 LRU の「直近性しか見ない」弱点を、LRU-K が頻度で、CLOCK が参照ビットの近似で克服してきました。そしてダーティページのフラッシュは、WAL 規律のもとで No-Force/Steal を安全に成立させ、チェックポイントとバックグラウンド書き出しで I/O をならします。

ページがそもそもなぜ固定サイズで、索引がどう載るかは B+Tree インデックスの内部構造 を、書き込み集中型で別のキャッシュ哲学を採る構造は LSM-Tree の仕組み を、そしてどのページをどれだけ読むかを決める計画づくりは クエリオプティマイザの内部 を参照してください。