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

1.目的

今後の分散DBでは、前提が分散ノードから分散コアに主体が移る。ムーアの法則の限界は、メニーコア化とノードの高密度化を推し進める。分散のノードではリードロックの問題とノード分散の相性の良さでSnapshot Isolation(以下SI）がほぼ前提であったが、RDMA等のハードウェアの技術革新でレイテンシーが改善されるのであれば、SILOのような(表面上は）単ノードのS2PLの改良版も有りになってくる。

そうなってくると理論的な背景も、SIを前提という話ではなくて、通常のConflict Serializability (以下CSR)も頭に置きながら話をおっていかないと理解が厳しい。

SI「だけ」であれば、なんとなくまぁセオリーでr-w依存での循環グラフだよね、ということを前提において議論を追いかけて、r-w依存はあとで復習して調べとけばなんとかやり過ごせる。が、通常のCSRも混線してくると、そもそもなんでr-wなんだっけということが、スルッと出てこないといちいち話を巻き戻す形になって、議論についていけなくなる。要するに途中でわけがわからなくなる。

結論から言うと、SIの理論はmulti-versionになっていて、Multi-version View Serializability (以下MVSR )が下敷きになっている。なので、conflictはr-wの話になる。その一方で例えばSILOのようなものは一見するとr-wのconflictの話をしているように見えるが、実際は通常のCSRでの延長で話をしている。そのためにS2PLが持ち出されているし、そこで決着をつける形になっている。(ただしSILO自体はそんな単純な話ではないので、それはまたあとでまとめる）

実装はCSRでもMVSRでも両者ともどもエッジグラフでのvalidationになるので、結果としては「同じ」read-setとwrite-setのintersectionの話になっているところがややこしい。やっていることは似ているが、導かれているクライテリアは異なるということだ。(大抵の教科書はCSRまでの定式化までしかしないので、その理屈だけで行く人が多いと思うが、そうなると議論についていけなくなる。)

なので、SIをserializabilityの議論のなかで、しっかり定式化して置く事が肝要になる。これを身につけておかないと、今後のTx系の論文の深いところの理解は覚束ない。ので、ちゃんと整理しておく。

2.Multi-versionでの serializability
multi-versionのserializabilityは、通常の単一スケジューリングのserializabilityとは異なる。通常の単一スケジューリングでは、CSRが基本になるが、multi-versionでは、VSRすなわち、View Serializabilityが基本になる。SIの話にしろ、なんにしろ、multi-versionの話になったときに、correctnessのクライテリアはVSRですよね、とガツンと路線を切り替えないと話が脱線する。

特にVSRの場合、read-fromの依存関係がserializabilityのキーファクターであり、これは「どのreadが結局はどのバージョンのwriteを読むか？」ということに依存することを考えれば、multi-versionのコンテクストでは、CSRよりはむしろVSRのcorrectnessのクライテリアに近い事は容易に想像できる。

multi-versionでのserializabilityは、通常multi-versionでのconflict serializability、すなわちMulitiversion Conflict Serializability（通常MVCRと略する）のことをさすが、このconflict serializabilityは、通常のCSRのスケジューリングのconflict ではなくて、VSRでのconflictの延長にある。通常のCSRでのconflictは w-w w-r r-wの三種類になるが、MVCRではr-wだけになる。これはVSRの延長から来ていることによる。

以下表記は、ri(xj)は、transaction iにおいて、verion jのxをreadするということを意味する。wi(xi)は自明であるが、mono-verisonと区別するためにxiを記述する。なお、順序は全順序が前提。

3. MVSRの定式化

3-1 version order と mono-version

version orderとはそのversionが作られた順番そのものではなく、serialization orderを決定する際に利用される、各書き込まれたversionの順序をさす。

mono-version とは単一のバージョンによるmulti-versionのスケジュールをさす。要するに普通のスケジュールになる。multi-versionでreadが直前のupdateのversionを読む制約を加えるとmono-versionと同じ属性を有することになる。multi-versionにおいて、read-fromの依存関係を維持したままで、各operationをスケジュール内で交換し、mono-versionに投影した時にserialなmono-versionのスケジュールを作る事ができれば、それはserializableということになる。

3-2 Serializability

判定はMulti-version Serialization Graph (MVSG)を利用する。このグラフはread-fromの依存関係からtransactionの依存グラフ(dependency graph)を作成し、そのgraphが非循環かどうかで判定する。非循環の場合はトポロジカルソートにより、serialなスケジュールを作る事が可能になる、というかできるはずという事になる。

MVSGのグラフのエッジは以下の条件により作成される

あるxについて、wj(xj), rk(xj), wi(xi)を想定した場合、まずrk(xj)があるので、
1. tj->tkの依存エッジが必ず存在する。
2. xi->xjのversion orderの場合
wi(xi)->wj(xj)が存在し、よってti->tjのエッジが存在する
または
xj->xiのversion orderの場合、
wj(xj)->wi(xi)となり、そもそもwj(xj)->rk(xj)であるので、xj->xiならば、必ずrk(xj)->wi(xi)になる。
よってtk->tiのエッジが存在する。

4. MCSRの定式化
MVSRのサブクラスになる。グラフがより簡易になるので、整理しやすい。
ややこしいのは、MCSRは以下の通りSIとは異なる。なので、ここでは本筋ではないが附随的な議論として置いておく。今後MCSRがロジックとして持ちだされた場合に必要なので、その理解のために整理しておく。

MVSRのサブクラスとして、MCSRを定式化する。
これはMVSRのdependencyをさらに簡潔にする。dependencyとして考慮するのは、rk(xj)->wi(xi)だけになる。MVSRの依存が、wj(xj), rk(xj), wi(xi)で判断することに対して、wj(xj)を判断しない形になる。まぁ、rk(xj)があるということは、wj(xj)が先行している（はず）と考えておく。先行していない場合は初期値(すなわちj=0）を除けば、そもそもスケジュールとして成り立たない。

なお、このグラフをMulti-version Conflict Graphといい、このグラフが非循環の場合をMulti-version Conflict Serializable といい、通常MCSRと称する。

直感的な説明は以下

1.そもそもwi(xi)-wj(xj)がなぜ依存関係ではないか？
これは後続のreadの対象の問題であるので、別段、xiとxjになんらかの関係があるわけではない。（これはMVSRも同じ）

2.wj(xj)-rk(xj)がなぜ依存関係ではないか？
仮にrとwを交換しようがしまいが、version orderには影響がない。よって、依存関係があるわけではない。そもそもスケジュールで読めていたということはread-fromが成立しているということなので、そのようにverison orderを維持することが可能だ。
（厳密にいうと、readの前に既にwriteがあるので、r-wに交換してもそれがserializableならばそもそもw-rもserializable になるはず。readできる選択肢は交換することで減る。）

3.rk(xj)-wi(xi)
r-wについては、仮に交換すると、rの前にwを持ってくることになる。この場合、交換前のversion orderと異なるversion orderを「強制的に」つくることができる。要するに”壊す”ことが可能になる。読めるversionを「追加」することになるので、後続readでいくらバージョンを指定しても、事前にあったversion orderを、交換後の操作で上書き(versionではなくてversion orderの上書き）する事が可能になってしまい、version order自身を維持（というか担保）する事ができない。よってconflictになる。

2017/7/29追記：正確にいうとversion orderを維持したスタイルでのserializablityの確保のプロトコルをとった場合に、である。version order自体は可変であるので、別のversion orderをとってかつGraphが非循環になるのであれば、問題ない。ただし、その判定がかなり面倒なので、version orderを維持するため（すなわち”壊す”ことができないように）順序を維持する、という言い方がより正しい。

ただし、abort検出の際にMVSRにできるがMCSRではないものを擬陽性で検出するリスクはある。wi(xi)wj(xj) rk(xj)の形が取れて、かつそもそもversion orderがserialに作れれば、MVSRになり、実際はserializableになる。これは、MCSR＜MVSRの例。（偽陽性といえば偽陽性ではあるが、これは判定コストの問題をどう考えるかによる。）

（なお、個人的感想だけど、この部分のちょっと（かなり）わかりづらい。Tx本の解説でも本自身が認めている有様だ。この部分に関してはグレード的には辛めに見ても5.13はあると思う。とほほ）

5. SIの定式化

1.各readに対するversionの割当は当該readのTxが開始される時点で、最も最近にコミットされたwriteのものを割り当てる。
ri(x) mapped wj(x) であるときに
wj(x)＜cj＜bi＜ri(x) かつ（ wh(x)＜bi and cj＜ch＜bi ）であるwh(x) chは存在しない cはcommit bはbegin

2.二つのconcurrentなTxのwrite setは交わらない
任意のtiとtjについて、bi＜bj＜ciまたはbj＜bi＜cjであれば、tiとtjは共通のobjectについて書き込みをしない

SIはmulti-versionである。「あるreadに対して特定のwriteのversionの割当を行う」という意味でSIがMVSRの特殊ケースである。ではあるが、SIはMVSRよりもwrite-setの交差を制限するという意味でより制限的である一方で、MSVRで要求されるread-fromの要件、すなわち該当するserialな単一versionでのスケジュールでのread-from（w-rのconflict）との互換性は、要求されない。この点でMVSRよりも制限的ではない。これらの意味で、非互換である。

依存グラフすなわちSnapshot Isolation Serialization Graphは以下に定式化できる。

1.すべてのrj(xi)について ti->tj

2.すべてのrk(xj)とwi(xi)について
ci->cjであればti->tj
cj->ciであればtk->ti

ここでMVSRと比較してみる。

1.についてまったく同じである。これはmulti-versionに共通のconflictである。

2.SIではcommit orderであり、MVSRではversion orderであるので、本来であれば別物であるが、
MVSR: xi->xjであればti->tj　または xj->xiであればtk->ti
SI: ci->cjであればti->tj または　cj->ciであればtk->ti

readしたものを後続（ここの後続の意味がSIとMVSRで違う）の別のTxがwriteする場合は、readのTxとwriteのTxでの依存関係が発生し、commit orderまたはversion orderが逆順の場合は、write Txとread するversionを書いたTxについての依存関係が発生するという意味では同じである。すなわち、メタレベルのセマンティクスは同一であることがわかる。

6. まとめ
以上のように、MVSR/MCSR/SIのserializationには、一定の共通したセマンティクスがあることがわかる。これは単一スケジュールのCSRとは別物であることも明快だ。今後MV系のTx処理が展開される場合には、この路線の上で議論はまずまちがいなく展開されるだろう。（逆にこれがわからないと話にならないと思うので、なんか分散TxでMV系の話が合わないなと感じたら、このブログを参照してもらえばいいかもしれない。ほんとかよ。）

上記のように、SIといってもMVSRと交差するコンセプトであり、かつおそらくMVSRの方が広い。証明はともかく、直感的にはcommit orderを考慮しない方がconcurrentなhistoryの選択の余地はある（と思う）ので、例えばLTT(long-time transaction)とSIの共存にMVSRを取れば、変なlockをとらなくてもserializableにできる可能性もあると思う。可能になればDBの使い勝手は非常に広がる。このように現行のDBは最先端であっても、まだまだ発展途上で有ると思う。transactionはベースが数理論理学なので、理論的には可能だがまだ道が発見されていない、または発見された道が割とイマイチ、というものが簡単に見つかる。個人的には本当に興味が尽きない。

なお、上記の元ネタはほとんどが、Tx本なので、そこを参照してもらえればよいけど、MVが5章で、SIが最終章なので、鬼の3-4章を突破して、さらに最後まで読まないと無理なので、がんばってください。白状しますと、なんとか3-4章はクリアした後の、5章の特にMCSRの下りは初見では、「まったく」理解できませんでした。あの部分は本当に難しいと思う。あそこがオンサイト一撃（フラッシュは駄目よ）の人は、間違いなく一種の才能があるので、ウチで採用するので連絡ください。まじで。