Database Concurrency Control Papadimitriou 読書会 第15回 議論メモ

勉強会について

Database Concurrency Control Papadimitriou 読会 第15回 - connpass の議論メモです。

自分のメモをベースにまとめています。発言の聞き間違い、解釈違いの可能性があることをご了承ください。

特記の無い引用は本で議論した箇所を示しています。

Theory of Database Concurrency Control

[memo]は私のメモです。勉強会で議論された内容ではないことにご注意ください。

2.6 CONFLICT SERIALIZABILITY

this notion is free from negative complexity results such as those in the previous section.

ここでの "negative complexity" とは NP-complete のこと。

conflict if the following is true: Both steps read or write the same entity, and not both are read steps.

conflict とは異なるトランザクションのステップが同じエンティティに対して以下の条件を全て満たすである。

• read or write している。
• 両方とも read ではない。

---

[memo]
Example 2.5
R₁(y) R₃(w) R₂(y) W₁(y) W₁(x) W₂(x) W₂(z) W₃(x)
スケジュール A₂A₁A₃ と view equivalent であることを確認します。
A₁, A₂ は A₂ → A₁ となる必要があります。オリジナルのスケジュールでは A₁, A₂ 共に y の初期値を読んでいますが、A₁ → A₂ だと A₁ が y に値を書き込み、A₂ がそれを読んでしまうためです。
また、A₃ はスケジュールで最後になる必要があります。A₁, A₂, A₃ 共に x へ値を書き込んでいますが、VSR が FSR も満たす必要があることを考えると、オリジナルのスケジュールで最後に x へ書き込んだ A₃ が最後になる必要があります。
よって、A₂A₁A₃ が唯一 view equivalent な serial schedule とわかります。

---

MVで全てのバージョンを保持できるとすれば、「最終状態」が複数ありうると考えるのが妥当なのではないか。今の理論は「最終状態」が一つに決まる前提を置いているのが気になる。

MVSR ではTXの順序が重要となるケースを考慮していない。
同じTX群を同じプロトコルに投入したとき、deterministic であれば同じ結果になる。ただ、現実の世界では物理レベルの微妙な latency を無視することができず、異なる結果となることがある。
それでもTXの順序を守る必要があるなら、ミドルかアプリがやるしかない。だが、それはパフォーマンスを落とすことになる。
そもそも、TXの順序が重要であればDBを使う必要があるのかを考える必要がある。突き詰めればファイルでも良いのではないか？
例として株取引がある。これはDBのTXではなく、他に定められたプロトコルで約定が決まる。となると、必ずしもTXの順序を守る必要があるとは言えない。

DBは「よしなにやってくれる」とみんなが思っているが、「よしな」とは何かをちゃんと理解せずに使っている。

Oracleが「Snapshot Isolation は serializable」と言ってしまったがために未だ誤解されている。

赤い会社「完全にserializableですよ。」
その他大勢「いや、SIではfull-serializableにはならないし。」
赤い会社「いや、ほぼ同じだし。」
その他大勢「なんだよ、ほぼ同じってww」
赤い会社「だからこのベンチマーク（TPC-C）でちゃんとanomalyなしだし」
その他大勢「いやだから、そのベンチマークがそもそもだな・・・」
あれやこれや・・・
（以上、脚色なし）

Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道

We can test in O(n²) time whether a schedule is conflict serializable.

O(n²) の n は node、つまりトランザクションの数だ。cycle を発見するために最悪 O(n²) かかるということだ。

Conflicts and Commutativity

reflexive-transitive closure は「反射推移閉包」と訳される。
reflexive closure（反射閉包）かつ transitive closure（推移閉包）なもの。

関係Rの反射推移閉包とは、Rを含み反射性と推移性の両者を満たす最小の関係のことです。

ソフトウェアの基礎

∼* を ∼ の reflexive-transitive closure とする。これは non-conflicting な step を交換したということだ。ここでの交換は step order を前提としている。

関連記事

papa本第15回参加メモ - 誰にも見えないブログ
@yuyabu2 さんの読書会ノート。