MVCCとInnoDBでの実装について
こんにちは。
id:shallow1729です。先日はredo logを中心にストレージエンジンについて解説を行いましたが、今回は同時実行制御、特にMySQLなど多くのデータベースで採用されているMultiversion Concurrency Control(MVCC)という技術にフォーカスしようと思います。
今回の記事ではまず前半でMVCCというものがどういうものかについて解説をして、次にMVCCの実装方法についてInnoDBの実装を参考にしながら見ていこうと思います。前提知識はあまりいらないと思いますが、リレーショナルデータベースの操作経験はあったほうがいいかなと思います。また、前回のストレージエンジンの解説で述べた内容はあまり説明しないので、軽く目を通してもらえると頭に入りやすいかなと思います。
トランザクションの原子性
まずトランザクションの原子性について軽くおさらいします。トランザクションは一つ以上の一連のクエリの事で、トランザクションの原子性とは、トランザクションで行われる一連の処理について、例えデータベースに障害が起きても「全ての処理を行う」か「全ての処理を行わない」かのどちらかにするという性質です。この性質によって、データーベースのユーザーは複数のレコードにまたがる複雑な処理の実装を簡単に行えます。
わかりやすい例としてお金の送金について考えます。ある口座Aから口座Bに1000円送金する場合、口座Aの預金を1000円減らして口座Bの預金を1000円増やすという処理が必要です。もしトランザクションとしてこれらの処理がひとかたまりになっていない場合、口座Aから預金を1000円引いた状態でサーバーがダウンして、口座Bの預金を1000円増やしていなかった場合、口座Aからお金だけは引かれているという状態が起こり得ます。これらの処理を一つのトランザクションとして一塊にした場合、仮に口座Aから預金を1000円引いた段階でサーバーがダウンしても、トランザクションが完了していない状況なので復旧時に口座Aから預金を1000円引く前の状態に戻す事ができます。
トランザクションの同時実行制御
トランザクションの原子性の解説では一人のユーザーだけが操作をしていましたが、現実のATMでは同時に複数のユーザーがデータを操作をします。これは同時に複数のトランザクションがある状態と言えます。複数のトランザクションがあった時にお互いの操作の影響がどのようなものになるかは原子性とは別の話題、分離性の話題になります。
例えばですが、下のようにユーザーAが口座Aから口座Bに送金するのと同じタイミングでユーザーBが口座Bからお金を引き落とすというケースを考えます。ここで仮に送金のトランザクションと引き落としのトランザクションのコミット前のデータが見えたとすると以下のようなケースが起こり得ます。
最終的に送金トランザクションは失敗したにも関わらず2000円の引き落としに成功していまい、銀行が1000円損してしまいました。この問題の面白いところは引き落としトランザクションのSELECTとUPDATEの間で残高が負にならないかのチェックをアプリケーションでしても効果がない点と、トランザクションの原子性が満たされていても発生する点です。
この問題を防ぐ最もシンプルな方法は並列実行を諦める事です。シングルスレッドだった場合どうしてこの問題が防がれるかというと、以下のどちらかになるからです。
- 送金のトランザクションが先に始まった場合、そのトランザクションがCOMMITかROLLBACKされるまで他のトランザクションを受け付けない。送金がrollbackされた後に2000円引き落とそうとしてもrollbackで口座Bの残高は1000円に戻っているので無事失敗する。COMMITされた場合はその後の引き落としに成功する、で問題ない。
- 引き落としのトランザクションが先に始まった場合、送金前の口座Bの残高は1000円なので無事引き落としに失敗する。
とはいえシングルスレッドではパフォーマンスの問題が起こります。世の中にはRedisのようにシングルスレッドで動くデータベースもあるのですが、MySQLなどのリレーショナルデータベースでは以下のようにパフォーマンスの課題があるので現実的ではなさそうです。
- SQLという複雑なクエリを受け付けるのでCPUのボトルネックがある
- Disk Oriented Databaseはストレージからの読み取りが必要なケースもある
- 耐障害性も考えると同期的なストレージへの書き込みも必要
なので、なんとか並列実行を行う必要があります。
ロックとパフォーマンスの問題
先ほどの議論でマルチスレッド化をやりたいモチベーションは伝わったと思うのですが、どう実装すれば良いでしょうか？ 並列化プログラミングについての知識がある人だと、複数のトランザクションが同じレコードにアクセスする時の問題は複数のスレッドが同時に一つの変数をアクセスする時の問題とよく似ている事に気づくと思います。そして、並列化プログラミングではこういった状況を防ぐために、アクセスするリソースのロックを取るという手法がある事をご存知かと思います。なので、データベースの場合も同じようにロックの仕組みを提供するというのはどうでしょうか？
ロックと一言で言ってもいろいろ戦略はありますが、一例としてここでは、トランザクションがあるレコードに「アクセスする」とロックを取得し、他のトランザクションがそのレコードに対して読み書きしようとすると「COMMITやROLLBACKでロックが手放されるのを待つ」という手法(悲観的ロック)を考えます。
これでもまだ「アクセスする」という言葉がふんわりしていて、いつどの範囲でロックを取るかという話題があります。一つの選択としてUPDATEがされた段階で更新されたデータは「汚れる」ので、UPDATEのタイミングで更新対象のロックを取り、COMMITやROLLBACKをする時にロックを手放すという手はありそうですね。
以下の図に示すように、先ほどの例の場合、送金トランザクションが口座BをUPDATEをした段階で他のトランザクションは口座Bのデータにアクセスできなくなるので、直後の引き落としトランザクションのSELECT文は送金トランザクションがCOMMITかROLLBACKされるまで待つという形になります。これによって未コミットのデータが読まれるのを防ぐことができるので先ほどのように銀行が損をするのは防ぐ事が出来ました。
この作戦は今回のように同じレコードについて更新の完了待ちが発生しない限りロック待ちが発生しないのでシングルスレッドよりパフォーマンスは良いと言えますが、シングルスレッドでは起きない以下の図に示すようなおかしな現象が発生します。
このような同じレコードを見ているはずなのに違う値が返ってくる事もシングルスレッドで動いていたらありえない事です。この問題を解決する手段の一つはSELECT時にも対象のレコードのロックを取るようにするというものです。そうした場合、トランザクションBの最初のSELECTでロックが取られるので、トランザクションAの更新はトランザクションBのCOMMITを待つことになります。この場合、トランザクションBの複数回の読み取りは同じ結果を返します。
SELECT時にもロックを取る戦略の方がUPDATE時のみロックを取るやり方よりもシングルスレッドで直列にトランザクションが処理される状態により近いのですが、一方でロック待ちの可能性も高くなります。このようにパフォーマンスとトランザクション間の分離度合いの間には相関があり、トランザクション間の分離度合いが上がるほどパフォーマンスが悪化する事が知られています。*1
Multiversion Concurrency Control
先ほどの解説でトランザクションを直列に近い状態にしようとするとパフォーマンスが悪くなっていく様子を確認しました。これはトランザクションを直列にしようとするほどロック待ちの可能性が上がるからでした。ですが、実はロックを取らずにこれらの問題を解決する事が可能です。それがMultiversion Concurrency Controlです。MySQLもこの仕組みを提供しているので先にデモで試してみましょう。以下のようなクエリを一つずつ二つのコンソールから試してみてください。
おそらく各クエリについて、#より後ろのコメントにある結果が得られたと思います。しかもロック待ちも無く即座にレスポンスが返ってきたと思います。このように、ロック待ち無しで先ほど出てきた未コミットの更新が見える問題や同じデータにアクセスしているはずなのに違う結果が返ってくる問題を防ぐ事に成功しています。
MVCCは書き込みが他のトランザクションの読み取りを阻害せず、読み取りが他のトランザクションの書き込みを阻害しないという特徴があります。より詳細な実装はこの後解説しますが、一般には各トランザクションの開始したタイミングのデータ(スナップショット)を用意しておいて、各トランザクションは自分のスナップショットの中でデータの読み書きを行うSnapshot Isolationという手法で実装されます。
InnoDBのMVCCの実装の概観
ここまででMVCCがどういうものかが伝わったと思うので、概略にはなりますがInnoDBの場合の実装についてみていきます。ここでは概略のみの解説になるので、もしソースコードレベルで理解したいという方は
id:nayuta-yanagisawaさんの日本MySQLユーザー会会での発表がとても綺麗にまとまっているのでおすすめです。
日本MySQLユーザ会会(MyNA会) 2021年03月 - YouTube
どのように過去のスナップショットを保存するか？
まず過去のスナップショットをどのように保持するか？を考えます。一つの方法はレコードの更新が発生するたびに過去のレコードもそのまま保存していくという方法です。ただ、前回の記事の中で解説しましたがレコードをそのまま保存する以外に、logを貯めていって後から再構成するという戦略もあります。InnoDBは最新のレコードの状態から更新前の方向の差分のログを残しており、これを用いて過去のレコードを再構成しています。これは前回のcrash recoveryの目的で使っていたredo logとは逆方向なので「undo log」と呼ばれています。undo logの構造に関するドキュメントは見つけられなかったのですが、中身としては変更差分、自分より過去の同一のレコードの書き込み時のundo logのポインター(ROLL_PTR)、そのundo logを作ったトランザクションを定めるID(TRX_ID)、INSERTやDELETE、UPDATEなどのどのクエリか？などの情報があるようです。*2
レコードの更新時にはそのレコード*3から最新のundo logへのポインターを用意しておきます。古いスナップショットを見る時はレコードから最新のundo logを見に行き、undo logがさらに過去のundo logへのポインターを持っているのでどんどん過去に遡る事ができます。
どのスナップショットを見れば良いかをどうやって決めるか？
過去のスナップショットをログを用いて保管している事は分かりましたが、適切なタイミングのスナップショットをどう取得するか？は別の課題です。イメージ的にはトランザクション毎にタイムスタンプを用意して、自分より古い最新の更新まで遡れば良さそうですが、トランザクションの開始時とコミット時の順序は入れ替わりうるので実際はもう少し厄介です。
まず、InnoDBについて言うと先ほどのundo logに出てきたTRX_IDがタイムスタンプに近い役割をします。この値はトランザクションの開始時*4に払い出されるインクリメンタルなIDなので、大きいほど新しい時刻のものになります。*5このTRX_IDをうまく使って遡り先を決めています。以下にルールをまとめました。
- まず、自分の更新は見えていて欲しいので自分の更新なら遡るのをやめてレコードを再構成して完了です。
- 自分より古いトランザクションであっても未コミットのトランザクションの場合はコミットされても変更が見えてはいけないのでトランザクション開始時にアクティブなトランザクションのTRX_IDのリストを持っておいて、そのリストに入っていたら遡ります。
- 自分より大きいTRX_IDの変更の場合は、後から開始したトランザクションによる変更なので遡ります。
- 自分より小さいTRX_IDで、トランザクション開始時にアクティブでなければ遡るのをやめます。
- 最初のINSERTまで遡った場合は、そのトランザクション開始時になかったレコードになります。
ガベージコレクション
MVCCを実装する上で過去のすべてのスナップショットを保存しておく必要はありません。必要なのは現在でもアクティブなトランザクションのスナップショットだけです。ガベージコレクションを行わない場合、先ほど説明したような追加のログデータや、後で述べるインデックスの葉などのデータが溜まっていってしまい、パフォーマンスの問題を引き起こします。
ガベージコレクションの基本戦略は、「生きてるトランザクションより古いトランザクションのスナップショットは消していい」です。ガベージコレクションの実行されるタイミングについては、InnoDBの場合について言うとpurge threadというバックグラウンドスレッドで定期的に行われています。undo logはメモリ上はBufferpoolにあるのですが、非同期でibdata1というストレージ領域にも書き込まれるのでガベージコレクション時はメモリとストレージの両方からデータを削除する必要があります。この辺についてはまた別の機会に詳しく触れようと思います。*6
インデックスの管理
インデックスで使われているカラムを更新する場合はインデックスの更新も必要になります。特にsecondary indexの場合は更新に伴ってB+ Treeの葉の位置が変わるので大変そうです。
更新の基本戦略は、インデックス上の位置が変わると考えるのではなく、古いデータについては削除フラグを立てて新しいデータを作成するというものです。
InnoDBの場合、secondary indexはclustered indexへのポインターを持っており、clustered indexがレコードとundo logへのポインターを持っているという構造です。*7secondary indexに用いられているカラムに対する更新があった場合、まず元の古い葉に削除フラグを立てて、新しいカラムの値に対応する葉を作成します。ただし、削除フラグが立っても他のトランザクションが検索時にそのノードを飛ばしていいかというとそうではないです。むしろ削除フラグが立っている葉にたどりついた場合、必ずclustered indexからundo logを追ってレコードを取得します。*8これは、削除フラグが立っていてもそのトランザクションのスナップショット上では正しい位置のものだったかもしれないからです。ただ、削除フラグは無意味なわけではなくて、削除フラグが立っている葉は先ほどのガベージコレクションの仕組みで削除対象かのチェックをして最終的に削除されます。
最後に
以上でMySQLなど多くのデータベースで用いられている同時実行制御手法であるMVCCの概念と実装についてのざっくりとした解説になります。ユーザー的な注意点(long transactionの問題)やTRX_IDがどう払い出されるか、ロックのいくつかの実装の話などいろいろ省いた要素もあるのですが、ざっくりとでも全体像が伝われば幸いです。また、僕自身まだ勉強不足な部分もあるのでぜひご指摘いただけたらと思います。最後まで読んでくださってありがとうございました。
*1:「トランザクション分離レベル」で調べるといろいろ情報が出てくると思います。
*2:https://blog.jcole.us/2014/04/16/the-basics-of-the-innodb-undo-logging-and-history-system/#:~:text=InnoDB%20keeps%20a%20copy%20of%20everything%20that%20is%20changed&text=It's%20called%20an%20undo%20log,record%20to%20its%20previous%20version.
*3:正確にはclustered indexのレコード
*4:実際は最初のSELECTなどのクエリ実行時に割り当てられて、BEGIN;したタイミングではない
*5:この辺かなりややこしいのですが実際にインクリメンタルなTRX_IDが払い出されるのは最初の書き込み処理の時です。 https://www.percona.com/blog/2018/10/10/instrumenting-read-only-transactions-in-innodb/
*6:僕の方でもまとめようと思いますが、たとえばこちらの記事などではソースコードレベルで詳細を追っています。
*7:http://nippondanji.blogspot.com/2010/10/innodb.html
*8:https://www.slideshare.net/MariaDB/m18-deep-dive-innodb-transactions-and-write-paths/38
