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

multiversionの基礎

自分用のMulti Version Concurrency Controlのまとめ
MVCCの基礎理論をまとめておく。今後はここを参照する。
基本的にTX本とCC本から必要な部分をまとめている。
（一回まとめてるけど、Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道
前回はそもそもCSRとの混線を防ぐという意味だったので、今回はもっと基本的なところからさらに。今回はCSRとの関係はガン無視。）

前置き：自分の考えを記録的に
基本的にMulti Version Concurrency Control （以下MVCC）は理論先行だった。これはMVCCのオーバへードがsingle-versionのパフォーマンスを凌駕できなかったことによる。以下の理由によりMVCCが今後は伸張すると考えている。

1.メモリーの進歩と低コスト化
特にメモリーの大容量化と高密度化が大きい。これによりIn placeの相対的なメリットが落ちる。single-versionの方が効率がよい、という前提がなくなりつつある。In placeは資源の効率的活用という意味では有効だが、前提が崩れると不必要に面倒な実装ということになりかねない。メモリー資源が貴重でなれければ、どかどかページの更新を書き足していくだけという手法も検討に値する。なお、当然GCもあり方を変える必要があると思う。より簡略化される可能性が高いと個人的には想像している。

2.Single-versionの限界
現在の分散OLTPでは、MOCC/Foedusに見るように、Single-versionの仕組みではabort率の高止まりが壁になっている。エンジニアリング的手法で乗り切るという考えかたも見られるが、single-versionの無駄（validation時点での偽陽性）が許容限界に近づいているともいえる。serializableの点から言うと、scheduling powerそのものは間違いなくMVCCの方が上で、そもそもabortが少ない。その意味ではMVCCのメリットが大きくクローズアップされると思う。

MVCCとsingle-versionの根本的な考え方の違い
端的に言えば、single-versionはin placeだ。“したがって”writeの競合が最大の課題になる。readについては、選択の余地はなく、直前のwrite(コミットの有無にかかわらず)を読むのみであり、検討課題には基本的にはならない。対して、MVCCはin placeではない。writeの競合はハナから問題ですらない。その代わりreadについては、どのversionを読むか？という選択が発生し、最優先に検討すべき事項になる。結果両者で理論のフレームワークが異なる。

1.“Read From” Relation(以下RF)
まず、RFを定義する。これはどのreadがどのwriteを読んでいるか、ということを表す。
Read from Relation
RF(m) := (ti,x,tj | rj(xi)∈op(m))
すなわちhistory m に含まれる手続き、でかつtransaction（以下tx） jに含まれるreadが、tx i で生成されたxを読む、ということを意味する。同一tx内部のwriteは当然readできるものとする。この場合は特にRFでは定義しない。

2.View equivalence
RFによりviewが生成されるので、同一のRFが存在するhistory間では、viewの互換があるものと考える。これをView equivalenceとする。

View equivalence m to m’について、RF(m)= RF(m’)が成立

Serializableを導入する。基本線としては、serialなスケジュールと同一のviewが提供できるのであれば、すなわちview equivalenceであれば、それはserializableである。これは一般的にView Serializableといい、VSRと称されることが多い。

ここで、multiversionに拡張する。
multiversionの定義として
Let T = {t1, . . . , tn} be a (finite) set of transactions.
1. A multiversion history (or complete multiversion schedule) for T is a pair　m = (op(m), ＜m), where ＜m is an order on op(m) and
(a) op(m) = h(∪i=1→n op(ti))　for some version function h (h has been canonically extended from single operations to sets of operations)
：すべてのopはなんらかのversionに割り当てる。
(b) for all t∈T and all operations p, q∈op(t) the following holds:　p ＜t q ⇒ h(p) ＜m h(q)
：同一tx内部ではop順はversion順
(c) if h(rj(x)) = rj(xi ), i != j, and cj is in m, then ci is in m　and ci ＜m cj .
：なんか読んでいるとすれば、読まれているものが先にコミットされる（注意：されているではない）。
2. A multiversion schedule is a prefix of a multiversion history.

multi-versionでのserializability：
自分のスケジュールと、同一のステップで構成される「serial」な「monoversion」において、同一のRFがある場合、（正確には、自分のスケジュールのステップを利用して、RFが同一な「serial」な「monoversion」を作成することができる場合、かつそのときに限り）、その自分のスケジュールをserializableあると言う。これを一般にmultiversion view serializableといい、MVSRと略す。

この「serial」な「monoversion」のserialになるtxの論理的な順序がserialization orderになる。後述するがこれが、multiversionのversion orderに一致する（corollary）（正確には一致ではなく包含が正しい）

以下：mono-versionの定義と、RFについて補足をしておく
◇monoversion
直前のwriteされたものを読むこと（コミットの有無は関係ない）。versionは全部dropしている。

・直前の定義はなにか？version orderに乗っ取った直前のもの、という意味ではないか？
そうではない。単純に直前のwrite stepを見る。具体的なMVTOを見ると、version orderに乗っ取ったものにする、というように見えているが、これはプロトコルの結果による。コミットの有無、すなわち、コミットのオーダーになるときもあるがそれはプロトコルによる。単純に直前のwriteを読むという理解でよい。serialなmonoversionということであれば、普通にコミットのorder（場合によってはversion order）になるのは結果であって、定義ではない。

◇RF
そもそもRFとは何か。基本的に単純にviewである。ただし、そのviewの結果が「どう使われるか」で拡張ができる。

・読んだ結果、何らかの値を書いた場合（同一txでなんらかのwriteが発生。なお、別段読んだ値を上書きするとは限らず、なんらかの値を書く場合）、これをusefulとする。

・さらにusefulなRFにおいて、その影響の結果が最後のDBの状態にまで影響を及ぼす場合（すなわちRF-usefulのclosureがtx∞まで及ぶ場合）、これをaliveとする。逆に、その影響の結果が最後のDBの状態に影響を及ぼさない、すなわち当該txが書いた値をまったく別のtxが上書きされる場合、これをdeadとする。

usefulの概念はDBそれ自体に影響を及ぼすことを意味する。単に読んだ「だけ」ではDBの内部には影響はない。もちろん外部での影響から見た場合にはそうではない。DBの内部の状態に着目し、あるhistoryについて、usefulなRFのうち、aliveなものだけのRFがserialなhistoryと互換である場合、そのhistoryをfinal state serializableといい、FSRと称する。すなわち　VSR-dead useful RF=FSRとなる。RFについて全部の互換をとる必要はなく、usefulでかつaliveなのものだけの互換をとればいいので、当然FSRの方が、VSRよりスケジューリングパワーは強い。

anomalyからの補足として
FSRではlost updateは排除可能。最終的の書き残るページについてのコンテクストが変わるので。
r1(x)r2(x)w1(x)w2(x)c1c2→これはFSRではない。w0(x)r2(x)w2(x)がaliveなusefulRF（以下LRF）
t1t2 r1(x)w1(x)r2(x)w2(x)c1c2 w0(x)r1(x)w1(x)r2(x)w2(x)のLRF
t2t1 r2(x)w2(x)r1(x)w1(x)c2c1 w0(x)r2(x)w2(x)r1(x)w1(x)のLRF
どれとも一致しないので、FSRにはならない。

ところがinconsistency readは排除できない
s=r2(x)w2(x)r1(x)r1(y)r2(y)w2(y)c1c2　で　LRFは　w2(x)r1(x)　w0(y)r2(y)w2(y)
t2t1　 r2(x)w2(x)r2(y)w2(y)r1(x)r1(y)c2c1　LRFは　w2(x)r1(x) w0(y)r2(y)w2(y)r1(y)
で同じセマンティクスよってFSRが成立。FSRのセマンティクスだとserializable
しかし、r1(y)は　sではw0(y)からで、t2t1ではw2(y)なので違うものを読んでいる。

sのFSRでは、w0(y)r1(y)r2(y)w2(y)だけど、w0(y)r1(y)がw2(y)で上書きされるので、dead stepであり、LRFにカウントされない。FSRは書いて（含む初期）読んで、その状態が最後まで影響するか、または、読んでそのtxで書いてその状態が最後まで影響した、もののみ意味があるとカウントされるので、途中のリードで、その結果が最後に影響しないものは考慮されない。すなわち、読みのコンテクストが違っても、結果に影響がでなければ、正しさの判定には影響しない。なので、inconsistency readは排除できない

つまりFSRは現在のanomalyベースの考え方では有用ではない。何を読もうが最終の状態とそれにまつわるコンテクストが保存されればよい、というsemanticsであれば意味がある。その分スケジューリングパワーもある。一般に VSR⊂FSRである。差分の例は上記の通りのinconsistency read等になる。

multiversionにおけるFSR
上の結果からいうと簡潔で、multiversionにおいては　FSR＝VSRになる。要はdead stepの扱いの違いにある。multiversion においては上書きは常に別 versionの生成になる。すなわちdead stepが存在しない。よってFSR＝VSRになる。言ってみれば MFSR=MVSR。

MVSRについて
・従来からのAnomalyの排除
典型なanomalyとして lost update, inconsistency read, dirty read, write skewで検査する。直感的どれもRFはserialなものとは互換性はないだろうな、というのはわかる。うざいけど、どの教科書にもないので、sanitization的にやっておく。（まぁ言って見ればANSI SQL92 Critics のMVCCバージョンだ）

lost update
S=r1(x)r2(x)w1(x)w2(x)
RF: w0→r1　w0→r2　w2→r∞
t1t2　 r1(x)w1(x)r2(x)w2(x)　RF w0→r1 w1→r2 w2→r∞
t2t1　r2(x)w2(x)r1(x)w1(x)　RF w0→r2 w2→r1 w1→r∞
まったく一致しない。よって検出可能。

inconsistency read
S=r2(x)w2(x)r1(x)r1(y)r2(y)w2(y)　
RF　x:w0→r2 w2→r1 y:w0→r1 w0→r2 w2→r∞
t1t2　r1(x)r1(y)r2(x)w2(x)r2(y)w2(y)　RF x:w0→r1 w0→r2 w2→∞ y:w0→r1 w0→r2 w2→r∞
t2t1　r2(x)w2(x)r2(y)w2(y)r1(x)r1(y)　RF x:w0→r2 w2→r1 y:w0→r2 w2→r1
上の順序だとyは一致するがxが不一致、下の順序だとxは一致するがyが不一致。よって検出可能

dirty read
S=r1(x)w1(x)r2(x)w2(x)a1c2
RF w0→r1 w1→r2 w2→r∞
t1t2　r1(x)w1(x)a1r2(x)w2(x)c2 tx1はabort RF w0→r2 w2→r∞
t2t1　r2(x)w2(x)c2r1(x)w1(x)a1 tx1はabort RF w0→r2 w2→r∞
abortされたものを読むRFがオリジナルにあるので、これはserialになれば存在しない。よって検出可能

write skew
S=r1(x)r2(y)w1(y)w2(x)
RF x:w0→r1　w2→r∞ y:w0→r2　w1→r∞
t1t2 RF r1(x)w1(y)r2(y)w2(x) RF x: w0→r1　w2→r∞ y: w1→r2
t2t1 RF r2(y)w2(x)r1(x)w1(y) RF x: w2→r1 y:w0→r2 w1→r∞
一致しない。よって検出可能。

正直、まぁそうだろうなというのは直感的にわかる。anomalyはほぼviewの誤謬によるものになることを考えれば当然とも言えるからだ。余談だが、これはそもそもMVSR以前のVSRレベルで排除できる話なので、例のANSI SQL92 Criticsの整理も当時は仕方がないとはいえ、RFをちゃんと定義していれば普通に整理できた話ではある。そのanomalyの残滓を現状のRDBは引っ張って、いわゆるIsolation levelの定義があいまいなまま、すなわち formalizeされないまま、残っている。個人的には非常によろしくないと思っている。現状のDBを利用したインテグレーションでは、Isolationレベルの設定が「よくわからない」ために、まずパフォーマンスがでるレベルとしてread committedあたりを適当に設定して、なにかと面倒なところは個別にlock制御をアプリ側で行う（実際は2PL）ということが多いように見受けられる。やる気あるのか。

・MVSRそれ自体について
・VSR⊂MVSR
これについては異論はないと思う。VSRが単一のversionのみを参照制約があるのに対して、MVSRはより広いversionを参照することができるので、スケジューリング・パワーが広いことは自明だ。証明は簡単なの省略する。逆向きの反例はm = w0(x0)w0(y0)c0r1(x0)w2(x2)w2(y2)c2r1(y0)c1　MVSRだとt0＜t1＜t2でserialize可能だが、VSRではr1(y0)がr1(y)になってしまい解決できない。

・VSR/MVSRの問題点
まずVSRの問題点だが、判定の一般解がNP完全になるということだ。まぁ普通に考えてもグラフの総当たり作戦になるのでアウト。ということはより制約が緩いMVSRは少なくともNP完全同等であることが容易に推定できる。ということで、MVSRはほぼ無敵のツールではあるが、その一般的な判定手法は、結局無理ゲーになる。（厳密にはVSRの判定はPolygraphの非循環の検出問題になる。）

なお追加だが、VSR系の問題点として、monotonicではないことが挙がるが　MVSRでは当たらない。さらに、そもそも実装上はone-shotリクエストが前提であれば、さらに問題にならない。

一般解は無理ゲーなので、ある程度制約をつけて、heuristicに持っていきたいので、もう少し定式化をする。

Serialなmonoversionで同じRFのものがあれば、mはMVSRにはなる。ただ、これだけだと判定がNP完全なので・・・
(wi(xi), rj(xi))において ti→tj)のグラフGを考える　ここでのconflictはRFなので　w-rのみ
m ≈v m′→　G(m) =G(m’) ただし逆は成立しない。
これを定式化して、version orderを導入する。

■MVSG
スケジュールm　version order ＜＜　において　conflict graph G(m)をつくる(MVSG)
Vertex：Tx　Edge：Tx→Tx
rk(xj ) and wi (xi )で if xi＜＜xj , then (ti, tj ) ∈ E, otherwise　(tk, ti ) ∈ E.
m∈MVSR iff there exists a version order ＜＜ such that MVSG(m ＜＜) is acyclic.
注意：MVSGの引数がm(RF)と＜＜(version order)。よってグラフのedgeは「二種類」存在する。RFによるedgeとversion orderによるedge。

MVSG非循環であるようなversion orderがあれば、そのスケジュールmはMVSRである。（そしてそのときに限る）すなわち、mとおなじRFをもつ、serial monoversion historyが存在する。留意すべきはversion orderは単一ではない、ということだ。あるversion orderではcyclicで、別のversion orderであればacyclicであることはありうる。

・version orderについて
あるスケジュールであるデータが書かれる”論理的な”順序。実行ステップとは関係ない。論理的なserialization orderになる。すなわち、実際のスケジュールからserialなmonoversionと整合的なversion orderがとれればよい。wi wj のステップ順でも wj ＜＜ wiにversion orderをとってもRFについて違いがないようなケースも当然ある。（ただし、ありがちなプロトコルの結果として基本的に各Txの開始時点のtime stampでorderを取ることが多い。この場合は読めるversionについてちゃんと証明することが必要で、それによってMVSRの証明に容易にもってこれる）

注意：補足すると、そもそもversion orderをどうつくるか？という話があって、これはserialization orderのつくりかたと同じ。
考え方としては・・・
1. まず天下り的にtransactionなり　commitなりの順序をとりあえずorderとして設定し（ただし普通はTO）、そこにいけるかどうかで判断する方法：実はこれがMCSR（プロトコルだけではそう見えないが、論理的には同値）
2. そうではなくて任意のorderをつくって（つくれればserialなmonoversionができる）と、評価するhistoryで整合性がとれるかトライする方法：これがMVSRの本筋
以上の2通りがあって、それぞれがプロトコル依存になる。広いのは当然後者で、その分計算量が増える。
結局version orderを事前に制約として決めれば、あとの整合性確認はコストが低いが、当然abort率があがる。version orderを広くとれた方が scheduling powerがあるので、abort率は低い。ただし、その分の計算量が増えるし、そもそものversion orderの管理コストが余計にかかる。（この説明はTx本のみでありCC本ではここまで述べていない）

補足すると、たとえば、実行順序がwj(xj) rk(xj) wi(xi)であったとしてこの場合はmustでtj → tkは必ずdependency (conflict)存在する。（これはRF）
この時、xi ＜＜ xj ならば ti → tj よって ti→tj→tk。このスケジュールのmonoversionが存在するとすればそれは必ずwi(xi)wj(xj)。この場合はtk → ti依存関係の維持は必要ない。すなわちMCSRではない（version orderはxi→xjがmust）
また、xj ＜＜ xi ならば tk → ti よって　tj→tk→ti　んで、このスケジュールのmonoversionが存在するとすればそれは必ずwj(xj)wi(xi)になる。この場合はtk → ti依存関係の維持が必要であり、すなわちMCSRになる。そしてversion order xj→xiがmust。wj(xj)wi(xi)を維持する必要があって、これはrk(xj) wi(xi)の順序維持で必要。（たとえば、ひっくり返そうwj(xj)rk(xj)とするとwi(xi)wj(xj)rk(xj)になり、version orderがxi ＜＜ xjになる）

大事なのは証明なので ifはともかくonly ifなかなか面倒だが、この定理は例の2PL＝serializableと同じくらい重要。証明はTx本より、Phil.B御大のCC本の方がわかりやすいのでそちらから引く

Theorem 5.4: An MV history H is 1SR iff there exists a version order ＜＜　such that MVSG(H, ＜＜) is acyclic.
dependency(conflict)が循環しないようなserial graphにおいてversion orderが存在すれば、それはserializableで、かつその時に限る。
注：1SR=one copy serializable
　
Proof: (If) Let Hs be a serial MV history Ti, Ti1..Tin, where Ti1,Ti2,..Tin is a topological sort of MVSG(H, ＜＜).
Since C(H) is an MV history, it follows that Hs, is as well.
Since Hs has the same operations as C(H), by Proposition 5.1, Hs == C(H).
注意：C(H)はcommitted projection
Prop5.1
Two MV histories over a set of transactions are equivalent iff the histories have the same operations.
It remains to prove that Hs is l-serial.
Consider any reads-from relationship in Hs, say Tk reads x from Tj, k!=i.
Let wi(xi) (i!=j and i!=k) be any other Write on x.
If xi ＜＜ xj, then MVSG(H, ＜＜) includes the version order edge Ti -> Tj,
which forces Tj to follow Ti in Hs.
If xj ＜＜ xi, thenMVSG(H, ＜＜) includes the version order edge Tk -> Ti,
which forces Tk to precede Tj in Hs.
Therefore, no transaction that writes x falls in between Tj and Tk in Hs. Thus, Hs is l-serial.

(Only if) Given H and ＜＜,
let MV(H, ＜＜) be the graph containing only version order edges.
Version order edges depend only on the operations in H and ＜＜ ;
they do not depend on the order of operations in H.
Thus, if H and H’are MV histories with the same operations, then MV(H, ＜＜)=MV(H’,＜＜) for all version orders ＜＜,
注意：version orderが所与でoperationが同一ならgraphは一致。一瞬うっ　ってなるけど冷静に。
Let Hs be a l-serial MV history equivalent to C(H).
All edges in SG(Hs) go“left-to-right;” that is, if Ti ->Tj then Ti precedes Tj in Hs.

Define ＜＜ as follows:
xi ＜＜ xj only if Ti precedes Tj in Hs.
All edges in MV(Hs,＜＜) are also left-to-right.
Therefore all edges in MVSG(Hs, ＜＜) = SG(Hs)∪MV(Hs,＜＜) are left-to-right.
This implies MVSG(Hs, ＜＜) is acyclic.

By Proposition 5.1, C(H) and Hs, have the same operations.
Hence MV(C(H), ＜＜) = MV(Hs, ＜＜).
Proposition 5.2: Let H and H’ be MV histories. If H== H’, then SG(H) = SG(H’).
By Proposition 5.1 and 5.2
SG(C(H)) = SG(Hs). Therefore MVSG(C(H), ＜＜) = MVSG(Hs, ＜＜).
Since MVSG(Hs, ＜＜ ) is acyclic, so is MVSG(C(H), ＜＜), which is identical to MVSG(H, ＜＜).

■MCSRの定式化
rwのdependencyのみでconflict graphをつくる。すなわちri (xj )のwk(xk) ステップについて、ri (xj )＜m wk(xk)の依存関係をconflictとする。このrwのコンフリクトが、同じ順序で出るmonoversionができればMCSRになる
s = r1(x0)w1(x1)r2(x0)r2(y0) w2(y2)r1(y0)w1(y1)c1c2
version order x t0→t1 y t0→t2→t1　r-w：r2(y0) → w1(y1)　当然yのversion orderは t0<<t1
s’= r2(x)r2(y)w2(y)r1(x)w1(x)r1(y)w1(y)c1c2
r-w: r2(y)→w1(y)さらにr2(x)→w1(x)のconflictが発生するが、t2→t1で元のスケジュールと互換なので問題ない

ちなみにri (xj )<m wk(xk)について、そもそもmultiversionとしての成立条件、すなわち、ri(xj)でciが存在するのであれば、cj<ciがあることに留意する。

例えば、s“ = r1(x0)w1(x1)r2(x1)r2(y0)w2(y2)r1(y0)w1(y1)c1c2　としてみると（せっかくなのでconcurrentに走って先行しているt1のxの書き込みをt2で読むとする）

version order x t0→t1 y t0→t2→t1 r-w：r2(y0) → w1(y1)
serial monoversionで　r2(x)r2(y)w2(y)r1(x)w1(x)r1(y)w1(y)c2c1

r-w　 r2(x)→w1(x) r2(y)→w1(y) なので、t2→t1で成立するように見える、が
このmonoversionでr2が読んでいるのはx0なので、そもそもx1を読んでいたもとのversionとは異なる。これはr2(x1)が存在する段階で c1<c2がhistoryとしての成立条件になるので、t1→t2が必須になるので成立しない。尚、sの場合はそれがないので、t2→t1でもよい。

・MCSR⊂MVSR
上記のとおりで、MCSR→MVSRは特に問題はない。RFの互換性がある。
MVSR→MCSRではない例を示す。これはMVSRであるので本来はserializableではあるが、MCSRではそうではない。すなわち偽陽性になってしまう。

s = w0(x0)w0( y0)w0(z0)c0 r2(y0) r3(z0)w3(x3)c3 r1(x3)w1(y1)c1 w2(x2)c2 r∞(x2)r∞(y1)r∞(z0)c∞
この場合で、r1(x3)w2(x2)について x: t1→t2になっている。他方、r2(y0) w1(y1)なので、 y:t2→t1になる。よって、monoversionが成立しないので、sはMCSRではない

ただしこれはversion orderからみると
version x t0→t3→t2 y t0→t1 なので、t0→t3→t2→t1→t∞でそもそも問題ない。
version orderを選択することで、MCSRでのconflict x t1→t2の依存関係を排除することができるはず。
実際、s’ = w0(x)w0( y)w0(z)c0 r2(y)　r3(z)w3(x)c3 r1(x)w1(y)c1 w2(x) c2　r∞(x)r∞(y)r∞(z)c∞　で問題ない。要は、MCSRではコンフリクトだがMVSRではそうではない。

翻って見るに、MCSRでは判定にversion orderは直接触っていない。tx orderのみで判定している。したがって実装上はより簡易に処理することができるが、その分狭くはなる。本来のmultiversionのパワーを完全に生かすのであれば、やはりMVSRが望ましいのは間違いない。かつ通常のVSRよりもよりスケジューリングパワーがあることは間違いない。

現実的な実装としてはMCSRでvalidation checkしてアウトの場合はversion orderの変更でいけるかどうかという確認を行うやり方があるかな、と思う。（そんなことよりはback-offのretryで十分だとかいう説もある。）個人的には「でもどうせ読んでないんだから、そのままversion維持やればいいじゃねーの、そもそもそれがmultiversionのいいところだろう。」とは思うんですがね。serial historyの時にread txの後ろに順序できることがわかればそれでおしまいのはず。人間が見れば直感的にわかるので、まだまだ人類の知らない近道があるのは間違いないのだが。

とりあえずこんなもんでMVCCの基礎理論はいいと思う。