次のような実行スケジュールを考える。T1がxを読んだらコミット前にT2がやってきてxの値を書き換えてしまった。

このトランザクションの挙動は

S2PLであればT1がxを読んだ時点でロックされるのでT2はロックが取れず停止する
OCCであれば、T1がコミットしようとしてValidateする段階でAbortする

というように、通常であれば走りえない。しかし、このT1の実行はT2がコミットした後であってもコミットできてもT1→T2の順に動作が完了したという形にSerializeできるので、本当はAbortする必要がない。つまりこの実行はSerializableだがCSRの外にある実行スケジュールという事になる。

1983年のTODSのPhilip A. BernsteinらによるMultiversion concurrency control-theory and algorithmsでは、この手の問題を解決するためのアルゴリズムであるMultiversion concurrency control(以後MVCC)が紹介されている。

マルチバージョンスケジュールの意義

例えば以下のようなスケジュールはCSRを満たさない。

Tx2はTx1のWrite結果に基づいてyを更新したにも関わらず、Tx1はTx2のWrite結果を読んでしまっているのでSerializeできる順序が存在しない。
しかし、同一の内容を実行するトランザクション列であっても、Tx1の最後のRead(y)がマルチバージョンの力で代わりにy0を読めるなら

このようにスッキリとしたCSRとして整理できる。これと同じような効果を、複数のバージョンの値を保持することで実現しようというのがMVCCの基本的なアイデアである。
最終的に達成されるスケジュールはSerializableでありながらただのCSRより広いモノになる。それによってより多くのSerializableな実行スケジュールが許容されるのでアボートの割合が減ってシステムがより高い実効スループットを実現できるようになる。

明日はそれをどのように実現していくかを解説する。