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

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月いっぱいで退職しました。僕は前職に居た事を誇りに思っているので、今後とも僕が周りの人に自慢できるようこれからも高い技術力でインターネットコミュニティを支えてもらえると嬉しいです。僕は僕の目指す方向で精一杯頑張ります!

Atcoderで緑色になりました

8月に始めて半年で緑になれました。緑は大した事ないって声をたまに聞くのですが普通にプログラミングの実装能力を求められると思うので緑コーダーですって言われたら僕ならエンジニアとして信頼するだろうなと思いました。

f:id:shallow1729:20210110235713p:plain
https://atcoder.jp/users/shallow1729

とはいえ緑ってatcoderの中ではまだまだ序盤なので弱点がたくさんある状態なのかなとも思います。僕の場合全探索以外のグラフのアルゴリズムやセグメント木みたいな高度なデータ構造は使いこなせていないのが露骨な弱点だなって感じています。一方で自分のアルゴリズムやデータ構造の知識の範囲で解ける問題はそこそこ解けると感じているので自分の知識を元にアルゴリズムを組み立てる力とかはまあまああるのかなって思っています。

次は水色目指して頑張ります!

AtCoder Beginner Contest 186に参加しました!

結果

atcoder.jp

ABCDの四問解けました。E解けそうだったので悔しい...

振り返り

Cまでは一瞬でした。

C - Unlucky 7 は8進数だとpythonはそういうメソッドがあるので脳死で解けてしまいましたね...今後のために任意のn進数への変換は何かライブラリ作っておきたいなって気持ちになりました。

D - Sum of difference は実装は簡単だけど頭使わないといけない系だから解けた時は自分に対して頭いい!って言ってたけど参加者の中では別に解けたの早かったわけじゃないんだなって分かってびっくりしました。つくづく思うんですけどプログラミングコンテストやってる人みんなむっちゃ頭いいですよね。

E - Throne今朝ぼーっと見てたサイトの記事とまんま一緒っぽそうでした。気づいてはいたんですけど中身読んで理解するのに時間がかかったのと、modでの割り算、除数が素数の場合にしか対応してなかったからそっちの対応してたら時間が足りませんでした。パッと直せたら良かったんですけどねー。人のコード理解するのが遅いのも問題だしライブラリが充実していないのも問題ですね。後者は時間をかければ解決するのでまあいいんですけど、前者はなんかうまい方法論見つけたいなー。最近Code Readingという本を読み始めたからうまくやっていきたいです。

Fはまだ見てないです。

良かった事

Atcoder初心者が成績アップに繋がったと感じた考え方の工夫 - shallowな暮らし で問題の解き方に困った時の考え方をまとめたんですけど、D問題はうまく生かされましたね。特に「簡略化した問題を考える」っていう方針が今回は効いてて、ソートされてたら絶対値取れて簡単だねって思いついて、良く考えたら普通にソートしたらええやんってなった感じでした。ちょっと前までだと何もできずに時間を溶かしてた気がします。仕事も含めてですけど最近はどちらかというと考え方とか概念的理解みたいな抽象的な根っこの部分よりは具体的な知識がボトルネックになってきていると感じているので、しばらくは知識をつける方にフォーカスしたいなって思っています。今の自分が昔見た本とかを読み返すとどう感じるか、みたいなのが今から楽しみです。

そんなわけで、とりあえず今回も点数には反映されなかったけど成長を実感できたのでまあよかったかなって思います。次こそE問題解きたい...!!!