ディスク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ログの再利用できる範囲が広がります。リストフラッシュは、チェックポイントの進行に合わせてバックグラウンドで継続的に行われます。

セカンダリインデックス更新の読み込みを先送りする

チェンジバッファ（Change Buffer）は、主に非ユニークなセカンダリインデックスへのINSERT・UPDATE・DELETEを、対象ページがバッファプールにないときに一時的に溜めておく仕組みです。溜めた変更は、あとでそのページがバッファプールへ読み込まれたタイミングでまとめて適用（マージ）します。狙いは、セカンダリインデックスを更新するためだけのディスクからのランダム読み込みを先送りして減らすことです。

なぜセカンダリインデックスで問題になるのかを押さえておきます。クラスタ化インデックス（主キー）のページは、挿入も更新もキー順で近い位置に集まりやすく、バッファプールに載っていることが多いです。一方、セカンダリインデックスは非ユニークなことが多く、更新される順序もばらばらになりがちで、更新したいリーフページがバッファプールにないことが頻繁に起きます。そのたびにディスクからページを読むとランダムI/Oがかさみます。チェンジバッファは、そういうとき毎回ページを読む代わりに変更内容だけを別のB-treeに記録し、後でまとめて適用します。

redoログとの違い

InnoDBには、I/Oを減らす仕組みとしてredoログもあります。名前も役割も似て見えますが、減らすI/Oの向きが逆です。

redoログは、変更したページを実際にディスクへ書き出すタイミングを先送りします。変更内容をまずログに記録しておけば、対象のデータページ自体は後からバックグラウンドで書き出せるため、コミットのたびにページの書き出し完了を待つ必要がありません。つまり書き出し側のI/Oを整えます。

チェンジバッファは、ページをディスクから読み込むタイミングを先送りします。セカンダリインデックスを更新したいのに対象ページがメモリにないとき、そのページを読まずに変更だけを記録し、実際に読むのは必要になったときまで遅らせます。つまり読み込み側のランダムI/Oを減らします。redoログが「書き出し」、チェンジバッファが「読み込み」を受け持つ、と対で覚えると整理できます。

どこに保存されるか

チェンジバッファに溜まっているのは、まだ実際のインデックスページへ反映していない未適用の変更です。ということは、サーバーをshutdownしてもこの変更が失われてはいけません。マージは対象ページが読み込まれるときに行うため、shutdown時点ではマージ待ちの変更が残っている可能性があり、次回起動後に正しく適用できなければデータの整合性が壊れます。

そこで、チェンジバッファの実体はディスク上にも永続化されます。チェンジバッファ用のB-treeは、通常のInnoDBデータページと同じくシステムテーブルスペース内に置かれます。メモリ上ではバッファプールの一部を占め、ディスク上ではB-treeとして保持されます。永続化の仕組みも他のページと変わりません。InnoDBはWAL（Write-Ahead Logging）を採用しており、ページをディスクへ書く前に変更をredoログへ記録します。コミット時にはredoログをフラッシュすればよく、実際のデータページ（チェンジバッファのB-treeページを含む）は後からバックグラウンドで書き出されます。再起動時にはredoログのリカバリでチェンジバッファも復元され、該当ページが読まれるたびにマージされます。

このB-treeのキーは「テーブルスペースIDとページ番号」の組み合わせで、どのセカンダリインデックスのどのページに対する変更かを識別します。各エントリには、適用すべき変更（挿入レコード、削除マーク、物理削除）が入ります。

注文テーブルに、非ユニークなセカンダリインデックス（customer_id）があるとします。customer_id='user01'の注文id=102を入れるとき、そのキーが載るセカンダリリーフ（ページ42）がバッファプールになければ、ディスク上のページ42は読みません。ディスクのページ42にはすでに(user01,101)と(user01,103)があり、新しい(user01,102)はチェンジバッファにだけ残ります。あとでページ42がディスクからバッファプールへ読まれると、102がメモリ上のリーフへマージされ、チェンジバッファのそのエントリは消えます。ディスク上のページ42は、このマージだけでは書き換わらず、ダーティページがフラッシュされるタイミングでディスクに書き込まれます。

バッファできる操作

チェンジバッファが扱う操作は3種類です。

UPDATEは、セカンダリインデックスでは「旧キーの削除マーク」と「新キーの挿入」に分解され、上記の組み合わせになります。主な対象は非ユニークなセカンダリインデックスです。

いつマージされるか

対象ページがバッファプールへ読み込まれたとき

SELECTや範囲スキャンなどでそのセカンダリインデックスのページがディスクから読まれるとき、チェンジバッファのB-treeを引き、そのページ宛ての変更があればマージします。読むついでに反映するので、先送りしていた読み込みが1回で片付きます。

バックグラウンドのpurge

purgeは、削除マーク付きレコードのうちどのRead Viewからも不要になったものを物理削除するバックグラウンド処理です。セカンダリインデックスではUPDATEが削除マークと挿入で表されるため、purgeがセカンダリインデックスのページを読むとき、そのページ宛てのチェンジバッファのエントリがあればマージされます。また、システムがアイドルに近いときやslow shutdown時には、メインスレッドが積極的にマージを進め、チェンジバッファが肥大化しすぎるのを防ぎます。

サーバー再起動後のリカバリ

クラッシュリカバリのときも、該当ページが読み込まれる過程でマージされます。

マージは必ず成功しなければなりません。マージは対象ページを読み込む処理の一部としてその場で行われ、失敗しても後からやり直す手段がないからです。そこでチェンジバッファは、変更を溜める時点で各ページの空き領域をビットマップで追跡し、実際の空き容量を超えるような変更は溜めないようにしています。こうして、マージを実行する段階になって初めて「空きが足りない」と分かるような不整合が起きないようにしています。

バッファされない場合

ユニークなセカンダリインデックスへのINSERTは、原則としてバッファできません。一意性を確認するには結局その対象ページを読む必要があり、読むならわざわざ先送りする意味がないからです。unique_checks=0のときは例外的にバッファできる場合がありますが、重複を挿入してしまうリスクがあります。なお、ユニークセカンダリでもDELETE_MARKや物理DELETEはバッファ対象になり得ます。

また、チェンジバッファのマージ処理は昇順インデックス向けに設計されているため、降順インデックスが関わるものには使われません。降順インデックスとは、CREATE INDEX ... ON t (col DESC)のように列を降順でソートするインデックスです。セカンダリインデックス自体が降順インデックス列を含む場合と、主キーに降順インデックス列を含むテーブルのセカンダリインデックスの場合が該当し、いずれも降順が関与するためチェンジバッファは使われません。

サイズと有効化の設定

チェンジバッファが占める最大サイズは、バッファプールに対する割合で指定します。innodb_change_buffer_max_sizeの既定は25で、バッファプールの最大25パーセントまで使えます。最大値は50です。

どの操作をバッファするかはinnodb_change_bufferingで制御します。MySQL 8.4では既定がnone（バッファしない）で、8.0系では既定がall（INSERT・DELETE_MARK・DELETEのすべてをバッファする）でした。設定値はいつでも変更でき、変更は新しい操作のバッファ有無にだけ効きます。すでに溜まっている分のマージには影響しません。

適応的ハッシュインデックスとは

適応的ハッシュインデックス（Adaptive Hash Index）は、等価検索を速くするための仕組みです。通常のB-tree検索では、ルートから中間ノードを経てリーフまで複数ページをたどる必要があります。もし同じキーへの検索が何度も繰り返されるなら、毎回この経路をたどるのは無駄です。InnoDBは、B-treeの検索パターンを監視し、よくアクセスされるリーフページについて、キーからバッファプール上のレコードへ直接飛べる参照を自動で構築します。

user_id='user01'、name='Alice'を探すとき、ハッシュインデックスに載っていればルートと中間ノードを経ることなくリーフ上のレコードへ直接アクセスすることができます。

ハッシュインデックスの構築

ハッシュ値の生成

ハッシュ値はインデックスキーのプレフィックスから計算されます。プレフィックスはn_fields（列数）とn_bytes（バイト数）で定義されます。n_fieldsはプレフィックスに含める列の数で、先頭からn_fields列を使います。n_bytesは、その次の列の先頭何バイトを含めるかです。列の境界でちょうど終わるならn_bytesは0になります。

例えば(user_id, name)の複合セカンダリインデックスで、user_id='user01'、name='Alice'という行を考えます。n_fields=2、n_bytes=0なら、プレフィックスはuser_idとnameがすべて含まれる'user01' + 'Alice'です。一方n_fields=1、n_bytes=3なら、user_id列全体に加えて次のname列の先頭3バイトだけを使い、'user01' + 'Ali'がプレフィックスになります。

同じプレフィックスを持つレコードが複数あるときは、キー未満とキー以上の境界に接する1レコードだけをハッシュインデックスに登録します。

ハッシュインデックスに登録されるレコード

等価検索で一致するレコードが存在するケースを考えます。プレフィックスに対してレコードが一意に定まる場合（この例ではn_fields=2、n_bytes=0）、キー以上の最小値は探している行そのものなので、そのレコードへの参照が登録されます。

等価検索で一致するレコードが存在しないケースでは、探しているキー未満の最大値とキー以上の最小値のうち、探しているキーと同じプレフィックスを持つ方を登録します。以降の例はプレフィックスをuser_id列のみ（n_fields=1、n_bytes=0）とします。

検索しているuser01,Bobは存在しないレコードです。左のuser01,Aliceは同じuser_id、右のuser02,Bobは別のuser_idなので、プレフィックスが同じ左が登録されます。

検索しているuser02,Aliceは存在しないレコードですが、左のuser01,Aliceは別のuser_id、右のuser02,Bobは同じuser_idなので、右が登録されます。

インデックスは、今検証中のn_fieldsとn_bytesの組み合わせについて、仮にハッシュエントリがあった場合に有効だったかをメモリ上のカウンタで数えます。バッファプールの各ページも、同じ組み合わせでハッシュエントリが有効だった回数を独自に保持します。両方の数が閾値を超えると、そのページにハッシュエントリを作ります。今の組み合わせでは有効とみなせない検索になると、n_fieldsとn_bytesを選び直し、インデックス側のカウンタはリセットされます。

ハッシュエントリの削除

適応的ハッシュインデックスは肥大化し続けるわけではありません。参照先のB-treeリーフページがバッファプールから追い出されると、そのページを指すハッシュエントリは削除されます。ページ分割やページ破棄などでB-treeの構造が変わったときも、該当するエントリは削除されます。検証中のn_fieldsとn_bytesが変更され、新しい組み合わせでインデックス側とページ側の両方の数が再び閾値を超えたときも、そのとき検索していたページの古いエントリを削除してから新しいエントリを作ります。