Resolving Tx Conflicts in CockroachDB ~Short Version~

Transcript

1. Resolving Tx Conflicts in CockroachDB \ ﾐｼﾞｶｲ / ~ Short Version ~
2. • Name: Takanori Yokoyama ◦ @kota2and3kan (Twitter, GitHub) • Job: Technical Support • Like: DB ◦ PostgreSQL, CockroachDB • Dislike: Real Cockroach @kota2and3kan こたつ&&みかん Who am I.
3. ※Note※ https://speakerdeck.com/kota2and3kan/how-commit-works-in-cockroachdb このスライドは、以下のスライドの続編的な位置づけです。 CockroachDB の概要等については以下のスライドをご参照ください。 \ ｿﾞｸﾍﾝ /
4. ※Note※ ちょっと自信が無いとこもあります！ 間違ってたらごめんさない！！！ \ ﾕﾙｼﾃ /
5. 目次 • Node 間の時刻差 (clock offset) について • Timestamp (HLC) を使った Tx の動作 • 宣伝 • まとめ
6. Node 間の時刻差 (clock offset) について \ ｼﾞｺｸｻ / Max clock offset enforcement
7. Max clock offset enforcement \ t1 / • CockroachDB では MVCC や Tx の Isolation のために Timestamp (Hybrid Logical Clocks) を使っている。 \ t1 / \ t1 / \ t1 / \ t1 /
8. Max clock offset enforcement • クラスタ内の各 Node では、常に (定期的に) “他の Node との時刻差 (clock offset)” を確認 している。 • クラスタ内で許容される clock offset の最大値 (max offset) は、Node 起動時に指定するオプ ション “--max-offset” で指定できる (デフォルト 500ms)。 \ t1 + 100ms / \ t1 - 50ms / \ t1 + 150ms / \ t1 - 50ms / \ t1 + 50ms /
9. Max clock offset enforcement \ t1 / \ t1 - 200ms / \ t1 / \ t1 / • クラスタ内の過半数の Node と比較し、max offset * 0.8 以上の時刻のずれを検知した Node は PANIC する。 ◦ https://github.com/cockroachdb/cockroach/blob/v21.1.0-beta.2/pkg/rpc/c lock_offset.go#L242 • このようにして、クラスタ内で発生する clock offset が一定の範囲に留まるようにしている。 ~ \ t1 - 400ms /
10. Max clock offset enforcement \ !? / \ !? / \ !? / \ t1 + 2000ms ! / • ただし、何らかの理由で Node の時刻が突然 大きくずれてしまうと、依存関係のある Tx 間で single-key linearizability が保証できなくなる可 能性があるので注意が必要。 • max offset の範囲内では single-key linearizability が保証される、らしい。 \ !? /
11. Timestamp (HLC) を使った Tx の動作 \ ﾀｲﾑｽﾀﾝﾌﾟ /
12. Timestamp (HLC) を使った Tx の動作 \ ｹｰｳﾞｨ / Tx と KV の Timestamp
13. k1 ~ k10 Tx と KV の Timestamp • CockroachDB はいわゆるシェアー ドナッシング方式 (ただし、各データ の Replica は分散して保持) なの で、各 Node が担当するデータ (key) の範囲が決まっている。 k31 ~ k40 k41 ~ k50 k11 ~ k20 k21 ~ k30 ※Replica は図から省略※ ※lease のみ図中に記載※
14. Tx1 : Write (k45, v7) Write OK k15=v5, Write OK Tx1 : Read (k15), Write (k45, v7) k1 ~ k10 • クエリを受け取った Gateway Node (Coordinator) は、当該 key を担当 する Node (Leaseholder) にクエリ をルーティングする。 k31 ~ k40 k41 ~ k50 k11 ~ k20 k21 ~ k30 Client Tx と KV の Timestamp Tx1 : Read (k15) k15=v5 ※Replica は図から省略※ ※lease のみ図中に記載※
15. Tx1 : Write (k45, v7) Write OK k15=v5, Write OK Tx1 : Read (k15), Write (k45, v7) k1 ~ k10 k31 ~ k40 k41 ~ k50 k11 ~ k20 k21 ~ k30 Client Tx と KV の Timestamp Tx1 : Read (k15) k15=v5 • この時、Tx1 の Timestamp は Gateway Node の Timestamp であ る t4 になる。 \ t4 / \ t5 / \ t3 / \ t1 / \ t2 / ※Replica は図から省略※ ※lease のみ図中に記載※
16. Tx1 : Write (k45, v7) Write OK k15=v5, Write OK Tx1 : Read (k15), Write (k45, v7) k1 ~ k10 k31 ~ k40 k41 ~ k50 k11 ~ k20 k21 ~ k30 Client Tx と KV の Timestamp Tx1 : Read (k15) at t4 k15=v5 • Read (k15) は t4 の時点での k15 の最新の値を Read する。 • Write された KV (k45=v7) の Timestamp は、Tx1 の Timestamp である t4 になる。 \ t4 / \ t5 / \ t3 / \ t1 / \ t2 / ※Replica は図から省略※ ※lease のみ図中に記載※
17. Tx1 : Write (k45, v7) Write OK k15=v5, Write OK Tx1 : Read (k15), Write (k45, v7) k1 ~ k10 k31 ~ k40 k41 ~ k50 k11 ~ k20 k21 ~ k30 Client Tx と KV の Timestamp Tx1 : Read (k15) at t4 k15=v5 \ t4 / \ k45=v7 at t4 / \ k45=v7 at t4 / \ k45=v7 at t4 / \ k45=v7 at t4 / • つまり、他の Node から見ると “k45 の最新の値 v7 は時刻 t4 で書き込 まれた” というふうに見える。 ※Replica は図から省略※ ※lease のみ図中に記載※
18. \ Read (k1) at t4 / \ Write (k1) at t5 / \ Read (k1) at t3 / \ ｵﾁﾂｹ / \ Write (k1) at t2 / • CockroachDB では全ての Node が Gateway Node (Coordinator) にな れる。 • そのため、各 Node の Timestamp を基にした複数の Tx が同時に実行 される。 • この時、Node 間に clock offset が あると、Timestamp を基にした Tx や KV の 順序が、実際の (Real Time の) Tx の実行順番と異なって しまう可能性がある。 k1 ~ k10 k31 ~ k40 k41 ~ k50 k11 ~ k20 k21 ~ k30 Tx と KV の Timestamp ※Replica は図から省略※ ※lease のみ図中に記載※
19. Timestamp (HLC) を使った Tx の動作 \ ﾘｰﾄﾞ / Read の動作
20. Timestamp (HLC) を使った Tx の動作 \ ｽﾞﾚﾃﾅｲ / Clock Offset が無い世界での Read の動作
21. Timestamp (HLC) を使った Read (Clock Offset 無し) Tx1 (key1 への Write) と Tx2 (key1 を Read) の 2つが、Tx1 -> Tx2 の順番で実行され る。Tx1 / Tx2 で Write / Read する key1 の Leaseholder は Node3。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) < ﾗｲﾄ t0 t Tx1’s Gateway Node (Node1) < ﾘｰﾄﾞ t0 t Tx2’s Gateway Node (Node2) < ﾘｰｽﾎﾙﾀﾞｰ t0 t key1’s Leaseholder (Node3) x0
22. Tx1 を受け取った Node1 (Tx1 の Gateway Node) は、ローカルの Timestamp を基 に、Tx1 に t1 を設定する。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) < Tx1.ts = t1 t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t1 Timestamp (HLC) を使った Read (Clock Offset 無し)
23. t1 Node1 は key1 の Leaseholder である Node3 に Write を送る。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) < ﾖﾛｼｸ t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) < OK t0 t key1’s Leaseholder (Node3) x0 Timestamp (HLC) を使った Read (Clock Offset 無し)
24. t1 Node3 (Leaseholder) は x1 を t1 で Write し、Node1 (Gateway Node) にレスポンスを 返す。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) < ｻﾝｸｽ t0 t Tx1’s Gateway Node (Node1) < ﾋﾏﾀﾞﾅ... t0 t Tx2’s Gateway Node (Node2) < ｶｲﾀﾖ t0 t key1’s Leaseholder (Node3) x0 x1 t1 Timestamp (HLC) を使った Read (Clock Offset 無し)
25. t1 Node1 (Gateway Node) は、Client に “Write OK” を返す。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) < Write OK t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) x0 x1 t1 t0 t key1’s Leaseholder (Node3) Timestamp (HLC) を使った Read (Clock Offset 無し)
26. t1 Tx1 完了後に、Tx2 (Read) が実行される。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) < ﾃﾞﾊﾞﾝｶﾅ? t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 x1 t1 Timestamp (HLC) を使った Read (Clock Offset 無し)
27. t1 Tx2 を受け取った Node2 (Tx2 の Gateway Node) は、ローカルの Timestamp を基 に、Tx2 に t2 を設定する。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) < Tx2.ts = t2 t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 x1 t1 t2 Timestamp (HLC) を使った Read (Clock Offset 無し)
28. t1 Node2 は key1 の Leaseholder である Node3 に Read を送る。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) < ﾖﾛｼｸ t0 t Tx2’s Gateway Node (Node2) < OK t0 t key1’s Leaseholder (Node3) x0 x1 t1 t2 Timestamp (HLC) を使った Read (Clock Offset 無し)
29. t1 Node3 (Leaseholder) は、t2 の時点での key1 の最新の値である x1 を Node2 (Gateway Node) に返す。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) < ﾋﾏﾃﾞｽﾜ... t0 t Tx1’s Gateway Node (Node1) < ｻﾝｸｽ t0 t Tx2’s Gateway Node (Node2) < x1 ﾀﾞﾖ t0 t key1’s Leaseholder (Node3) x0 x1 t1 t2 t2 x1 Timestamp (HLC) を使った Read (Clock Offset 無し)
30. t1 Node2 (Gateway Node) は、Client に “key1 = x1” を返す。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) < key1 = x1 t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 x1 t1 t2 t2 t0 t Tx1’s Gateway Node (Node1) x1 Timestamp (HLC) を使った Read (Clock Offset 無し)
31. t1 Tx1 -> Tx2 の順番で Tx が実行された時、Node 間に Clock Offset がなければ、Tx2 は正しく Tx1 で Write された値 (最新の値) を Read できる。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) < ﾗｲﾄｼﾀﾖ t0 t Tx1’s Gateway Node (Node1) < ﾘｰﾄﾞｼﾀﾖ t0 t Tx2’s Gateway Node (Node2) < ｲﾛｲﾛｼﾀﾖ t0 t key1’s Leaseholder (Node3) x0 x1 t1 t2 t2 x1 Timestamp (HLC) を使った Read (Clock Offset 無し)
32. Timestamp (HLC) を使った Tx の動作 \ ｽﾞﾚﾃﾙ / Clock Offset に起因して発生する問題
33. Clock Offset に起因して発生する問題 先程と同じように Tx1 と Tx2 が、Tx1 -> Tx2 の順番で実行される。Tx1 / Tx2 で Write / Read する key1 の Leaseholder は Node3。また、Node1 の時刻がずれており、 Cluster 内に Clock Offset がある。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) < ｽﾞﾚﾃﾙ t0 t Tx1’s Gateway Node (Node1) < ﾘｰﾄﾞ t0 t Tx2’s Gateway Node (Node2) < ﾘｰｽﾎﾙﾀﾞｰ t0 t key1’s Leaseholder (Node3) x0 Clock Offset
34. Tx1 を受け取った Node1 (Tx1 の Gateway Node) は、ローカルの Timestamp を基に (自分自信のずれた時刻を基に)、Tx1 に t3 (t2 < t3) を設定する。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) < Tx1.ts = t3 t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Clock Offset に起因して発生する問題
35. Node1 は key1 の Leaseholder である Node3 に Write を送る。この時、Tx1 の Timestamp t3 を基に Node3 で key1 の Write が実行される。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) < ﾖﾛｼｸ t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) < OK t0 t key1’s Leaseholder (Node3) x0 t3 t3 Clock Offset Clock Offset に起因して発生する問題
36. x1 t3 Node3 (Leaseholder) は x1 を t3 で Write し、Node1 (Gateway Node) にレスポンスを 返す。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) < ｻﾝｸｽ t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) < ｶｲﾀﾖ t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Clock Offset に起因して発生する問題
37. x1 t3 Node1 (Gateway Node) は、Client に “Write OK” を返す。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) < Write OK t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Clock Offset に起因して発生する問題
38. x1 t3 Tx1 完了後に、Tx2 (Read) が実行される。この時、Tx2 には “Tx1 が Write した値 (key1 = x1) を Read すること” (一貫性があること) が期待されるが... Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Clock Offset に起因して発生する問題
39. x1 t3 Tx2 を受け取った Node2 (Tx2 の Gateway Node) は、ローカルの Timestamp を基 に、Tx2 に t2 (t2 < t3) を設定する。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 t2 < Tx2.ts = t2 Clock Offset Clock Offset に起因して発生する問題
40. x1 t3 Node2 は key1 の Leaseholder である Node3 に Read を送る。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 t2 < ﾖﾛｼｸ t2 < OK Clock Offset Clock Offset に起因して発生する問題
41. x1 t3 しかし、Node3 (Leaseholder) には t3 (t2 < t3) で Write された x1 と、t0 (t0 < t2) で Write された x0 がある。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 t2 t2 < ﾁｮｯﾄﾏﾃ... Clock Offset Clock Offset に起因して発生する問題
42. x1 t3 Tx1 -> Tx2 の順番で実行されているため、Tx1 で Write された key1 = x1 を返すことが 期待されるが、単純に Timestamp の値を比較すると t0 < t2 < t3 であるため、t0 で Write された x0 (古い値) を返すことになる。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 t2 t2 < ﾄﾞｯﾁﾀﾞ...? Clock Offset Clock Offset に起因して発生する問題
43. x1 t3 Node3 (Leaseholder) には、Tx2 の Timestamp (t2) の情報と key1 = x1 (t3) の情報し か見えず、Tx の実行順序の情報 (Tx1 -> Tx2) を知り得ることはできないので、x0 (t0) と x1 (t3) のどちらの値を返すべきなのか判断できない。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 t2 t2 < ﾅﾝﾓﾜｶﾗﾝ... < ﾏﾀﾞｰ? Clock Offset Clock Offset に起因して発生する問題
44. x1 t3 この時、x0 (t0) の値を返してしまうと、先に実行された Tx1 で Write された最新の値 x1 ではなく、古い値を Read してしまうことになり、Tx 間での一貫性がなくなってしまう。 Tx1: Write (key1, x1) Tx2: Read (key1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 t2 t2 < ﾀﾌﾞﾝ x0… < ﾎﾝﾄﾆ? Clock Offset Clock Offset に起因して発生する問題
45. Timestamp (HLC) を使った Tx の動作 \ ﾌﾒｲﾘｮｳ / Uncertainty Intervals
46. 用語概要 (Uncertainty Intervals) • Tx には Gateway Node の Timestamp が設定される。 • この時、Tx には 2つの Timestamp が設定される。 ◦ commit_ts ▪ Gateway Node の Local HLC を基にした仮の Timestamp。 ◦ commit_ts + max_offset ▪ commit_ts に Cluster 内の Clock Offset を加算した Timestamp。 • つまり、Tx は [commit_ts, commit_ts + max_offset] という “時刻の幅” の 情報を持っている。 • この “時刻の幅” を “Uncertainty Interval” という。
47. x1 t3 Timestamp を使った Read (Uncertainty Interval) 先程と同じように、時刻がずれた Node1 が Tx1 の Write (x1 を Write) を t3 で実行し、 Tx1 完了後に Tx2 (Read) を実行する。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Tx2: Read (key1) < ﾗｲﾄｼﾀﾖ
48. x1 t3 Timestamp を使った Read (Uncertainty Interval) Tx2 を受け取った Node2 (Tx2 の Gateway Node) は、ローカルの Timestamp を基 に、Tx2 に t2 (t2 < t3) と “t2 + max_offset” を設定する。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Tx2: Read (key1) t2 t2 + max_offset < Tx2.ts = [t2, t2 + max_offset]
49. x1 t3 Timestamp を使った Read (Uncertainty Interval) Node2 は key1 の Leaseholder である Node3 に Read を送る。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Tx2: Read (key1) t2 t2 + max_offset t2 < ﾖﾛｼｸ < OK
50. x1 t3 Timestamp を使った Read (Uncertainty Interval) この時 t2 + max_offset の Timestamp を基にした Uncertainty Interval が設定される。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Tx2: Read (key1) t2 t2 + max_offset t2 Uncertainty Interval
51. x1 t3 Timestamp を使った Read (Uncertainty Interval) Node3 (Leaseholder) での処理で、Uncertainty Interval の範囲に収まる Timestamp t3 (t2 < t3 < t2 + max_offset) で Write された値 x1 が存在することを検知する。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Tx2: Read (key1) t2 t2 + max_offset t2 < ｵﾔ? Uncertainty Interval
52. x1 t3 Timestamp を使った Read (Uncertainty Interval) この Uncertainty Interval の範囲に収まる Timestamp t3 で Write された値 x1 は、 Cluster 内の Clock Offset に起因して順序 (時刻) が逆転している可能性が有る “不確 実な値” であると判断される。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Tx2: Read (key1) t2 t2 + max_offset t2 < ｽﾞﾚﾃﾙｶﾓ Uncertainty Interval
53. x1 t3 Timestamp を使った Read (Uncertainty Interval) この “不確実な値” を検知した Node3 (Leaseholder) は、(t2 に対して確実に過去である t0 の値 x0 ではなく) その “不確実な値” である t3 の値 x1 を Node2 (Gateway Node) に返す。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Tx2: Read (key1) t2 t2 + max_offset t2 < ﾀﾌﾞﾝ x1 (t3) < ﾅﾙﾎﾄﾞ?
54. x1 t3 Timestamp を使った Read (Uncertainty Interval) Node2 (Gateway Node) は、Node3 (Leaseholder) から受け取ったレスポンス (x1) の Timestamp が “Tx2 の Timestamp より大きい (Tx2.ts < x1.ts) か否か” を確認する。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Tx2: Read (key1) t2 t2 + max_offset t2 < “Tx2.ts < x1.ts“ or Not? t3
55. t3 x1 t3 Timestamp を使った Read (Uncertainty Interval) Node2 (Gateway Node) は、Node3 (Leaseholder) から受け取ったレスポンス (x1) の Timestamp を確認し、”Tx2.ts = t2” < “x1.ts = t3” だった場合、Tx2 の Timestamp を t2 から t3 に変更 (push) する。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Tx2: Read (key1) t2 + max_offset t2 < Tx2.ts = t3
56. x1 t3 Timestamp を使った Read (Uncertainty Interval) Node2 (Gateway Node) は、Tx2 (Read) の結果として key1 = x1 を Client に返す。 Tx2 は “t3 で実行された” という扱いになる。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Tx2: Read (key1) t2 + max_offset t2 < key1 = x1 t3
57. x1 t3 Timestamp を使った Read (Uncertainty Interval) 結果として、Tx1 -> Tx2 の順番で Tx が実行された時に、Node 間で Clock Offset が あった場合でも、Tx2 は Tx1 で Write された値 (最新の値) を Read できる (一貫性のあ る Read が実行される)。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Tx2: Read (key1) t2 + max_offset t2 < ﾗｲﾄｼﾀﾖ < ﾘｰﾄﾞｼﾀﾖ < ｲﾛｲﾛｼﾀﾖ t3
58. t3 x1 t3 Timestamp を使った Read (Uncertainty Interval) 言い換えると、Uncertainty Interval の上限である t2 + max_offset 以下の Timestamp T (T < t2 + max_offset) で Write された値は、Tx2 から見て “全て過去の値である” もの として扱われる。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Tx2: Read (key1) t2 + max_offset t2 < ﾗｲﾄｼﾀﾖ < ﾘｰﾄﾞｼﾀﾖ < ｲﾛｲﾛｼﾀﾖ
59. t3 x1 t3 Timestamp を使った Read (Uncertainty Interval) ただし、この処理 (単純な Timestamp の変更) のみではカバーしきれない問題が有るの で、実際には Read Refresh という処理も併せて実行される。 Tx1: Write (key1, x1) Tx’s Real Time Order (Clients) t0 t Tx1’s Gateway Node (Node1) t0 t Tx2’s Gateway Node (Node2) t0 t key1’s Leaseholder (Node3) x0 t3 Clock Offset Tx2: Read (key1) t2 + max_offset t2 < ﾎｶﾆﾓ < ｼｮﾘｶﾞ < ｱﾙﾖ
60. 宣伝 \ ｾﾝﾃﾞﾝ /
61. こちら、前回の LT で得た「LT で分散 Tx を語るの is 無理」という知 見を活かして「LT には収まらないだろうなぁと思いながら作成した 172 ページあるスライド」です。ご査収ください。 Resolving Tx Conflicts in CockroachDB https://speakerdeck.com/kota2and3kan/resolving-tx-conflicts-in-cockroachdb • Tx の Timestamp を未来の値に変更 (push) した際に実行される Read Refresh や、未来の Timestamp t1 で Read された key を過去の Timestamp t0 (t0 < t1) で 上書きしてしまうことを防ぐための Timestamp Cache 等についても解説しています。 宣伝
62. まとめ \ ﾏﾄﾒ /
63. まとめ LT で分散 Tx を語るの is 無理！ \ ﾑﾘ / (37日ぶり 2回目)
64. Thank you!