TiDBのトランザクションモデルの進化

TiDBのトランザクションモ デルの進化 発表者 TONG MU TiDB/TiKV コミッター

自己紹介 ● ● ● 2019年から PingCAP でインターンシップを開始。 2021年正式に PingCAP に加入。 2023年に JLPT N1 に合格し、その後日本に住むこと にしました。 ● 趣味：ペット、写真撮影、ゲーム、ウェブサイト制作、 サーバーの組み立て。 GitHub: you06

• https://github.com/you06

はじめに ● TiDB トランザクションチームの目標 / ミッション ● ● ● 正確性は一番 パフォーマンスはデータベースの長期目標 遅延と資源の利用二つの方面の安定は重要で す わかりやすいなら、ユーザーからの誤用を減ら します 制限を突破、より自由的にデータベースを利用 できるようにすることを願います グローバルの視点で TiDB の開発を進めます ● ● ● 正確性 性能と安定性 限界を突破 わかりやすさ エコシステムの やさしさ グローバル ビュー

目次 ● ● ● ● 基本的なモデル (Percolator) ○ 分散トランザクションの正解性を保証します ○ コーディネーターはステートレスになる Async Commit & 1PC ○ 書き込み遅延を減らす 排他ロック (悲観的ロック) ○ ロック競合のトラブルシューティング 非トランザクション DML & バルクDML ○ 無限大なトランザクションを実行できます

説明 ● ● このスライドでは具体的なコードについては触れませんが、右下隅に関連資料とコードへのリン クを提供します。 リンクは数種類があります： ○ 公開の wiki ○ 他の DB から参考にできるページ ○ TiDB のデサイン ○ TiDB のキーコード（ v8.1.0） 例：関する資料やコードのリンク

Part I 基本的なモデル

TiDB システム https://github.com/tikv/client-go https://github.com/tikv/tikv

• https://github.com/tikv/client-go
• https://github.com/tikv/tikv

基本的な Percolator ● ● ● Primary Key(PK) によって原始性を保証する。 ○ Primary Key は1つだけで。 ○ その他は Secondary Keys です。 TiDB はステートレスにする。 原子性を保証する以外に、ほとんど最適化が行われ ていない。 ○ 書き込みトランザクションは読み取りをブロック する可能性があります。 ○ 高いレテンシ。 Large-scale Incremental Processing Using Distributed Transactions and Notifications 2PC implementation in TiDB

• https://www.usenix.org/legacy/events/osdi10/tech/full_papers/Peng.pdf
• https://github.com/tikv/client-go/blob/tidb-8.1/txnkv/transaction/2pc.go#L1450-L1777

ブロックせずに読み取る ● PK のみで min_commit_ts が保存されます。 TiKV min_commit_ts definition

• https://github.com/tikv/tikv/blob/v8.1.0/components/txn_types/src/lock.rs#L85

ブロックせずに読み取る ● min_commit_ts がないと、Non-repeatable Read が発生する可能性があります。 txn1 txn2 x begin, start_ts = 1 0 write(x, 1) 0 commit start, commit_ts = 2 0 begin, start_ts = 3 r(x, 0) commit end, commit_ts = 2 0 0, ts <1 1, ts >= 2 r(x, 1) 🤒 0, ts <1 1, ts >= 2 Wikipedia: 分離レベル

• https://ja.wikipedia.org/wiki/トランザクション分離レベル#分離レベル

Part II 書き込むレイテンシを下げる / 11

レイテンシを下げる - 挑戦 ● ● もし TiDB が commit 前にトランザクションの状態が 返信したら、エラーが出る時、実際の状況がどう確認 しますか。 y -> x。z は見えない。 key primary key prewrite x x ok y x ok z x ?

レイテンシを下げる - Async Commit ● ● ● Primary Key(PK) の中で Secondary Keys を保存し、ト ランザクションの最終状態を確認できます。 commit_ts = max{pd TSO, prewrite returned min_commit_ts} y -> x -> [y, z] CRDB Parallel Commit Blog TiDB Async Commit Design

• https://www.cockroachlabs.com/blog/parallel-commits/
• https://github.com/tikv/sig-transaction/blob/master/design/async-commit/spec.md

レイテンシを下げる - 1PC ● ● ● 1PC は 1 Phase Commit。 分散データベースであっても、分散トランザクションは可能な 限り避けます。 commit_ts = max{pd TSO, prewrite returned min_commit_ts}

レイテンシを下げる - 線形化可能性 1pc Async Commit Document: TiDB の線形化スイッチ Wikipedia: 線形化可能性

• https://docs.pingcap.com/tidb/stable/system-variables#tidb_guarantee_linearizability-new-in-v50
• https://ja.wikipedia.org/wiki/線形化可能性

レイテンシを下げる - 線形化可能性 ● ● ● Commit の最初段階で PD から min_commit_ts をゲットすることが線形化可能 性を保証する。 右の表によって、 txn2 が commit の内容が見 えないはず（x の読む結果は 0）。 もし、txn1 が PD から最新の TSO を取得しない 場合、txn1 の commit_ts を txn2 の start_ts により低いかも。つまり、 txn2 が txn1 をコミット したデータを見ることが可能となり、線形化可能 性が破られることになります。 txn1 txn2 x begin start_ts = 1 0 write(x, 1) 0 begin start_ts = 3 commit calc commit_ts = 2 0 0, ts <1 1, ts >= 2 r(x, 1) 🤒 0, ts <1 1, ts >= 2

Part III 競合耐性を上げる

問題：楽観的ロックの競合耐性が低い ● ● 一度書き込み競合エラーが発生すると、トランザクション全体を再試行する必要があります。 トランザクションの再試行のコストは高くつく可能性があります。 Session A Session B Session C > begin; > begin; > begin; > execute large DMLs 🐢 > execute large DMLs 🐢 > execute large DMLs 🐢 > update test set v = v + 1 where k = 1; > update test set v = v + 1 where k = 1; > update test set v = v + 1 where k = 1; > commit; ERROR 9007 (HY000): Write conflict, …, reason=Optimistic [try again later] > commit; ERROR 9007 (HY000): Write conflict, …, reason=Optimistic [try again later] > commit;

悲観的ロック ● ● 悲観的ロックを導入。 ステートメントがロックに遭遇した場合、再試行する必要があります。 Session A Session B Session C > begin; > begin; > begin; > execute large DMLs 🐢 > execute large DMLs 🐢 > execute large DMLs 🐢 > update test set v = v + 1 where k = 1; -- lock k = 1 > update test set v = v + 1 where k = 1; -- lock k = 1, block > update test set v = v + 1 where k = 1; -- lock k = 1, block > commit; lock released, retry update test set v = v + 1 where k = 1; blocked > commit; lock released, retry update test set v = v + 1 where k = 1; Document: Pessimistic Lock Transaction

• https://docs.pingcap.com/ja/tidb/stable/pessimistic-transaction

問題：悲観的ロック自体のコスト ● ● ● TiKV に書き込むと、 CPU/IO リソースの消費が増加しま す。 ○ 悲観的なロックが Disk で永続性を保証します。 ○ 悲観的なロックが Raft でレプリカを作ります。 悲観的ロックが DML レイテンシを上がります。 解決の鍵：悲観的ロックが失敗しても、トランザクショ ンが失敗する可能性はありますが、正確性を損なうこ とはありません。

悲観的ロック - レイテンシ ● パイプライン化されたロック ● 競合がない場合、 TiKV はロック成功を返し、バックグラ ウンドで Raftstore を通じてロックを書き込みます。 TiKV Pipelined Lock Type Document: Pipelined Lock

• https://github.com/tikv/tikv/blob/v8.1.0/src/storage/txn/scheduler.rs#L1988-L1989
• https://docs.pingcap.com/ja/tidb/stable/pessimistic-transaction#pipelined-locking-process

悲観的ロック - 資源を省略 ● メモリ化 ● ● ロックは出来るだけ TiKV leader のメモリで保存します。 メモリが足りない場合、パイプライン化されたロックにフォール バックします。 リーダーが移動または分割されると、ロックはリーダーととも に移動します。 ● TiKV In-mem Lock Type TiDB In-mem Pessimistic Lock Design

• https://github.com/tikv/tikv/blob/ba73b0d92d94463d74543550d0efe61fa6a6f416/src/storage/txn/scheduler.rs#L1990-L1991
• https://github.com/tikv/rfcs/blob/master/text/0077-in-memory-pessimistic-locks.md

悲観的ロック - 残りの興味深いトピック ● ● ● デッドロック検出 ○ https://github.com/tikv/tikv/blob/v8.1.0/src/server/lock_manager/deadlock.rs#L113-L130 ロック待ちの可観測性 ○ https://github.com/pingcap/tidb/blob/v8.1.0/docs/design/2021-04-26-lock-view.md ロック待ちのスケジュール ○ https://github.com/tikv/rfcs/pull/100 ○ https://github.com/tikv/tikv/issues/13298

• https://github.com/tikv/tikv/blob/v8.1.0/src/server/lock_manager/deadlock.rs#L113-L130
• https://github.com/pingcap/tidb/blob/v8.1.0/docs/design/2021-04-26-lock-view.md
• https://github.com/tikv/rfcs/pull/100
• https://github.com/tikv/tikv/issues/13298

Part IV トランザクションのサイズ / 24

メモリの制限 ● ● ● TB（テラバイト）単位のトランザクション を実行するユーザーがいます。 トランザクションが commit 前に、TiDB のメモリ内でバッファリングされます。 トランザクションのサイズが無制限であ る場合、OOM（Out of Memory）が発 生します。

メモリの制限 ● MemBuffer（赤黒木）の時間計算量は O(log N)であるため、トランザクションのサイズが大きく なるとパフォーマンスが低下する可能性があります。

制限を解除 ● ● ● パイプライン書き込み。 ユーザーに向かえインタフェスはバルク DML と呼ばれている。 トランザクション実行中の変更を TiKV にフラッシュ。 Doc: bulk DML TiDB Pipelined DML Design

• https://docs.pingcap.com/tidb/stable/system-variables#tidb_dml_type-new-in-v800
• https://github.com/pingcap/tidb/blob/master/docs/design/2024-01-09-pipelined-DML.md

メリット ● TiDB のメモリ利用が大幅に下がります（上：一気に書き込み、下：パイプライン書き込み）

メリット ● スムーズな書き込みフロー（上：一気に書き込み、下：パイプライン書き込み）

問題 ● パイプラインフラッシュはロックが TiKV に長い時間で存在あるのせい、下流のデータ同期を長時間 ブロックする可能性があります。 ○ 解決: https://github.com/tikv/rfcs/pull/114

• https://github.com/tikv/rfcs/pull/114

Thank you! / 31