バッファマネージャ - Chapter 4 Memory Management
データベースエンジンはユーザーデータをメモリ上にキャッシュし、ディスク I/O を最小限に抑えます。単にファイルの末尾にデータが追加されるだけのログレコードは異なり、ユーザーデータはいかにアクセス頻度の高いデータを効率よくキャッシュするかがパフォーマンスの鍵となります。
バッファ
ディスクから読み込まれたユーザーデータを含むページは、メモリ上の バッファ (Buffer) というオブジェクトに格納されます。バッファはページの変更を監視し、変更されたページをディスクに書き戻す責務を負います。
バッファは後述のアルゴリズムに基づき、できるだけページの書き出しを遅らせています。また、クライアントはバッファに存在するページにアクセスすることで、ディスク I/O なしに変更後のデータを参照することができます。
バッファの集合を バッファプール(Buffer pool) と呼びます。バッファプールは物理メモリに収まる容量の固定数のページの集合といえます。
バッファマネージャ
バッファマネージャ (Buffer manager) はバッファプールにあるページの追加や削除を管理します。
バッファプール内のページは ピン留めされている (pinned) か ピン留めが解除されている (unpinned) 状態を取ります。
クライアントがバッファマネージャに対し、あるページを利用するリクエストを行うと、そのページは pinned となり、バッファプール内に保持されます。ページ処理が完了すると、クライアントは unpinned をバッファマネージャに指示します。
バッファマネージャのアルゴリズム
バッファプールは有限であり、バッファマネージャは unpinned のページのうち、置換するページを選択する必要があります。このとき、最も長い間アクセスされていないページを選択することで、バッファプール内のページの平均アクセス時間を最小化することができます。
どの unpinned のページを置換するかは、バッファマネージャのアルゴリズムによって決定されます。
次の図のように、バッファプールに 4 つのバッファが存在する状況を考えてみます。それぞれのページについて、バッファに読み込まれた順序を読み込み時間、unpin された順序を unpinned 時間として記録しています。
ナイーブ戦略 (The Naïve Strategy)
最も単純なアルゴリズムで、バッファプールを 0 から順番にスキャンし、最初に見つかった unpinned のページを置換します。
実装は簡単ですが、通常バッファプール内のページの利用は均等ではないので、後述のアルゴリズムに比べ効率は悪いです。
図の状態に対し pin(60) を要求すると、unpinned 状態の バッファ 0 が置換されます。
pin(60); unpin(60); pin(70); unpin(70); pin(60); unpin(60); … と、ブロック 60 と 70 が交互にピン留めされる状況を考えると、どちらもバッファ 0 を置換するため、毎回ディスク I/O が発生します。
FIFO 戦略 (First In First Out)
バッファプールに追加された時刻に基づいて置換を判断するアルゴリズムで、バッファプール内に最も長く存在している unpinned のページを置換します。
古いページは最近読み込まれたページよりも再度使用される可能性が低いため、ナイーブ戦略よりも通常は良い結果をもたらしますが、常に最良の選択ができるわけではありません。データベースにはカタログページなど、しばしば頻繁に使用されるページが存在するため、古いページを一律に置換してしまうと、それらを再度読み込む必要がでてくるためです。
図の状態に対し pin(60) を要求すると、最も読み込み時間が小さい (= 最も古い) バッファ 0 が置換されます。次に pin(70) を要求すると、バッファ 2 が置換されます。
LRU 戦略 （Least Recently Used Strategy）
ページが最後にアクセスされた時刻 に基づいて判断するアルゴリズムです。unpinned 時間が早いページを置換します。
「最近使用されていないページは、今後もしばらく使用されない可能性が高い」という仮定に基づいており、一般的に使われているアルゴリズムです。
図の状態に対し、pin(60) を要求すると、unpinned 時間が最も小さい (= 最後にアクセスされた時間が古い) バッファ 3 が置換されます。次に pin(70) を要求すると、バッファ 0 が置換されます。
クロック戦略 (The Clock Strategy)
ナイーブ戦略と同じで、バッファプール全体をスキャンし、最初に見つけた unpinned のページを置換するアルゴリズムです。違いは、スキャンの開始位置です。アルゴリズムは、前回置換を行ったページの次のページからスキャンを開始します。
クロック戦略はバッファをできるだけ均等に使用しようとします。pinned の頻度が高いページはスキップされる確率が高いため、LRU 戦略と似た結果をもたらします。
図の状態に対し、pin(60) を要求すると、最後に置換が行われたバッファ 1 の次からスキャンを開始します。したがってバッファ 2 が置換されます。次に pin(70) を要求すると、バッファ 3 が置換されます。
実際に使われているアルゴリズム
MySQL では LRU アルゴリズムを改良したものが採用されています。新しく読み込まれたページは LRU リストの 中心より少し後ろ (厳密にはパラメータで設定される) の位置に挿入されます。よく使われるページはアクセス時に先頭へ、そうでないページはリストの末尾へ移動するようになっており、より使用率の高いページが残るよう設計されています。
一方、PostgreSQL では Clock Sweep というクロック戦略に近いものが採用されています。各バッファには usage count というカウンタがあり、ページがアクセスされるたびにインクリメントされます。クロックのポインタは、usage count が 0 なら置換、そうでないならデクリメントして次のバッファへ移動します。これにより、LRU アルゴリズムと同じように、よく使われるページが長く残るようになっています。