ディスクI/Oを減らすキャッシュ

バッファプール（Buffer Pool）は、InnoDBがディスク上のデータページとインデックスページをメモリ上にキャッシュしておく領域です。ここで注意したいのは、バッファプールは検索でたどるページ数そのものを減らす仕組みではない、という点です。B-treeを何ページたどるかは変わりません。変わるのは、そのページをディスクから読むのか、すでにメモリにあるものを使うのか、という部分です。よくアクセスされるページがメモリに載っていれば、遅いディスクI/Oを避けられ、処理が速くなります。

バッファプールは16KBのページ単位で、ディスク上のInnoDBページをキャッシュします。載るのはB-treeのデータページやインデックスページだけでなく、undoログやチェンジバッファなど、InnoDBが扱う各種ページです。ディスク上の1ページとバッファプール上の1フレームは1対1に対応し、ページサイズが16KBである限り、ページを格納するメモリ領域も16KBです。

制御ブロックとバッファフレーム

バッファプール内の各ページは、制御ブロック（control block）とバッファフレーム（buffer frame）の2つで管理されます。バッファフレームは、ページデータそのものを置く16KBのメモリ領域です。制御ブロックには、ページの状態、このページを参照中のスレッド数（バッファフィックス数）、I/Oの状態、各種リストへのリンクといった、ファイルには書かない管理用の情報が入ります。

データ本体と管理情報を分けておくことで、ページの中身に触れずに状態やリンクだけを操作できます。

ページを管理するリストとハッシュ

バッファプールは、制御ブロックを複数のリストと、検索用のハッシュテーブルで管理します。それぞれ役割が違い、ページの配置・追い出し・書き出しに使われます。

ページを読むときの流れはこうです。まずページハッシュで、そのページがすでにバッファプールにあるか調べます。なければ空きリストからブロックを取り、空きがなければLRUリストの末尾から追い出し候補を探して置き換えます。読み込んだページはLRUリストに載ります。ページを更新すると、そのブロックはフラッシュリストにも登録され、適切なタイミングでディスクへ書き出されます。

LRUを2つに分ける理由

LRUリストは、素朴なLRU（Least Recently Used、最近最も使われていないものから捨てる）ではなく、2つのサブリストに分けた変形LRUで管理されます。なぜひと工夫が必要なのでしょうか。

素朴なLRUでは、新しく読んだページは必ずリストの先頭に入ります。ここで大きなテーブルの全件スキャンや事前読み込み（read-ahead。次に必要になりそうな連続ページを先読みする処理）が走ると、スキャン対象のページが一気に先頭へなだれ込み、それまで頻繁に使っていたホットなページを末尾へ押し出してしまいます。多くは1回しか読まないページなのに、大事なページを追い出してしまうわけです。

そこでLRUリストを、頻繁に使うページのnew（young）サブリストと、あまり使われていないページのoldサブリストに分けます。既定ではバッファプールの3/8がoldサブリストです。ディスクから新しく読んだページは、先頭ではなくmidpoint（newとoldの境界）に挿入されます。こうすると、1回しか読まないスキャン由来のページはいきなりnew側へは入らず、old側でしばらく過ごしてから追い出されます。

oldサブリストのページが再びアクセスされ、かつ最初にアクセスされてから一定時間（既定1000ミリ秒）が経っていれば、そのページはnewサブリストの先頭へ移ります（young化）。すぐに再アクセスされないページは、他のページのyoung化に押されて徐々に末尾へ寄り、やがて追い出し対象になります。一時的なスキャンがホットデータを追い出しにくくなるのが、この2分割の狙いです。

追い出しとフラッシュ

バッファプールに空きがなく新しいページを読みたいとき、LRUリストの末尾付近から追い出せるブロックを探します。その候補がクリーン（未更新のまま）なら、そのまま捨てて構いません。しかしダーティ（メモリ上で更新済みでまだディスクへ書いていない）なら、そのまま捨てると更新内容が消えてしまいます。そこで、追い出す前にディスクへ書き出します。この書き出しをフラッシュと呼びます。フラッシュには、目的と契機の違うLRUフラッシュとリストフラッシュの2種類があります。

LRUフラッシュ

LRUフラッシュは、追い出し用の空きブロックを確保するためのフラッシュです。新しいページを読むには、使っていないブロックを1つ追い出す必要があります。その候補がクリーンならそのまま追い出せますが、ダーティなら追い出す前にフラッシュしなければなりません。

ただ、追い出しのたびに1件ずつフラッシュを待つと読み込みが遅れます。特にLRU末尾付近にダーティページが続くと、待ち時間が積み重なります。そこで、バックグラウンドのページクリーナースレッドが、追い出しに備えてLRU末尾のダーティページを前もってフラッシュしておきます。こうしておけば、いざ追い出しが必要になったとき、すでにクリーンになったブロックをすぐ使えます。いずれにせよLRUフラッシュは、LRUリストの末尾方向からダーティページを探し、追い出し用のブロックを確保するために行うフラッシュです。

リストフラッシュ

リストフラッシュは、redoログのチェックポイントを進めるためのフラッシュです。redoログはクラッシュリカバリ用に変更履歴を記録しますが、ファイルの合計サイズには上限があり、古い領域をリングバッファとして再利用（上書き）します。上書きしてよいのは「その変更はもうディスク上のデータページへ反映済み」と言える範囲だけです。この境界を表すのがチェックポイントLSNで、これを進めるには、そのLSN以前の変更をすべてディスクのデータファイルへ書き出しておく必要があります。書き出していないと、クラッシュ後に古いログが必要になったとき、対応するページがディスクにないことになってしまいます。

フラッシュリストは、各ページの「最も古い更新のLSN」順に並んでいます。つまり末尾ほど古い変更を持つページです。リストフラッシュでは、このフラッシュリストの末尾（最も古いダーティページ）から順にディスクへ書き出します。十分な数を書き出せればチェックポイントLSNを進められ、redoログの再利用できる範囲が広がります。リストフラッシュは、チェックポイントの進行に合わせてバックグラウンドで継続的に行われます。