MVCCを実現するTiDBトランザクションの流れ　データの整合性を保つための5つの技術

TiDBトランザクションの流れ

水戸部章生氏：（スライドを指して）こちらのバッチクライアント側からTiKVに、Raft側に処理を流して、Raftは受け取ったデータをそれぞれしっかりとコピーして整合性を保つとされていますが、本日はこのトランザクションについて紹介しようと思っています。

TiDBのトランザクションはもちろん、MVCC（MultiVersion Concurrency Control）で実現している分散型のデータベースです。このMVCCを実現するための技術キーポイント5つを紹介します。

先ほど名前が出ていましたが、1つ目がGoogle Percolatorと呼ばれる技術、2つ目がTimestamp Oracleです。3つ目はかなり前から提唱されているTwo Phase Commit、4つ目と5つ目はCompare And SwapとTime To Liveです。TiDBのトランザクションは、この5つで支えられています。

簡単なトランザクションの流れです。（スライドを指して）こちらは、私のPCで実際にやったものです。1つ目にMySQLと書いてありますが、TiDBです。先ほどMySQLのインターフェイスを持っていると紹介しましたが、このようなかたちで普通のBEGIN、select、updateと、同じコマンドが叩けます。

今回は、BEGINの後ろに楽観を意味するoptimisticをつけていますが、selectをしたあとupdateをして、commitする簡単なトランザクションの流れを実施しています。このトランザクションを実施すると、フィジカルの部分では実際にどのようなやり取りになっているかを、次のスライドに書いています。

（スライドを指して）左から右がトランザクションの流れです。まず、TiDBからstart_tsというかたちでBEGINを発行すると、Placement DriverからStart TSOと呼ばれるタイムスタンプを取得します。この取得が終わると、selectをする時にRaftを使っているので、どこにデータがあるかをPlacement Driverから取得します。

この取得が終わると、タイムスタンプを使ってスナップショットされたデータ、自分の位置がどこにあるかを確認した上でデータの読み込みが始まります。

本当はselectなどがありますが、updateしてデータを書き込むと、TiDBのメモリバッファ内にすべて書き込んだあと、バッチ処理するために必要なキーをまとめあげるなどして、次のcommitの処理に備えます。

次はcommitの処理です。先ほど1文でcommitと書きましたが、commitとしてはTwo Phase Commitを採用しています。分散型だと必須かと思いますが、最初にprewriteが発行されます。このprewrite時に、まずCAS（Compare And Swap）と呼ばれるメモリにスナップショットしたデータを配置します。そのあと、PercolatorによるSnapshot isolationとTTLを設定します。TTLを設定することによって、トランザクションが生きている間にTTLを延長します。トランザクションが消失した際にはTTLが無効になり、ほかのトランザクションが読み込みにいけるような設定になっています。

（スライドを指して）prewriteですが、すべてのキーに対してprewriteでロックを取得できると、次のcommitのフェーズに移れます。ただし、ロックを取得できないと、この時点でデータのロールバックが始まります。

無事にそれぞれのロックが取得できた際には、commitフェーズに移ります。commitフェーズは、さらにTSOタイムスタンプをPlacement Driverから取得し、取得したTSOを使って、それぞれのデータを書き込んでいきます。（スライドを指して）ここにCASによるデータのチェックと書いていますが、こちらは特に楽観処理の時に使います。のちほどスライドで詳しく紹介するので、ここでは割愛します。

最後にPrimaryKeyのロックの解除が終わるとcommitが完了し、クライアントに処理が戻るのが、一般的なTiDBのトランザクションの流れです。

トランザクションの中で使われている5つの技術

本日は、詳細というより、全体の流れの中でどのような技術が使われてるかを紹介しようと思っています。（スライドを指して）少しわかりづらいと思うので、右上にトランザクション処理の中の、どの部分に位置するか書いています。この数字は最初にあったキー技術のどの番号かを意味しています。

1つ目はGoogle Percolatorによるスナップショット作成です。Google検索インデックスの更新に使用されるようなアーキテクチャーですが、TiDBの場合はこちらを使用しています。使用しているColumn Familyと呼ばれるそれぞれのcolumnを用意し、役割を持たせてスナップショットを取得するようなアーキテクチャーですが、TiKVではData、Lock、Writeの3つを使用しています。

（スライドを指して）こちらが、特定のキーのデータの持ち方です。まず、Keyと呼ばれる主となるキーがあります。Keyの次にDataとあります。のちほど紹介しますが、こちらのTSOというタイムスタンプで、それぞれData、Lock、Writeというかたちで1つのレコードを作っていきます。

今は$10というデータが存在していますが、この2つ目がcommitした際に出てくるデータです。commitすると5番目が今確定しているようなデータになっています。ほかのトランザクションがデータを読みにくる時には5番が確定しているので、10番を読み込みにいくような流れになります。

一番上がprewriteしている状態です。先ほどprewriteの際にはロックを取得する必要があると紹介しましたが、このロックの部分にprimary、もしくはほかのセカンダリであればprimaryのキー名を書いてロックを取得します。ロックがある時はまだprewriteが行われている状態で、それぞれのisolationレベルを分けてデータを持つような構造になっています。

この下で1つ特徴を挙げれば、CF_LockにTTLを入れるようになっています。このTTLものちほど紹介するので、ここではこのようなデータが入っていることを理解してもらえればと思います。また、CF_Writeのステータス情報も使って、ステータス情報の管理をしています。

2つ目はTSOです。commitの時に取得したTSO（Timestamp Oracle）はデータ不整合が起こるケースをすべてサポートするために、タイムスタンプを採用しています。先ほどGoogle Percolatorによるスナップショットと取得を紹介しましたが、スナップショットで不整合の起こるパターンのどこをサポートしているかと言うと、Dirty WriteやFuzzy Read、Lost Updateです。これらのケースに関してはサポートできています。

ただ、Write Skewと呼ばれるデータ不整合は、時系列で管理しないと発生してしまうので、これをサポートするためにTimestamp Oracleラインナブルの制御を入れています。

先ほどの基本的なトランザクションの処理にもありましたが、TiDBとPDでタイムスタンプを取得して、タイムスタンプにしたがって先ほどのスナップショットのレコードを作っていきます。Timestamp Oracleの番号は、Int64のシステム全体でユニーク値を必ず発行する仕組みになっています。

3つ目は、Two Phase Commitです。やはりGoogle Percolatorでは必須と思われるTwo Phase Commitも実装しています。先ほど紹介したとおり、例えば Bobが3ドル送り、Joeから9ドルにするという、BobからJoeに7ドル送るようなトランザクションがあった時、まずprewriteを実施します。（スライドを指して）こちらはprewriteの状態ですが、ノードが別々になっているので、ノード間でしっかりとデータの整合性を保つことが必要です。

まず、BobではTSO7（タイムスタンプ7を取得した）として、7ではデータ3を入れ込むとLockでprewrite状態です。Writeにはまだ何も書いていない状態です。Joeの状態に関しても9ドルを入れます。LockにはPrimary@Bob balと書いてありますが、Bobをprimaryとしたロックを取得し、7はない状態でprewriteが完了します。

ロックがすべて取得できれば、次のcommit処理にいきます。ロックがすでに1つでも取られている場合はロールバックというかたちになります。（スライドを指して）実際このcommit処理を行うと、次はどのような処理になるかがこちらの絵ですが、commitのTSOを再度取得して8番目のcommit処理に走ります。

prewriteが終わったあとには、commitがほぼ確定で走るようになっています。こちらに8、8とありますが、7が最新のデータとして、7番が記録されます。

（スライドを指して）こちらのJoeのところにもTSO7が最新のデータとして書き込まれ、この下のTSO7のPrimary Lockが消えるようになっています。primaryのLockだけ最初に削除して、Lockが終わるとTiDBはcommit処理が終わったとして返します。後ろに関しては、のちほど処理をするような流れです。

4つ目は、スナップショットのCAS（Compare And Swap）という機能です。スナップショットを取る際のデータをCASと呼ばれるOSの命令に入れるようになっています。（スライドを指して）こちらではkey=Bob, Data=5となっていますが、スナップショットを取った段階では同じデータです。基本的には、TiDBのデータ自体はオンメモリ上で更新します。

メモリ上で更新すると、トランザクション1とトランザクション2のどちらが更新したかがわからなくなります。その際に、CASの中でデータを入れ込みます。CASはマルチスレッド対応であり、一度データを書き込むと、次に書き込もうとしたトランザクションにエラーを返すような仕組みになっています。

先にデータがcommitされていると、次にデータが来た時、すでにそのデータは書き込まれている状態になります。楽観Lockでデータを持ってきても、ほかのトランザクションがすでにcommit処理していることに気づけるので、その時点でロールバックします。TiDBの場合はリトライ1になっているので、楽観Lockならもう一度commit処理（データのやり直し）をするのがCASの機能です。

5つ目は、TTLによるトランザクション制御です。トランザクションがTTLを確認して、ノードダウン時などに検知する仕組みです。先ほど紹介したPercolatorのロックのところに入っているTTLですが、heartbeatでTTLのexpireを伸ばす処理をします。このexpireが切れると、すでにLockがなくなっていると判断し、ほかのトランザクションがデータを更新できるような仕組みになっています。

（次回につづく）