なぜPostgreSQLは「LRU」を使わないのか？ ― Clock-Sweepアルゴリズムの深淵
エンジニアの皆さん、お疲れ様です。
データベースのチューニングをしていると、必ずぶち当たる壁がありますよね。「なぜこのクエリは、メモリに乗っているはずなのにディスクI/Oが発生しているんだ？」という疑問です。
PostgreSQLのパフォーマンスを語る上で欠かせないのが「共有バッファ（Shared Buffers）」の仕組みですが、その中でも「バッファ置換アルゴリズム」は、まさにデータベースの心臓部。今回は、PostgreSQLがなぜ一般的なLRU（Least Recently Used）ではなく、「Clock-Sweep」という一見風変わりなアルゴリズムを採用しているのか、その裏側にある「大人の事情」と仕組みを紐解いていきましょう。
—
LRUの限界と「Clock-Sweep」という選択
教科書的には、メモリが溢れたら「一番最近使われていないもの（LRU）」を追い出すのが正解だと思われています。でも、PostgreSQLの設計者は、LRUに潜む大きな弱点に気づいていました。
それは、「スキャン耐性の低さ」です。
例えば、数テラバイトあるテーブルを全件スキャンするバッチ処理が走ったとします。LRUだと、その巨大なスキャンデータがバッファを埋め尽くし、これまで大切に保持していた「頻繁にアクセスされるインデックス」や「ホットなデータ」をすべて追い出してしまうんです。いわゆる「キャッシュ汚染（Cache Pollution）」ですね。
これを防ぐためにPostgreSQLが選んだのが、Clock-Sweepです。
Clock-Sweepの仕組みを「時計」でイメージする
Clock-Sweepは、バッファプール全体を時計の文字盤に見立てます。
1. 各バッファページには「使用ビット（Usage Count）」というカウンターがついています。
2. ページにアクセスがあるたびに、このカウンターがインクリメントされます（最大値あり）。
3. バッファが不足すると、時計の針がぐるぐる回り始めます。
4. 針が指したページのカウンターを確認し、「0なら追い出す」「1以上ならカウンターを減らしてスルーする」という動きをします。
つまり、「最近頻繁に使われたページは、一度の針の通過では追い出されない」というガードがかかるわけです。これで、全件スキャンにバッファを食い尽くされるリスクを劇的に減らしています。
—
現場で意識すべきこと：`shared_buffers`と実務の距離感
「じゃあ、このアルゴリズムをハックしてチューニングできるのか？」というと、実はClock-Sweepのパラメータを直接いじることはできません。PostgreSQLは驚くほど「自律的」に動くように設計されています。
実務で皆さんができることは、「Clock-Sweepが健全に働ける環境を作ってあげること」です。
- `shared_buffers` の適切な設定
- よくあるミスは「とりあえずOSのメモリの半分を割り当てる」というもの。PostgreSQLのバッファは、OSのファイルシステムキャッシュと「二重管理」の状態になります。Clock-Sweepを正しく機能させるには、OSのキャッシュ分も考慮し、過剰に割り当てすぎないのがコツです。
- `pg_buffercache` 拡張の活用
- 実際にどのページがバッファに常駐しているか、確認したことはありますか？以下のクエリで「どのテーブルがどれだけバッファを占有しているか」を可視化できます。
— 現在の共有バッファの使用状況を確認するクエリ
SELECT
c.relname,
count() AS buffers
FROM pg_buffercache b
INNER JOIN pg_class c ON b.relfilenode = pg_relation_filenode(c.oid)
AND b.reldatabase IN (0, (SELECT oid FROM pg_database WHERE datname = current_database()))
GROUP BY c.relname
ORDER BY 2 DESC
LIMIT 10;
—
先輩エンジニアからのアドバイス
Clock-Sweepの挙動を理解しておくと、トラブルシューティングの質が変わります。
例えば、特定のクエリがやたらと遅いとき。ディスクI/Oのレイテンシを疑う前に、「Clock-Sweepが激しく回転しすぎていないか」を想像してみてください。もし特定の巨大なテーブルがバッファを占有しているなら、それはクエリの書き方を変えるか、インデックスを見直すサインかもしれません。
データベースのアルゴリズムは、魔法ではありません。あくまで「限られたリソースの中で、いかに効率よくデータをやり取りするか」というパズルです。
PostgreSQLは、今日もせっせと時計の針を回して、あなたのクエリを高速化しようと頑張っています。たまには `pg_stat_bgwriter` などを見て、その頑張りを労ってあげてくださいね。
また次回のテックブログでお会いしましょう。質問があればいつでもどうぞ！
コメント