【テクニカル・上級編】バッファ置換アルゴリズム（Clock-Sweep） – PostgreSQL

なぜ今さら「Clock-Sweep」を語るのか？

PostgreSQLのアーキテクチャを語る上で、Shared Bufferの管理は避けて通れない聖域だ。多くのエンジニアが「LRU（Least Recently Used）」という言葉には馴染みがあるだろう。しかし、Postgresのソースコードを覗いたことがある人なら知っているはずだ。PostgreSQLは純粋なLRUを採用していない。

彼らが選んだのは「Clock-Sweep（クロックスイープ）」アルゴリズムだ。

なぜ、教科書通りのLRUを使わないのか？結論から言えば、LRUは高負荷なマルチスレッド環境において「ボトルネックの塊」だからだ。今日は、この一見古風で、しかし極めて実戦的なアルゴリズムが、なぜPostgreSQLという巨大なシステムを支え続けているのか、その深層を紐解いていこう。

—

Clock-Sweepの心臓部：なぜLRUではいけないのか

LRUの弱点は、アクセスが発生するたびにリストの順序を更新しなければならない点にある。シングルスレッドならまだしも、数千のバックエンドプロセスが並行して動くPostgreSQLで、すべてのアクセスに対して共有リストのポインタを排他制御（ロック）していたらどうなるか？想像するだけで悪夢だ。コンテンション（競合）でCPUが張り付き、スループットは地に落ちるだろう。

そこで登場するのがClock-Sweepだ。

Clock-Sweepの仕組みを「時計」で例える

イメージしてほしい。Shared Buffer上の全ページを円形に並べ、ポインタ（Hand）が時計回りにぐるぐると回っている様子を。

1. Usage Count（利用回数）: 各ページには「Usage Count」というカウンターがある。
2. アクセス時: ページが参照されるたびに、このカウントがインクリメントされる（上限5など）。
3. 置換時: 空きバッファが必要なとき、Handは現在地から時計回りに進む。

カウントが0より大きければ、「まだ使われているな」と判断してカウントを1減らし、Handを次へ進める。
カウントが0なら、「ここだ、追い出そう」と判断し、そのページを置き換える。

この手法の最大の利点は、「グローバルなリストの更新が不要」であることだ。ページへのアクセスが発生したとき、そのバッファのフラグを立てるだけでいい。厳密な「一番古いもの」を探すコストを支払う代わりに、コスト効率の良い「そこそこ古いもの」を捨て去る。これがPostgres流のリアリズムだ。

—

パフォーマンストラブルの現場から：ここが「罠」になる

このアルゴリズムを理解していると、現場でのトラブルシューティングの景色が変わる。

1. 「Buffer Mapping Lock」の争奪戦

Clock-Sweep自体は効率的だが、バッファをスキャンする過程で、当然ながらロックが必要になる。もしバッファサイズ（`shared_buffers`）が物理メモリに対して不適切に小さかったり、極端に大きなテーブルフルスキャンが頻発すると、Handがバッファ全体を何度も高速で周回することになる。

結果として、バックエンドプロセスがバッファ確保のためにスピンロックを奪い合い、CPU使用率が跳ね上がる。「なぜかI/Oは少ないのにCPU負荷が高い」という時は、往々にしてこのClock-Sweepの空回りや、バッファ競合が原因だ。

2. 「Usage Count」の偏り

一時期、特定のインデックスやテーブルがメモリを占有し、Usage Countが最大値で固定されることがある。こうなるとClock-SweepのHandは、そのページをスキップするために何度もカウントを減らさなければならず、結果としてスキャン効率が落ちる。

Postgresのチューニングにおいて、単に`shared_buffers`を大きくすれば解決するとは限らない。アクセスパターンがClock-Sweepのロジックと乖離していないかを見極めるのが、真のエンジニアの仕事だ。

—

結論：洗練された「妥協」の美学

Clock-Sweepは、現代のメモリ容量からすれば少しレガシーなアプローチに見えるかもしれない。しかし、PostgreSQLは常に「並行性」を最優先事項に置いている。完璧な追い出しアルゴリズムよりも、ロックの競合を最小化し、システム全体のスループットを最大化する。この「妥協の最適化」こそが、PostgreSQLが四半世紀にわたって信頼され続けている理由だと私は思う。

もし君が今、システムのパフォーマンスチューニングに苦しんでいるなら、まずは`pg_buffercache`拡張を使って、今この瞬間、共有バッファの中で何が起きているか覗いてみてほしい。Clock-SweepのHandが、君のクエリのために必死に時計の針を回している姿が、きっと見えるはずだ。

データベースを扱うということは、その内部構造という「リズム」と対話することに他ならない。今日も存分に、その深淵を楽しんでほしい。