【入門編】バッファ置換アルゴリズム（Clock-Sweep） – PostgreSQL

こんにちは！データベースの世界へようこそ。

普段、私たちが何気なく「検索」したり「保存」したりしているデータ。その裏側で、データベースがどんなふうに汗をかいて働いているのか、想像したことはありますか？

今日は、PostgreSQLという優秀なデータベースが、限られた「メモリ（共有バッファ）」というスペースをどうやりくりしているのか、その秘密のテクニックについてお話しします。

専門用語でいうと「バッファ置換アルゴリズム」なんて堅苦しい名前がついているんですが、考え方はすごくシンプル。例え話で覗いてみましょう。

—

想像してみてください。あなたは、ものすごく人気のあるカフェの店長さんです。でも、お店にはテーブルが数席しかありません。

お客さんが来るたびに料理を出したいけれど、席が全部埋まっていたらどうしますか？誰かに帰ってもらって、新しいお客さんに座ってもらわないといけませんよね。

「さて、誰に帰ってもらおうかな？」

ここで登場するのが、PostgreSQLの「Clock-Sweep（クロック・スイープ）」という考え方です。

PostgreSQLは、席（バッファ）を円形に並べて管理しています。そこに「時計の針」のようなポインターを置いて、クルクルと回しながら様子を見ているんです。

針が席を通り過ぎるとき、そこに座っているお客さんにこう尋ねます。
「すみません、まだこの席、必要ですか？」

もし、そのお客さんが最近使ったばかりの資料を広げていたら、PostgreSQLは「あ、この人はまだ作業中なんだな」と判断して、その席をそっとしておきます。

逆に、さっきからずっとスマホを眺めているだけで、特に何も作業していない人がいたらどうでしょう？
「お待たせしている他のお客様のために、席を空けてもらえますか？」とお願いして、その席を空けます。

この「ぐるっと回って、使っていない人を探して退席してもらう」という一連の動作が、Clock-Sweepの正体なんです。

—

よくあるアルゴリズムに「一番長い時間座っている人を追い出す（LRU）」というものがあります。でも、データベースの世界では、これが必ずしもベストとは限りません。

なぜなら、「一番長く座っている人＝重要じゃない人」とは限らないからです。

例えば、朝一番に読んだ「分厚い辞書」は、時間が経ってもまたすぐに見るかもしれませんよね。Clock-Sweepは、「単に古くからいるか」だけでなく、「最近使った形跡があるか」という情報をポチッとフラグ（目印）として残しておくことで、より賢く、より素早く判断を下せるようになっているんです。

この「シンプルだけど、無駄がない」という絶妙なバランスこそが、PostgreSQLが長年愛されている理由の一つなんですよ。

—

今日のお話をまとめると、こんな感じです。

データベースの内部動作を知ることは、まるで高性能なエンジンの仕組みを学ぶような面白さがあります。次にPostgreSQLを触るときは、「あ、今あいつが時計の針を回して席を探してるのかもな」なんて想像してみてください。

きっと、今まで以上にデータベースのことが愛おしくなるはずですよ！

それでは、また次回の記事でお会いしましょう。質問があったら、ぜひコメントで教えてくださいね！