MCSR の conflict が r-w (read-write) だけなのはなぜなのか？

はじめに

MCSR (Multiversion Conflict Serializability) を知るには以下の本及び記事を読むのが最も理解に近づきます。

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

TX本 5.3.3 Multiversion Conflict Serializability

multi-versionの基礎 - 急がば回れ、選ぶなら近道

Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道

MCSR - nikezono

ただ、これらの本・記事を読んでもなお、r-w が依存関係になる、つまり可換性 (commutativity) がない、という点はなかなか理解し難いです。そこで、本エントリではこの点に絞って解説を行います。

先に挙げた本及び記事は読んでいる前提とします。

step の交換による MCSR の判定

---

DEFINITION 5.10 Multiversion Reducibility
A (totally ordered) multiversion history m is multiversion reducible if it can be transformed into a serial monoversion history by a finite sequence of transformation steps, each of which exchanges the order of two adjacent steps, (i.e., steps p,q with p < q such that o < p or q < o for all other steps o) but without reversing the ordering of a multiversion conflict (i.e., rw) pair.

---

---

DEFINITION 5.11 Multiversion Conflict Serializability
A multiversion history m is multiversion conflict serializable if there is a serial monoversion history for the same set of transactions in which all pairs of operations in multiversion conflict occur in the same order as in m. Let MCSR denote the class of all multiversion conflict-serializable histories.

---

From what we have discussed above, the following theorems can be derived.

---

THEOREM 5.5
A multiversion history is multiversion reducible iff it is multiversion conflict serializable.

---

引用：TX本 5.3.3 Multiversion Conflict Serializability

オリジナルの multiversion history を隣り合う step の交換で serial monoversion history に変換できるのであれば、それは MCSR であるとしています。ただし、multiversion conflict pair である r-w は交換できません。

r-w がなぜ交換不可なのか、他の操作はなぜ交換可能なのかを確認していきます。

reads-from

TX本において MCSR の章 (5.3.3) の前までは history と同時に reads-from (RF, view) も与えられている (given) ことを前提としていました。

つまり、
w₁(x₁)c₁r₂(x₁)r₃(y₀)w₃(x₃)w₂(y₂)c₂c₃
のような history で r₂(x₁) は w₁(x₁) の write した version を読んでいるし、それが変わることはない、という前提が置かれていました。

ですが、RF は後で自由に決めて良いと考えることもできます。

TX本の5章では以下の仮定を置いています。

An important assumption we will make in this chapter is that versioning is transparent to the outside world. In other words, users or applications will not be aware of the fact that data items can appear in multiple versions.
引用：TX本 5.1 Goal and Overview

ユーザ視点で version が見えない（指定できない）ということはスケジューラに version を決める裁量があるということです。

つまり、history における RF の定式化には以下の2つがあります。
(1) RF が一つ与えられている（かつ変わらない）
(2) RF は後で自由に決めて良い

具体的な例で確認します。
w₁(x)w₂(x)r₃(x)
このスケジュールを multiversion (MV) で考えた時、
w₁(x₁)w₂(x₂)r₃(x₂)
と RF を決めたとします。
(1) の方式では r₃(x₂) を後から r₃(x₁) にすることを認めません。
(2) の方式では r₃(x₂) を r₃(x₁) としても構いません。
※ MV なので r₃(x) は x₁, x₂ のいずれも read することができます。

TX本の MVSR では (1) を前提としています。これに対し、MCSR では (2) を前提としています。このことは明記されておらず、混乱を招くポイントとなっています。

なお、現実に (2) の方式を採用するのは困難に思えます。RF を後で決められるということは r(x) の段階で read する version を確定しないということです。ですが、r(x) が実行できたということは何らかの version を read したはずであり、それを後から変えるというのは現実的に実現困難と思われます。

equivalence

MV における equivalence とは View Equivalence のことです。

DEFINITION 5.5 View Equivalence
Let m and m' be two multiversion schedules such that trans(m') = trans(m). m and m' are view equivalent, abbreviated m ≈_v m', if RF(m) = RF(m').
引用：TX本 5.3.1 Multiversion View Serializability

commutativity

commutativity（可換性）とは隣り合う命令ペアを交換したとしても、交換前後でスケジュール／ヒストリーが equivalent である操作のことです。先に引用した DEFINITION 5.5 より、RF を崩さなければ equivalent であるとわかります。

命令ペアを交換しても RF を維持できるか見ていきます。
なお、確認の対象は異なる transaction (TX) が同じ item に対する操作についてです。同じ TX 間で操作の交換はできませんし、異なる TX かつ異なる item に対する操作であれば常に交換可能です。

w-w (write-write)

以下のスケジュールを考えます。
w_i(x_i)w_j(x_j)r_k(x_j)

w_i-w_j を交換すると以下のスケジュールが得られます。
w_j(x_j)w_i(x_i)r_k(x_j)
MV ですので r_k(x_j) は実行可能です（1つ前のバージョンを読んでいるに過ぎない）。

よって、w-w は交換可能と分かります。

w-r (write-read)

以下のスケジュールを考えます。
w_i(x_i)w_j(x_j)r_k(x_j)

w_j-r_k を交換すると以下のスケジュールが得られます。
w_i(x_i)r_k(x_j)w_j(x_j)
w_j(x_j) が write する前に r_k(x_j) が read してしまいました。これではまずいので r_k(x) がread する version を変更します。
w_i(x_i)r_k(x_i)w_j(x_j)
このスケジュールであれば成立します。

ですが、r_k の read する version が x_j → x_i になってしまいました。これは RF を崩したことにならないのでしょうか？

実は問題ありません。

前提として、ユーザ視点では version が見えていないことを思い出してください。つまり、ユーザからは以下のスケジュールが見えていたはずです。
w_i(x)w_j(x)r_k(x)
これにスケジューラが勝手に version を割り振ったにすぎません。それが冒頭のスケジュールである
w_i(x_i)w_j(x_j)r_k(x_j)
ということです。

つまり、スケジューラは r_k(x) に別の version を割り振ることも可能ということです。なので、以下のスケジュールも可能です。
w_i(x_i)w_j(x_j)r_k(x_i)
このスケジュールで w_j-r_k を交換したのが以下のスケジュールです。
w_i(x_i)r_k(x_i)w_j(x_j)
これは先ほどの交換結果と同じになりました。

つまり、w-r の交換は可能と分かります。

繰り返しになりますが、このような version の再割り当てを現実で実現するのは困難でしょう。ですが、理論上は可能ということです。

r-w (read-write)

以下のスケジュールを考えます。
w_i(x_i)r_j(x_i)w_k(x_k)

r_j-w_k を交換すると以下のスケジュールが得られます。
w_i(x_i)w_k(x_k)r_j(x_i)

一見問題ないように見えますが、交換したことでもう一つのスケジュールの可能性が生まれました。それが以下のスケジュールです。
w_i(x_i)w_k(x_k)r_j(x_k)
r_j(x_i) が r_j(x_k) になっています。w_k(x_k) が先行しているので read することは可能です。

実はこの「もう一つのスケジュール」こそが問題なのです。

r_j(x_k) はオリジナルのスケジュールでは不可能です（w_k(x_k) の前に read しているため）。つまり、交換したがためにオリジナルにはない可能性が広がってしまいました。これでは RF が同じではなく、equivalent とは言えません。

MV なのだから r_j-w_k を交換しても r_j(x_i) のままでよいと考えるかもしれません。ですが、MCSRは「オリジナルの multiversion history を隣り合う step の交換で serial monoversion history に変換できる」ものでなければいけません。交換したスケジュールを monoversion で考えれば r_j(x_k) となります。つまり、交換後のスケジュールを monoversion で考えた時、equivalent でないとわかります。

これが r-w を交換できない (multiversion conflict pair) 理由となります。

ただし、他の交換操作と組み合わせれば r-w も交換できるケースがあります。
※以降、太字は次の step で交換する操作を示しています。
w_i(x_i)r_j(x_i)w_k(x_k)
w_i(x_i)w_k(x_k)r_j(x_i)
w_k(x_k)w_i(x_i)r_j(x_i)
このような交換を行えば monoversion でも equivalent になります。
私はこれが MCSR と MVSR の範囲の違いとして現れていると考えています。この後の実例でも確認します。

MCSR 判定の実例

TX本 Figure 5.2 より2例用いて MCSR の判定を行います。

(1)

MCSR である（つまり MVSR でもある）s₄を例に考えます。

s₄ = r₁(x)w₁(x)r₂(x)r₂(y)w₂(y)r₁(y)w₁(y)c₁c₂

初期値とバージョンの割り当てを行います。その後、変換操作を行います。
w₀(x₀)w₀(y₀)r₁(x₀)w₁(x₁)r₂(x₀)r₂(y₀)w₂(y₂)r₁(y₂)w₁(y₁)
w₀(x₀)w₀(y₀)r₁(x₀)r₂(x₀)w₁(x₁)r₂(y₀)w₂(y₂)r₁(y₂)w₁(y₁)
w₀(x₀)w₀(y₀)r₂(x₀)r₁(x₀)w₁(x₁)r₂(y₀)w₂(y₂)r₁(y₂)w₁(y₁)
w₀(x₀)w₀(y₀)r₂(x₀)r₁(x₀)r₂(y₀)w₁(x₁)w₂(y₂)r₁(y₂)w₁(y₁)
w₀(x₀)w₀(y₀)r₂(x₀)r₂(y₀)r₁(x₀)w₁(x₁)w₂(y₂)r₁(y₂)w₁(y₁)
w₀(x₀)w₀(y₀)r₂(x₀)r₂(y₀)r₁(x₀)w₂(y₂)w₁(x₁)r₁(y₂)w₁(y₁)
w₀(x₀)w₀(y₀)r₂(x₀)r₂(y₀)w₂(y₂)r₁(x₀)w₁(x₁)r₁(y₂)w₁(y₁)

最終的に serial monoversion history (T2 → T1) を得ることができましたので、s₄ は MCSR であるとわかります。

(2)

MCSR ではないが MVSR な s₂ を例に考えます。

s₂ = w₁(x)c₁r₂(x)r₃(y)w₃(x)w₂(y)c₂c₃

s₂ は以下の通り MVSR であると判明しています（※TX本に記述あり）。
w₁(x₁)c₁r₂(x₁)r₃(y₀)w₃(x₃)w₂(y₂)c₂c₃
これを参考に T3 → T1 → T2 な serial monoversion history へ変換を目指します。

w₀(x₀)w₀(y₀)w₁(x₁)r₂(x₁)r₃(y₀)w₃(x₃)w₂(y₂)
w₀(x₀)w₀(y₀)w₁(x₁)r₃(y₀)r₂(x₁)w₃(x₃)w₂(y₂)
w₀(x₀)w₀(y₀)r₃(y₀)w₁(x₁)r₂(x₁)w₃(x₃)w₂(y₂)
r₂(x₁)w₃(x₃) を交換したいのですが、r-w なので交換できません。よって、MCSR ではありません。今回は交換できたとして先に進めます。
w₀(x₀)w₀(y₀)r₃(y₀)w₁(x₁)w₃(x₃)r₂(x₁)w₂(y₂)
w₀(x₀)w₀(y₀)r₃(y₀)w₃(x₃)w₁(x₁)r₂(x₁)w₂(y₂)
w₁(x₁)w₃(x₃) を交換したことで、monoversion でみても正しいスケジュールとなりました。

このように、r-w の交換をしても最終的には RF の崩れない（そして MVSR になる）ケースがあるとわかりました。