課題
db tech showcase Tokyo 2018 (db tech showcase Tokyo 2018 | db tech showcase)
でノーチラステクノロジーズ 神林さんが以下のテーマで講演されました。
MVCCにおけるw-w/w-r/r-wのあり方とcommit orderのあり方の再検討～Sundial: Harmonizing Concurrency Control and Caching in a Distributed OLTP Database Management Systemを題材に
講演の中で
w1(x1) w2(x2) c2 c1
※ r : read, w : write, c : commit, a : abort, x : item（添字は書き込んだトランザクションの番号）
が Lost Update ではないと説明がありました。ただし、その詳細については各自の宿題ということで解説はスキップされています。
これについて、私なりの理解をまとめます。結論として、これは Dirty Write であり、Lost Update ではありません。以下で説明します。
説明のベースとして "A Critique of ANSI SQL Isolation Levels" （以下、Isolation論文）を参照します。
Isolation論文のリンク：
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-95-51.pdf
神林さんによるIsolation論文解説スライド（今回の講演スライドではありません）：
Dirty Write
Isolation論文で Dirty Write (P0) は以下の定義としています。
P0 (Dirty Write): Transaction T1 modifies a data item. Another transaction T2 then further modifies that data item before T1 performs a COMMIT or ROLLBACK. If T1 or T2 then performs a ROLLBACK, it is unclear what the correct data value should be.
（中略）
P0: w1[x]...w2[x]...(c1 or a1) (Dirty Write)
今回の課題のスケジュールである、
w1(x1) w2(x2) c2 c1
は P0 に合致します。
このスケジュールは1V、つまりアイテム毎に最新の値しか保持できないケースで困ります。元のスケジュール順で実行した場合、最後のc1はxの値がx1となることを期待しているはずですが、w2(x2)で上書きされてしまっているからです。
ですが、このスケジュールは S2PL で T1 → T2 の Serializable になります。
ここではロックをl、Unlockをuとします。また、xの添字を外します。
オリジナルのスケジュール：
w1(x) w2(x) c2 c1
S2PL：
l1(x) w1(x) c1 u1(x) l2(x) w2(x) c2 u2(x)
これが講演スライドの「勝手にロックが働く」の意味となります。
Lost Update
Isolation論文の Lost Update (P4) の定義と例をまとめて引用します。
P4 (Lost Update): The lost update anomaly occurs when transaction T1 reads a data item and then T2 updates the data item (possibly based on a previous read), then T1 (based on its earlier read value) updates the data item and commits. In terms of histories, this is:
P4: r1[x]...w2[x]...w1[x]...c1 (Lost Update)
The problem, as illustrated in history H4, is that even if T2 commits, T2's update will be lost.
H4: r1[x=100] r2[x=100] w2[x=120] c2 w1[x=130] c1
Dirty Write との違いは Lost Update の定義に r1[x] がいることです。これにより、P4は Serializable になりません。
r1[x] は w2[x] の前に実行されています。当然、T2のupdateはlostすることになります。
H4の例でみると、T1は x+30 、T2は x+20 なので、T1, T2 が順に実行されれば x=150 になるはずですが、x=130 となってしまいました。
今回の課題のスケジュールに r1[x] に相当する操作はなく、Lost Update ではないとわかります。
Dirty Write と Lost Update の比較
Dirty Write と Lost Update の定義を再掲します。
P0: w1[x]...w2[x]...(c1 or a1) (Dirty Write)
P4: r1[x]...w2[x]...w1[x]...c1 (Lost Update)
Dirty Write の場合、仮に先行する w1[x] がなかったとしても（T1のUpdateがLostしたとしても）、DBの最終状態には何も影響を及ぼしません。
ですが、Lost Update の場合、T2->T1 で実行された場合と、P4のorderで実行された場合とでDBの最終状態に違いが現れます。それはT1が参照すべきT2のupdateがLostしたからです。
この違いは r-w が conflict の肝だ、という話につながっていくように思うのですが、さて…？
