InnoDBのMVCCのガベージコレクションについて

こんにちは、shallow1729:detailです。今回は先日MyNA会というイベントで発表したMySQLの標準のストレージエンジンであるInnoDBのMVCCのガベージコレクションについて書こうと思います。発表自体もアーカイブされているので以下から見る事ができます。

「日本MySQLユーザ会会(MyNA会) 2021年07月 -下位レイヤ勉強会-」 公開版 - YouTube

まず前半ではMVCCに関連するデータ構造を見ながらガベージコレクションの重要性やlong-running transactionの問題点について解説します。後半では実際のガベージコレクション(purge)の処理をソースコードレベルで追いながら、ユーザーに提供されているパラメーターを解説をします。

これまでに比べると踏み込んだ話題なのであまり基礎的な事は解説しません。知らない単語が多いかもしれないですが、適宜調べながら読んでいただけたらと思います。また、ユーザー視点でも面白い話題になるように工夫はしたつもりですが、ユーザー向けに伝えたいメッセージは「long-running transactionは避けよう」だけです。どちらかというと実際のデータ構造やソースコードを紹介して、読んでくださった方にデータベース面白いなって思って欲しいという気持ちです。

以下の解説ではMySQL5.7.32をベースに解説します。

MVCCについて

MVCCは複数のトランザクションが同時にデータベースにアクセスした際に、それらのトランザクションをうまく分離して捌くための仕組み(ACID特性のIの実装方法の一つ)です。MVCC以外の同時実行制御の実装方法としてはTwo-phase lockingやTimestamp Ordering Protocolなどがあるのですが、MVCCの特徴は他のトランザクションの書き込みが読み取りをブロックせず、他のトランザクションの読み取りも書き込みをブロックしないという性質です。そのためパフォーマンスが良いのでInnoDBなど多くのデータベースで使用されています。

InnoDBのMVCCのイメージはトランザクションの開始時にその瞬間のデータベースの状態のスナップショットを撮り、その上でデータの読み取りを行うイメージです。図に示すように複数のトランザクションが同時に開始した際、それぞれがデータベースの状態のスナップショットを撮るのでお互いのトランザクションの読み書きは独立して行えます。

f:id:shallow1729:20210723063532p:plain
スナップショットを用いたトランザクションの分離のイメージ。図では二つのトランザクションがお互いの読み取り対象のデータを書き込んでいるが、読み取りは各々のスナップショットの上で行うのでロック待ちは発生しない。

ちなみにMySQLのデフォルトのトランザクション分離レベルはREPEATABLE READで、SERIALIZABLE(トランザクションが同時に一つしか動いていないのに対応する分離レベル)ではないのでlost updateなどいくつかのanomaly(複数のトランザクションが同時に実行される事で起きる変な事)を防ぐ事はできません。なのでSELECT FOR UPDATEなどでユーザーが明示的にロックを取得する必要があります。

MVCCでできるゴミ

MVCCはトランザクション間でのブロックが発生しにくいのでパフォーマンスが良いのですが、一方でデータを共有していた場合に比べるとトランザクション毎のスナップショットを保持するための追加のデータ領域が必要になります。なので、あらゆるタイミング(バージョン)のスナップショットにアクセスするには過去のスナップショットを全て保持する必要があります。ですが実際にはトランザクション開始時のスナップショットが使われるので古いバージョンのスナップショットは、そのスナップショットを見ているトランザクションが完了(commit or rollback)すれば誰もアクセスできなくなるので捨てる事ができます。

あとで詳しく見ていくように、スナップショットをいつまでも放置しているとデータ容量的にもパフォーマンス的にもよくないのでガベージコレクション(InnoDB的にはpurge)する必要があります。

スナップショットを作るために必要なデータ構造

ガベージコレクションを理解するためにはまずInnoDBがスナップショットをどう表現しているかを考える必要があります。先ほどまではあたかもトランザクション開始時にデータを全てdeep copyするかのような表現をしましたが、実際は差分のみを保存する形で実現します。

まず、スナップショットを考えない場合にInnoDBがデータをどう保存、アクセスしているかを見ていきましょう。

f:id:shallow1729:20210723090717p:plain
InnoDBのレコードに関するデータ構造
図に示すように、InnoDBはclustered indexとsecondary indexという二種類のB+ Tree indexを用意しています。clustered indexは一般に主キーを用いたB+ Tree indexで、葉ノードにはレコードの全てのカラムの情報が全て入っています。一方secondary indexの葉ノードはsecondary indexで使うカラムと主キーのみが入っています。secondary indexを使ってレコードを検索する場合、secondary indexの葉ノードに到達したら主キーを取得し、それを用いてclustered indexのレコードを検索します。ただし、secondary indexだけで欲しいカラムが揃っている場合はclustered indexに検索する事なくレスポンスを返す事ができます。これをcovering indexと呼びます。

ここにInnoDBで使っているスナップショットの情報を追加すると以下のようになります。

f:id:shallow1729:20210723072933p:plain
スナップショットを保持するために追加で生まれるデータ構造。赤色で示すのは更新、削除などの処理で発生する過去のバージョンのデータ。青は更新時に変更、作成されるデータ。clustered indexのレコードからはundo logという差分情報がlinked listの形で連なる。また、B+ Treeの葉ノードは削除されても一旦削除マークだけをつけるだけで物理的な削除は行わない。
一つ一つについてはあとで細かく見ていきますが、ざっくりとは過去のレコードを保持するための差分情報(undo log)と削除マークがついた葉ノードがあります。

また、各トランザクションがどのバージョンのデータを見ればよいか(visibility)を確認するためにclustered indexのレコードやundo logにはタイムスタンプ(TRX_ID)があります。

B+ Treeの葉ノードに削除マークが必要なのは、たとえあるトランザクションに削除されたレコードでも別のトランザクションからはまだ見えるものかもしれないからです。削除マークがついたレコードは全てのトランザクションから見えなくなった時にpurgeの対象にできます。

undo logは更新が行われる度に伸びていく差分ログですが、こちらもいずれ古い差分は誰も見なくなるのでpurgeの対象にできます。

undo logの保存方法

ここからは先ほど説明した各データ構造についてより詳細に見ていこうと思います。まずはundo logについて、どのように保存されているかを見ていきます。

f:id:shallow1729:20210723073622p:plain
undo logを保管するrollback segmentのデータ構造。rollback segmentはトランザクション毎に割り当てられるデータ領域で、そのトランザクションの更新について過去方向(undo)への差分をundo log recordとして保存する。clustered indexの葉ノードとundo log recordは過去のundo log recordへのポインターを持っているのでこれで過去のバージョンに遡る。

undo logはrollback segmentという領域にundo log recordとしてためられます。この領域はバッファープール上にもありますし、crash recoveryでもundoは必要なのでストレージにも割り当てられています。

rollback segmentはトランザクション毎に割り当てられて、そのトランザクションが更新を行なった場合、古いバージョンへの差分(undo log record)がrollback segmentに書き込まれます。なので、rollback segmentのundo log recordを使えば、そのrollback segmentに割り当てられたトランザクションの開始前のバージョンを見る事ができます。

clustered indexのレコードは最新のundo logへのポインターを保持しており、undo log recordは一つ前のundo log recordへのポインターを持つという形になっているので、過去のバージョンが欲しい時はポインターをたどる事で実現します。

undo logをpurgeできるタイミング

最初の方で原理的にはスナップショットはそれを見ているトランザクションが不要になったら捨てられると述べましたが、実際はもう少しナイーブな方法でpurgeの対象を決めています。

先ほどのundo logの保存方法からその更新を行なったトランザクションとundo log recordが紐づいている事がわかります。undo log recordはその更新を行ったトランザクション以前のバージョンにアクセスするために使うものなので、もしその更新を行ったトランザクションのcommit以後のトランザクションしかアクティブで無ければ、そのundo log recordはpurgeできる事になります。なのでInnoDBはこの発想でpurge対象を決めています。

一方この判断方法で全てのゴミを捨てられるわけではありません。アクティブなトランザクションの後に始まったトランザクションがレコードを二度更新した場合、誰からも見えなくなるバージョンが発生し得ますがこのゴミは捨てる事ができません。

undo logをpurgeするためのデータ構造 history_list

先ほどの解説でundo logのpurge基準はその変更をしたトランザクションのコミットより後のトランザクションしかいなくなった時という事が分かりました。なのでうまくコミットした順序になるようにundo log recordをlinked listなどで繋げておくとその順番を辿ってpurgeを行える事が分かります。InnoDBではこのデータ構造をhistory_listと呼びます。

history_listはトランザクションのコミット時にそのトランザクションのundo log recordを末尾に繋げていく事でcommit順になるようにしています。後で述べるようにlong-running transactionはシステム全体のパフォーマンスへの悪影響を及ぼすのでそれを監視するためにhistory_list_lengthを監視する事があると思いますが、history_list_lengthというのはこのcommitされたpurge前のhistory_listの長さの事です。undo log recordの数という意味だと未コミットのトランザクションのundo log recordもあるので少しずれます。

また、InnoDBhistory_listとほぼ同じ情報を持つデータ構造としてpurge_queueというデータ構造も持っています。これはトランザクションのcommit時に払い出されるtrx_noというインクリメンタルなIDの順序に並ぶようにrollback segmentへのポインターを保持するpriority queueで、後で見るpurge処理のパフォーマンス向上の目的で使っているようです。linked listとpriority queueなのでデータ構造は違いますがhistory_listはcritical sectionで伸ばされて、trx_noも同一のcritical sectionで払い出されるので中身は同じものと考えて大丈夫です。

f:id:shallow1729:20210723081828p:plain
undo logをpurgeするために作られるデータ構造、history_listとpurge_queueの図。どちらもトランザクションがコミットされた順序でundo log recordを取り出せるようにしている。

レコードの削除時のclustered index

undo logの解説だけでかなりの量になってしまったのですが、先ほど述べたようにスナップショットを保持には削除マークがついた葉ノードも発生します。

clustered indexの葉ノードは削除された場合その削除を行ったTRX_IDと削除マークを持っています。削除マークのついた葉ノードはundo logのpurgeのタイミングでそのrollback segmentのTRX_IDと同じTRX_IDによる削除がされた葉ノードを物理的に削除します。*1

f:id:shallow1729:20210723083052p:plain
clustered indexのデータ構造。葉ノードは削除されてもすぐには削除されず、一旦削除マークだけがつく。

レコードの更新時のsecondary index

clustered indexについては一般的にprimary keyが更新される事を考える必要がないと思いますが、secondary indexについてはレコード更新によってindexに用いているカラムが更新される可能性について考える必要があります。例えばintegerのカラムの順序で並ぶsecondary indexの場合、そのカラムの値が10から20になると、10だった葉ノードは11や12を追い越すので別の場所に移動する可能性があります。この更新のコミット前に始まった別のトランザクションが1~15の範囲で検索していると、単に葉ノードの位置を変えてしまうとそのトランザクションだと本来見えていたはずの葉ノードが見えなくなります。なのでこれを防ぐためにsecondary indexに関連するカラムの更新時は古い葉ノードに削除マークをつけて新しい葉ノードをinsertする形で複数のバージョンのスナップショットを提供しています。削除マークのついた葉ノードのpurgeはclustered indexの方で解説したようにundo logのpurgeの中で行います。

f:id:shallow1729:20210723083433p:plain
レコードが更新、削除された時のsecondary indexの図。削除時に削除マークがつくのはclustered indexと同様だが、更新時に葉ノードの位置が代わりうるので削除マーク+insertで複数のバージョンに対応している。

secondary indexのvisibilityとcovering index

これまでの解説から考えられるsecondary indexで検索した時の挙動は、削除マークがついている葉ノードの時はその葉ノードのTRX_IDを見て自分が見て良いかを判断するというものですが、実はsecondary indexの葉ノードはTRX_IDを持ちません。

ではどうやってvisibilityを判断するかというと、covering indexが効かないレコードを取得する時と同じように、TRX_IDを持つclustered indexを見にいく形で判断しています。

そのため、削除マークがついた葉ノードについてはたとえ自分からは見えないバージョンの葉ノードだったとしても飛ばす事はできず、必ずclustered indexを見に行きます。また、clustered indexを見にいかないといけないのでcovering indexも効かなくなります。結果として削除マークのついた葉ノードを放置しているとシステム全体のパフォーマンスがどんどん悪くなっていきます。これがガベージコレクションの必要な理由の一つです。

long-running transactionの問題点の考察

MySQLのバッドプラクティスの一つとして長時間コミットされないトランザクション(long-running transaction)があります。ここまでの解説からlong-running transactionがなぜ問題かを考えていきます。

まず、long-running transactionが存在する場合、そのトランザクション以後に作られたスナップショットのゴミは捨てる事ができません。また、secondary indexの検索でみたように、ゴミがたまるほどパフォーマンスが悪くなってしまいます。そのため、long-running transactionの存在はpurgeを阻害するためにシステム全体のパフォーマンスを悪化させてしまいます。

ここで重要なのはlong-running transactionがどのテーブルを見るかをデータベースは知らないという事です。そのため、long-running transactionがたとえ一部のテーブルにしか関心を持っていなかったとしてもシステム全体のパフォーマンスはどんどん悪くなっていきます。また、long-running transaction自身については遡るundo logがどんどん増えるのでパフォーマンスはさらに悪化していきます。以上の理由から、long-running transactionはバッドプラクティスと考えられます。

purgeのパフォーマンスに関わるパラメーター

ここまででpurge対象となるデータやpurgeのタイミングについて解説しました。次にpurge処理の大まかな流れを書こうと思うのですが、今回はユーザーが設定できるパラメーターの理解に繋がるようなまとめ方をしようと思っているので、先に注目したいパラメーターをまとめます。

innodb_max_purge_lag

innodb_max_purge_lagの値がhistory_listの長さが閾値を越えるとDMLにsleepを挟むというものです。これによって書き込みにpurgeが追いつかないような時に無理やりpurgeを間に合わせる事ができます。

innodb_purge_batch_size

これは後で解説するpurge処理の一サイクルで処理するundo logの数です。これを設定する事で一サイクルあたりに処理するundo logの数や128回に1回行われるrollback segmentからundo logをtruncateする量をコントロールできます。

innodb_purge_threads

purge処理に割り当てるthreadの数です。

以下ではこれらのパラメーターに注目しながらpurge処理を見ていこうと思います。

purge処理の流れ

まず、図で示すものがpurge処理の全体像です。以下で一つ一つのステップについて解説します。

f:id:shallow1729:20210723084935p:plain
purge処理の全体像

purgeのメインスレッド

まず、InnoDBはpurge処理をpurge_coordinator_threadというバックグラウンドスレッドが行います。このスレッドはpurgeに関わるメインスレッドで、シングルスレッドで動いています。

purgeの遅れ度合いの計算

purge_coordinator_threadはまずtrx_purge_dml_delayというメソッドでhistory_listの長さをチェックします。もしhistory_listがinnodb_max_purge_lagより長かったらhistory_listとの差分からdmlの遅延時間を計算してsrv_dml_needed_delayというグローバルな変数に遅延時間を入れます。dml実行時はrow_mysql_delay_if_neededというところでsrv_dml_needed_delay分sleepを入れるようにしています。

purge対象のundo log recordの取得

次にtrx_purge_attach_undo_recsというメソッドでpurge対象のundo log recordをinnodb_purge_batch_size個取得します。これをどう行なっているかというと、undo logのpurgeのタイミングで解説したように現在アクティブなトランザクションより前にコミットしたトランザクションのundo logはpurgeできるので、まず現在アクティブな一番古いトランザクションを取得して、undo logがそのトランザクションより前に作られたかをチェックする事で実現しています。

「一番古いアクティブなトランザクションの取得」はclone_oldest_viewで行なっています。ここで取得されるReadViewという構造体はトランザクションのvisibilityを評価するために使う構造体で、トランザクション開始時までにコミットされたトランザクションやアクティブなトランザクションの情報を持っています。

purge対象のundo log recordの取得はtrx_purge_fetch_next_recで行います。この中を追ってみるとpuge_queue->popで新しいrollback segmentを取得しています。そして、このrollback segmentのundo log recordを取り出して、それを先ほど取得した一番古いアクティブなトランザクションと比較してpurgeして良いならpuge対象に追加する、という形で行なっています。

そして、innodb_purge_batch_size個取れるか、それ以上取れなくなったらこの処理を完了してpurge作業に入ります。

worker_threadへのジョブの依頼

purge作業では削除マークがついたB+ Treeの掃除やpurgeが完了したundo logにマークをつける処理が行われます。この処理はworker_threadにjob queueを介して依頼する形で行います。

worker_threadは広くInnoDBのバックグラウンドの処理を行うスレッドで、渡されたジョブのコンテキストに基づいていろいろやります。purgeに割り当てられるworker_threadの数はinnodb_purge_threads個です。そのため、innodb_purge_threadsはpurge処理を依頼できるworker_threadの数という事になります。

これらのworker_threadの処理が全て完了したらpurgeの一サイクルが完了します。

undo log recordのtruncate

サイクルが完了すると基本的には最初に戻るのですが、128回に一回rollback segmentのundo log recordのtruncateを行います。この処理によってrollback segmentを再利用可能な状態にします。

この処理はhistory_listを辿りながら行い、truncateが完了するとhistory_listからundo log recordが削除されるという仕組みです。truncateは毎回行う訳ではないのでpurge_queueとhistory_listという同じような情報を別々で用意した方がパフォーマンスがよくなります。

ちなみにundo logが溜まっている時にhistory_list_lengthを監視していると、この値が減らないフェーズが見える事があると思いますが、history_list_lengthが小さくなるのはこのtruncateのフェーズなので、worker_threadによるpurgeフェーズに時間がかかっているとhistory_listが減らない瞬間が見える現象が発生するというのが原因です。

ちなみになぜtruncateを別処理にしてるかについてですけど、work_queueが並列に動くとrollback segmentが再利用可能な状態になるかの判断がしんどいからかなーと思っています。

最後に

以上でInnoDBでのpurgeの解説になります。ニッチな話題と思われたかもですが、途中書いたようにMVCCのガベージコレクションはパフォーマンス的にも重要なものなので、OLAPとOLTPが混合するようなケースを想定したデータベースでは特に重要なもので、現在も研究が進められています。*2

長くなってしまいましたが、普段ブラックボックスとして使いがちなデータベースの中身について興味を持つきっかけになってもらえたらなーと思います。

*1:物理削除といってもoptimize tableを実行しない限りは再利用できるようにするだけです。

*2:例えばhttps://dl.acm.org/doi/10.14778/3364324.3364328