それが僕には楽しかったんです。

ミドルウェアとかやってます

CMU Database Systems をひたすら追っていく ~05 Buffer Pools~

この記事は「 けんつの1人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar 」 4日目の記事です。

はじめに

どうも、最近「これ1人アドカレめちゃくちゃキツイな」とにわかに思い始めたけんつです。
最近は Netflix オリジナルコンテンツの映画にはまっています。

今回は前回紹介したページなどを一時的に保存するために使う Buffer Pools についてです。

Buffer Pools

Buffer Pools Organization

バッファプールはメモリ上に固定長のページを要素に持つ配列として構築される。この配列の各エントリーをフレームと呼ぶ。
DBMS がページをリクエストする際にディスク上のページをこれらフレームにコピーする。

Buffer Pools Meta Data

ページテーブルという現在メモリに格納されている*1ページを追跡するための領域が存在する。
これらのようにページ毎に追加のメタデータを保持する。メタデータの中にはダーティフラッグ*2*3や Pin Counter *4が存在する。

Lock vs Latches

Lock

ロックはよく聞くやつ。他のトランザクションから現在走らせているトランザクションの処理を保護するもので、これはトランザクションが有効な期間は保持される。
しかし、変更をロールバックできるという特性を満たす必要がある。保護されるものとしてはタプルやテーブル、インデックスが挙げられる。

Latches

ラッチと言われる代物。DBMS 内部のデータ構造の重要なセクションを他のスレッドから保護する役目がある。これもロックと同様に、オペレーションが走っている間は保持される。
こっちはロックと異なり、ロールバック出来なくても良い。

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に設定されているかどうかをスイープチェック時に確かめる
  • 1 なら 0 に設定して、 0 ならそのページを開放する。

これによりバッファプールを置き換えるという。

その他のアルゴリズム
  • LRU-K
  • LOCALIZATION
  • PRIORITY HINTS

Allocation Policies

この章は、めちゃくちゃ短いけどどうやって Buffer Pool に割り当てるかということ。おそらくどのように割り当てても大体は問題ないという感じなのかなと思っている。*7

これには2つある。

  • グローバルポリシー:DBMSがすべてのアクティブなトランザクションに対して決定を行う方法。
  • ローカルポリシー:同時送信の動作を考慮せずに、特定の送信にフレームを割り当てる。

おわりに

ひとまず Buffer Pool についてはまとめきったと思いたい。ところどころ怪しいところがあるけど。
書いてて唯一疑問に思ったこと、といえばバッファプールがデータ原本であり、INSERT,UPDATE,DELETE 時にバッファプールが更新され、そのあと色々あってファイルに吐き出されるなら
ACID 特性の永続性ってどうやって担保しているんだろうか?という疑問が残っている。これを担保するにはそれらの処理が終わった段階でファイルに書き込まないといけないのでは?と思っている。

今後その解説が出てくるだろうか。

*1:つまりバッファプールに格納されている

*2:スレッドがページを変更するときに設定される

*3:バッファプールには存在するがテーブルスペースが存在しないものをダーティページという

*4:そのページを操作するスレッドの数

*5:ここがわからない

*6:最後のアクセスが最も古いものから削除する

*7:実際 InnoDB における Buffer Pool Size で適切な数値というのはデータベースそのものと同等となっている。つまりデータベースにある全てのデータがメモリに乗るような Buffer Pool が存在すればどのようにデータを割り当てても問題はそこまでないということ?