データベース内のデータはページ単位でHDD内に配置され、ページ単位でメモリにバッファ及びキャッシュとして複製される。
HDD内のデータにアクセスする際は一旦メモリにページごと複製してからアクセスするわけだが、メモリ内におけるページの量は一般にHDDに置けるページ量より小さい（そうでない前提での話題はまた後日）。
LRU
どのページをメモリに写し、どのページをHDDに置くかというのは、基本的にディスクアクセスの量を最小化する方向に最適化をする。
その際にはLeast Recently Used(LRU)という方法でキャッシュを管理する事が常套手段である。
それは「一番最近からみて使われた頻度が一番少ないページを解放して、そのメモリ領域を新たなディスクページの為に使いまわす」という戦略である。
具体的な実装方法としては双方向線形リストを使う。
- 新たにページをメモリに複製した際、双方向線形リストの左端にそのページ情報を保存する
- ページを参照する際に、双方向線形リストの中にそのページがあれば、リストの左端にそのページ情報を移動する
- 新たにメモリ領域を空けたい場合はリストの右端のページを開放する
まさに整理術のようである。そして任意のページにアクセスしたい場合に即座に索引できるようにハッシュテーブルを別で用意する。
さて、このLRUにはいくつか問題がある。
- 双方向線形リストを複数のスレッドから触ると壊れるのでシングルスレッド化せざるを得ない
- データベース全体を舐める操作をすると、LRUの中身がDBの後半のページだけで埋まってしまい他のトランザクションが大いに遅くなる事がある
そのためいくつか改良がある…とまで書こうとしたが Wikipediaにそれなりにまとまっているのでそれを参照して欲しい。
昔のPostgreSQLではLRUを使っていたようだが、最新の実装ではClock-Sweepというアルゴリズムを使っているようだ。
具体的にはクロックという固定長配列を使う。
- 新たにページをメモリに複製した際、クロックの中からその要素をポインタで指し、カウンタを1にする。
- ページを参照する際に、クロックの中のポインタがそのページを指していればそのクロックのカウンタを増やす。
- 新たにメモリ領域を空けたい場合はクロックの数字を1ずつ減らしながら配列をぐるぐる回っていき、最初に0になった場所を新たにそのページ用のクロックとする
このアルゴリズムはLRUの近似でありながら、配列内の数値の増減とポインタの繋ぎ変えでできているのでLRUよりはマルチスレッド用への対応が楽である。
そして「最近使っていなくても良く使っていたページ」のカウント値が高止まりするので、データベース全体を舐めたぐらいで中身が全部吹き飛ぶような事にはなりにくい。
LRUなりClockなりのアルゴリズムでページのメモリへの存在を管理するが、トランザクションの文脈ではこれはもう少し面倒な話になる。ここ以降では話を簡単にするために、キャッシュ管理アルゴリズムにLRUを前提とするが他のアルゴリズムでも大した違いは無いと思う。
WAL
バッファがLRUで管理されるなら、LRUが「開放しろ」と判断したメモリ領域は常にディスクに書き戻した後に開放して良いかというと、ダメである。
LRUが判断して書き戻したデータは、まだコミットされていないトランザクションの更新を含んでいる可能性があるからだ。そんな更新をうっかり書き戻してしまうとどうなるか、トランザクションが走っている状態でそのトランザクションが更新した一部のページを永続化し、電源を落として再起動すると、未コミットのトランザクションが永続化された状態が観測されてしまう。復旧しようにも古いデータは既に書き換えられているのでログから復旧せざるを得ないが、そのためのUndo情報を含んだログはまだ永俗化されていない、そのため過去のログを先頭から実行するぐらいしないと復旧できない。そのまま走らせたら、完了していないトランザクションの途中経過が他のスレッドから見えているのでAtomicityとIsolationに違反してしまう事になる。
それを解決するのがWrite Ahead Loggingである。それはLRUと組み合わせて使い「ログが永続化されるまでページを永続化してはならない」というルールを組み合わせる。
実装レベルではセマフォを使い、トランザクションがページの値を読み書きする際には必ずセマフォを獲得してから行う事にする。これは単純に複数のトランザクションが同時に読み書きする際にデータ構造レベルでの衝突を防ぐが、2PLで使うロックと違いアクセスが終わったら即座にセマフォを手放す事でデッドロックを避ける。そしてページを永続化する際はそのページを最後に更新したログが先に永続化されたことを確認してから永続化する。
たまにWALの事をジャーナリングや単にlogの事と混同して話す人が居るが、僕の理解では「どの瞬間でもページとログの情報を合わせれば更新前と後の情報が両方ディスク上に載っている」という状態を続けるためのプロトコルがWALである。「LogのWriteがページのWriteよりAheadとなるようにページのWriteを遅らせるプロトコル」であって「ページをWriteする前にログをWriteする事全般」という表現は重要なエッセンスを欠いている。なのでDBの教科書ではよくWALの対義語としてシャドーページが使われる。こちらはあんまりおもしろくないし現代ではあまり実用例も無いので書かない。NVMの時代になったら注目されるかも知れないが。