この記事は「 けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar 」 10日目の記事です。
はじめに
どうも、最近 B Tree Index を実装しても、重複ありで範囲検索するのめっちゃ難しくない？って思い始めたけんつです。
インデックスにとりつかれている気がする。
今日は、 Buffer Pools を実装しているなかでどうやって設計すると良いのか迷ったので PostgreSQL の Buffer Pool の仕組みを追うことでもうちょい理解を深めていこうかなと思っています。
使えそうな部分を重点的に列挙していくので短くなりそうです。
Buffer Pool
参考資料↓
http://www.interdb.jp/pg/pgsql08.html
(ぽすぐれって内部仕様の詳細ドキュメントが充実してていいよね)
そもそも Buffer Pool ってなんぞというところから始めると、Buffer Pool はストレージエンジンが担保していることが多いが
ストレージ的な機能を提供するのではなく物理的なストレージのデータをメモリ上に展開したり、データが追加された際に一時的に保持するためのメモリ領域のことを指す。
言わばファイルキャッシュのようなもので、更に平たくいうなら単にキャッシュと思ってもらっても差し支えないと思う。
実際以下のような構図になっている。
ここでいうところの Backend Process とはマルチスレッドでそれぞれ動作する SQL の解析や実行計画の決定、最適化よりユーザ側の面の全てを指す。
それでは順を追ってみていく。
Buffer Pool Manager の構成
バッファプールを管理するバッファプールマネージャーはバッファテーブル、バッファディスクリプタ、バッファプールから構成されている。
このあたりの詳しい解説はこのあとまとめる。
ここでまず大事なのはバッファプールは配列であり、各スロットに 1 page が配置されるようになっているということである。そして、その配列のインデックスを buffer_id と呼ぶこと。
これが、バッファプールマネージャを通したバッファプールの扱いに関連している。
バックエンドプロセスによるバッファプールの操作
バッファプールのデータを扱う場合に、以下のプロセスを踏む。
- テーブルやインデックスを読み込む場合、バックエンドプロセスはページの buffer_tag をバッファプールマネージャに渡す。
- バッファプールマネージャは既にページがバッファプールに存在する場合はそのインデックス*1を返す。バッファプールに存在しない場合はストレージから読みだしてバッファプールに対象のページを格納した上でそのインデックスを返す。
- バックエンドプロセスは buffer_id を利用して、バッファプールにアクセスする。
データの読み込みではなく、書き込みが走った場合はそのページをダーティページ*2として認識する必要がある。
また、読み込む際に空きスロットがない場合は LRU ではなくクロックスイープを使用してスロットを開放する。
バッファプールマネージャの構造
バッファプールマネージャは以下の構造をとる。
ポイントは以下の通り。
- Buffer Pool は配列であり、各スロットにページデータを持つ。また Buffer Pool のインデックスを buffer_id という。
- Buffer Descriptor は配列であり、 Buffer Pool の buffer_id と同一の*3 buffer_id で参照できる。この Descriptor はページのメタデータを保持する。
- Buffer Table は格納された buffer_tag と、 Buffer Descriptor の buffer_id とを対応付けるハッシュテーブルとなっている
Buffer Table
バッファテーブルはハッシュ関数、ハッシュスロット、データエントリの３要素で構成されている。
ここでは、まずハッシュ関数を使って buffer_tag をハッシュスロットにマッピングする。またハッシュを使用するということは当然ハッシュが衝突する可能性があるがバッファテーブルはそのような状態を単方向リストを使用したチェーン方式で解決する。
具体的に何をするかというと、以下の図がわかりやすい。
このように、同じハッシュスロットを用いる場合、それらを単方向リストとして表現する。
データエントリはページのバッファタグと、メタデータを持つ buffer_id の２つから構成されている。
Buffer Descriptor
バッファディスクリプタはページのメタデータを保持している。PostgreSQL では次のフィールドから構成される。
- tag: Buffer Tag を持つ
- buffer_id: 前述の通り
- refcount: ディスクリプタが示すページに現在アクセスしているプロセスの数を示す。 Pin Count とも言われる。この数値が 0 よりも大きければページは固定*4され、そうでないならページの固定は解除される。*5
- usage_count: これはアクセスされた回数。この回数をクロックスイープで使用する。
- context_lock, io_in_progress_lock: おそらく排他制御、軽量ロックと書かれているのでラッチに近い機能をもっていると考えられる。*6
- dirty bit :ページがダーティページかどうかを示す
- valid bit :保存されたページが読み取り、書き込みが可能かどうかを示す。
- io_in_progress bit : 関連するページをストレージから読み書きするかどうかを示す。
基本的にロックやラッチに関わる値を保持している。
番外編 MySQL の Buffer Pools
ここにもあるし、前にもどこかでまとめた記憶があるが LRU キャッシュとなっている。
バッファプールを 5/8, 3/5 に分割してそれぞれをサブリストとすることで二度目以降の使用がないデータを優先的に開放するようになっている。
ただこれ以上詳細な情報がなかったので、どういったフィールドを保持していてどのようにロックやラッチを使っているかというところまではわからない。
まとめ
参考文献を使った章以降は、基本的にそのバッファプールマネージャの構造においてどのようにページを開放するかなどなので説明を省略した。