Multiversion Concurrency Control(MVCC) その2

Reads-From関係の導入

トランザクション内で値を書き込む場合、その書き込み操作はMultiversionの実行時には必ず「新たなバージョンを作る」という操作で代用する（無限にバージョンを増やしていくとメモリが足りないという問題はあるがそれは後日の議論で解決する）。

「トランザクションaがxに書き込む」場合、その値をバージョンaを付けてxaと表現することにする。トランザクション1が書いた値ならx1と表現するしトランザクション2が書いた値ならx2と表現する。そうしてバージョンを付けた値を扱うスケジュール図をマルチバージョンスケジュール図と以後では呼ぶ。

マルチバージョンスケジュール図から「それぞれのReadが読んだバージョンはどのバージョンか」を集合の形で抽出し、それをReads-From関係と呼ぶ。なお初期状態はTx0という特殊なトランザクションがすべて書き込んだ物として扱う。

↑のマルチバージョンスケジュール図から導き出されるReads-From関係は

• 「Tx1のRead(x)はTx0の書いたバージョンを読んでいる」
• 「Tx1のRead(y)はTx2の書いたバージョンを読んでいる」
• 「Tx2のRead(x)はTx1の書いたバージョンを読んでいる」

であり、太字の部分を抽出して大きさ3の集合の形で

Reads-From関係1

RF(m1) = {(Tx1, x, Tx0), (Tx1, y, Tx2), (Tx2, x, Tx1)}

と表現する。

↑のマルチバージョンスケジュール図から導き出されるReads-From関係は

• 「Tx1のRead(x)はTx0の書いたバージョンを読んでいる」
• 「Tx1のRead(y)はTx0の書いたバージョンを読んでいる」
• 「Tx2のRead(x)はTx1の書いたバージョンを読んでいる」

であり、集合で表現すると

Reads-From関係2

RF(m1) = {(Tx1, x, Tx0), (Tx1, y, Tx0), (Tx2, x, Tx1)}

となる。これは任意のマルチバージョンスケジュールから機械的に抽出できる。
とある2つのマルチバージョンスケジュールから抽出されたそれぞれのReads-From関係の集合が一致する場合、その2つのスケジュールの事をView Equivalentであると言う。
数式っぽいものが出てくると身構える人も多いと思うが、要するに[Read]の箱に刺さっている矢印の両端が2つの図で一致しているか、という観点で捉えて構わない。

Multiversion View Serializability(MVSR)

このReads-From関係は、当然個々のトランザクションを１つずつSerialに実行した場合からも得られる。

Serial実行であってもMultiversionなのでReadは任意のバージョンの物を読みうるが、その中ですべてのReadが最後にその値に書き込んだ値を読むという条件に従っている（図的に言うなら、それぞれのReadの箱から見て左にある中で、同じ値にWriteしている箱の一番右の箱から矢印が伸びている）スケジュール図になっているものとReads-From関係が一致するスケジュールの事を**Multiversion View Serializability(MVSR)**と呼ぶ。

VSRと比べてエルブランセマンティクスは出てこないが、ややこしさはやや増えている気がする。