ReadViewを読む(1)
ReadViewとは、InnoDBのMVCCで使われているスナップショット的なやつで、トランザクション分離レベルがREAD COMMITED, REPEATABLE READの時に使われています。その仕組みを実装を追いながら調べてみました。
トランザクション分離レベルのおさらい
SERIALIZEBLE
trxを直列に実行する。パフォーマンスの観点から基本採用しない。
REPEATABLE READ
trx開始時にCOMMIT済みのデータだけ読み取る。
同一trx内で複数回データの集計処理を行うとき、その間別のtrxがCOMMITしたレコードの追加,削除の結果が反映される = Phantom Readが起きる。
READ COMMITTED
trx開始以降にCOMMITされたデータも読み取る。
同一trx内で複数回データを読み取るとき、その間別のtrxがCOMMITすると前後で読み取り結果が異なる = Fuzzy Readが起きる。Phantom Readも起きる。
READ UNCOMMITED
COMMITされてないデータを読み取る = Dirty Readが起きる。Fuzzy Read、Phantom Readも起きる。
ReadViewとMVCCの挙動
この記事がわかりやすかったので、参考にしながら説明する。
なぜMVCCが必要なのか
SERIALIZEBLE以外のトランザクション分離レベルでは、複数のトランザクションを同時実行できる一方、トランザクション同士の独立性が損なわれる。つまり上に書いたようなPhantom Read、Fuzzy Readが起きてしまう可能性がある。それを回避するためにはSELECT … LOCK IN SHARE MODEやSELECT … FOR UPDATEを使って、実際のレコードに対してロックを取得して読み取ればよい。しかしその場合、ロック待ちによるパフォーマンス劣化の問題が生じてしまう。
InnoDBでは別の解決方法として、実際のレコードではなく、そのsnapshotをロックなしで読み取ることで、同時実効性を損なうことなく独立性を担保している。その仕組みがMVCC(MultiVersion Concurrency Control)である。
関連ワード
ReadViewの説明のために必要な用語を挙げる。
Transaction ID(trx_id)
trxが実行されるたび、そのtrxに対してauto-incrementに付与されるID。
Undo Log
InnoDBでは、あらゆるテーブルに対してdb_trx_id, db_roll_pointerという2つのカラムが暗黙的に追加される。レコードが更新される前、今のレコードの値(current version)をUndo Logとしてコピーして、db_roll_pointerにUndo Logへのポインタを入れる。db_trx_idには、レコードを更新したtrx_idが入る。
Undo Logによって、
- trxがROLLBACKしたら、前のversionを復元する
- トランザクション分離レベルによってcurrent versionが読み取れない場合は、読み取れるversionまでUndo Logを辿る
ことが可能になる。またレコード削除時、InnoDBはまずdeleted flagを立てて論理削除を行い、他の更新と同様にUndo Logを作る。なのでDELETEのROLLBACKも過去のversionを辿ることも可能。
ReadViewの仕組み
ReadViewはtrxがSnapshot readを行う際に生成されるデータ構造である。
主な変数
- creator_trx_id: ReadViewを生成したtrx_id
- trx_ids: active(まだCOMMITされていない)trx_idのリスト。creator_trx_idは含まれない
- low_limit_id: 次に割り当てられるtrx_id
- up_limit_id: trx_idsの最小値
ロジック
読み取ろうとしたレコードのcurrent versionに対して、以下のロジックの元読み取り可能か判定する。
- db_trx_idがcreator_trx_idと同じ場合、current trx内で更新されたレコードなので読み取り可能
- db_trx_idがup_limit_idより小さい場合、既にCOMMIT済みのtrxで書き込まれたversionなので読み取り可能
- db_trx_idがlow_limit_idより大きい場合、current trxよりも後に開始されたtrxで書き込まれたversionなので読み取り不可
- db_trx_idがup_limit_idとlow_limit_idの間の場合、trx_idsにそのidが含まれているか確認する
a. 含まれる: ReadView作成時にはまだactiveなtrxで書き込まれたversionなので、読み取り不可
b. 含まれない: ReadView作成時には既にCOMMIT済みのtrxで書き込まれたversionなので読み取り可能
ロジックのフローチャート
ReadViewを使ったMVCCの挙動
- トランザクション開始時(BEGIN)に、そのtrxのIDすなわちtrx_idが決まる
- SELECT実行時にReadViewを用意する
a. REPEATABLE READならtrx内で1つのReadViewを使い回す
b. READ COMMITEDならSELECTの度に作り直す - SELECT条件にマッチしたデータがあった場合、そのtrx versionとReadViewを比較する
- 3.の結果、ReadViewのルールにマッチしなかったデータは、ルールにマッチするまでそのUndoLogを遡って、過去のtrx versionのsnapshotを取得する
trxは直列に実行するSERIALIZEBLE、常に最新のデータを取得するREAD UNCOMMITEDの場合にMVCCは不要。残り2つの場合にReadViewを作るタイミングが違うのは以下のように説明できる。
- REPEATABLE READ
- 1つのtrx内で1つだけReadViewを作る
- InnoDBではReadViewを使うことで、trx開始時点でCOMMIT済みのデータだけ読み取るようになるので、Phantom Readは起きない
- “その間別のtrxがCOMMITしたレコードの追加,削除の結果” として存在するデータのtrx versionは、 “ReadView作成時にはまだactiveなtrxで書き込まれたversionなので、読み取り不可” になるため
- READ COMMITTED
- SELECT実行のたびにReadViewを作り直す → 都度COMMIT済みのデータを取れるようになる
ReadViewの実装を覗いてみる
storage/innobase/include/read0types.h にある ReadView クラスがその実装である。
ReadViewの実装 で説明した変数は、名前は完全一致しないがprivate変数としてこのクラスが持っている。
/** The view does not need to see the undo logs for transactions
whose transaction number is strictly smaller (<) than this value:
they can be removed in purge if not needed by other views */
trx_id_t m_low_limit_no;
m_low_limit_no(このブログだとlow_limit_id)のコメントにある “strictly” に、「トランザクション分離レベルで振る舞いが変わるよ」というニュアンスを感じる。
フローチャートで表したロジックは、 changes_visible() というメンバ関数で実装されている。
1つめ2つめのif else文がフローチャートの分岐1,2,3と一致している。最後のbinary_searchはそのままの意味で二分探索をして、idがm_idsに含まれるかを判定している=フローチャートの最後の分岐を実装していそう。
イテレータ範囲[first, last)から、二分探索法によって条件一致する要素の検索を行う。
気になるのは change_visible() の引数がtable nameなこと。行ごとのdb_trx_idを見て、visibleか判定していると思っていたけど。
こうなると実際にデバッグして動きを見てみるのが早そう!!
ということで「ReadViewを読む(2)」へ続く...
Discussion