MVTO (multi-version timestamp ordering)

MVCC系の実装プロトコルの代表例。

そのほかにMV2PL(実際は2V2PLが多い)とMVSGTがある。なおMVTOにも様々なバリエーションがある。理論自体は1980年後半から存在している。version無制限というのは、従来のH/Wでは非現実的だったが、近年のノードあたりのメモリーの大容量化やNVRAMの登場によってそれほどデタラメな前提ではなくなりつつある。適切にGCをかけることやversion traverseを工夫することでパフォーマンスを維持することができる。その結果最近のMVCC系のプロトコル実装はMVTOが多くなっているように見受けられる。というよりもほぼMVCC=MVTO一色の様相だ。実際、ベンチマークも数字は出ている。
(修正:MVCCの中にOCCではあるがMulti-versionを利用する形式のものをあり(MVOCC)、それもMVCCとすれば、MVCCはMVOCC+MVTOになる)

■MVTOのメリット・デメリット

1 メリット

・シンプルでわかりやすい

その他のプロトコルに比べて、ぶっちぎりでわかりやすい。ということは実装する場合はバグが出にくいというメリットがある。ただし理屈はちゃんと理解するとかなり深いところまで必要になる。実装は簡単だが理屈は深い。コンピュータ・サイエンスのお手本のようなプロトコルだ。(念のために言うと「簡単」というのは「動かすだけなら」と言う意味で。パフォーマンスを出そうとするとそう簡単ではない。)

・後で追加的な修正がしやすい

実際SSNのように仕組みをあとから追加することが容易だろう。MV2PLやMVSGTあたりに後から何か実装追加するのは、あまり現実的とは思われない。実際、2017年現在のMVCC実装である、Hyper Cicada Bohm等々はそれぞれ独自の味付けをしている。この辺りは別の機会にするが、ざっくりの印象としては、HyPerはそもそも新しい手法を提案しているし、CicadaはむしろMVTOを実直に行いエンジニアリング寄りに振った形、Bohmはできるだけシンプルにもってくるように感じる。骨格がはっきりしているので、肉付けが色々できると言う証左だ。
(修正:HyPerについてはMVTOではなくてMVOCC(ほぼOCC)という話もあるのであとで検証)

・read lock free

これはもはやDBMS界の常識なのでいまさらではあるが、readがブロックされない。ただし、これはMVCC固有のメリットではない。OCCも同じメリットはある。
なお、validationをロックと見るかどうかにもよるが、writeについてもmultiverisonなのでw-wの競合は発生しない。基本的にwriteについても2PLタイプのいわゆるlockは存在しない。

2 デメリット

・timestamp(以下ts)の維持がちゃんとできるか?

これができないとそもそもいろいろ崩壊する。ただ、これはTrueTimeである必要なくmonotonic increasedであれば十分である。現在の事情ではそれほどデメリットとはいえない。とはいえ、ボトルネックにはなりやすい。tsの管理は、一体、(a)どのtsを使うのか、(b)どうtsをとるかがポイントになる。各実装を見る時には、この2点に絞って違いをみていく必要がある

・versionの管理をどう捌くか?

もともとmultiversionのコストの大半がversion管理なので、この問題は常に顕在化する。
課題としては大きく以下の二つ。

1. versionトラバース
基本戦略はversionトラバースをさせない。だらだらトラバースさせると時間を食うし、キャッシュラインが汚れる。うまくキャッシュを使う方法や、そもそもトラバースさせないようにする手法などが使われる。

2. GC
基本version数は無制限なので、どこかでGCする必要がある。いつ・どうやって行うかが手間になる。現状のMVCCはとにかくスループットが跳ね上がるので、普通に 3 million TPSあたりが普通の基準になる。数10msであっという間にstale recordが数百MByteになったりする。うまくやらないとあっという間に何もできなくなる。

・ロングバッチが走ると絶望的にabort率があがる。

これは、OCCも同じであり、むしろtransaction一般の問題に近い。MVCC固有の問題とするのは酷だろう。対処は基本リトライになる。よって以下にうまくリトライさせるか?がポイントになる。そもそも単一の仕組みでは対応できない気が個人的にはしている。

OCCの比較や、より細かい話になるとまだいくらでもあるが、ざっくりのポイントとしては上記が代表的な論点になっている。

■MCSR

後段のように事実上version orderが事前に決定するので、validation phaseでの論理的なMVSG(Multi-Version Serialization Graph)がすべてのMVSRをカバーするわけではない。ということは偽陽性がある。single-versionのOCCよりも理論的にはabort率は低いとはいえ、もっとabort率を低減する手段はheuristicではあるが存在するはず(一般解はNP完全)。なので、追加的に色々措置を講ずるのはありだとは思うが、今のところその有効な手段を人類はまだ発見していない。

MVTO自体のserialization空間はMCSRよりも狭いと思われる。
・w1(x1)w2(x2)r3(x1)c1c3c2だと、r3の時にtx2が追い越しになるのでtx2はabortになるが、tx1-tx3-tx2でserializable
要は追い越したときに
・MVSR:前後にversion orderを変更
・MCR:後ろにversion orderを変更
・MVTO:abort
になっている。とはいえ、MCSRの一部は実行可能で
CSR<MVTO<MCSRだと思われる。

■実装プロトコル

Tx本より引用する。
1. read step (ri(x))は自身ts以前(含む)でかつ、最大のtsをもつversionを読む。
すなわち ri(x)→ri(xj)でts(tj) <= ts(ti): j = Max version number of x

2. write step (wi(x))は以下の順で処理
2-1 そのwriteが生成するtsよりも後のtsをもつreadが、そのwriteが生成するversionよりも前のversion(そのwriteのtsよりも前のtsをもつtxで生成されたversion)を読むことになりそうな場合は、abortする。
すなわち、rj(xk): ts(tk) < ts(ti) < ts(tj)が存在する場合は、wi(x)はabort
2-2 でなければ普通にwi(x)を実行する

3. readのコミットはそのreadが読んでいるversionを生成するwriteを含むtxのコミットが終了するまで遅延させる。これはdirty readの防止+リカバリーの保証になる。

日本語で書くとちょっとわかりづらいが、要するに「readするときは必ず最新のversionを読んでいる」ということ「だけ」が保証されていれば良い、というプロトコルである。たったそれだけでfull-serializableである。
書く方は「readするときは必ず最新のversionを読んでいる」と言う不変条件を満たさないときはabortし、それ以外には何も考えずに書き込める。*1

以下論点

■最新のversionとは何か?

MVCC系では、この「最新のversion」というのを(単純にlatestって言うと後から割り込んだversionがlatestになるので)、あるTxから見た「visible version」という言い方をすることが多い。場合によっては定義なしでvisibleという言い方もしたりするので、その場合は確認した方が良い。

Cicadaの場合の定義を貼っておく
The visible version of a record for a transaction is a version whose write timestamp is the latest (highest) among all committed versions of the record and is earlier (smaller) than the transaction’s timestamp.

ただ、MVTOではdirty(possible committed)なwriteも読むことができるようになっている。基本的にはCommitted Projectionが前提になっているので、commitされる前提(ただしrecoveryのことがあるのでcommit orderは決まっている)は敷いている。なお、実装的には上記にある通り、committed versionを使うのが主流なので、一見するとSnapshot Isolationの制限版と同じに見えるが理屈が全くことなる。

もちろん念のために言っておくと、字義どおりにcommittedだけを対象にすると自分が書いたものを読めなくなるので、そうならないようにどの実装も工夫はしている。

■serializablityの証明 

CC本から引用する。
まずformalization
The following properties describe the essential characteristics of every MVTO history H over (T0, . . . Tn).

Property1.
For each Ti, there is a unique timestamp ts(Ti);
That is, ts(Ti) = ts(Tj) iff i = j.
tsの定義。注意すべきは別段startimeにはしていない。順序があれば良い。

Property2.
For every rk(xj)∈H, wj(xj) < rk(xj) and ts(Tj) <= ts(Tk).
読むべきものは書かれていること。ここは普通はcommitであるが、別段installでも良い。

Property3.
For every rk(xj) and wi(xi)∈H, i!=j,
either (a) ts(Ti) < ts(Tj)
or (b) ts(Tk) < ts(Ti)
or (c) i = k and rk[xj] < wi(xi).
version orderの属性。(a)はvisibilityの属性(kは判断されない) (b)はvalidationの基準(kとiが交差するとき)(c)はまぁ常識で

Property4.
If rj(xi)∈H, i!=j, and cj∈H, then ci < cj.
読む場合は必ずコミット順がある。

そしてProof
Theorem : Every history H produced by MVTO is 1SR.
1SRはone-copy-serializableのこと、少なくとも一つのmonoversionでserialなスケジュールと同一のsemanticsが保てるということ。

Proof:
Define a version order as follows : xi << xj iff ts(Ti) < ts(Tj).
version orderの定義

We now prove that MVSG(H, <<) is acyclic by showing that for every edge
Ti -> Tj in MVSG(H,<<), ts(Ti) < ts(Tj).
証明のターゲット MVSGが非循環であれば良い。

Suppose Ti -> Tj is an edge of SG(H).
グラフのエッジ=dependency

This edge corresponds to a reads from relationship.
この段階でのdependencyはRF

That is, for some x, Tj reads x from Ti.
By Property2, ts(Ti) <= ts(Tj).
By Property1, ts(Ti) != ts(Tj). So,ts(Ti) < ts(Tj) as desired.
全順序

Let rk(xj) and wi(xi) be in H where i,j,and k are distinct, and consider the version order edge that they generate.
あるxについて読み書きがぞれぞれ別にあるケースは以下になる

There are two cases:
(1) xi << xj, which implies Ti -> Tj is in MVSG(H, <<);
and (2) xj << xi, which implies Tk -> Ti is in MVSG(H, <<)
全順序なのでversion orderが形成できて、その場合はどちらが先になるので、それぞれのケースでMVSGのエッジが形成される。

In case (l), by definition of <<, ts(Ti) < ts(Tj)
In case (2), by Property3, either ts(Ti) < ts(Tj) or ts(Tk) < ts(Ti)

The first option is impossible, because xj << xi implies ts(Tj) < ts(Ti). So, ts(Tk) < ts( Ti) as desired.
Since all edges in MVSG(H, <<) are in timestamp order, MVSG(H, <<) is acyclic.
最初のケースは前提(Property2,1)からありえないので、(2)のケースのみ成立。よってトポロジカルソート可能。

あとはMVSG一般の証明
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で、かつその時に限る。要は、MVSGが非循環あれば(かつその時に限り)1SRである。
証明はこちら。multi-versionの基礎 - 急がば回れ、選ぶなら近道
要はこの定理がまずは前提になっているということ。

以上終了。

ちなみにこのMVSRはrk(xj) とwi(xi)において、ts(Tk) < ts(Ti)の維持なのでMSCRになる。(つまり偽陽性はある。)基本的にr-wを維持する形になっている。MVTO⊂MVSRなのは上記の通りで良いとして、MVSR != MVTOの例は簡単にわかる。
w1(x1)w1(y1)w1(z1) r2(x1) r3(y1)w3(x3) w2(x2) r4(z1) w3(y3) r4(x3)w4(x4)c1c2c3c4
でMVTOはアウトだが
w1(x)w1(y)w1(z)c1 r2(x)w2(x2)c2 r3(y)w3(x)w3(y)c3 r4(z)r4(x)w4(x)c4
でserializable。要は追い越しで書いても後続で追い越しの値しか読まないのであれば別に問題ないということだ。(通常は書き込むその値を事前に読まずに書くということはまぁないのでMVTOでも良いという考え方もあるが、ある値が一義的に別の値で決定されるときには別に読まずにノータイムで書けるはずなので、そのようなケースがはねられてしまう。)

プロトコルを見れば、恐ろしく簡単で、しかもreadは全てブロックされない。writeのみがvalidationがかかって、readとその読んでいるversionに「割り込む」場合のみabortすれば良い、ということだ。それでserializableが保証される。

ちなみに実装はrecordにwriteのtsとreadのtsを打っておけば、それでほぼ判別できるので、そういう形が多い(BOHMはちょっと工夫している)

余談だが、MVTOは2017年のVLDBのCicadaで実装されているプロトコルで、公称ではFoedus/MOCC/TicTac等を軒並み抑えるパフォーマンスを出している。前述のようにCicada, BOHM, HyPer, ERMIAあたりはこの方式が根っこである。今後MVCCを見ていくときは上記のMVTOはほぼ前提になっているので、理解しておかないと真面目にわからなくなる。

例えばMSのSQLServer2014 (Hekaton)はMVCCですぜ、と論文を出しているが、背景に想定しているプロトコルは MVCCではない。BOCCを想定している。高速化や使い勝手の問題で形式はmultiversionを利用している。これをMVCCというかどうかは本来であれば議論が別れるところであると思う。

なるほど、形式がmultiversionであれば広義のMVCCだという言い方も可能ではある。ただしそれを言い出したら、極論すればbefore image/after image方式も2versionのmultiversionになるので、この手のリカバリー方式をとっているDBは全部MVCCになる。そんな馬鹿な話はない。

Hekatonの場合はBOCCであり、よってserializationのセマンティクスはCSRである。一般にMVCCのserializationのセマンティクスはMCSR(またはそれに同等)であるので、スケジューリング・パワーという意味ではHekatonはMVCCの広さほどにはない。

スケジューリング・パワーの差は偽陽性の範囲にかかわり、今の分散OLTPの争点の一つがabort率である以上、看過できない論点のはずだ。個人的はMCSR同等のスケジューリング・パワーがあって初めてMVCCを名乗る資格があると思う。その意味ではHekatonはMVCCというよりもOCCに近い。(正直、この辺りがわかっていてVLDB/SIGMODあたりに採択されているのか多少疑問を感じる)

確かにTPC-CやYCSB前提であればそれほど問題にならないかもしれない。が、実際のアプリケーションの適用時点でパフォーマンスに差が出て来る可能性はある。実際 (MCSR-CSR)なスケジュールが多数出るようなアプリケーションの場合は、極端に差が出るだろう。両者共にserializableのisolationの設定であるにもかかわらずである。

そんな感じ。
(前回はMVCCの一般の話を基本にまとめた。今回はそれをベースに実装プロトコルをまとめた。次にそのreference implとしてCicadaを解説する(予定)。)

*1:と書くと正確ではない。より前に遡ってversionをつくるということも実は可能で、この場合はMCSRではないMVSRになる。ただし、これは全部がconcurrentに走っている前提があるので、commit orderを考えるとちょっと面倒。なのでここでは目をつむる。