ストレージエンジンの話 ~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:20210418234028p:plain
データの書き込み時の反映のタイミングの図。青色は書き込みリクエスト時に同期的に書き込む場所で、緑色はバックグラウンドスレッドやリブート時などの同期的でないタイミングのものです。書き込みのリクエストがあった場合はBufferpoolの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