Upgrade to Pro — share decks privately, control downloads, hide ads and more …

分散トランザクション in CockroachDB / Distributed Tx in C...

分散トランザクション in CockroachDB / Distributed Tx in CockroachDB

kota2and3kan

July 16, 2021
Tweet

More Decks by kota2and3kan

Other Decks in Technology

Transcript

  1. • Name: Takanori Yokoyama ◦ @kota2and3kan (Twitter, GitHub) • Job:

    Technical Support • Like: DB ◦ PostgreSQL, CockroachDB • Dislike: Real Cockroach @kota2and3kan こたつ&&みかん Who am I.
  2. 目次 • 超概要 • 課題 • COMMIT / ABORT (Write)

    の動作 • Read の動作 • Parallel Commits • Timestamp を使った Tx の制御 • 宣伝 • まとめ
  3. Node 1 Node 3 クラスタ構成 (3匹の場合) Node 2 • 分散

    DB なので、複数 Node で構成されたクラ スタで動作する。 論理的に 1つの DB
  4. データの格納 • RDBMS なのでユーザか らは TABLE に見える。 • TABLE は

    Key-Value 形 式に変換される。 • Key-Value は 512MB に 分割される (Range)。 Range Range Range
  5. データの格納 • RDBMS なのでユーザか らは TABLE に見える。 • TABLE は

    Key-Value 形 式に変換される。 • Key-Value は 512MB に 分割される (Range)。 • 各 Range を分散して 各 Node に格納する。 k1 ~ k10 k10 ~ k20 k20 ~ k30 Range Range Range
  6. データの格納 • RDBMS なのでユーザか らは TABLE に見える。 • TABLE は

    Key-Value 形 式に変換される。 • Key-Value は 512MB に 分割される (Range)。 • 各 Range を分散して 各 Node に格納する。 • Raft を使って Replica も 作成される (デフォルト 3 つ)。 k1 ~ k10 Replica Replica k10 ~ k20 Replica Replica k20 ~ k30 Replica Replica Range Range Range Raft Group 1 Raft Group 2 Raft Group 3
  7. Node の役割 (全ての Node が Coordinator) k1 ~ k10 Replica

    Replica k10 ~ k20 Replica Replica k20 ~ k30 Replica Replica Tx1: Write (k15, v1) Tx2: Read (k3) Tx3: Write (k28, v2) Tx4: Read (k5) Tx5: Write (k12, v3) • クラスタ内の Node 間に 役割の差異はない。 • 全ての Node が Coordinator として動作 することが可能。 • つまり、全ての Node で Read / Write の Tx を処 理可能。
  8. Node の役割 (全ての Node が Coordinator) k1 ~ k10 Replica

    Replica k10 ~ k20 Replica Replica k20 ~ k30 Replica Replica Tx1: Write (k15, v1) Tx3: Write (k28, v2) • CockroachDB では、 Coordinator Node のこと を Gateway Node と呼 ぶ。 • Gateway Node は、処理 対象の key を持っている Node に、クエリをルー ティングする。
  9. 課題 1 : Atomicity を満たす k1 ~ k10 Replica Replica

    k10 ~ k20 Replica Replica k20 ~ k30 Replica Replica Tx: Write (k1 , v1) Write (k10, v2) Write (k20, v3) • Tx 内の複数 Write は、 全て COMMIT される か、全て ABORT される か、のどちらかである必 要がある。 • 中途半端な状態は許され ない。 • つまり、Atomicity (All or Nothing) を満たす必要 がある。
  10. 課題 2 : Tx の状態を判断 k1 ~ k10 Replica Replica

    k10 ~ k20 Replica Replica k20 ~ k30 Replica Replica • ある Tx (Tx1) が k15 を Write する。 • 他の Tx (Tx2) が k15 を Read する。 • この時、Tx2 は Tx1 が COMMIT した / ABORT した / 処理の途中 (未確 定)、のどれであるかを判 断する必要がある。 Tx1: Write (k15, v1) Tx2: Read (k15) \ イソガシイ /
  11. 課題 3 : Tx の順番を判断 k1 ~ k10 Replica Replica

    k10 ~ k20 Replica Replica k20 ~ k30 Replica Replica • 実際には複数の Tx が複 数の Node で同時に実 行される。 • この時、各 Tx の実行順 序を判断する必要があ る。 • e.g. a) Tx1 -> Tx2 -> Tx3 b) Tx2 -> Tx3 -> Tx1 c) Tx3 -> Tx1 -> Tx2 etc... Tx1: Write (k15, v1) Write (k3, v2) Tx2: Write (k3, v3) Write (k25, v4) Tx3: Read (k15) Read (k25)
  12. 用語概要 • Transaction Record ◦ https://github.com/cockroachdb/cockroach/blob/v20.2.5/pkg/roachpb/data.pb.go#L940 • Write Intent ◦

    https://github.com/cockroachdb/cockroach/blob/v20.2.5/pkg/roachpb/data.pb.go#L985 ◦ https://github.com/cockroachdb/cockroach/blob/v20.2.5/pkg/storage/enginepb/mvcc3.pb.go#L 31 • Transaction Liveness Threshold ◦ https://github.com/cockroachdb/cockroach/blob/v20.2.5/pkg/kv/kvserver/txnwait/queue.go#L46
  13. 用語概要 (Transaction Record) • Transaction の状態を管理する。 • Tx 内で最初に Write

    された key と同じ Range に書き込まれる。 • 以下の State がある。 ◦ PENDING ▪ Tx は処理中。 ◦ COMMITTED ▪ Tx は COMMIT 済み。 ◦ STAGING ▪ Tx は Parallel Commits で処理中。 ◦ ABORTED ▪ Tx は ABORT 済み。 ◦ (MISSING) ▪ Transaction Record そのものが無い。
  14. 用語概要 (Write Intent) • Transaction の状態 (COMMIT / ABORT) が確定していないレコード

    (KV) に付けられる印。 • 以下のような情報を持っている。 ◦ 関連する (当該レコードを Write した) Tx の ID。 ◦ Write Intent が書き込まれた時間。
  15. 用語概要 (Transaction Liveness Threshold) • Transaction の生死 (Tx を管理している Node

    の生死) を判断するための 閾値 (死んだと判断するまでの時間)。 ◦ Gateway Node での障害発生有無を確認する場合等に使われる。 ◦ 文字通り、そのまんまの感じのやつ。
  16. COMMIT の仕組み Range : Set of KV date (512BM) Tx1

    (timestamp t1) BEGIN; Write (key1, x1); COMMIT; key1 (t0): x0 key2 (t0): y0 key3 (t0): z0
  17. Tx 開始 Range : Set of KV date (512BM) Tx1

    (t1) BEGIN; Write (key1, x1); COMMIT; key1 (t0): x0 key2 (t0): y0 key3 (t0): z0
  18. key1 を更新 Range : Set of KV date (512BM) Tx1

    (t1) BEGIN; Write (key1, x1); COMMIT; Write (UPDATE) は Inplace   Update ではなく、新しい   Timestamp で追記する。 この時 COMMIT / ABORT  が 確定していない KV には  “write intent” という印が付 けられる。 key1 (t0): x0 key2 (t0): y0 key3 (t0): z0 key1 (t1): x1 (intent:Tx1)
  19. Transaction Record (PENDING) を作成 Range : Set of KV date

    (512BM) Tx1 (t1) BEGIN; Write (key1, x1); COMMIT; Tx の状態を管理するための ”Transaction Record” が他の KV データ同様に書き込まれる。 各 “write intent” は、対応する Transaction Record を特定する 情報 (Tx の ID) を持っている。 key1 (t0): x0 key2 (t0): y0 key3 (t0): z0 key1 (t1): x1 (intent:Tx1) Tx1’s “Transaction Record” ------------------------------------ State: PENDING
  20. Transaction Record の State を COMMIT に更新 Range : Set

    of KV date (512BM) Tx1 (t1) BEGIN; Write (key1, x1); COMMIT; COMMIT を実行すると、  Transaction Record の値が COMMITTED に変更される。 このタイミングで、クライアントに COMMIT 完了を返す。 key1 (t0): x0 key2 (t0): y0 key3 (t0): z0 key1 (t1): x1 (intent:Tx1) Tx1’s “Transaction Record” ------------------------------------ State: COMMITTED
  21. “write intent” を削除 (COMMIT とは非同期で実施) Range : Set of KV

    date (512BM) BEGIN; Write (key1, x1); COMMIT; key1 (t0): x0 key2 (t0): y0 key3 (t0): z0 key1 (t1): x1 Tx1’s “Transaction Record” ------------------------------------ State: COMMITTED COMMIT 完了後、非同期で “write intent” が削除され、通常 の KV と同じ状態になる。
  22. Tx Record を削除 (COMMIT とは非同期で実施) Range : Set of KV

    date (512BM) BEGIN; Write (key1, x1); COMMIT; key1 (t0): x0 key2 (t0): y0 key3 (t0): z0 key1 (t1): x1 Tx1’s “Transaction Record” ------------------------------------ State: COMMITTED Tx に関連する全ての “write intent” が削除された後、 Transaction Record が非同期 で削除される。
  23. ABORT の仕組み Range : Set of KV date (512BM) Tx1

    (timestamp t1) BEGIN; Write (key1, x1); ABORT; key1 (t0): x0 key2 (t0): y0 key3 (t0): z0
  24. Tx 開始 Range : Set of KV date (512BM) Tx1

    (t1) BEGIN; Write (key1, x1); ABORT; key1 (t0): x0 key2 (t0): y0 key3 (t0): z0
  25. key1 を更新 Range : Set of KV date (512BM) Tx1

    (t1) BEGIN; Write (key1, x1); ABORT; Write (UPDATE) は Inplace   Update ではなく、新しい   Timestamp で追記する。 この時 COMMIT / ABORT  が 確定していない KV には  “write intent” という印が付 けられる。 key1 (t0): x0 key2 (t0): y0 key3 (t0): z0 key1 (t1): x1 (intent:Tx1)
  26. Transaction Record (PENDING) を作成 Range : Set of KV date

    (512BM) Tx1 (t1) BEGIN; Write (key1, x1); ABORT; Tx の状態を管理するための ”Transaction Record” が他の KV データ同様に書き込まれる。 各 “write intent” は、対応する Transaction Record を特定する 情報 (Tx の ID) を持っている。 key1 (t0): x0 key2 (t0): y0 key3 (t0): z0 key1 (t1): x1 (intent:Tx1) Tx1’s “Transaction Record” ------------------------------------ State: PENDING
  27. Transaction Record の State を ABORT に更新 Range : Set

    of KV date (512BM) Tx1 (t1) BEGIN; Write (key1, x1); ABORT; ABORT を実行すると、  Transaction Record の値が ABORTED に変更される。 key1 (t0): x0 key2 (t0): y0 key3 (t0): z0 key1 (t1): x1 (intent:Tx1) Tx1’s “Transaction Record” ------------------------------------ State: ABORTED
  28. “write intent” を削除 (ABORT とは非同期で実施) Range : Set of KV

    date (512BM) BEGIN; Write (key1, x1); ABORT; key1 (t0): x0 key2 (t0): y0 key3 (t0): z0 key1 (t1): x1 (intent:Tx1) Tx1’s “Transaction Record” ------------------------------------ State: ABORTED ABORT 後、非同期で ABORT された key が削除される。
  29. Tx Record を削除 (ABORT とは非同期で実施) Range : Set of KV

    date (512BM) BEGIN; Write (key1, x1); ABORT; key1 (t0): x0 key2 (t0): y0 key3 (t0): z0 Tx1’s “Transaction Record” ------------------------------------ State: ABORTED Tx に関連する全ての key が削 除された後、Transaction Record が非同期で削除される。
  30. Read Tx はどの値を読み込むのか? Range : Set of KV date (512BM)

    Tx1 (timestamp t1) BEGIN; Write (key1, x1); COMMIT / ABORT; Tx2 (timestamp t2) Read (key1); key1 (t0): x0
  31. Read Tx は Timestamp を見て読み込む値を決める Range : Set of KV

    date (512BM) Tx1 (t1) BEGIN; Write (key1, x1); Tx1’s “Transaction Record” ------------------------------------ State: PENDING Tx2 (t2) Read (key1); -> x0 t0 < t2 < t1 だった場合は、t0 の値 (x0) を 読む。 key1 (t1): x1 (intent:Tx1) key1 (t0): x0
  32. Read Tx は Timestamp を見て読み込む値を決める Range : Set of KV

    date (512BM) Tx1 (t1) BEGIN; Write (key1, x1); Tx1’s “Transaction Record” ------------------------------------ State: PENDING Tx2 (t2) Read (key1); -> x1 (intent:Tx1) t0 < t1 < t2 だった場合は、t1 の値 (x1) を 読む。(x1 は “write intent” なのでこの時 点で COMMIT / ABORT は不明) key1 (t1): x1 (intent:Tx1) key1 (t0): x0
  33. Read した値が “write intent” だった場合 Range : Set of KV

    date (512BM) Tx1 (t1) BEGIN; Write (key1, x1); Tx1’s “Transaction Record” ------------------------------------ State: PENDING Read した値が “write intent” だった場合、 Tx Record の値を確認する。 key1 (t1): x1 (intent:Tx1) key1 (t0): x0 Tx2 (t2) Read (key1); -> x1 (intent:Tx1)
  34. Read した値が “write intent” だった場合 (COMMIT) Range : Set of

    KV date (512BM) Tx1 (t1) BEGIN; Write (key1, x1); COMMIT; Tx1’s “Transaction Record” ------------------------------------ State: COMMITTED Tx Record の値が COMMITTED だった 場合は COMMIT 済みなので、そのまま x1 を Read する。 key1 (t1): x1 (intent:Tx1) key1 (t0): x0 Tx2 (t2) Read (key1); -> x1
  35. Read した値が “write intent” だった場合 (ABORT) Range : Set of

    KV date (512BM) Tx1 (t1) BEGIN; Write (key1, x1); ABORT; Tx1’s “Transaction Record” ------------------------------------ State: ABORTED Tx Record の値が ABORTED だった場合 は Tx1 の更新が無かったことになるので、 x0 を Read する。 key1 (t1): x1 (intent:Tx1) key1 (t0): x0 Tx2 (t2) Read (key1); -> x0
  36. Read した値が “write intent” だった場合 (PENDING) Range : Set of

    KV date (512BM) Tx1 (t1) BEGIN; Write (key1, x1); … ... Tx1’s “Transaction Record” ------------------------------------ State: PENDING Tx Record の値が PENDING だった場合 は状態 (COMMIT / ABORT) が確定して いないので、Tx1 の完了を待つ。 key1 (t1): x1 (intent:Tx1) key1 (t0): x0 Tx2 (t2) Read (key1); -> wait...
  37. Read した値が “write intent” だった場合 (MISSING) Range : Set of

    KV date (512BM) Tx1 (t1) BEGIN; Write (key1, x1); 特定のタイミング (Tx 処理中) や Gateway Node の障害等に起因して、Tx Record が 存在しない場合もある。 key1 (t1): x1 (intent:Tx1) key1 (t0): x0 Tx2 (t2) Read (key1); -> ??? Tx1’s “Transaction Record” ------------------------------------ MISSING
  38. Read した値が “write intent” だった場合 (MISSING) Range : Set of

    KV date (512BM) Tx1 (t1) BEGIN; Write (key1, x1); Tx Record が無い場合は “write intent” の Timestamp が “Transaction Liveness Threshold” の範囲内か否かをチェックす る。 key1 (t1): x1 (intent:Tx1) key1 (t0): x0 Tx2 (t2) Read (key1); -> ??? 無い...? Tx1’s “Transaction Record” ------------------------------------ MISSING
  39.   補足 (Transaction Liveness Threshold) Node 1 Tx1 (t1) BEGIN; Write

    (key1, x1); … Range : Set of KV date (512BM) Tx1’s “Transaction Record” ------------------------------------ State: PENDING key1 (t0): x0 key1 (t1): x1 (intent:Tx1) SQL を受け取った Gateway Node (いわゆるコーディネーター) が Tx を管理している。 Manage Create Write \ カンリ /
  40.   補足 (Transaction Liveness Threshold) Node 1 Tx1 (t1) BEGIN; Write

    (key1, x1); … Range : Set of KV date (512BM) Tx1’s “Transaction Record” ------------------------------------ State: PENDING key1 (t0): x0 key1 (t1): x1 (intent:Tx1) Tx1 の途中で Node 障害が発生すると、その Node が管理していた Tx1 は ABORT することになるが、Range の中に Transaction Record が PENDING のまま残ってしまう。 ~
  41.   補足 (Transaction Liveness Threshold) Node 1 Range : Set of

    KV date (512BM) Tx1’s “Transaction Record” ------------------------------------ State: PENDING key1 (t0): x0 key1 (t1): x1 (intent:Tx1) Range の中に Transaction Record が PENDING のまま残ってい ると、他の Tx2 が Tx1 の状態を判断できず、いつまでも Tx1 の状 態が確定 (COMMIT or ABORT) するのを待ってしまう。 Tx2 (t2) Read (key1); -> wait... Wait forever... Read \ マダー? / Node 2
  42.   補足 (Transaction Liveness Threshold) Node 1 TxnCoordSender Tx1 (t1) BEGIN;

    Write (key1, x1); … Range : Set of KV date (512BM) Tx1’s “Transaction Record” ------------------------------------ State: PENDING key1 (t0): x0 key1 (t1): x1 (intent:Tx1) Transaction Record の残存を防ぐため Gateway Node 内の TxnCoordSender が Transaction Record に対して定期的に Heartbeat を実施している。多分デフォルト 1秒間隔。 https://github.com/cockroachdb/cockroach/blob/v20.2.5/pkg/base/constants.go#L27 Heartbeat \ イキテルヨ /
  43.   補足 (Transaction Liveness Threshold) Node 1 TxnCoordSender Tx1 (t1) BEGIN;

    Write (key1, x1); … Range : Set of KV date (512BM) Tx1’s “Transaction Record” ------------------------------------ Tx1 is expired! Heartbeat が一定時間途絶えた場合、Tx (Node) が死んでいると判 断できる。この Tx の生死を判断する閾値が “Transaction Liveness Threshold”。多分デフォルト 5秒。 https://github.com/cockroachdb/cockroach/blob/v20.2.5/pkg/kv/kvserver/txnwait/queue.go#L46 ~ Heartbeat key1 (t0): x0 key1 (t1): x1 (intent:Tx1)
  44. Node 1 TxnCoordSender Range : Set of KV date (512BM)

    Tx1’s “Transaction Record” ------------------------------------ Tx1 is expired! key1 (t0): x0 key1 (t1): x1 (intent:Tx1) Tx2 (t2) Read (key1); -> x1 (intent:Tx1) 2. Check 1. Read \ イッタカ... / Heartbeat   補足 (Transaction Liveness Threshold) Tx1 を管理する Node が死んだ場合でも、他の Tx2 が write intent 読み込み Transaction Record を確認した際に、正しく「死んだ」と判 断できる。 Node 2
  45. Node 1 TxnCoordSender Range : Set of KV date (512BM)

    Tx1’s “Transaction Record” ------------------------------------ State: ABORTED key1 (t0): x0 key1 (t1): x1 (intent:Tx1) Tx2 (t2) Read (key1); -> x0 ABORT Read \ サラバダ... / Heartbeat   補足 (Transaction Liveness Threshold) Tx1 が「死んだ」と判断された場合、それを見つけた Tx2 を管理する Node 2 が Tx1 の Transaction Record の値を ABORTED に更新 し、Tx2 は 1つ前の値 x0 を Read する (t0 < t1 < t2 の場合)。 Node 2
  46. 補足 (Transaction Record が作成される条件) Node 1 TxnCoordSender Tx1 (t1) BEGIN;

    Write (key1, x1); … Range : Set of KV date (512BM) Tx1’s “Transaction Record” ------------------------------------ State: XXXXXX key1 (t0): x0 key1 (t1): x1 (intent:Tx1) 1. COMMIT が実行された時。(※詳細は Parallel Commits で) 2. TxnCoordSender が Heartbeat を実行した時。 3. Tx が強制的に ABORT された時。 Create \ ジョウケン /
  47. 補足 (Transaction Record が作成される条件1) Node 1 Tx1 (t1) BEGIN; Write

    (key1, x1); COMMIT; Range : Set of KV date (512BM) Tx1’s “Transaction Record” ------------------------------------ State: STAGING 1. COMMIT が実行された時 (STAGING)。 ※何故 COMMIT のタイミングなのかについては後述する   Parallel Commits 参照。 When it COMMITs \ コミット / key1 (t0): x0 key1 (t1): x1 (intent:Tx1)
  48. 補足 (Transaction Record が作成される条件2) Node 1 TxnCoordSender Tx1 (t1) BEGIN;

    Write (key1, x1); … Range : Set of KV date (512BM) Tx1’s “Transaction Record” ------------------------------------ State: PENDING 2. TxnCoordSender が Heartbeat を実行した時。 ※Heartbeat は 1秒間隔なので、Tx 内の最初の Write から   1秒経つと Transaction Record が作成される。 When it Heartbeats \ イキテルヨ / key1 (t0): x0 key1 (t1): x1 (intent:Tx1)
  49. Node 1 Tx1 (t1) BEGIN; Write (key1, x1); … Range

    : Set of KV date (512BM) Tx1’s “Transaction Record” ------------------------------------ State: PENDING key1 (t0): x0 key1 (t1): x1 (intent:Tx1) 3. Tx1 が key1 への Write は実行したが Transaction Record は まだ作成していない状態で障害が発生すると、write intent は 存在するが対応する Transaction Record が無い、という状態 になる。   補足 (Transaction Record が作成される条件3) ~ Write Not yet...
  50. Node 1 Range : Set of KV date (512BM) key1

    (t1): x1 (intent:Tx1) Node 2 Tx2 (t2) Read (key1); -> x1 (intent:Tx1) 2. Check 1. Read \ ナイ / 3. 他の Tx2 が write intent 読み込んだ際に、対応する Transaction Record が存在しないことを検知する。 ※ただし、この時点で Node 1 が死んでいるか否かは判断でき ない (単純に Node 1 が処理途中の可能性が有る)。 補足 (Transaction Record が作成される条件3) key1 (t0): x0
  51. Node 1 Range : Set of KV date (512BM) Node

    2 Check Timestamp \ カクニン / 3. Transaction Record が無い場合は、読み込んだ write intent の Timestamp が Transaction Liveness Threshold 以内か否 かを確認する。 補足 (Transaction Record が作成される条件3) key1 (t1): x1 (intent:Tx1) Tx2 (t2) Read (key1); -> x1 (intent:Tx1) key1 (t0): x0
  52. Node 1 Range : Set of KV date (512BM) Node

    2 Treat as PENDING \ マツワ / 3. write intent の Timestamp t1 が Transaction Liveness Threshold 以内の場合 PENDING として扱い、待つ。 多分 (Current time - t1) < 5 の場合。 補足 (Transaction Record が作成される条件3) key1 (t1): x1 (intent:Tx1) Tx2 (t2) Read (key1); -> x1 (intent:Tx1) key1 (t0): x0
  53. Node 1 Range : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: ABORTED key1 (t0): x0 key1 (t1): x1 (intent:Tx1) Node 2 Tx2 (t2) Read (key1); -> x0 ABORT Read \ シンダナ / 補足 (Transaction Record が作成される条件3) 3. write intent の Timestamp t1 が Transaction Liveness Threshold の範囲外 (古い) の場合、Tx1 を ABORT させるた めに Transaction Record を作成する。 多分 (Current time - t1) > 5 の場合。
  54. Read した値が “write intent” だった場合 (MISSING) Range : Set of

    KV date (512BM) Tx1 (t1) BEGIN; Write (key1, x1); Tx1’s “Transaction Record” ------------------------------------ MISSING Tx Record が無い場合は “write intent” の Timestamp が “Transaction Liveness Threshold” の範囲内か否かをチェックす る。 key1 (t0): x0 key1 (t1): x1 (intent:Tx1) Tx2 (t2) Read (key1); -> ??? 無い...? 再掲
  55. Read した値が “write intent” だった場合 (MISSING) Range : Set of

    KV date (512BM) Tx1 (t1) BEGIN; Write (key1, x1); “write intent” の Timestamp が “Transaction Liveness Threshold” 以内 の場合、PENDING として扱い、待つ。 key1 (t0): x0 key1 (t1): x1 (intent:Tx1) Tx2 (t2) Read (key1); -> wait... Tx1’s “Transaction Record” ------------------------------------ MISSING
  56. Read した値が “write intent” だった場合 (MISSING) Range : Set of

    KV date (512BM) Tx1 (t1) BEGIN; Write (key1, x1); ※Tx1 に「何らかの  問題が発生した」 と 判断される。 key1 (t0): x0 key1 (t1): x1 (intent:Tx1) Tx2 (t2) Read (key1); -> x0 “write intent” の Timestamp が “Transaction Liveness Threshold” の範 囲外 (古い) の場合、ABORT として処理し x0 を Read する。 Tx1’s “Transaction Record” ------------------------------------ State: ABORTED
  57. v2.0 まで BEGIN; Write (key1, x1); Write (key2, y1); Write

    (key3, z1); COMMIT; Timeline Tx 内の Statement は順番に 実行される。
  58. v2.0 まで BEGIN; Write (key1, x1); Write (key2, y1); Write

    (key3, z1); COMMIT; Timeline Write1 実行 Tx Record 作成 (PENDING) 最初の Statement と一緒に Tx Record も作成される。
  59. v2.0 まで BEGIN; Write (key1, x1); Write (key2, y1); Write

    (key3, z1); COMMIT; Timeline 各 Statement は並列実行でき ないので、順番に実行される。 Write2 実行
  60. v2.0 まで BEGIN; Write (key1, x1); Write (key2, y1); Write

    (key3, z1); COMMIT; Timeline 各 Statement は並列実行でき ないので、順番に実行される。 Write3 実行
  61. v2.0 まで BEGIN; Write (key1, x1); Write (key2, y1); Write

    (key3, z1); COMMIT; Timeline 最後に、Tx Record の値を PENDING -> COMMITTED に変える処理が実行される。 COMMIT 実行 Tx Record 更新 (COMMIT)
  62. v2.0 まで BEGIN; Write (key1, x1); Write (key2, y1); Write

    (key3, z1); COMMIT; Timeline Tx 内の Statement は順番に 実行されるので、処理時間は O(n) になる。  ※n = Num of Statements COMMIT (Tx Record の更新 処理) も入れると O(n+1) にな る。
  63. BEGIN; Write (key1, x1); Write (key2, y1); Write (key3, z1);

    COMMIT; Timeline v2.1 で Pipelining という機能 が実装され、Tx 内の各 Statement は並列で実行され るようになった。 v2.1 ~ v19.1 まで (Pipelining)
  64. v2.1 ~ v19.1 まで (Pipelining) BEGIN; Write (key1, x1); Write

    (key2, y1); Write (key3, z1); COMMIT; Timeline Write1 実行 Tx Record 作成 (PENDING) Write2 実行 Write3 実行 各 Statement を並列で実行。 ただし、全ての Statement の 書き込み完了が返ってくるまで Tx Record の値を COMMIT に更新できない。
  65. v2.1 ~ v19.1 まで (Pipelining) BEGIN; Write (key1, x1); Write

    (key2, y1); Write (key3, z1); COMMIT; Timeline 全ての Statement の書き込み 完了が返ってきたら、Tx を COMMIT する (Tx Record の 値を COMMITTED に更新す る)。 COMMIT 実行 Tx Record 更新 (COMMIT)
  66. v2.1 ~ v19.1 まで (Pipelining) BEGIN; Write (key1, x1); Write

    (key2, y1); Write (key3, z1); COMMIT; Timeline Pipelining により各 Statement を並列で実行でき るようになったので、理論上の 最短処理時間は O(2) になっ た。 ※この O(2) を O(1) にするの が Parallel Commits。
  67. BEGIN; Write (key1, x1); Read (key1); Write (key3, z1); COMMIT;

    Timeline なお、Statement 間に依存関 係が有る場合は、並列には実 行されず、ちゃんと順番に実行 される仕組みになっている。 v2.1 ~ v19.1 まで (Pipelining : Read-Your-Writes)
  68. BEGIN; Write (key1, x1); Read (key1); Write (key3, z1); COMMIT;

    Timeline Write1 と Write3 は別々の key に対する Write であり、依 存関係はないので並列実行。 v2.1 ~ v19.1 まで (Pipelining : Read-Your-Writes)
  69. BEGIN; Write (key1, x1); Read (key1); Write (key3, z1); COMMIT;

    Timeline Write1 と Write3 は別々の key に対する Write であり、依 存関係はないので並列実行。 Read は Write1 が更新した key1 の値を読む必要が有る (依存関係が有る) ので、 Write1 完了後に実行される。 v2.1 ~ v19.1 まで (Pipelining : Read-Your-Writes)
  70. BEGIN; Write (key1, x1); Read (key1); Write (key3, z1); COMMIT;

    Timeline Tx 内の Statement 間に依存 関係が有る場合は、必ずしも O(2) になるわけではない。 ※あくまで理論上の最短が O(2) になる感じ。 ※この “理論上の最短” を O(2) から O(1) にするのが Parallel Commits。 v2.1 ~ v19.1 まで (Pipelining : Read-Your-Writes)
  71. Parallel Commits (v19.2 ~) BEGIN; Write (key1, x1); Write (key2,

    y1); Write (key3, z1); COMMIT; Timeline Parallel Commits は、 COMMIT の処理 (Tx Record の作成) も他の Statement と 並列で実行することで、処理時 間の理論上の最短を O(1) に するもの。 Tx 内で Write する key が全て 確定している必要があり、 Transaction Record は COMMIT のタイミングで作成 される。
  72. Parallel Commits (v19.2 ~) BEGIN; Write (key1, x1); Write (key2,

    y1); Write (key3, z1); COMMIT; Timeline 書き込み完了前 に COMMIT して 大丈夫か...?
  73. Parallel Commits (Write) Node 1 Range1 : Set of KV

    date (512BM) key1 (t0): x0 Range2 : Set of KV date (512BM) key2 (t0): y0 \ スタート / Client key1, key2 を更新する。 BEGIN; Write (key1, x1); Write (key2, y2); COMMIT;
  74. Node 1 Range1 : Set of KV date (512BM) Range2

    : Set of KV date (512BM) \ リクエスト / Client BEGIN; Write (key1, x1); Write (key2, y2); COMMIT; Write のタイミングではまだ Tx Record は作成しない。 Parallel Commits (Write) key1 (t0): x0 key2 (t0): y0 key1 (t1): x1 (intent:Tx1) key2 (t1): y1 (intent:Tx1) Write Write
  75. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: STAGING Keys: key1, key2 Range2 : Set of KV date (512BM) key1 (t1): x1 (intent:Tx1) key2 (t1): y1 (intent:Tx1) \ ヘイレツ / Parallel Write Client BEGIN; Write (key1, x1); Write (key2, y2); COMMIT; COMMIT のタイミングで Tx Record を作成する。この時、State には STAGING を設定 し、一緒に「更新対象の key の一覧 (key1, key2)」の情報を Tx Record 内に含める。 Parallel Commits (Write) key1 (t0): x0 key2 (t0): y0
  76. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: STAGING Keys: key1, key2 Range2 : Set of KV date (512BM) \ カンリョウ / Write OK Client BEGIN; Write (key1, x1); Write (key2, y2); COMMIT; Write OK Write OK 各 Write 及び Tx Record の作成が完了したことを確認する。 Parallel Commits (Write) key1 (t1): x1 (intent:Tx1) key2 (t1): y1 (intent:Tx1) key1 (t0): x0 key2 (t0): y0
  77. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: STAGING Keys: key1, key2 Range2 : Set of KV date (512BM) \ オワッタヨ / Client BEGIN; Write (key1, x1); Write (key2, y2); COMMIT; COMMIT Complete 各 Write 及び Tx Record の作成が完了したことを確認した時点で、Client に COMMIT 完了を返す。 Parallel Commits (Write) key1 (t1): x1 (intent:Tx1) key2 (t1): y1 (intent:Tx1) key1 (t0): x0 key2 (t0): y0
  78. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: COMMITTED Keys: key1, key2 Range2 : Set of KV date (512BM) \ ヒドウキ / Client Client に COMMIT 完了を返した後に「非同期」かつ並列で Tx Record の更新 (COMMITTED に更新) と write intent の削除を実施する。他の Tx が Read する可能 性が有るため、非同期ではあるが「できるだけ速く」更新する。 State is COMMITTED Resolve intent Resolve intent Parallel Commits (Write) key1 (t1): x1 (intent:Tx1) key2 (t1): y1 (intent:Tx1) key1 (t0): x0 key2 (t0): y0
  79. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: COMMITTED Keys: key1, key2 Range2 : Set of KV date (512BM) \ オワリ / Client write intent の処理完了後に、Tx Record は削除され更新した値の状態が確定 (COMMIT 済みに確定) する。 Parallel Commits (Write) key1 (t1): x1 key2 (t1): y1 key1 (t0): x0 key2 (t0): y0
  80. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: STAGING Keys: key1, key2 key1 (t1): x1 (intent:Tx1) Range2 : Set of KV date (512BM) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0 Node 2 \ リードスルヨ / \ ヘイレツ / Node 1 が Tx1 で key1, key2 を更新し、Node 1 の処理途中 (Tx Record の State が STAGING のタイミング) で Node 2 が Tx2 で key1 を Read する。 Parallel Write Parallel Commits (Read) Tx2 (t2)    ※t0 < t1 < t2 Read (key1);
  81. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: STAGING Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ リード / \ ショリチュウ... / Node 2 が Tx2 で key1 を Read すると、write intent (COMMIT or ABORT が不定) に なっている。また、Node 1 は処理中であるため Tx1 の Tx Record に定期的に Heartbeat が送信されている。 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); Read key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0 Parallel Commits (Read) Heartbeat Write OK Write OK Write OK
  82. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: STAGING Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ カクニン / \ ショリチュウ... / Node 2 (Tx2) が key1 の状態を確認するために Tx Record を参照すると、State が STAGING であることがわかる。また、Node 1 からの Heartbeat も継続しているため Node 1 (Tx1) は生きている (処理中) であることも確認できる。 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); Check key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0 Parallel Commits (Read) Heartbeat Write OK Write OK Write OK
  83. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: STAGING Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ マツワ / \ イキテルヨ / Tx1 を管理する Node1 からの Heartbeat が続いているため、Node 1 (Tx1) は生きて いる (処理中) と判断し、Node 2 (Tx2) は Tx1 が完了するまで待つ。 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); -> wait... Heartbeat key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t0): y0 Parallel Commits (Read) key2 (t1): y1 (intent:Tx1) Write OK Write OK Write OK
  84. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: STAGING Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ タイキ / \ ショリチュウ... / Tx1 は処理中... (Heartbeat は継続) Tx2 は待機... (Tx1 の完了待ち) Tx2 (t2)    ※t0 < t1 < t2 Read (key1); -> wait... key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0 Parallel Commits (Read) Heartbeat Write OK Write OK Write OK
  85. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: COMMITTED Range2 : Set of KV date (512BM) Node 2 \ オワッタッポイ / \ オワッタヨ / Tx1 の処理が完了すると、Tx2 (Node 2) は Tx1 にて更新された値 (x1) を Read する。 後述する Status Recovery Procedure は非常に重い処理であるため、Tx1 を管理する Node 1 が生きている場合は、Tx1 が COMMIT されるまで待つ。 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); -> x1 Read State is COMMITTED key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0 Parallel Commits (Read)
  86. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: STAGING Keys: key1, key2 key1 (t1): x1 (intent:Tx1) Range2 : Set of KV date (512BM) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0 Node 2 \ リードスルヨ / \ ヘイレツ / Case 1 : Node 1 が Tx1 で key1, key2 を更新し、Node 1 の処理途中 (Tx Record の State が STAGING のタイミング) で Node 2 が Tx2 で key1 を Read する。また、全て の write intent 書き込み完了後に Node 1 で障害が発生する。 Parallel Write   Status Recovery Procedure1 Tx2 (t2)    ※t0 < t1 < t2 Read (key1);
  87. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: STAGING Keys: key1, key2 key1 (t1): x1 (intent:Tx1) Range2 : Set of KV date (512BM) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0 Node 2 \ リードスルヨ / 全ての write intent 書き込み完了後に Node 1 で障害が発生する。また、Node 1 の障 害に起因して Tx1 の Tx Record への Heartbeat が途切れる。   Status Recovery Procedure1 ~ Heartbeat Tx2 (t2)    ※t0 < t1 < t2 Read (key1); Write OK Write OK Write OK
  88. Node 1 Range1 : Set of KV date (512BM) Tx1’s

    “Transaction Record” ------------------------------------ State: STAGING (expired) Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ リード / Node 2 が Tx2 で key1 を Read すると、write intent (COMMIT or ABORT が不定) に なっている。また、Node 1 に障害が発生し Heartbeat が途切れたため、Tx1 は expired となる。 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); Read key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0   Status Recovery Procedure1 Heartbeat
  89. Range1 : Set of KV date (512BM) Tx1’s “Transaction Record”

    ------------------------------------ State: STAGING (expired) Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ カクニン / Node 2 (Tx2) が key1 の状態を確認するために Tx Record を参照すると、State が STAGING であることがわかる。また、Node 1 からの Heartbeat が途切れているため Node 1 (Tx1) が死んだと判断する。 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); Check (Tx1 is expired) key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0   Status Recovery Procedure1 Node 1
  90. Range1 : Set of KV date (512BM) Tx1’s “Transaction Record”

    ------------------------------------ State: STAGING (expired) Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ サラニカクニン / Tx Record に含まれている更新対象の key の情報を基に、Tx1 の更新対象である key2 の write intent が作成されているかを確認する。 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); Check key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0   Status Recovery Procedure1 Node 1
  91. Range1 : Set of KV date (512BM) Tx1’s “Transaction Record”

    ------------------------------------ State: STAGING (expired) Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ コミットダナ / Tx Record (STAGING) 内に含まれている key の write intent が全て書き込まれている 場合、implicitly committed (暗黙的な COMMIT である) として扱い、Tx2 (Node 2) は write intent の値を Read する。 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); -> x1 Read key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0   Status Recovery Procedure1 Node 1
  92. Range1 : Set of KV date (512BM) Tx1’s “Transaction Record”

    ------------------------------------ State: COMMITTED Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ コミットダヨ / 他の Tx が Status Recovery Procedure を実行しなくても済むように、Node 2 が Tx1 の Tx Record の State を COMMITTED に更新する。 key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0   Status Recovery Procedure1 Node 1 State is COMMITTED
  93.   Status Recovery Procedure2 Node 1 Range1 : Set of KV

    date (512BM) Tx1’s “Transaction Record” ------------------------------------ State: STAGING Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ リードスルヨ / \ ヘイレツ / Case 2 : Node 1 が Tx1 で key1, key2 を更新し、Node 1 の処理途中 (Tx Record の State が STAGING のタイミング) で Node 2 が Tx2 で key1 を Read する。また、key2 の write intent 作成前に Node 1 で障害が発生する。 Parallel Write key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0 Tx2 (t2)    ※t0 < t1 < t2 Read (key1);
  94.   Status Recovery Procedure2 Node 1 Range1 : Set of KV

    date (512BM) Tx1’s “Transaction Record” ------------------------------------ State: STAGING Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ リードスルヨ / 一部の write intent 書き込み完了前に Node 1 で障害が発生する。また、Node 1 の障 害に起因して Tx1 の Tx Record への Heartbeat が途切れる。 key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); ~ Heartbeat Write OK Write OK
  95. Range1 : Set of KV date (512BM) Tx1’s “Transaction Record”

    ------------------------------------ State: STAGING (expired) Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ リード / Node 2 が Tx2 で key1 を Read すると、write intent (COMMIT or ABORT が不定) に なっている。また、Node 1 に障害が発生し Heartbeat が途切れたため、Tx1 は expired となる。 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); Read key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0   Status Recovery Procedure2 Node 1 Heartbeat
  96. Range1 : Set of KV date (512BM) Tx1’s “Transaction Record”

    ------------------------------------ State: STAGING (expired) Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ カクニン / Node 2 (Tx2) が key1 の状態を確認するために Tx Record を参照すると、State が STAGING であることがわかる。また、Node 1 からの Heartbeat が途切れているため Node 1 (Tx1) が死んだと判断する。 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); Check (Tx1 is expired) key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t0): y0 Node 1   Status Recovery Procedure2 key2 (t1): y1 (intent:Tx1)
  97. Range1 : Set of KV date (512BM) Tx1’s “Transaction Record”

    ------------------------------------ State: STAGING (expired) Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ ナイ / Tx Record に含まれている更新対象の key の情報を基に、Tx1 の更新対象である key2 の write intent が作成されているかを確認する。しかし、key2 の write intent は存 在していないことが確認される。 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); Check key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t0): y0 Node 1   Status Recovery Procedure2 key2 (t1): y1 (intent:Tx1)
  98. Range1 : Set of KV date (512BM) Tx1’s “Transaction Record”

    ------------------------------------ State: STAGING (expired) Keys: key1, key2 Range2 : Set of KV date (512BM) Node 2 \ アボートダナ / Tx1 は ABORT したものとして扱い、Tx2 (Node 2) は x0 を Read する。 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); -> x0 Read Node 1 key1 (t0): x0 key2 (t0): y0   Status Recovery Procedure2 key1 (t1): x1 (intent:Tx1) key2 (t1): y1 (intent:Tx1)
  99. Range1 : Set of KV date (512BM) Tx1’s “Transaction Record”

    ------------------------------------ State: ABORTED Range2 : Set of KV date (512BM) Node 2 \ シンダッポイ / 他の Tx が Status Recovery Procedure を実行しなくても済むように、Node 2 が Tx1 の Tx Record の State を ABORTED に更新する。 Tx2 (t2)    ※t0 < t1 < t2 Read (key1); Node 1 State is ABORTED key1 (t1): x1 (intent:Tx1) key1 (t0): x0 key2 (t1): y1 (intent:Tx1) key2 (t0): y0   Status Recovery Procedure2
  100. Parallel Commits (v19.2 ~) BEGIN; Write (key1, x1); Write (key2,

    y1); Write (key3, z1); COMMIT; Timeline COMMIT 時に作成する Tx Record (STAGING) の中に更 新対象の key の一覧を含める ことで、処理時間を (最短で) O(1) にしつつ、他の Tx の Read も正しく処理できるように している。
  101. Parallel Commits (v19.2 ~) BEGIN; Write (key1, x1); Write (key2,

    y1); Write (key3, z1); COMMIT; Update Tx Record & Remove write intent Timeline 非同期 (async) Client に COMMIT 完了を返し た後に、非同期で Tx Record の値を (できるだけ速く) COMMITTED に更新し、write intent を削除する。 Status Recovery Procedure は「重い処理」であり、通常 (Gateway Node が生きてる場 合) は COMMIT 完了を待つ が、障害発生時は他の Node で適切に対処できる。
  102. • 分散 RDBMS には分散トランザクションが必要。 • CockroachDB は Transaction Record を使って分散

    Tx を実 現している。 • 更に、Parallel Commits で性能向上も図っている。 • 今回紹介した内容以外の機能も使って (Timestamp 等を使っ て) Tx の競合を解決したり一貫性を確保したりしている。 まとめ