ディスク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='alice01'の注文id=102を入れるとき、そのキーが載るセカンダリリーフ（ページ42）がバッファプールになければ、ディスク上のページ42は読みません。ディスクのページ42にはすでに(alice01,101)と(alice01,103)があり、新しい(alice01,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のすべてをバッファする）でした。設定値はいつでも変更でき、変更は新しい操作のバッファ有無にだけ効きます。すでに溜まっている分のマージには影響しません。

B-treeたどりを飛ばす近道

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

user_id='alice01'、name='Alice'を探すとき、ハッシュに載っていればルートと中間ノードを経ずに、リーフ上のそのレコードへ着地します。

左が毎回たどるページ、右がハッシュから同じリーフへ飛ぶ参照です。着地点はバッファプール上のレコードなので、対象ページがメモリにないときはこの近道は使えません。

「適応的」というのは、開発者が設定するのではなく、InnoDBが実際の検索傾向を見て必要なところだけ勝手に作る、という意味です。テーブルがほぼメモリに収まり、適したワークロードであれば、この近道によってインメモリデータベースに近い検索性能が得られます。トランザクション機能や信頼性を犠牲にするわけではありません。有効・無効はinnodb_adaptive_hash_indexで切り替えられます。MySQL 8.4では既定がOFFですが、8.0系では既定がONでした。

何をキーにハッシュを作るか

各ハッシュエントリは、インデックスキーのプレフィックス（先頭部分）からハッシュ値を計算し、そのプレフィックスに対応するバッファプール上の着地レコードへの参照を持ちます。点検索でキーが指定されると、ハッシュテーブルを引いて該当レコード（とそのページ）へ直接アクセスします。

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

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

構築のきっかけも決まっています。同じ検索パターン（同じプレフィックス）でのヒットが連続した回数を、InnoDBがインデックスごとにメモリ上のカウンタで数えており、テーブルの列やユーザーが直接参照・設定できるものではありません。この回数が一定を超えると、そのとき検索していたページに対してハッシュエントリが作られます。検索パターンが変わるとカウンタはリセットされます。逆に、ハッシュでヒットしない検索が続くと、新規の構築は控えられます（すでにあるエントリを消すわけではありません）。

検索パターンに合わせて調整する

プレフィックスの具体的な長さ（n_fieldsとn_bytes）は固定ではなく、検索でヒットしやすく、かつエントリ数を抑えられる長さが選ばれます。

同一リーフページ内で同じプレフィックスを持つレコードは1つのグループになり、各グループからは左端または右端の1件だけがハッシュに登録されます。1ページあたりのエントリ数を抑えるためです。ハッシュの目的は、正確なレコード位置をピンポイントで当てることではなく、該当ページ（またはページ内の着地点）へ到達することにあります。だからプレフィックスがユニークでなくても構いません。代表レコードに着いたあと、ページ内を少し走査して目的のキーを探せば足ります。ユニークにしなければ1エントリで複数レコードをカバーでき、メモリ効率が良くなります。左端と右端のどちらを取るかは、そのインデックスの検索パターンに応じて決まります。

検索頻度の高いページほど構築の閾値に達しやすく、限られた容量の中で優先的にハッシュ化されます。検索パターンが変わったときには推奨プレフィックスが更新され、ハッシュが作り直されます。

エントリが消えるとき

適応的ハッシュインデックスは増える一方ではなく、次の契機で削除されます。

参照先のB-treeリーフページがバッファプールから追い出されると、そのページを指すハッシュエントリは削除されます。メモリ上にないページへの参照は無効だからです。また、ページ分割やページ破棄などB-tree構造が変わったときも、該当するエントリが削除されます。ハッシュエントリは「キーKはページPにある」と記録していますが、分割でレコードが別のページへ移ると、この対応が壊れてしまうためです。

右端への連続昇順挿入で分割が起きる場合は、この削除の影響が小さく済みます。新しく挿入されたレコードだけが新ページへ移り、既存レコードはページ番号ごと旧ページにそのまま残るため、既存キーと「そのキーがどのページにあるか」という対応関係は分割の前後で変わりません。そのため、旧ページのハッシュエントリが分割で消えたあとに同じキーへ検索が来ても、B-treeをたどれば以前と同じ旧ページに行き着いてすぐ見つかり、以前と同じ対応関係でハッシュエントリがすぐに作り直されます。