TiDB 5.0におけるトランザクションコミットのアクセラレーターであるAsync Commit

※このブログは2021年05月18日に公開された英語ブログ「Async Commit, the Accelerator for Transaction Commit in TiDB 5.0」の拙訳です。

著者: Yilin Chen  (PingCAPソフトウェアエンジニア、TiKVコミッター)

編集者: Tom Dewan, Charlotte Liu

TiDB は、オープンソースの分散型スケールアウトMySQL代替データベースで、HTAP (Hybrid Transactional and Analytical Processing)ワークロードをサポートします。分散トランザクションをネイティブにサポートしています。

TiDBの開発者として、私たちは低レイテンシの分散トランザクションを実装することに取り組んできました。最近、TiDB 5.0はトランザクションコミットのレイテンシを大幅に削減するための大きな一歩を踏み出しました – Async Commit機能の導入です。

本稿では、Async Commitの設計思想とその主要な実装の詳細について説明します。

Percolatorの追加遅延

TiDBのトランザクションは、Percolatorトランザクションモデルに基づいています。Percolatorのトランザクションモデルについて詳しくは、GoogleのPercolatorの論文を参照してください。

以下の図は、Async Commitが導入される前のTiDBのコミットプロセスを示しています。

ユーザーがTiDBにCOMMIT文を送った後、TiDBはコミット結果をユーザーに返す前に少なくとも以下のステップを踏む必要があります:

1. すべてのkeyを同時にprewriteする。
2. コミットタイムスタンプとしてPlacement Driver (PD)からタイムスタンプを取得する(Commit TS)。
3. Primary Keyにコミットする。

コミットプロセス全体のクリティカルパスには、TiDBとTiKVの間で少なくとも2回のラウンドトリップが含まれます。Secondary Keyのみバックグラウンドで非同期的にコミットされます。

TiDBのトランザクションモデルでは、TiDBノードがトランザクションのコーディネーターのような存在で、TiKVノードは参加者のような存在です。一般的な2フェーズコミットの実装では、コーディネーターのデータはローカルに保存されますが、TiDBのトランザクションモデルでは、トランザクションに関するデータはすべてTiKVに保存される仕組みになっています。そのため、理論上は第1フェーズの終了時にトランザクションの状態が決定されますが、TiDBは決定したトランザクションの状態をユーザーに返す前に、第2フェーズの一部(トランザクションの状態をTiKVに格納)を完了させる必要があります。

しかし、これはTiDB独自のトランザクションモデルに改善の余地があることも意味しています。Percolatorのトランザクションモデルを改良して、最初のフェーズが完了した後に、追加のリモートプロシージャコール(RPC)なしでトランザクションの状態を判断できるようにすることは可能でしょうか？

トランザクションの状態をより早く判断する

Async Commit導入以前は、トランザクションのPrimary Keyがコミットされた後でなければ、トランザクションのコミットは成功しませんでした。Async Commitの目的は、トランザクションの状態の決定を、prewriteが完了する時点まで進めることです。このようにして、コミットの第2フェーズ全体を非同期で行うことができます。Async Commitトランザクションでは、トランザクション内のすべてのKeyのprewriteが成功している限り、コミットは成功することを意味します。

以下の図は、Async Commitトランザクションのコミットプロセスです。従来のCommit TSを取得する部分が抜けていることがわかります。その代わり、TiDBはPDからMin Commit TSとして、prewriteの前にタイムスタンプを取得します。このように変更した理由は、次のセクションで説明します。

トランザクションの状態を判断する時間を短縮するという目標に到達するためには、主に2つの課題があります:

• すべてのKeyがPrewriteされているかどのように判断するか
• トランザクションのCommit TSをどのように決定するか。

すべてのトランザクションキーの見つけ方

Async Commitが導入される前は、トランザクションの状態はPrimary Keyだけによって決定されていたので、Primary KeyへのポインタをすべてのSecondary Keyに保存するだけでよかったのですが、Async Commitが導入された後は、Primary KeyへのポインタをすべてのSecondary Keyに保存する必要がなくなりました。もしコミットされていないSecondary Keyに遭遇したら、Primary Keyの状態を問い合わせることで、現在のトランザクションの状態を判断することができます。

Async Commitトランザクションに関しては、トランザクションの状態を判断するために、すべてのKeyの状態を知る必要があります。つまり、トランザクション内のどのKeyからでも、すべてのKeyを問い合わせることができなければなりません。したがって、Primary Keyのエントリに各Secondary Keyへのポインタも格納します:

Primary Keyは、実際にはすべてのSecondary Keyのリストを格納しています。当然ながら、トランザクションに多数のKeyが含まれる場合、それらをすべてPrimary Keyに格納することはできません。そのため、Async Commitトランザクションはあまり大きくできません。現在、Async Commitを使用するのは、最大256個のKeyを含むトランザクションのみで、すべてのKeyの合計サイズは4,096byte以下でなければなりません。

さらに、大きなトランザクションのコミットには長時間かかるため、TiDBとTiKV間のラウンドトリップを1回減らすことによるレイテンシの改善はあまり意味がありません。そのため、大規模なトランザクションのAsync Commitをサポートするために多階層構造を使用することも考慮していません。

トランザクションのCommit TSを決定する方法

Async Commit トランザクションの状態は、prewritesが完了した時点で決定される必要があります。したがって、トランザクションの状態の一部として、Commit TSもその時点で決定されなければなりません。

デフォルトでは、TiDBトランザクションはスナップショット分離と線形化可能性という要件を満たしています。これらの特性がAsync Commitトランザクションにも当てはまるようにするためには、Async Commitトランザクションに適切なCommit TSを決定することが重要です。

Async CommitトランザクションのKeyごとに、TiDBはそのKeyのMin Commit TSを計算し、Prewriting処理中にTiKVに記録します。トランザクションのすべてのKeyの中で最大のMin Commit TSが、このトランザクションのCommit TSとなります。

以下の2つのセクションでは、Min Commit TSの計算方法と、Async Commitトランザクションのスナップショット分離と線形化可能性の保証方法について説明します。

スナップショットアイソレーションを保証する

スナップショット分離を保証するTiDBは、MVCC (multi-version concurrency control)でスナップショット分離を実装しています。また、TiDBトランザクションはコミット開始時にTimestamp Oracle (TSO)からStart TSを取得します。スナップショット分離を実現するためには、Start TSをスナップショットのタイムスタンプとして読み込んだスナップショットが常に一貫していることを確認する必要があります。

そのため、TiDBからスナップショットを読み込むたびに、TiKV [^1] のMax TSが更新されます。Prewriting処理中、Min Commit TSは現在のMax TS [^2] よりも大きくなければなりません。つまり、以前のすべてのスナップショット読み出しのタイムスタンプよりも大きくなければなりません。そのため、Max TS + 1をMin Commit TSの値として選択することができます。このAsync Commitトランザクションが正常にコミットした後、そのCommit TSは以前のすべてのスナップショットの読み込みのタイムスタンプよりも大きいため、スナップショット分離を壊すことはありません。

以下の例では、トランザクションT1がキーxとキーyの両方を書き込み、トランザク ションT2がキーyを読み取ります。T2はyを読み取る際にMax TSを5に更新します。したがって、T1がその後yを事前に書き込んだ場合、Min Commit TSの値は少なくとも6になります。T1がyを正常に書き込んだ後、つまりT1が正常にコミットした後、T1のCommit TSも最低でも6になります。そのため、T2が再びyを読み込むとき、T1によって更新された値は読み込まれず、トランザクションT2のスナップショットは一貫性を維持します。

T1: Begin(Start TS = 1)
T1: Prewrite(x)	T2: Begin(Start TS = 5)
	T2: Read(y) => Max TS = 5
T1: Prewrite(y) => Min Commit TS = 6
	T2: Read(y)

線形化可能性を保証する

線形化可能性には2つの側面があります：

• リアルタイム性
• 逐次一貫性

「リアルタイム」という観点からは、前のトランザクションが正常にコミットされた直後に、新しいトランザクションがトランザクションの変更を読み取ることができなければならないことが要求されます。新しいトランザクションのスナップショットタイムスタンプは PD上でTSOから取得されるため、Commit TSはあまり大きくならないようにする必要があります。Commit TSの値は、TSOによって割り当てられた最大タイムスタンプに1を足した値までしか設定できません。

スナップショット分離のセクションで述べたように、Min Commit TSの可能な値の1つはMax TS + 1です。Max TSを更新するために使用されるタイムスタンプはTSOからのものであるため、Max TS + 1はTSO上の最小未割り当てタイムスタンプ以下であることは確実です。したがって、「リアルタイム」の要件は満たされています。

逐次一貫性とは、トランザクションの論理的な順序が物理的な優先順位に反しないことを意味します。例えば、T1とT2という2つのトランザクションがあるとします。T1がT2より先にコミットされる場合、T1のCommit TSはT2のCommit TSより小さいか等しいはずです [^3]。

逐次一貫性を保証するため、TiDBはPD上のTSOからMin Commit TSの最小制約としてタイムスタンプを取得してから、Prewriting処理に入ります。リアルタイム性が保証されているため、T2がPrewriting処理前に取得するタイムスタンプは、T1のCommit TS以上でなければなりません。したがって、因果関係の逆転が起きないことが保証され、逐次一貫性が保証されます。

つまり、各KeyのMin Commit TSは、TiDBがPrewriting時に取得するMax TS + 1と、prewriting処理前にPDから取得したタイムスタンプの間の最大値をとります。トランザクションのCommit TSは、全KeyのMin Commit TSの最大値となります。これらを合わせて、Async Commitトランザクションのスナップショットの分離と線形化可能性の両方を保証します。

One-phase commit (1PC)

トランザクションがレコードの非インデックス列を更新するだけ、またはセカンダリインデックスなしでレコードを挿入する場合では、1つのリージョンにしか関与しません。このシナリオでは、分散トランザクションプロトコルを使用せずに、1つのフェーズだけでトランザクションのコミットを完了することは可能でしょうか？もちろん可能ですが、難しいのはone-phaseのコミットトランザクションのCommit TSをどのように決定するかという点です。

Async CommitがCommit TSの計算根拠を提供することで、one-phase commitの実装の難しさが解消されます。Async Commitと同様にone-phase commitトランザクションのCommit TSを計算し、TiKVで1回のRPCで直接トランザクションをコミットします。

One-phase commitは分散コミットプロトコルを使用しないため、TiKVの書き込み操作の回数を減らすことができます。そのため、トランザクション [^4] が1つのリージョンだけを含む場合、one-phase commitを使用すると、トランザクションのレイテンシーを短縮するだけでなく、データのスループットも向上します。

TiDB 5.0では、Async Commitの一部としてone-phase commitの機能が導入されています。

因果一貫性

前述の通り、TSOからMin Commit TSを取得することで、逐次一貫性が確保されます。では、このステップがなくなったらどうなるでしょうか？PDとTiDB間のラウンドトリップレイテンシーをもう1つ短縮できるでしょうか？

しかし、この場合、逐次一貫性に違反する例があります。キー x とキー y が異なるTiKVノードに格納されているとしよう。トランザクションT1は x を修正し、トランザクションT2は y を修正します。T1はT2より早く開始するが、ユーザーはT2が正常にコミットした後にT1にコミットを通知します。ユーザーにとって、トランザクションT1のコミットはトランザクションT2のコミット完了後に開始されるが、論理的には、逐次一貫性が満たされるならT1はT2より遅くコミットする必要があります。

また、Prewriting処理の前にMin Commit TSを取得する操作を省略した場合、T1のCommit TSはT2のCommit TSより小さい2になってしまう可能性があります。同時にCommit TSが3のトランザクションT3があった場合、T3のキーxとキーyを読むことで、T2がT1より論理的に遅いという事実を観察することができます。したがって、この例では線形化可能性は存在しません。

T1: Begin(Start TS = 1)
		T3: Begin(Start TS = 3)
	T2: Begin(Start TS = 5)
	T2: Prewrite(y) => Min Commit TS = 6
	Notify T1 to commit
T1: Prewrite(x) => Min Commit TS = 2
		T3: Read(x, y)

TiDBがTSOからMin Commit TSを取得しない場合、スナップショットの概念が想定と大きく異なることがあります。以下の例では、T1より遅く開始するT2がT1にコミットを通知し、T1のCommit TSがT2のStart TSより小さくなる可能性があります。

ユーザにとって、T2がT1のxに対する変更を読むことは想定外です。このシナリオでは、反復可能な読み取り性という性質は侵害されませんが、スナップショット分離という要件がまだ満たされているかどうかは議論の余地があります[^5]。

T1: Begin(Start TS = 1)
	T2: Begin(Start TS = 5)
	T2: Read(y)
	Notify T1 to commit
T1: Prewrite(x) => Min Commit TS = 2
	T2: Read(x)

因果一貫性のあるトランザクションの順序は、物理的にコミットする順序と同じですが、因果一貫性のないトランザクション間のコミット順序は不確実です。2つのトランザクションは、それらがロックまたは書き込むデータが交差する場合にのみ、因果関係があります。ここでいう因果関係には、データベースが知りうる因果関係のみが含まれ、上記の例でいう「サイドチャネル通知」のような外部からの因果関係は含まれません。

このような特別なシナリオがあまり発生しないため、Min Commit TSの取得をスキップする方法も提供されています。START TRANSACTION WITH CAUSAL CONSISTENCY ONLY でオープンされたトランザクションは、コミット時にMin Commit TSを取得しません。データベース外部で2つの同時実行トランザクションのコミット順序を制御するシナリオでない場合は、整合性レベルを下げて、PD TSOからTiDBがタイムスタンプを取得する操作を1つ減らし、時間短縮を試みることができます。

 

 

パフォーマンスの向上

Async Commitは、トランザクションの完了点をprewriteの最後に移動し、Primary Keyのコミットを非同期化します。トランザクション内でPrimary Keyのコミットステップに時間がかかればかかるほど、Async Commitによってもたらされる改善効果は大きくなります。インタラクションの少ない小規模なトランザクションでは、Async Commitによって大きな改善が得られることがよくあります。

sysbenchのoltp_update_indexシナリオでは、トランザクションは2つのKey、行レコード、およびインデックスを書き込むだけです。これは追加のインタラクションを伴わない自動コミット・トランザクションでもあり、理論的にはAsync Commitはそのレイテンシを大幅に削減することができます。

当社のテストもこれを証明しています。下図に示すように、Async Commitを有効にして、2,000TPS固定でsysbencholtp_update_indexをテストすると、平均待ち時間が42%短縮し、99パーセンタイル待ち時間は32%短縮しています。

リージョンが1つしかないトランザクションに関しては、one-phase commitの最適化により、トランザクションコミットの待ち時間をさらに大幅に短縮することができます。また、TiKVへの書き込みを減らすことができるため、データのスループットを向上させることも可能です。

下記グラフは、2,000TPS固定でsysbench oltp_update_non_indexをテストした結果を示しています。このシナリオでは、トランザクションは1つのリージョンにのみ書き込みを行います。one-phase commitを有効にすると、平均待ち時間は46%短縮され、99パーセンタイル待ち時間は35%短縮されました。

逆に、Async Commitがパフォーマンスを大きく向上させないシナリオもあります：

• トランザクションに多くのステートメントが含まれ、長いインタラクションロジックがあり、トランザクションコミットの時間割合が低い場合、Async Commitがもたらす改善効果は限定的です。
• トランザクションに多くのKeyが含まれ、書き込み操作が多く、Prewriteにかかる時間が Primary Keyのコミット時間より大幅に長い場合、Async Commitはこのトランザクションの待ち時間を短縮するのにあまり役に立ちません。
• Async CommitはTiKVへの読み書きの量を減らすわけではないので、スループットを向上させることはできません。システム自体がスループットの限界に近い場合、Async Commitは大きな改善をもたらすことはできません。

まとめ

Async Commitは、TiDBトランザクションコミットにおけるTiKVへの1回の書き込みのレイテンシーを短縮し、オリジナルのPercolatorトランザクションモデルから大きく改善されました。新規に作成されたTiDB 5.0クラスタでは、Async Commitとone-phase commitがデフォルトで有効になっています。古いバージョンから5.0クラスタにアップグレードする場合は、ユーザーが手動でAsync Commitとone-phase commit機能を有効にする必要があります。グローバルシステム変数tidb_enable_async_commit  とtidb_enable_1pc をONに設定する必要があります。

Async Commitの設計についてもっと知りたい方は、設計ドキュメントをご覧ください。今後、TiDBがより多くの人に役たてられるよう、TiDBトランザクションのパフォーマンスを向上させ、皆様のTiDB体験をより良いものにしていきます。

私たちのコミュニティに参加してください

TiDBとその新機能に興味がある場合は、ぜひコミュニティ版をお試しください。フィードバックやご不明な点などございましたら、いつでもお気軽にお問い合わせください。

Notes

[^1]：リージョンリーダーが移った後に新リーダーのMax TSが十分に大きくなるように、TiKVもPDから最新のタイムスタンプを取得し、リージョンリーダーが移った後にMax TSを更新し、リージョンがマージされるようにします。

[^2]：Prewrite処理では、より新しいスナップショットの読み取りがこの制約を破ることを防ぐために、TiKVはPrewrite Keyにメモリロックを追加し、Start TSがMin Commit TS以上である読み取り要求を一時的にブロックしています。

[^3]：T1とT2のコミットメント処理が重なった場合、その論理的な順序を決定することができません。

[^4]：正確には、one-phase commit機能は、トランザクションが単一のTiKVリクエストで完了できる場合にのみ使用されるべきです。コミット効率を上げるために、より大きなトランザクションは多くのリクエストに分割され、この場合、たとえそれらがすべて同じ単一のリージョンを含むとしても、one-phase commitは使用されていません。

[^5]：T1の論理コミット時刻がT2の開始時刻より早い(線形化可能性が満たされないため)ことに同意する場合、このケースはスナップショット分離の要件を満たしています。