TiDBのトランザクションモデルの進化

1K Views

October 07, 24

#TiDB #トランザクションモデル #分散データベース #Async Commit #悲観的ロック

スライド概要

you06

@you06

スライド一覧

TiDBの開発者です。

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

ダウンロード

ダウンロード(pdf - 1.81MB)

関連スライド

各ページのテキスト

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

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

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

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

10.

ブロックせずに読み取る ● 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/トランザクション分離レベル#分離レベル

11.

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

12.

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

13.

レイテンシを下げる - 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

14.

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

15.

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

16.

レイテンシを下げる - 線形化可能性 ● ● ● 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

17.

Part III 競合耐性を上げる

18.

問題：楽観的ロックの競合耐性が低い ● ● 一度書き込み競合エラーが発生すると、トランザクション全体を再試行する必要があります。トランザクションの再試行のコストは高くつく可能性があります。 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 conﬂict, …, reason=Optimistic [try again later] > commit; ERROR 9007 (HY000): Write conﬂict, …, reason=Optimistic [try again later] > commit;

19.

悲観的ロック ● ● 悲観的ロックを導入。ステートメントがロックに遭遇した場合、再試行する必要があります。 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

20.

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

21.

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

22.

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

23.

悲観的ロック - 残りの興味深いトピック ● ● ● デッドロック検出 ○ 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