データ変更を伴うバッチ処理を書く時に考慮していること

こんにちは、id:shallow1729です。最近はインフラ寄りなお仕事をよくやっていますがこれまでにいくつかデータ移行やデータ基盤構築などのバッチ処理のお仕事をしてきました。以前にも一度そういった経験を元に記事を書いたのですが、MySQLやシステムに関する知識が以前よりも増えた今もう一度書き直したいなと思いました。

なので今回はバッチ処理を書く時のテクニック2022版という感じです。今の仕事の関係でMySQLrailsを前提にしている話が多いですが、おそらく他のデータベースを使っている人にも役に立つ話が多いのではないかと思います。ただ、今回の記事は経験に基づくものが多く、あまりよくないアイデアもあるかもしれません。改善点や間違いなどあればご指摘ください。

冪等性を持つように

冪等性とは端的に言えばある操作を複数回実行しても一回しか実行しなかった時と同じ結果になる性質の事です。長時間かかるバッチはしばしば途中で失敗します。事前の試運転で気づけるバグもありますが、デッドロックやロック待ちのタイムアウトのような並列実行の影響やネットワークタイムアウト、サーバーのOOM kill、外部apiのrate limitなど実際に動かしてみて初めて気づく事もよくあると思います。なのでこけたらもう一回実行できるように作る事が重要です。

冪等性を壊すやつらとしては例えば以下のような奴らがいます。

  • auto increment
  • uuidやulidなどのランダムな値
  • タイムスタンプ

もちろん全てのデータが冪等である必要は無いと思います。例えば更新のタイムスタンプとかは都度最新のものになって欲しい事があると思います。

ただ、例えばあるテーブルのレコードの内容を別のテーブルにコピーする時にコピー先のidを新規に払い出したりすると元のテーブルでどこまでコピーされたかを把握するのは難しくなります。なので基本的にはなるべく先ほど述べたような冪等性を壊すようなやつらは新規に払い出さない方がいいです。

とはいえ。例えば水平シャードされていてidがグローバルにユニークじゃないケースでそれらをマージしたものを作ろうとするとこういった問題は避けられません。そういったケースでうまくやる作戦の一つとして「これらの値を払い出すフェーズとバッチ処理のフェーズを分割しておく」という手はあると思います。例えばあるテーブルのデータを別のテーブルにコピーする時はコピー元とコピー先のidのマッピングを先に作って永続化しておけば、再実行するときにinsert済の箇所はすでにレコードが入っている事が分かります。こうなっていればupsertにすれば冪等にできるかなと思います。

途中からの再実行をできるように

短時間のスクリプトであれば冪等性を担保できれば十分ですが、数時間かかる処理の場合は冪等性に加えて途中からの再実行も欲しい機能です。丸一日かけて90%まで進んだところで失敗して1からやり直しはつらい事が多いと思います。また、「普段は大丈夫だったけどある日突然大量のインプットが来て何回再実行してもタイムアウトで死ぬ」という事はあるので大事なバッチ処理は先んじて再実行できるようにしておけると良いと思います。

途中からの再実行を行うためには「処理をこまめにセーブする事」と「まだ処理がされていない箇所を把握できる事」が特に大事だと思います。「処理をこまめにセーブする」にはDBへのリクエストならトランザクションを細かく分割した上で、何かしらの形で「ここまでは処理を終えた」と分かるようにする必要があります。重要なのは「ここまでは終えた」と分かるように処理を作る必要があるという事で、データ更新ならid何番までは処理した、とか何時より前のデータは処理したと分かるように作る必要があるという感じです。

「途中から再実行」の技術はページネーションで調べるとオフセット法やシーク法というのが出てくると思います。MySQL的には一般にシーク法の方が嬉しいですがオフセット法の方が書きやすい印象なので無理に最初から最適化しなくていいと思います。

あわせてですが、途中からの再実行を実現するためには「途中の状態が許容される事」も重要です。稼働中のサービスの場合に一部のデータは更新済み、他は未更新という状態が許容されるようにバッチ以外含めて設計しておけると良いと思います。

ユーザー影響の削減

稼働中のサービスの裏でバッチが動く時はユーザー影響をなるべく小さくなるように作った方が良いです。

トランザクションはなるべく短く

トランザクションはなるべくすぐに抜けるようにした方が良いです。長いトランザクションはシステム全体のパフォーマンスを悪くしますし、この後説明するギャップロックのように想定外にユーザー影響を与えるロックを取ってしまうリスクがあるのでリスクヘッジの意味でもトランザクションを短くした方が良いです。トランザクションを開始する前にできる事をなるべくやってから開始、最低限の処理をやってトランザクションをコミットするのが大切です。

また、ユーザーもアクセスするようなテーブルについて大量のデータを一度に更新するのは避けて、ほとほどのサイズに分けて更新すると良いです。細かすぎるとN+1問題の弊害が大きくなるのでほどほどが大事です。 バッチスクリプトのパフォーマンスを確認する時はトランザクションの開始から終了までの時間を計ると良いです。この時間がユーザーがそのデータの書き込みできない時間になります。その時間がサービス的に許容できるか考えるのが大事です。

ロックをとる範囲はなるべく少なく

トランザクションはなるべく短く」に近いですが、ロックを取る範囲はなるべく少なくすると良いです。例えば今のデータを読んでその結果を元に何か更新するような場合は最初のread時にロックを取って、更新してから手放すのが基本ですが、データが変更される心配が無いケースであったり、データの正しさが結果整合で十分な場合などはread時にlockを取らないという戦略もあります。

MySQLの場合ロックを取る範囲を確認したい時はInnoDB Lock Monitorが便利です。これはinnodb_status_output_locksを有効にすると確認できます。例えばupdate … where cid=1;(cidはなんらかの外部キー)みたいなケースではこの検索に使うsecondary indexの検索中に操作したレコードのロックと後述するギャップロック、更新対象のレコードのprimary keyのレコードロックが確認できると思います(REPETABLE READの場合)。また、適切なsecondary indexがない場合使われるindex上で走査されたレコードが全てロックを取られると思います。

可能な限り削除/更新対象はユニークに定まるようにする

ロックについて特に見落としがちなのがMySQLでデフォルトのREPEATABLE READの場合に発生するギャップロックの影響です。例えばupdate … where cid=1;みたいなクエリを考えます。この時cidはnon uniqueな外部キーのカラムで、cidのインデックスが貼られているとします。このクエリが実行中ロックを取る範囲は手元で試したところ「cidのindexのcid=1のレコードロック」、「cidのindexのcid=1の値が入る場所(新規にcid=1のレコードがinsertされる場所)のギャップロック」、「primary keyのcid=1のレコードロック」でした。MySQLはREPETABLE READの場合実行中にクエリの実行対象が増える事を防ぐためにクエリの実行中はcid=1のレコードのinsertをさせないようにしています。これは例えばlockを取らずにselectで更新対象のprimary keyを取得して、取得したprimary keyで指定して更新すれば「primary keyのcid=1のレコード」だけをロックの対象にする事ができます。ただし、これはselectしてから更新するまでに新規に作られたcid=1のレコードは更新できない事に注意してください。

今回はupdateを例にしましたが、これらの現象はdeleteでも起きます。deleteの場合は特に空振りするとネクスキーロックと言って空振りした前後の空の範囲にもロックを取るため大きな影響がでるリスクがあります。いずれにしてもunique keyで対象をuniqueになるように絞れば問題の影響範囲は最小限に抑えられると思います。

単一プロセスのパフォーマンス向上

パフォーマンスについて考える時は計測するのが大事です。バッチ処理は実行環境を用意するのが難しいケースが多いので大変だと思いますが、さくっと何度でも試せるようにするのが大事です。片道切符のデータ変更のバッチなどの場合は都度データを戻すのが大変だと思うのでテストモードの時はトランザクションロールバックするようにするとかは手だと思います。こういうのを実装しやすくする意味でもトランザクションの範囲を小さくするのは大切です。

バッチ処理の高速化で重要なのはN+1を防ぐ事です。rails5系の時はactiverecord-importなどが使われていましたがrails6だとinsert_allなど標準のメソッドでバッチ処理が行えます。

言ってる事はread系の画面を作る時の注意と同じ事なのですが、実際に経験しないと「書き込み系の処理だとディスクI/Oの方が問題でしょ?」みたいな感覚になるんじゃないかと思います。ですが実際前職での経験で書き込みのN+1の改善だけでデータ移行のバッチを60倍程度早くできたこともあるので結構大きな効果があると思います。

バッチ処理のN+1で特に難しいのが親子関係のあるようなデータのバッチです。よくやるのが親ごとでループを回して子だけバルクで処理するようなやつです。これだと親がN+1になります。親子ならいいですが孫まで出てくるとナイーブな作りでは高速化できません。

こういうケースの戦略はORMの構造体(ActiveRecordのモデルなど)にインメモリにまずinsert/updateしたいデータを構築して、最後にまとめてバルクで処理するというものです。このやり方なら元のロジックを崩さず、可読性を保った形で全体をバルクで処理する事ができます。

並列実行によるパフォーマンス向上

メンテ中など負荷は気にしなくていいけど短時間で終わらせないといけない時は並列実行できるように設計すると良いです。並列化の戦略は「ユーザー影響の削減」のところと似たような感じです。他のプロセスがユーザーのプロセスかバッチのプロセスかという違いです。

各バッチについて担当範囲がかぶらないように注意して、処理の途中でもギャップロックなどによるロック競合が起きないように気を遣ったロジックにする事が大事です。

負荷対策

N+1を防ぐ、処理の分割、トランザクションを短く、などをきちんと行えば自然と負荷対策になると思っているのでここについては追加で書く事があまりないのですが、定期的にsleepを入れるのはよくやると思います。注意点として初歩的な事ですがsleepのタイミングは必ずトランザクションの外にした方が良いです。トランザクションを手放す前にsleepするとロックがかかったままになるので。

負荷も「試してから考える」でいいと思います。あとは、止めていい処理なら想定外に負荷が上がったら止められるように作るのが大事だと思います。それは冪等に作るとか途中から再実行できるようにするというのと同じような事だと思います。

バッチサイズの制御

負荷のコントロールの難しい内容としてはバッチサイズの制御の話があります。例えば親、子、孫のテーブルのデータを処理して他のテーブルにコピーするような時に親テーブルでバッチサイズを決めてループを回すのがよくやる方法ですが、親のバッチサイズが100としてもバッチ毎に子が1000、孫が10000の事もあれば子も孫も100の事もあります。このようにバッチサイズは親テーブルだけでは十分にコントロールできないケースもあります。こういう時の戦略として前職でやったのは、先に子や孫のidだけ先読みして一定サイズに分割してコピー先のidとのマッピングを永続化(冪等性のところで解説したような手法です)して、親をコピーするフェーズ、子をコピーするフェーズ、孫をコピーするフェーズに分けてそれぞれでバッチサイズを決めてコピーするという事をやりました。外部キーにつっこみたいデータも先に払い出されているのでテーブル毎でのコピーが可能になります。ただ、この作戦はメンテ中などユーザーによってデータが触られないケースでないと難しいと思います。

データ同期で気をつけたいデータ不整合

バッチ処理でよくやるのがあるDBやテーブルのデータに何らかの処理をして別のDBやテーブルにコピーをするというやつです。世間的にニーズが多いのでツールは多い一方で基本的に難しいのでどういうところが難しいかについて書きました。

何が難しいかと言うとソースのデータの変更、削除を追跡するのが難しいからです。 まず単純なappend onlyなログの場合のようにdeleteやupdateが発生しないデータの同期を考えます。この場合データ同期はもし途中でこけてしまってもコピー先の最後のレコードのidやタイムスタンプを見て、それより大きい値のレコードを再同期すれば十分です。

問題はdeleteやupdateが発生した時です。前回のコピーの後に更新された箇所は更新のタイムスタンプがあれば追跡できるかもしれませんが、そのタイムスタンプの更新漏れのリスクはあると思いますし、deleteされた箇所を得るのは困難です。

updateやdeleteの問題を避けるシンプルな戦略としては以下のようなケースが思いつきます。

  • 更新を止めて同期する
    • ワンタイムであれば同期中にupdateやdeleteが走らないようにすればこの問題は解決できます。
  • ログの形式にする
    • 先ほどappend onlyならコピーが簡単と書いたのですが、updateやdeleteもappend onlyなログの形式に変換するというイメージです。*1
  • 毎回全部コピー
    • 全データを毎回全部入れ替えたらdeleteやupdateもちゃんと反映されます。BigQueryみたいなむっちゃ安いストレージに対してならありな戦略だと思います。
  • 削除しない
    • updateだけならタイムスタンプを信用して前回の処理以降のタイムスタンプを使えば良いのでまだ実現が可能です。この場合削除は論理削除というものになります。ただ、僕はdeleted_atを用いた論理削除でつらい経験(意図せず削除したはずのデータがユーザーに見えるなど)をした事があり、開発上のデメリットが大きいと感じています。削除済みレコードテーブルを別で用意するとかだとまだ安心できるかもしれないですが僕は経験が無いです。

もしこういった単純な方法が困難な場合はpt-online-schema-changeが行っているようにdatabaseのトリガーを用いる方法やAWS Database Migration Serviceなどがおそらく内部的にやっているバイナリログを用いた方法などで更新を追跡する必要があると思います。

最後に

自分がぱっと思いつく範囲でバッチ処理のテクニックをまとめました。何か参考になることがあれば嬉しいです。

*1:追記: 例えばレコードの更新時にログテーブルに更新内容を一緒に書いて、定期的にそのログテーブルの内容を元に同期する、とかです。ログテーブルに書き込む時点で最初の方に書いた冪等性を崩すようなデータを払い出して保存しておけば冪等にデータを同期できるかなと。

pt-online-schema-changeによる負荷を好きなメトリクスでコントロールする

こんにちは、id:shallow1729です。この記事はMySQL Advent Calendar 202119日目のものです。昨日はid:next4us-tiさんでMySQL8.0を再起動するとアプリからつながらなくなる理由でした。インターネットって情報はたくさんあるけど分かってないと検索できないケースが多いと思っていて、ユーザーの立場に立って記事を書いているというのが伝わってすごくいいなと思いました。僕も会社のMySQlを8系にする時のトラブルシューティングをうまくやるために参考にしようと思います。

今回はpt-online-schema-changeを自分向けに改造した話です。

pt-online-schema-change(pt-osc)

pt-oscはカラムのデータ型の変更のようなオンラインDDLが使えないalter tableをオンラインで行いたいケースなどに使えるツールです。このMySQL advent calenderでもpt-online-schema-changeとgh-ostの比較(データが損失するかもしれないAlterTable編)id:kenken0807さんが話題にしているようにデータベース屋さんの間だと結構有名なツールだと思います。

pt-osc自体の解説は特にしませんが基本的な挙動としては以下のイメージです。

  1. alter table後のテーブル定義の新しいテーブルを作成
  2. 元のテーブルのレコードを新しいテーブルにコピー、この間に起きる元のテーブルへのinsertやupdateはtriggerで拾う
  3. 新しいテーブルの名前をコピー元のテーブル名にrenameする事で新しいテーブル定義への変更を完了する

alter table済みのコピーを作成してrenameで入れ替えるという感じですね。

pt-oscの負荷の制御の仕組みの改造

先ほどの動作の説明で出たレコードのコピーについては当然負荷がかかるのでpt-oscは--max-loadというオプションでMySQLの状態を見て負荷が高そうならコピーを止めるという事をやってくれるのですが、SHOW GLOBAL STATUSで取得できるものしかサポートされておらず、インスタンスのCPU使用率のような負荷状況の監視に用いるようなメトリクスでの制御はできませんでした。実際pt-oscのデフォルトはThreads_running(sleepでないスレッド数)を見ながらコピーの頻度を制御するのですが、アクセスのほとんどない検証環境で動かしてみるとCPU使用率が100%に張り付いてしまいました。まあ本番ならいっぱいアクセスあるだろうし大丈夫かな?と思いつつも制御できるなら制御したいと思って制御できるようにコードを変更したものが以下です。

github.com

$varが--max-loadで渡した値のメトリクス名のようなので、この値で分岐して独自のメトリクス取得方法を実装した感じです。僕のサンプルだとcpuutilizationというのを--max-loadで指定できるようにして、AWSのcloudwatch metricsで取得したRDSのCPU使用率が指定した値を上回るとコピーを止める事ができるようにしています。 一応実際に軽く動かしてみてCPU使用率が--max-loadで渡した値を下回るまではコピーが進まない事の確認はしましたが、本番での活用は自己責任でお願いします。

$ DB_INSTANCE=database-1 pt-online-schema-change --alter "add column c1 int" D=test,t=sample  --password testtest --user root --host localhost --execute --max-load cpuutilization=7 --chunk-size 10
No slaves found.  See --recursion-method if host ip-172-31-37-79.ap-northeast-1.compute.internal has slaves.
Not checking slave lag because no slaves were found and --check-slave-lag was not specified.
cpu utilization is 7.33333333333334
Operation, tries, wait:
  analyze_table, 10, 1
  copy_rows, 10, 0.25
  create_triggers, 10, 1
  drop_triggers, 10, 1
  swap_tables, 10, 1
  update_foreign_keys, 10, 1
Altering `test`.`sample`...
Creating new table...
Created new table test.____sample_new OK.
Altering new table...
Altered `test`.`____sample_new` OK.
2021-12-16T10:46:28 Creating triggers...
2021-12-16T10:46:28 Created triggers OK.
2021-12-16T10:46:28 Copying approximately 15 rows...
cpu utilization is 7.33333333333334
Pausing because cpuutilization=7.33333333333334.
cpu utilization is 7.33333333333334
...
cpu utilization is 7.33333333333334
Pausing because cpuutilization=7.33333333333334.
cpu utilization is 7.33333333333334
cpu utilization is 6.39344262295083
2021-12-16T10:48:01 Copied rows OK.
2021-12-16T10:48:01 Analyzing new table...
2021-12-16T10:48:01 Swapping tables...
2021-12-16T10:48:01 Swapped original and new tables OK.
2021-12-16T10:48:01 Dropping old table...
2021-12-16T10:48:02 Dropped old table `test`.`_sample_old` OK.
2021-12-16T10:48:02 Dropping triggers...
2021-12-16T10:48:02 Dropped triggers OK.
Successfully altered `test`.`sample`.

最後に

以上です。percona toolkitはGPL2.0で、コードを変更して公開する分には問題ないはずだと思っていますが何か問題あれば教えてください。

明日はyy_hrachiさんです!おたのしみに〜

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

リンク集

データベース関連->database カテゴリーの記事一覧 - shallowな暮らし

プログラミングコンテスト関連->procon カテゴリーの記事一覧 - shallowな暮らし

雑多な開発テクニック-> development カテゴリーの記事一覧 - shallowな暮らし

MVCCとInnoDBでの実装について

こんにちは。id:shallow1729です。先日はredo logを中心にストレージエンジンについて解説を行いましたが、今回は同時実行制御、特にMySQLなど多くのデータベースで採用されているMultiversion Concurrency Control(MVCC)という技術にフォーカスしようと思います。

今回の記事ではまず前半でMVCCというものがどういうものかについて解説をして、次にMVCCの実装方法についてInnoDBの実装を参考にしながら見ていこうと思います。前提知識はあまりいらないと思いますが、リレーショナルデータベースの操作経験はあったほうがいいかなと思います。また、前回のストレージエンジンの解説で述べた内容はあまり説明しないので、軽く目を通してもらえると頭に入りやすいかなと思います。

shallow1729.hatenablog.com

トランザクションの原子性

まずトランザクションの原子性について軽くおさらいします。トランザクションは一つ以上の一連のクエリの事で、トランザクションの原子性とは、トランザクションで行われる一連の処理について、例えデータベースに障害が起きても「全ての処理を行う」か「全ての処理を行わない」かのどちらかにするという性質です。この性質によって、データーベースのユーザーは複数のレコードにまたがる複雑な処理の実装を簡単に行えます。

わかりやすい例としてお金の送金について考えます。ある口座Aから口座Bに1000円送金する場合、口座Aの預金を1000円減らして口座Bの預金を1000円増やすという処理が必要です。もしトランザクションとしてこれらの処理がひとかたまりになっていない場合、口座Aから預金を1000円引いた状態でサーバーがダウンして、口座Bの預金を1000円増やしていなかった場合、口座Aからお金だけは引かれているという状態が起こり得ます。これらの処理を一つのトランザクションとして一塊にした場合、仮に口座Aから預金を1000円引いた段階でサーバーがダウンしても、トランザクションが完了していない状況なので復旧時に口座Aから預金を1000円引く前の状態に戻す事ができます。

f:id:shallow1729:20210517191213p:plain
トランザクションの途中で障害が発生した場合のロールバックの図。口座Aだけ更新した状態で障害が発生した場合、データベースはその状態で永続化せず、トランザクション開始時点に巻き戻るようにする。
データベースが原子性をどのように実装しているかに興味がある方は前回の解説をご参照ください。ここではとりあえずトランザクションとその原子性について思い出してもらえたら十分です。

トランザクションの同時実行制御

トランザクションの原子性の解説では一人のユーザーだけが操作をしていましたが、現実のATMでは同時に複数のユーザーがデータを操作をします。これは同時に複数のトランザクションがある状態と言えます。複数のトランザクションがあった時にお互いの操作の影響がどのようなものになるかは原子性とは別の話題、分離性の話題になります。

例えばですが、下のようにユーザーAが口座Aから口座Bに送金するのと同じタイミングでユーザーBが口座Bからお金を引き落とすというケースを考えます。ここで仮に送金のトランザクションと引き落としのトランザクションのコミット前のデータが見えたとすると以下のようなケースが起こり得ます。

f:id:shallow1729:20210517210837p:plain
送金リクエストと引き落としが同時に起きた場合の図。未コミットの値が見える場合、図に示すように送金に失敗しているにも関わらず引き落としに成功してしまう。

最終的に送金トランザクションは失敗したにも関わらず2000円の引き落としに成功していまい、銀行が1000円損してしまいました。この問題の面白いところは引き落としトランザクションのSELECTとUPDATEの間で残高が負にならないかのチェックをアプリケーションでしても効果がない点と、トランザクションの原子性が満たされていても発生する点です。

この問題を防ぐ最もシンプルな方法は並列実行を諦める事です。シングルスレッドだった場合どうしてこの問題が防がれるかというと、以下のどちらかになるからです。

  1. 送金のトランザクションが先に始まった場合、そのトランザクションがCOMMITかROLLBACKされるまで他のトランザクションを受け付けない。送金がrollbackされた後に2000円引き落とそうとしてもrollbackで口座Bの残高は1000円に戻っているので無事失敗する。COMMITされた場合はその後の引き落としに成功する、で問題ない。
  2. 引き落としのトランザクションが先に始まった場合、送金前の口座Bの残高は1000円なので無事引き落としに失敗する。

とはいえシングルスレッドではパフォーマンスの問題が起こります。世の中にはRedisのようにシングルスレッドで動くデータベースもあるのですが、MySQLなどのリレーショナルデータベースでは以下のようにパフォーマンスの課題があるので現実的ではなさそうです。

  1. SQLという複雑なクエリを受け付けるのでCPUのボトルネックがある
  2. Disk Oriented Databaseはストレージからの読み取りが必要なケースもある
  3. 耐障害性も考えると同期的なストレージへの書き込みも必要

なので、なんとか並列実行を行う必要があります。

ロックとパフォーマンスの問題

先ほどの議論でマルチスレッド化をやりたいモチベーションは伝わったと思うのですが、どう実装すれば良いでしょうか? 並列化プログラミングについての知識がある人だと、複数のトランザクションが同じレコードにアクセスする時の問題は複数のスレッドが同時に一つの変数をアクセスする時の問題とよく似ている事に気づくと思います。そして、並列化プログラミングではこういった状況を防ぐために、アクセスするリソースのロックを取るという手法がある事をご存知かと思います。なので、データベースの場合も同じようにロックの仕組みを提供するというのはどうでしょうか?

ロックと一言で言ってもいろいろ戦略はありますが、一例としてここでは、トランザクションがあるレコードに「アクセスする」とロックを取得し、他のトランザクションがそのレコードに対して読み書きしようとすると「COMMITやROLLBACKでロックが手放されるのを待つ」という手法(悲観的ロック)を考えます。

これでもまだ「アクセスする」という言葉がふんわりしていて、いつどの範囲でロックを取るかという話題があります。一つの選択としてUPDATEがされた段階で更新されたデータは「汚れる」ので、UPDATEのタイミングで更新対象のロックを取り、COMMITやROLLBACKをする時にロックを手放すという手はありそうですね。

以下の図に示すように、先ほどの例の場合、送金トランザクションが口座BをUPDATEをした段階で他のトランザクションは口座Bのデータにアクセスできなくなるので、直後の引き落としトランザクションのSELECT文は送金トランザクションがCOMMITかROLLBACKされるまで待つという形になります。これによって未コミットのデータが読まれるのを防ぐことができるので先ほどのように銀行が損をするのは防ぐ事が出来ました。

f:id:shallow1729:20210517192903p:plain
UPDATE時にロックを取ってSELECTを止めるようにした場合。この場合、未コミットのデータを見れないので先ほどの不整合が解決している。

この作戦は今回のように同じレコードについて更新の完了待ちが発生しない限りロック待ちが発生しないのでシングルスレッドよりパフォーマンスは良いと言えますが、シングルスレッドでは起きない以下の図に示すようなおかしな現象が発生します。

f:id:shallow1729:20210517194213p:plain
UPDATE時にロックを取っても起きる不整合の例。コミットをした段階でロックを手放すので、トランザクションBは一つのトランザクション中で同じレコードを見ているはずなのに異なる値が返ってくる。

このような同じレコードを見ているはずなのに違う値が返ってくる事もシングルスレッドで動いていたらありえない事です。この問題を解決する手段の一つはSELECT時にも対象のレコードのロックを取るようにするというものです。そうした場合、トランザクションBの最初のSELECTでロックが取られるので、トランザクションAの更新はトランザクションBのCOMMITを待つことになります。この場合、トランザクションBの複数回の読み取りは同じ結果を返します。

SELECT時にもロックを取る戦略の方がUPDATE時のみロックを取るやり方よりもシングルスレッドで直列にトランザクションが処理される状態により近いのですが、一方でロック待ちの可能性も高くなります。このようにパフォーマンスとトランザクション間の分離度合いの間には相関があり、トランザクション間の分離度合いが上がるほどパフォーマンスが悪化する事が知られています。*1

Multiversion Concurrency Control

先ほどの解説でトランザクションを直列に近い状態にしようとするとパフォーマンスが悪くなっていく様子を確認しました。これはトランザクションを直列にしようとするほどロック待ちの可能性が上がるからでした。ですが、実はロックを取らずにこれらの問題を解決する事が可能です。それがMultiversion Concurrency Controlです。MySQLもこの仕組みを提供しているので先にデモで試してみましょう。以下のようなクエリを一つずつ二つのコンソールから試してみてください。

f:id:shallow1729:20210517193953p:plain
MVCCのサンプル

おそらく各クエリについて、#より後ろのコメントにある結果が得られたと思います。しかもロック待ちも無く即座にレスポンスが返ってきたと思います。このように、ロック待ち無しで先ほど出てきた未コミットの更新が見える問題や同じデータにアクセスしているはずなのに違う結果が返ってくる問題を防ぐ事に成功しています。

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へのポインターを持っているのでどんどん過去に遡る事ができます。

f:id:shallow1729:20210517200652p:plain
レコードとundo logの構造の概略。ROLL_PTRが過去のundo logへのポインターになっている。変更前の差分が保管されているので、ポインターを辿る事で過去のレコードを復元する事ができる。

どのスナップショットを見れば良いかをどうやって決めるか?

過去のスナップショットをログを用いて保管している事は分かりましたが、適切なタイミングのスナップショットをどう取得するか?は別の課題です。イメージ的にはトランザクション毎にタイムスタンプを用意して、自分より古い最新の更新まで遡れば良さそうですが、トランザクションの開始時とコミット時の順序は入れ替わりうるので実際はもう少し厄介です。

まず、InnoDBについて言うと先ほどのundo logに出てきたTRX_IDがタイムスタンプに近い役割をします。この値はトランザクションの開始時*4に払い出されるインクリメンタルなIDなので、大きいほど新しい時刻のものになります。*5このTRX_IDをうまく使って遡り先を決めています。以下にルールをまとめました。

f:id:shallow1729:20210517201652p:plain

  1. まず、自分の更新は見えていて欲しいので自分の更新なら遡るのをやめてレコードを再構成して完了です。
  2. 自分より古いトランザクションであっても未コミットのトランザクションの場合はコミットされても変更が見えてはいけないのでトランザクション開始時にアクティブなトランザクションのTRX_IDのリストを持っておいて、そのリストに入っていたら遡ります。
  3. 自分より大きいTRX_IDの変更の場合は、後から開始したトランザクションによる変更なので遡ります。
  4. 自分より小さいTRX_IDで、トランザクション開始時にアクティブでなければ遡るのをやめます。
  5. 最初の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これは、削除フラグが立っていてもそのトランザクションのスナップショット上では正しい位置のものだったかもしれないからです。ただ、削除フラグは無意味なわけではなくて、削除フラグが立っている葉は先ほどのガベージコレクションの仕組みで削除対象かのチェックをして最終的に削除されます。

f:id:shallow1729:20210517204437p:plain
secondary indexの更新が行われた場合の検索の様子。茶色がsecondary indexで用いられているカラムが更新された葉ノードで、削除フラグが立っている。検索時は削除フラグがついていても自分のスナップショット上では正しい位置のものかもしれないので中のデータを見に行く。削除フラグが立っている葉ノードについてはアクセスされなくなる事がわかった段階で削除される。

最後に

以上で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

ストレージエンジンの話 ~InnoDBのredo logをざっくり理解する~

こんにちは。id:shallow1729です。最近Database Reliability Engineerというお仕事を始めたのでデータベースの勉強をしたりMySQLソースコードを読んだりしています。仕事でMySQLが標準で用いているInnoDBソースコードを読む機会があったのでなんかアウトプットしたいなと思いつついきなりコアな話するのもなって思ったのでざっくりとストレージエンジンの話をしようかなと思います。とはいえストレージエンジンは本当にいろいろな仕事をしていて全部を書こうとするとものすごい事になりそうだった(+僕も分かってない部分が多い)ので、とりあえず第一回はredo logというやつを中心にストレージエンジンを追っていこうと思います。なるべく一般的なデータベースの設計の話を軸に置きつつInnoDBの場合の話もしていこうと思います。読者としてはMySQLのようなリレーショナルデータベースの利用経験があることは前提にしていますが前提として必要なのはそれくらいかなと思います。もしデータベースをもっと深く理解したいと思った方はCarnegie Mellon Universityの公開している講義がとても面白いのでそちらもぜひ見ていただけたらと思います。

www.youtube.com

以下この記事でMySQLの話をしている時はMySQL5.7.32をベースに話しています。また、僕もまだデータベースの勉強を始めて日が浅く、きちんとコードを追わずに書いている箇所もあるので誤りがあればご指摘いただけたらと思います。

ストレージエンジンの役割(の一部)

まずInnoDBなどのストレージエンジンの役割についてざっくりと解説します。データベースへの読み書きのクエリがデータベースに送られた時、データベースはまずSQLのparse、実行計画の作成などを行なったあとにディスクへデータを書き込んだりデータをディスクから読み出したりします。ストレージエンジンはHDDなどの不揮発性のストレージとメモリ(バッファープール)の管理を行い、上位のレイヤー(execution engine)にストレージへの書き込みのインターフェースを提供する仕組みを提供します。一般的にはOSのファイルシステムがディスクの情報をバッファープールに乗せたりバッファープールの情報をディスクに書き込んだりといった仕事を担当しているのですが、データベースの場合は独自の要件が様々あるのでより効率的な読み書きを提供するために独自にこの仕組みを用意しています。バッファープールとストレージのデータ構造についてですが、基本的には同じ(バッファープール上でB+Treeならストレージ上でもB+Treeで、ログはログ)という認識でいいと思います。バッファープールからデータを削除するタイミング、ストレージにデータを反映するタイミング、ストレージからデータをバッファープールに載せるタイミングを処理していると考えるといいかなと思います。ストレージエンジンの役割という意味だと並列実行時のデータのアクセス制御など他にも重要なものがありますが、今回の説明では割愛します。

f:id:shallow1729:20210418202225p:plain
clientのリクエストを返すまでの概観の図です。execution engineはSQLのparseや実行計画を行い、ストレージエンジンに読み書きを行います。ストレージエンジンは読み書きが効率よく行われるようストレージからバッファープールにデータを載せたりバッファープールのデータをストレージに反映させる処理を行います。

Disk Oriented Database

先ほどストレージエンジンはメモリとディスクの間のやりとりをすると説明しましたが、具体的に何をやりとりするかはデータベースの設計思想次第になります。MySQLはDisk Oriented Databaseというデータがメモリに乗り切らない事を前提に設計されたデータベースになるので、バッファープールがいっぱいにならないようにうまくリソースを管理する必要があります。そのため、データの永続性の観点では必ずしも必要ないデータ(例えばあとで説明するundo logなど)もディスクに書き込みが行われます。とはいえ全てをリクエストが来た時に書き込むとレスポンスタイムが悪くなるのでMySQLの場合はデータの永続性の観点で書き込まないといけないもの以外は非同期にバックグラウンドスレッドが書き込んでします。現代のようなメモリの潤沢な環境で開発をしていると永続化しないデータをディスクに書き込んだりしないと思うので、最初はディスクへの書き込みが永続化目的かそうでないかで混乱するかもです。

ちなみにメモリが潤沢なんだからそんな設計しなくてもメモリに乗り切る前提で設計すればもっと効率の良い設計ができるんじゃないか?と思うかもしれません。実際webサービスの開発で車バッファープールのサイズをデータが全部載り切るように調整すると思います。そのようなメモリにデータが全部乗り切る事を前提に設計されたデータベースはIn Memory Databaseと呼ばれていて、VoltDBなどいろいろあるようです。また、Amazon Auroraはあとで説明するredo logという最低限同期的に書き込まないといけないデータのみをバックエンドのKVSに送っているようですが、これもSQLを処理するサーバー自身の仕事からバックグラウンドスレッドの仕事をKVSに寄せる事で負荷分散をしているという事かなと理解しています。

独自でストレージエンジンを持つ理由

先ほどの説明でMySQLのようなDisk Oriented Databaseはバッファープールにデータが乗り切らない事を前提に設計されている事が分かりました。次に、なぜこのバッファープールの管理をOSのファイルシステムでなく独自に管理するのか?という事を説明します。

まず、同期的な書き込みとそうでないバッファープールを介した書き込みを使い分けることはOSのファイルシステムでも管理ができます。例えばfsyncを使えば同期的に書き込めます。

独自に管理しないといけないケースとしては、例えばバッファープールから消すデータを選ぶ処理があります。あとで詳しく説明するのですが、例えばinsertが行われた時にB+Treeにそのレコードを同期的にストレージに挿入する必要はcrash recoveryの観点では無いのですが、バッファープールから未反映のデータを削除すると再読み込みが大変になるのでフラグを立てて反映してから削除するようにする必要があります。また、なるべくアクセスされていないデータから順に削除しないとすぐに再読み込みが発生する可能性が高まるので、ホットなデータをうまく見分けてバッファープールの管理をする必要があります。また、where句などで複数のレコードにアクセスされる場合は次にアクセスされるレコード(実際はストレージエンジンはページというもう少し大きい単位で管理していますが、レコードと思ってもそこまでおかしくならないと思うので今回はレコードで統一します。)をバッファープールに先読みして乗せておくとパフォーマンスが上がります。こういった処理もB+Treeの事を知っていないとできないのでOSには難しい処理になります。このように、データベースの機能を理解しないとうまくバッファープールを管理できないのでストレージエンジンを独自に用意する必要が出てきます。

f:id:shallow1729:20210418205300p:plain
B+ Tree indexのサーチの図。次に読むデータを先読みしてBuffer poolに載せたいがどれが次のデータかはB+Treeを知っていないと分からない。

レコードのデータ配置

なんとなくストレージエンジンの仕事が把握できたかと思うので今回の主題のInnoDBredo logとundo logの話に行こうと思ったのですが、そのためにはレコードのデータをストレージ上でどう管理するかという話題も話した方がいい気がしたのでもう少し寄り道します。ストレージ上でのデータ配置を説明する理由は、ストレージのランダムアクセスが非常に遅くデータ配置がパフォーマンスに強く影響するためです。なので、三つほどデータ構成のモデルを紹介してメリットデメリットを考えます。かなり簡略化しているので詳細に興味がある場合はCMUの講義のChapter 3, Chapter 4をご参照ください。

まず一番簡単に思いつくのはレコードの情報をそのまま横に並べるようなデータ構造で、update時はこのレコードの値を修正する、select時はこの一連のデータを読み取るという形で実現できます。この配置はn-ary storage modelという構成で、レコード単位でのデータの読み取りが非常に簡単で、書き込みも単純に該当レコードを検索して更新すれば良いです。InnoDB含め広く採用されています。

次に紹介するのはDecomposition Storage Modelという構造で、これは複数のレコードについて同じカラムのデータを近い場所に配置しています。このデータ配置のメリットとしては、テーブル全体を集計するような集計系のワークロード(OLAP)に対して、集計に必要なカラムだけにアクセスする事ができる点があります。そのためGoogle BigQueryなどのデータウェアハウスで広く用いられています。n-ary modelではたとえ集計に使うカラムがレコードの中に一つであってもフルスキャンになってしまうのでこの点でDecomposition Storage Modelは優れています。一方で一レコードの複数のカラムをupdateしたい時にn-ary modelだと単に対象レコードを検索してupdateするだけだったのが、このモデルだとディスク上の離れたカラムに書き込みに行くのでランダムアクセスが発生してしまいます。なので、シンプルな書き込みが頻繁に発生するOLTPにはn-ary modelが採用されています。これはweb開発でMySQLのようなn-ary modelを採用しているデータベースを用いる理由の一つでもあります。

ここまで説明したn-ary modelとDecomposition Storage Modelは1レコードに対して一つのマスターデータがあって、update時はそのデータを上書きするようなモデルでした。最後に紹介するlog structured file organizationはupdate時に上書きするのではなくログを追加するようなモデルです。このモデルは頻繁に更新されるレコードについてはログがどんどんたまっていっていくので読み取り時は都度最初からリプレイする必要があってパフォーマンスが悪いです。しかし、メリットとしては複数のレコードを更新する時にたとえそれらがストレージ上は離れていてもランダムアクセスが発生しないので書き込みが高速になります。InnoDBなどのストレージエンジンではこの形式は読み取りが大変なのでデータを読みに行く時には使っていないのですが、実はinsertやupdateなどの書き込み系の処理が走る時にcrash recoveryできるようにする目的で同期的に書き込むのはここで説明したようなログの形式のデータ(redo log)になります。(正直書いていてredo logをlog structured file organizationと呼ぶのは不適切かもなと思いました。ここで伝えたかった事はレコードを構成するにはカラムのデータを書かなくてもログだけでも再構成できるよという事でした。以下では単にログ形式と表現します。)

f:id:shallow1729:20210418214142p:plain
n-ary model, Decomposition Storage Model, log structured file organizationのそれぞれのデータ構成の図です。idnはレコードのユニークid、cnはカラムの種類です。n-ary modelはレコード単位でカラムのデータが近い配置で置かれています。Decomposition Storage Modelはレコードをまたがって同一カラムのデータが近い配置で置かれています。log structured file organizationではupdate時は変更したカラムの値のログを残し、delete時も削除を行わずログだけ残しています(ログの形式はイメージです。)

redo log

redo logは書き込み実行後の状態を残していくログで、障害復旧時にcommit済の内容をレコードに書き込むのに使えるログです。InnoDBはもう一つundo logというログも持っていて、こちらは変更前の値を残すログになります。こちらはトランザクションのrollbackの際や、MVCCという古いレコードの状態を参照したい時に用います。undo logについては別の記事で紹介します。

InnoDBredo logとレコードの関係

先ほどの説明でInnoDBがn-ary modelで構成されたレコードとログ形式(redo log)の二つのモデルを採用している事が分かりましたが、これらはどういう関係なのかについて解説していきます。

まず、基本的にレコードの読み取り時はredo logは参照しません。読み取り時はバッファープール上のレコードの形式で保管されたデータを読みにいきますし、書き込む時もバッファープール上のレコードを書き込みます。ここでバッファープールはメモリなのでディスクアクセスに比べてランダムアクセスの問題は特に気にしなくて大丈夫です。このように、基本的にはバッファープールの上の読み書きで完結するようにしています。ただ、書き込みをバッファープールだけで済ませて書き込み成功を返してしまうと、もしストレージに反映する前にデータベースがクラッシュしてしまうとそのデータは消えてしまいます。

f:id:shallow1729:20210419002616p:plain
insertをcommitした時にバッファープールにだけ書き込んで成功を通知したけど実はストレージに書き込む前にクラッシュした場合の図。バッファープールの青色の箇所が同期的に反映したレコードです。ユーザーは書き込みに成功したと思っていますがサーバーを再起動するとそのデータは消えてしまっています。

そのため同期的に何かしら書き込む必要があるのですが、InnoDBを含め一般にこれにはログ形式を用いています。このログを用いた手法をwrite ahead log(WAL)と呼ぶのですが、crash recoveryの観点で重要な事はログを書くというよりは間にワンクッション置く事の方が重要で、例えばログを使わない方法としては更新時は更新後のレコードをストレージの別の場所に書いて、書き込みが完了したら参照の向け先を変えるような方針も可能です。ログ形式は読み取りが大変なので障害からの復旧には時間がかかりそうですが、障害が滅多に起きないなら障害時のパフォーマンス上のデメリットより書き込み速度のメリットが大きそうです。以下の図でログのワンクッションを置く事で障害復旧できないデータが発生する事を防げる事を示します。

f:id:shallow1729:20210418230642p:plain
直接ストレージのレコードを書き込みに行った場合の図です。上から下の時系列でinsertしたデータをupdateしようとしており、updateをストレージに書き込む時にクラッシュが発生した場合を想定します。もし書き込み途中でクラッシュが発生すると書き込み中のデータは中途半端になる可能性があり、元のデータの情報もupdate後の値の情報も残っていないのでに変更する事もできない復旧できなくなってしまいます。
f:id:shallow1729:20210418231302p:plain
間にログを挟んだ場合の図です。ログの形式はいったん"end"で終わっていたら書き込み成功とします。図はログの書き込み中にクラッシュした場合になります。この場合レコードのデータはまだ触れられていない状態なのでログを単に捨ててしまえば良いです。ログの書き込みは同期的に行うのでユーザーはcommitの成功を受け取っていないのでこれで問題ないです。また、ログの書き込みは完了しているけどレコードへの反映が中途半端な状態の時はログを元にレコードを復元すればよくなります。

ちなみにredo logの書き込みのタイミングですが、基本的にinsertやupdate時にバッファープールに書き込まれて、transactionのcommit時にストレージに反映させるという感じです。*1注意点として、MySQLのユーザーの感覚だとtransactionを明示的にcommitするのは複数のテーブルにまたがってinsertする時などかと思いますが、MySQL的には一レコードのinsertであっても内部的にはtransactionの開始、insert(レコードやログをバッファープールに書き込む)、commit(ログをストレージに反映)という流れです。なぜcommit時までストレージへの反映を待つかというと、commitされていない場合はユーザーにまだデータが反映された事を約束しておらず、障害時は消えてもよい変更だからです。(ただしDisk Oriented Databaseなのでバッファープールの管理の一環でディスクに書き込まれるのはあると思います。その場合はむしろゴミ掃除になるはずです。)

ちなみに正常時にいつレコードに書き込んだデータをストレージに反映しているかというと、MySQLではpage cleaner threadというバックグラウンドスレッドが担当しているようです。(まだこの辺ちゃんと把握しきれてないのでバックグラウンドスレッドが間に合わなかったらどうなるかなど分かってないです。*2 )基本的にはバッファープールとストレージのデータは同一の形式なので普段はバッファープールのデータをそのままストレージに反映させる方向のはずです。redo logが用いられるのは本当にクラッシュ時と、おそらくクラッシュ時の復旧速度を上げるために最近のログまで反映しきるcheckpointの作成時ぐらいなんじゃないかなーと思います。以下に概略図を置きます。

f:id:shallow1729:20210516220653p:plain
データの書き込み時の反映のタイミングの図。青色は書き込みリクエスト時に同期的に書き込む場所で、緑色はバックグラウンドスレッドやリブート時などの同期的でないタイミングのものです。書き込みのリクエストがあった場合はBuffer poolのレコードとredo log bufferへのredo logの書き込みはどちらも行われ、redo logについてはストレージにsyncします。(正確にはsyncはコミットのタイミングを待ちます。)redo logを用いるのはcrash recoveryと、それを高速化するためのチェックポイントの作成時のみで、正常時はbackground threadでbufferpoolのレコードをストレージの領域に反映させます。ちなみにここではレコードとredo logのみしか書き込んでいませんが、実際にはundo logなど他にもいろいろ書き込んでいます。

最後に

今回はストレージエンジンの役割をredo logを中心にざっくりと見ていきました。redo logはcrash recoveryというデータベースの重要な機能の主役になります。次回はundo logというInnoDBが扱うもう一つのログを見ていきます。(実は本当に話したかったのはundo logで、redo logとundo logの役割は独立しているのでいきなりundo logの話を書いても良かったのですが、フォーマット的には対になっているしredo logの方が主役っぽい仕事をしているのでredo logを説明せずにundo logを説明する事に気が引けてしまいました。)ある程度基礎的な概念を出したらソースコード紹介的な記事も書いていきたいと思います。長々と書きましたが最後まで読んでくださってありがとうございました。データベースは非常に長い歴史があり、現在進行形で発展の進んでいる面白い分野なのでこの機会にぜひ興味をもっていただけたらと思います。以上です。

*1:追記: InnoDBではログバッファーとバッファープールは別で管理されているようなのでこの記述は間違いです。InnoDBアーキテクチャの図のurlを貼りましたので参照ください。

https://dev.mysql.com/doc/refman/8.0/en/innodb-architecture.html

*2:追記: 書き込みが多い時はログバッファーの方が普通先に枯渇するので、ログバッファーを見て必要に応じてdirty pageをflushするという挙動のようです。https://dev.mysql.com/doc/refman/5.6/ja/innodb-performance-adaptive_flushing.html

転職しました

別に退職/入社エントリーみたいなのを書くつもりは無かったんですけど、今後ここに何か書いた事が何か良くない方向に行った時に前の所属の人間の言葉として広まって迷惑かけたら嫌だなと思ってという感じで書いたエントリーです。1月いっぱいで退職しました。僕は前職に居た事を誇りに思っているので、今後とも僕が周りの人に自慢できるようこれからも高い技術力でインターネットコミュニティを支えてもらえると嬉しいです。僕は僕の目指す方向で精一杯頑張ります!