TiDB 検証ライフ(8-分散トランザクションの理論)

いよいよ、残しておいた大好物「分散トランザクション」の検証に入ります。
除夜の鐘がなるまで無事検証終え、気持ちよく年越したいですが、果たしてどうなるやら。

## まずは理論武装から

関連知識をざっとおさらいします。

### トランザクションとは

分けることのできない一連の情報処理の一単位を意味する。この一連の処理を分割して実行した場合、結果の整合性を保てなくなる。
※　Wikipediaから抜粋: [トランザクション](https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%83%B3%E3%82%B6%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3#%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0%E3%81%AB%E3%81%8A%E3%81%91%E3%82%8B%E3%83%88%E3%83%A9%E3%83%B3%E3%82%B6%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3%E5%87%A6%E7%90%86)

トランザクションと言ったら、パッと思い浮かぶのがACID特性ですね。

- Atomicity(原子性)
- Consistency(一貫性)
- Isolation(分離性)
- Durability(永続性)

トランザクションに含まれる個々の手順が「すべて実行される」か「一つも実行されない」のどちらかの状態になるのが肝のようです。

よくある、銀行口座からの引き出しを例に、トランザクションを考えると、

1. 処理１:　指定金額を引き出す
2. 処理２:　預金残高を更新する

処理１だけ実行し処理２を省いたら、預金残高が変わらず永遠に引き出せてしまいますね。

### では、分散トランザクションとは
トランザクション処理の処理形態の1つであり、ネットワーク上の2つ以上のホスト(処理するコンピュータ)が関連する、1まとまりの操作(処理、取引、トランザクション)のことを示す。
※　Wikipediaから抜粋: [分散トランザクション](https://ja.wikipedia.org/wiki/%E5%88%86%E6%95%A3%E3%83%88%E3%83%A9%E3%83%B3%E3%82%B6%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3)

要点二つありました

- トランザクションが複数ノード(または、データベース、ホスト)間にまたがる

処理が複数データベースに分散されるので処理の整合性を保つは至難の技?

- ACIDを保証する一般的な方法は2フェーズコミットプロトコルである

2PC(Two-Phase Commit)とは、複数のノードで処理の整合性が保たれるよう2段階に分けてコミットを行う手法。

たとえば旅行の予約を、下記複数システムによる分散トランザクションと考えた場合、

1. 航空券の予約
2. レンタカーの予約
3. ホテルの予約

2フェーズコミットは、以下の2フェーズで行われるようです(もっと複雑ですが、イメージとして)。

- フェーズ１: 上記三つのシステムに、コミットしてもいいですか、と事前確認

いずれの一つから「ごめんなさい、予約できそうにありません」と返されたら、旅行はキャンセル(ロールバック)され、なかったことに。

- フェーズ２: 正式コミット

フェーズ１で、全てのシステムからOK返されたら、正式コミット(支払い)し、旅に出る。

### じゃ、TiDBは分散トランザクションの課題をどう解決したか

背景や全体像の説明がとっつきやすいPingCAP社謹製資料見つけました。
https://pingcap.com/blog/deep-dive-into-tikv#transaction

#### TiKVのトランザクションモデル
Googleの[Percolator](http://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/36726.pdf)とXiaoMiの[Themis](https://github.com/XiaoMi/themis) からインスピレーションを受け、さらに下記最適化を施したものらしいです。

1.　Timestamp Oracle(TSO)の最適化
Percolatorライクのシステムは、単調に増加するタイムスタンプを割り当てるため、TSOと呼ばれるグローバルに一意のタイムサービスが必要となるようです。TSOの機能はTiKVのPDにより提供され、PDでのTSOの生成は純粋にメモリ操作であり、TSO情報を定期的にetcdに格納するため、PDが再起動した後でもTSOが単調に増加するようになるとのことです。

トランザクション制御にタイムサービスが大事と言うことですね。

2.　ロック処理速度の最適化
Percolatorでは特定の行に列を追加してロックなどの情報を保存するのに対し、TiKVはRocksDBの列ファミリー(CF)を使用して、ロックに関連するすべての情報を処理するようです。大量データの場合、同時トランザクションにおける行ロックは多くないため、最適化された追加CFに配置することでロック処理速度が大幅に向上するとか。

トランザクションにロック制御が欠かせませんので、これも大きいか。

3.　残留ロックのクリーンアップの最適化
トランザクションによって取得された行ロックが、スレッドのクラッシュまたはその他理由でクリーンアップされず、かつ残留ロックにアクセスする後続トランザクションが存在しない場合、ロックは取り残されてしまいます。列ファミリー(CF)を使用する利点は、CFをスキャンすることで、これらのロックを簡単に検出してクリーンアップできることらしいです。

ピンと来ませんが、まあ、一旦はこれぐらいでいいか。

まとめると、分散トランザクションの実装は、「TSOサービス」と、TiDBに実装されている特定トランザクションアルゴリズムをカプセル化する「クライアント」に依存するようです。

- 単調に増加するタイムスタンプは、同時トランザクションの時系列を設定するため
- 外部クライアントは、トランザクションの競合または予期せぬ終了を解決するコーディネーター

とのことです。

うーん、机上で理解するのは難しいので、検証しながら再吟味することにします。

#### トランザクションの実行フロー

TiDBのトランザクションは、開始、処理、コミット、三つのフェーズとなっていました。

##### TiDBの楽観的トランザクション(説明は後述)フロー図となります。

                      Optimistic transaction mode

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/61975/6206e51b-e0ab-078d-6333-8c2c83a8c939.png)

※ [PingCAP社のドキュメント](https://docs.pingcap.com/tidb/stable/troubleshoot-lock-conflicts)から引用

##### TiDBは悲観的トランザクション(説明は後述)もサポートしており、そのフロー図です。

                      Pessimistic transaction mode

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/61975/2dcfbbbc-7bde-f55d-1513-75430a22a763.png)

※ [PingCAP社のドキュメント](https://docs.pingcap.com/tidb/stable/troubleshoot-lock-conflicts)から引用

以下、トランザクションフローの詳細説明です。

1.　トランザクション開始
クライアントはTSOから現在のタイムスタンプ(startTS)を取得します。TSOはタイムスタンプの単調な増加を保証するため、startTSを使用してトランザクションの時系列を識別できます。

2.　トランザクション処理
読み取り操作で、RPC要求をstartTSと一緒にTiKVに送信、TiKVはMVCCを使用してstartTSの前に書き込まれたデータを確実に返します。
書き込み操作で、TiKVは楽観的並行性制御を使用します。現在のトランザクションが他のトランザクションに影響を与えないと想定するため、データはサーバーに書き込まれるのではなく、クライアントにキャッシュされます。

ここで、MVCCと楽観的並行性制御、新しいキーワードが出現しました。Wikipediaから、

[MultiVersion Concurrency Control(MVCC, マルチバージョン コンカレンシー コントロール)](https://ja.wikipedia.org/wiki/MultiVersion_Concurrency_Control)
データベース管理システムの可用性を向上させる制御技術のひとつで、複数のユーザから同時に処理要求が行われた場合でも同時並行性を失わずに処理し、かつ情報の一貫性を保証する仕組みが提供される。

MVCCの利点は、書き込み処理(トランザクション)が行われている最中に他のユーザによる読み取りアクセスがあった場合、書き込みの直前の状態(スナップショット)を処理結果として返す。よって、書き込み中も読み取りができ、読み取り中でも書き込みができるらしい。

MVCCにおいて可用性を達成するには、最低限、全ての処理が「どの順番で」行われたかを確実に記録する必要があり、そのためタイムスタンプやトランザクションIDなどを用いて全ての更新処理が管理されるみたい。

[楽観的並行性制御(optimistic concurrency control)](https://ja.wikipedia.org/wiki/%E6%A5%BD%E8%A6%B3%E7%9A%84%E4%B8%A6%E8%A1%8C%E6%80%A7%E5%88%B6%E5%BE%A1)
並行性制御(ロック)手段の一種で、楽観的ロックの概念である。他の処理と競合してはならないトランザクションにおいて、開始時には特に排他処理など行なわず、完了する際に他からの更新がされたか否かを確認し、もし他から更新されてしまっていたら自らの更新処理を破棄し、エラーとする。

ようは、更新時に他と競合するか気にせず(楽観的?)、とにかく更新してみて、最後に競合あったかチェック。

ついでに、
[悲観的並行性制御(pessimistic concurrency control)](https://ja.wikipedia.org/wiki/%E6%82%B2%E8%A6%B3%E7%9A%84%E4%B8%A6%E8%A1%8C%E6%80%A7%E5%88%B6%E5%BE%A1)
他の処理と競合してはならないトランザクションにおいて、開始時に更新の抑止がされていないことを確認後(抑止されている場合は解除されるまで待機するか、エラーとして処理をあきらめる)、他からの更新を抑止し(排他制御)、完了する際に抑止情報を解除する。

ようは、更新時に他と競合しないかチェックし、ロックをかけ、更新処理を行ってからロック解除。

3.　トランザクションコミット

TiKVは2フェーズコミットアルゴリズムを使用しますが、一般的な2フェーズコミットとは違い、独立したトランザクションマネージャーがないとのこと。トランザクションのコミット状態は、コミット対象キーから選択されたPrimaryKeyのコミット状態によって識別されるようです。

よくわからないので、検証時に忘れず理解できるようにしたいです。

コミットの詳細フェーズです。

　　1)　下書き(Prewrite)フェーズ
クライアントは、複数のTiKVサーバーに書き込み対象データを送信します。データがサーバーに保存されると、サーバーは該当キーをロック済みと設定し、トランザクションのPrimaryKeyを記録します。 いずれかのノードで書き込み競合が発生した場合、トランザクションは中止されロールバックされます。

　　2)　下書き(Prewrite)が終わったら
新しいタイムスタンプがTSOから取得され、commitTSとして設定されます。

　　3)　コミット(Commit)フェーズ
リクエストはPrimaryKeyを使用してTiKVサーバーに送信されます。TiKVがコミットを処理するプロセスは、
　　- PrimaryKeyフェーズからロックをクリーンアップ
　　- 該当コミットレコードをcommitTSと一緒に書き込む
PrimaryKeyコミットが終了すると、トランザクションがコミットされます。
他のキーに残っているロックは、Primarykey状態を取得することで、コミット状態と当該commitTSを取得できます。

ただし、後でロックをクリーンアップするコストを削減するため、実際は、トランザクションに関係するすべてのキーをバックエンドで非同期送信します(どういうこと?検証で理解できたらいいな)。

#### 更に、以下資料3点も、TiDB分散トランザクションの理解に有意義のようですので共有します。

https://docs.pingcap.com/tidb/stable/transaction-overview

トランザクジョン関連コマンドの構文など。

https://tikv.github.io/deep-dive-tikv/distributed-transaction/introduction.html

分散アルゴリズムやロックの仕組み。

https://pingcap.com/blog/tikv-prewrite-request-life-story

下書き(Prewrite)フェーズが詳細に。難しい内容でしたので後でじっくり読もうっと。

## 終わりに

理論だけでお腹いっぱいになりました、一旦ここで休憩とさせてください。
次回は、実際分散トランザクションを仕掛けながら、動きを見てみます。
お楽しみに。