CMU Database Systems をひたすら追っていく ~05 Buffer Pools~
この記事は「 けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar 」 4日目の記事です。
はじめに
どうも、最近「これ１人アドカレめちゃくちゃキツイな」とにわかに思い始めたけんつです。
最近は Netflix オリジナルコンテンツの映画にはまっています。
今回は前回紹介したページなどを一時的に保存するために使う Buffer Pools についてです。
Buffer Pools
Buffer Pools Organization
バッファプールはメモリ上に固定長のページを要素に持つ配列として構築される。この配列の各エントリーをフレームと呼ぶ。
DBMS がページをリクエストする際にディスク上のページをこれらフレームにコピーする。
Buffer Pools Meta Data
ページテーブルという現在メモリに格納されている*1ページを追跡するための領域が存在する。
これらのようにページ毎に追加のメタデータを保持する。メタデータの中にはダーティフラッグ*2*3や Pin Counter *4が存在する。
Lock vs Latches
Page Table vs Page Directory
ページディレクトリとは前にもやったように、ページをまとめて特定のディレクトリに格納しておきページIDとその場所をマッピングするというもの。ただし、DBMS が再起動した時のために全ての変更を終了前にディスクに書き込む必要がある。
対してページテーブルという代物は先にも説明したように、バッファープールフレームにコピーしたページのIDをマッピングする。
これはページテーブルとは異なり、メモリ上に保存されるためディスクに保存する必要はない。
ここまでのメモ
バッファプールにはデータの原本、またはコピーが存在する。
SELECT 等を行った時はバッファプールを検索する。仮に対象のページが無い場合はバッファプールを LRU に沿うかたちで開放してページをバッファプールに確保してから検索する。
UPDATE,INSERT,DELETE のときはバッファプールに書き込んで、ログファイルに書き込むそのあとにゴニョゴニョする*5
Buffer Pools Optimization
Multiple Buffer Pools
DBMS は様々な目的のために複数の種類のバッファプールを持つ場合がある。これにより、ラッチが競合するイベントが減り局所性が向上する。
いくつかの実例は以下に挙げる。
- Multiple Buffer pool instances
- Per-database buffer pool
- Per-page type buffer pool
Pre-Fetching
クエリプランに基づいてページを事前に取得することで最適化することが出来る。ページに対して連続アクセスするときによく使用される。
Scan Sharing
同一のページを複数のスレッドが同時に読み込む場合にそれらのカーソルを他のカーソルにアタッチして同一の結果を用いるというもの。
Replacement Policies
この章は、バッファプールに確保したデータを必要に応じてどうやって置き換えて行くかという話になる。
基本的には LRU*6 が前提となる感じがある。
CLOCK
その名の通り、時計と似たような動きをするやつ。
ページごとのタイムスタンプを必要としないアルゴリズム。循環バッファを構築する必要がある。
- 各ページにアクセス時にフラグを立てる参照ビットが存在する
この性質を使う。
「時計の針」と言われる基準を利用する。この「時計の針」がどのように影響するかというと
- ページビットが１に設定されているかどうかをスイープチェック時に確かめる
- 1 なら 0 に設定して、 0 ならそのページを開放する。
これによりバッファプールを置き換えるという。
その他のアルゴリズム
- LRU-K
- LOCALIZATION
- PRIORITY HINTS
おわりに
ひとまず Buffer Pool についてはまとめきったと思いたい。ところどころ怪しいところがあるけど。
書いてて唯一疑問に思ったこと、といえばバッファプールがデータ原本であり、INSERT,UPDATE,DELETE 時にバッファプールが更新され、そのあと色々あってファイルに吐き出されるなら
ACID 特性の永続性ってどうやって担保しているんだろうか？という疑問が残っている。これを担保するにはそれらの処理が終わった段階でファイルに書き込まないといけないのでは？と思っている。
今後その解説が出てくるだろうか。
