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
ストレージエンジンの話 ~InnoDBのredo logをざっくり理解する~
こんにちは。id:shallow1729です。最近Database Reliability Engineerというお仕事を始めたのでデータベースの勉強をしたりMySQLのソースコードを読んだりしています。仕事でMySQLが標準で用いているInnoDBのソースコードを読む機会があったのでなんかアウトプットしたいなと思いつついきなりコアな話するのもなって思ったのでざっくりとストレージエンジンの話をしようかなと思います。とはいえストレージエンジンは本当にいろいろな仕事をしていて全部を書こうとするとものすごい事になりそうだった(+僕も分かってない部分が多い)ので、とりあえず第一回はredo logというやつを中心にストレージエンジンを追っていこうと思います。なるべく一般的なデータベースの設計の話を軸に置きつつInnoDBの場合の話もしていこうと思います。読者としてはMySQLのようなリレーショナルデータベースの利用経験があることは前提にしていますが前提として必要なのはそれくらいかなと思います。もしデータベースをもっと深く理解したいと思った方はCarnegie Mellon Universityの公開している講義がとても面白いのでそちらもぜひ見ていただけたらと思います。
以下この記事でMySQLの話をしている時はMySQL5.7.32をベースに話しています。また、僕もまだデータベースの勉強を始めて日が浅く、きちんとコードを追わずに書いている箇所もあるので誤りがあればご指摘いただけたらと思います。
ストレージエンジンの役割(の一部)
まずInnoDBなどのストレージエンジンの役割についてざっくりと解説します。データベースへの読み書きのクエリがデータベースに送られた時、データベースはまずSQLのparse、実行計画の作成などを行なったあとにディスクへデータを書き込んだりデータをディスクから読み出したりします。ストレージエンジンはHDDなどの不揮発性のストレージとメモリ(バッファープール)の管理を行い、上位のレイヤー(execution engine)にストレージへの書き込みのインターフェースを提供する仕組みを提供します。一般的にはOSのファイルシステムがディスクの情報をバッファープールに乗せたりバッファープールの情報をディスクに書き込んだりといった仕事を担当しているのですが、データベースの場合は独自の要件が様々あるのでより効率的な読み書きを提供するために独自にこの仕組みを用意しています。バッファープールとストレージのデータ構造についてですが、基本的には同じ(バッファープール上でB+Treeならストレージ上でもB+Treeで、ログはログ)という認識でいいと思います。バッファープールからデータを削除するタイミング、ストレージにデータを反映するタイミング、ストレージからデータをバッファープールに載せるタイミングを処理していると考えるといいかなと思います。ストレージエンジンの役割という意味だと並列実行時のデータのアクセス制御など他にも重要なものがありますが、今回の説明では割愛します。
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には難しい処理になります。このように、データベースの機能を理解しないとうまくバッファープールを管理できないのでストレージエンジンを独自に用意する必要が出てきます。
レコードのデータ配置
なんとなくストレージエンジンの仕事が把握できたかと思うので今回の主題のInnoDBのredo 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と呼ぶのは不適切かもなと思いました。ここで伝えたかった事はレコードを構成するにはカラムのデータを書かなくてもログだけでも再構成できるよという事でした。以下では単にログ形式と表現します。)
redo log
redo logは書き込み実行後の状態を残していくログで、障害復旧時にcommit済の内容をレコードに書き込むのに使えるログです。InnoDBはもう一つundo logというログも持っていて、こちらは変更前の値を残すログになります。こちらはトランザクションのrollbackの際や、MVCCという古いレコードの状態を参照したい時に用います。undo logについては別の記事で紹介します。
InnoDBのredo logとレコードの関係
先ほどの説明でInnoDBがn-ary modelで構成されたレコードとログ形式(redo log)の二つのモデルを採用している事が分かりましたが、これらはどういう関係なのかについて解説していきます。
まず、基本的にレコードの読み取り時はredo logは参照しません。読み取り時はバッファープール上のレコードの形式で保管されたデータを読みにいきますし、書き込む時もバッファープール上のレコードを書き込みます。ここでバッファープールはメモリなのでディスクアクセスに比べてランダムアクセスの問題は特に気にしなくて大丈夫です。このように、基本的にはバッファープールの上の読み書きで完結するようにしています。ただ、書き込みをバッファープールだけで済ませて書き込み成功を返してしまうと、もしストレージに反映する前にデータベースがクラッシュしてしまうとそのデータは消えてしまいます。
そのため同期的に何かしら書き込む必要があるのですが、InnoDBを含め一般にこれにはログ形式を用いています。このログを用いた手法をwrite ahead log(WAL)と呼ぶのですが、crash recoveryの観点で重要な事はログを書くというよりは間にワンクッション置く事の方が重要で、例えばログを使わない方法としては更新時は更新後のレコードをストレージの別の場所に書いて、書き込みが完了したら参照の向け先を変えるような方針も可能です。ログ形式は読み取りが大変なので障害からの復旧には時間がかかりそうですが、障害が滅多に起きないなら障害時のパフォーマンス上のデメリットより書き込み速度のメリットが大きそうです。以下の図でログのワンクッションを置く事で障害復旧できないデータが発生する事を防げる事を示します。
ちなみに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の作成時ぐらいなんじゃないかなーと思います。以下に概略図を置きます。
最後に
今回はストレージエンジンの役割を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月に始めて半年で緑になれました。緑は大した事ないって声をたまに聞くのですが普通にプログラミングの実装能力を求められると思うので緑コーダーですって言われたら僕ならエンジニアとして信頼するだろうなと思いました。
とはいえ緑ってatcoderの中ではまだまだ序盤なので弱点がたくさんある状態なのかなとも思います。僕の場合全探索以外のグラフのアルゴリズムやセグメント木みたいな高度なデータ構造は使いこなせていないのが露骨な弱点だなって感じています。一方で自分のアルゴリズムやデータ構造の知識の範囲で解ける問題はそこそこ解けると感じているので自分の知識を元にアルゴリズムを組み立てる力とかはまあまああるのかなって思っています。
次は水色目指して頑張ります！
AtCoder Beginner Contest 186に参加しました！
結果
ABCDの四問解けました。E解けそうだったので悔しい...
振り返り
Cまでは一瞬でした。
C - Unlucky 7 は8進数だとpythonはそういうメソッドがあるので脳死で解けてしまいましたね...今後のために任意のn進数への変換は何かライブラリ作っておきたいなって気持ちになりました。
D - Sum of difference は実装は簡単だけど頭使わないといけない系だから解けた時は自分に対して頭いい！って言ってたけど参加者の中では別に解けたの早かったわけじゃないんだなって分かってびっくりしました。つくづく思うんですけどプログラミングコンテストやってる人みんなむっちゃ頭いいですよね。
E - Throne は今朝ぼーっと見てたサイトの記事とまんま一緒っぽそうでした。気づいてはいたんですけど中身読んで理解するのに時間がかかったのと、modでの割り算、除数が素数の場合にしか対応してなかったからそっちの対応してたら時間が足りませんでした。パッと直せたら良かったんですけどねー。人のコード理解するのが遅いのも問題だしライブラリが充実していないのも問題ですね。後者は時間をかければ解決するのでまあいいんですけど、前者はなんかうまい方法論見つけたいなー。最近Code Readingという本を読み始めたからうまくやっていきたいです。
Fはまだ見てないです。
良かった事
Atcoder初心者が成績アップに繋がったと感じた考え方の工夫 - shallowな暮らし で問題の解き方に困った時の考え方をまとめたんですけど、D問題はうまく生かされましたね。特に「簡略化した問題を考える」っていう方針が今回は効いてて、ソートされてたら絶対値取れて簡単だねって思いついて、良く考えたら普通にソートしたらええやんってなった感じでした。ちょっと前までだと何もできずに時間を溶かしてた気がします。仕事も含めてですけど最近はどちらかというと考え方とか概念的理解みたいな抽象的な根っこの部分よりは具体的な知識がボトルネックになってきていると感じているので、しばらくは知識をつける方にフォーカスしたいなって思っています。今の自分が昔見た本とかを読み返すとどう感じるか、みたいなのが今から楽しみです。
そんなわけで、とりあえず今回も点数には反映されなかったけど成長を実感できたのでまあよかったかなって思います。次こそE問題解きたい...!!!
Atcoder初心者が成績アップに繋がったと感じた考え方の工夫
こんにちは。id:shallow1729です！この記事ははてなエンジニア Advent Calendar 2020の7日目の記事です。
昨日は
id:stefafafanさんで「iTerm2の機能を使いこなして日頃の作業の効率をあげたい2020」でした！
iTerm2僕も使ってるはずなんですけど知らない機能がいっぱいでした。
はじめに
この記事は半年ほど前から参加していたAtcoderというプログラミングコンテストを振り返って、特に成績アップに繋がった問題を解く時の思考方法の工夫について書いたものです。まだ始めて4ヶ月ほどで十分に参加できていないのでまだ茶色ですが、ここ三回はパフォーマンスが一気に上がって、Atcoder Begineer Contest(以下ABC)の問題ならD問題までは安定して解けるようになってきましたし、E問題も方針はうまく選べるようになってきました。まだまだ初心者ですが、工夫が成長に繋がった事がすごく嬉しかったので試した事をいろいろ書いてみようと思います。なお、この記事ではABC181からABC184の問題のネタバレも入っているのでそういうのが嫌な人はブラウザバックしてもらえたらと思います。
アルゴリズムの勉強
メインの考え方の話の前にアルゴリズムの知識に関する話から入ります。プログラミングコンテストに参加するとなるとアルゴリズムの知識が結構いると思っていたのですが、少なくとも僕が参加していたABCのD問題ぐらいまでだと、自分の実装の計算量を見積もるなどの基本的なアルゴリズムの解析やメモ化を使った高速化はできる必要がありますが、名前のあるアルゴリズムの実装についての知識はそれほど多くは求められていないような印象です。計算量の見積もりが重要な理由は、コンテストの制限時間は結構短いので、明らかに間に合わなそうな実装の時はパフォーマンス改善を考えたり、逆に不必要にパフォーマンスチューニングをして実装コストを増やさないなどの判断を素早くできる必要があるからです。経験上はO()あたりがギリギリ間に合うか間に合わないかという感覚なのでそういうイメージで設計をすると良い気がします。ただ、もう少しテクニカルなアルゴリズムの知識についていうと、スタックやキュー、グラフの全探索あたりは頻繁に出てくるので実装に慣れておく必要があるかなと思います。あと、場合の数を求める問題などで出てくるでかい素数で割った余りを答えよみたいな奴対策でmod計算用のライブラリは事前に用意しておいたほうがいいと思います。modの計算というのはこちらで紹介されているようなやつです。
drken1215.hatenablog.com これだけは持っておかないと方針があってる回答でもTLEになってしまったりするので。。。
E問題になると整数問題で使うアルゴリズムや二分探索、Union-Find Treeなど、もう少しアルゴリズムの知識を必要とする問題も出てくる印象なので勉強はやっとくに越した事は無いと思います。ただ、知識があるのと実際に知識を使えるようになる事の間は結構あると感じているので、知識があれば問題が解けるかというとそうでは無いと思います。
数学的な問題解決の思考方法
今回メインで書きたかったのは数学の問題を解く時によくやるような試行錯誤のテクニックです。数学の勉強ってもちろん覚えないといけないことがたくさんありますけど、大事なのはそれをうまく使って問題を解くところというのは受験などを経験した人は分かるんじゃないかなと思います。そこの能力って才能として見られがちですが、案外訓練で改善できるものだと思っています。実際数学の問題解決の方法についてはいくつか本があって、有名な本だとG.Polyaの「いかにして問題をとくか」があると思います。今回はそういう試行錯誤の技術について、実際の問題を解いた時の思考の流れと一緒に説明できたらなと思います。
実験する
見慣れない問題や方針に困る問題を見たらとりあえず手を動かしてみましょう。いくつか試してみるとアイデアが思いつく事があると思います。
なんか難しそうな問題ですね。難しそうな問題はとりあえず手を動かしてみましょう。(0, 0)から(100, 0)だと(0, 0)->(50, 50)->(100, 0)で二手、(0, 0)から(101, 0)だと(0, 0)->(50, 50)->(100, 0)->(101, 0)で三手になりそうです。じゃあ(0, 0)から(105, 0)なら四手になるかというとそうはならなくて(0, 0)->(52, 52)->(104, 0)->(105, 0)で三手になってしまいます。こんな感じで実験をすると最大でも三手でクリアできると分かってくるんじゃないかなと思います。あとは一手か二手か三手かを判定する方法を考えるという形になります。(この場合分け難しかったんですよね。。。今後の反省点です。。。)
全ての都市間について移動ができるようなグラフの問題に見えます。グラフの問題として全探索を行っても解けるかなと思いますが、実際に経路を並べてみるともっと単純なパターンが見えてきます。4都市の場合は例にあるように
- 1->2->3->4->1
- 1->2->4->3->1
- 1->3->2->4->1
- 1->3->4->2->1
- 1->4->2->3->1
- 1->4->3->2->1
というパターンがあります。1を除くと2, 3, 4については単純に順列の全列挙になっている事がわかります。順列の全列挙はPythonだとitertoolsで用意されているのでそれを使ってしまえば良いという感じです。これを紹介した理由として、実験する時は元の問題の文章に引っ張られずにフラットに見ると良いよと伝えたかったからでした。もちろん問題文から得られるイメージは解決に役立つ事もありますが、変にバイアスになって重要な性質を見落としたりする事もあるので要注意です。
逆から考える
問題の道筋が見えない時はゴールから逆算するという戦略が有効です。
この問題は各人iについてから
までの間
リットル水を使おうとした時に使おうとする水の量がWを超える瞬間があるか？という事に答える問題です。NとTが 最大で
なので単純に時刻ごとに全件を足してると間に合わなさそうです。この問題に答えるために各時刻で使われる水の量の総和さえあれば良さそうです。ある時刻に使われる水の量の総和は「その一つ前の時刻に使われている水の量」+「その時刻に使い始める水の量」-「その時刻に使うのをやめる水の量」で求められます。つまり、この問題を解くためにはこれらの情報を準備すればいい事がわかります。「その時刻に使い始める水の量」は時刻
の関数として
で初期化の時に計算できる。「その時刻に使うのをやめる水の量」についても同様ですね。「一つ前の時刻に使われている水の量」は初期値0で時間発展の中で都度計算されるものなので特別な準備は不要です。このようにすると計算時間が間に合うようになります。大事なのは問題を解くのに必要なデータ構造を先に考えて、それをもらった入力から作れるか？と考えた点です。ゴールから考えた事で実装までの流れが見えやすくなりました。
簡略化した問題を考える
複雑な問題をそのまま解くのではなくて、それをもう少し簡単な問題にした時に解けるかを考えてそこから考えるという奴です。
atcoder.jp 例えばこの問題はN人の児童と身長の変わる一人の先生でペアの身長差が最小になるような組み合わせを作るという問題です。この問題だと「先生の身長が変わる」というのは明らかに問題を難しくしています。なので、いったん先生の身長は変わらないと仮定して自由度の少し減った問題を考えます。そうすると小学校でよくやるように背の順で並んでペアを組むという戦略が多分思いつきやすくなると思います。N人の児童を背の順にソートして隣同士をペアにすればいいという基本方針が思いついた段階で、先生の身長が変わるという条件を持ってきます。この問題は先生の身長のパターンを全て試した中でペアの身長差が最小の答えを求めればいいとわかりますね。この問題を解くために考える必要がある事は二つで、一つは先生の身長が決まった場合にペアを決めるという事、もう一つはペアが決まった時に合計をどのように求めたらいいかという問題があります。前者についてはソートされた配列の中での自分の場所を決める問題なので二分探索が使えそうです。後者のペアが決まった時に合計をどのように求めたらいいかについてですが、児童のペアの作り方は先生とペアになるか、前の人とペアになるか、後ろの人とペアになるかになります。例えばもともと前の児童とペアになっていた児童の間に先生が割り込んできた場合、その児童は後ろの児童とペアを組むことになります。同様にそこから後ろの児童は全員ペアが前の人から後ろの人に変わります。なので、ペアの身長差の総和は先生より前のペアについての総和と先生と児童のペアの身長差と先生と児童のペアから後ろのペアの身長差の総和の三つで計算できるようになります。先生と児童のペア以外は事前に前のペアと組む場合と後ろのペアと組む場合について累積和を作っておけば定数時間で総和を計算できますね。難しい問題に見えますがステップを分割して一つ一つの段階をよく考えればきっと解けるんじゃないかなと思います。
最後に
というわけで今回は僕が成績アップに繋がったと感じたプログラミングコンテストの問題を解くための考え方の工夫をまとめてみました。一番伝えたかったのは数学の問題を解くイメージでプログラミングの問題を解くと筋道を立てやすいよというところです。プログラミングと数学の関連はよく強調される一方で個人的にはなかなか実感を持てなかったのですが、今回試行錯誤をする中でなんとなく分かってきたような気がします。とはいえ僕もまだまだ解けない問題多いので、もっと試行錯誤して今後もプログラミングコンテスト楽しめたらなと思います。
明日は
id:kouki_danさんです！よろしくお願いします！！
AtCoder Beginner Contest 175に参加しました！ + 最近やってたこと
タイトルの通り先週末はAtCoder Beginner Contest 175に参加しましたー。
ABCの三問しか解けなくて悔しかったけどパフォーマンスは1119なので緑ぐらいのパフォーマンスにはなりました！
C問題を開始20分で解けて気分良くD問題に行けたのですが、結局Dをうまく通せずに終わってしまいました。
atcoder.jp D問題、Kの範囲に対してNがむっちゃ小さい+飛び先が自分自身でない事から循環しうる事がまず分かって、一周した時に0より大きいかで場合分けが必要なのもなんとなく分かってパフォーマンス的にもO(N2)程度で済みそうやしいけるかなと思ったものの、これ結構大変じゃない？？ってなって解くのにひよってしまいました。Dなんだからもっと簡単なのあるでしょ？とか思って20分ぐらい悩んでも思いつかないから諦めて循環見つけようってなりました。多分一般には循環は深さ優先探索で見つけるんだと思うんですけど、グラフアルゴリズムはまだあまり勉強してない状態だったのでこの前趣味で書いたFloydのうさぎとかめのアルゴリズムを使いました。 Floydのうさぎとかめのアルゴリズムは動画でたまたま知って面白かったのでその時に実装しました。
でも今思うと循環を難しく考えすぎですね。
今回の場合なら循環の開始地点と開始地点は一致すると考えていいので、単に開始地点をメモって、開始地点に戻ってくるまでfor文を回すだけで十分ですね。
で、一周させた時にスコアが0より大きいなら何周もさせればどんどん大きいスコアにする事ができます。一方で0より小さいなら何周もさせる意味は無いので一周させる中でベストの値を返せば良いです。ここまでは制限時間内に思いついてそこそこ通るものができたのですが、いくつか通らないまま終わってしまいました。何で引っかかっていたかというと一周のスコアが0より大きい場合に先に周れるだけ周ってからあまりを足してたんですけど、それが良くなかったんですよね。
4 40 3 1 4 2 1000 2000 4000 -6000
↑みたいな入力の時って10周させるよりも9周して残りいい感じのところでやめた方がいいスコアになるんですよね。なので周るだけ周ってからあまりを進むのではなく、一周回るまでの範囲で連続する長さをいろいろとって、残りの値で周れるだけ回った中で一番いいスコアをとるのが実際はいい戦略になります。こういうの結構教育的ですね。端数をあまり雑に扱うと痛い目をみるんだなーって思ったので次からの教訓にします。Eからは見てないです。正確にはEはチラ見してそっ閉じしました。問題にはなんか見覚えあると思いつつ全然分からなかったので諦めました。
前のABC174から二週間あって、その間はほとんどCとDの問題を解いていました。全探索とか合同式を使う問題をパッと解けたいなーと思ってその辺を勉強していました。2値の全探索ならbit演算でシュッとかけると思うんですけど3値以上のめんどくさいやつの時の実装がなんかうまく書けないなーってなってました。一回アドリブで再帰を使って実装したんですけど、こちらの記事にきれいにまとまってるように考えて書くとすごくいい感じになりました。
あとは「アルゴリズムイントロダクション」とか「離散数学への招待」みたいな本を読んでました。まだちゃんと勉強できてないんですけどマトロイドとかいうやつむっちゃかっこよくないですか！？凸関数の一般化みたいな感じっぽいですね。凸関数、最適化がスムーズにいくのがイメージつくと思うんですけどそれをもっと抽象化する事で貪欲法が使えるかを判断できるって感じですよね。ちょーかっこいい！！なんか面白そうだからちゃんと勉強したいですね！！
あとはなんか急にどうやってグラフって描画されるんだろう？ってのが気になってコンピューターグラフィクスのラスタライズのアルゴリズムを調べたりしてました。アルゴリズムの勉強、なんか自分の肌に合ってる気がしているのでもっと深くやっていきたいです。
