論文メモ Multiversion Concurrency Control - Theory and Algorithms

January 6, 2021

データベースのトランザクション制御Multiversion Concurrency Control(MVCC, 多版型同時実行制御) 下のトランザクションが逐次実行と等価な結果になる条件を定義した。 また、その定義を既存のMVCCのアルゴリズム3つにあてはめ、アルゴリズムの正しさを確かめた。

MVCCは、データを書き込むときに、もとのデータを上書きせず、新しいバージョンを生成する。 トランザクションが複数のバージョンから読み込むデータを選べるため、単一バージョンの実行制御よりも読み込みと書き込みの実行順序を柔軟に入れかえられ、結果、処理性能が向上する。

一方、ユーザーは、データのバージョンが単一で、既存のデータがあれば書き込みが上書きになることを期待する。 ところが、MVCC下で起こりえる実行系列のなかには、単一バージョンの実行制御ではありえないものがある。 そのため、MVCC下のある実行系列が単一バージョンの実行制御でも起こえりる条件が必要になる。 加えて、その実行系列が逐次実行と等価な結果になる条件も必要になる。

まず、単一バージョンの並行制御における実行系列が逐次実行と等価になる条件を整理する。 トランザクション\(T_i\)を1つ以上の読み込みか書き込みからなる半順序集合とみなす。 データ\(x\)への読み込みを\(r_1[x]\), 書き込みを\(w_1[x]\)であらわす。 1つ以上のトランザクションの書き込み、読み込みの要素からなる半順序集合をログとよぶ。

\(w_i[x]\)が\(r_j[x]\)に先行することを\(w_i[x]<r_j[x]\)とあらわし、関係\(T_j \textit{ reads-x-from } T_i\)が\(w_i[x]<r_j[x]\)かつ二つの操作の間に\(w_k[x]\)がないことを意味するとき、\(\{T_0, \dots T_n\}\)の2つのログが任意の\(i, j, x\)で\(T_j \textit{ reads-x-from } T_i\)が成立すれば、両者は等価とみなす。 逐次実行のログは関係\(<\)をみたすトランザクションの全順序集合になる。 逐次実行のログと等価なログをserializableという。

MVCC下のトランザクション\(T_i\)の書き込みで生成されるデータ\(x\)のバージョンを\(x_i\)とおく。 このとき、単一バージョンの並行制御での関係\(T_j \textit{ reads-x-from } T_i\)は\(T_j\)が\(x_i\)を読み込むことであり、MVCCではこれを\(\textit{reads-from}\)と言いかえる。 すると、2つのログが同じ\(\textit{reads-from}\)をもつとき、両者を等価とみなせる。

MVCCのログのなかには単一バージョンの並行制御でおこりえないものがある。 たとえば、次の逐次実行のログは単一バージョンではおこりえない。 $$ w_0[x_0]w_0[y_0]r_1[x_0]w_1[y_1]r_2[y_0]w_2[x_2] $$ 任意の\(i, j, x\)について\(T_j \textit{ reads-from } x_i\)であるとき\(i=j\)であるか\(T_i\)が任意のバージョンの\(x\)に書き込んだ\(T_j\)に先行する最後のトランザクションならば、MVCC下の逐次実行のログは単一バージョンの並行制御でも起こりえる実行結果をもたらす。 このようなログをone-copy-serialとよぶ。 そして、one-copy-serialと等価なログをone-copy serializableでといい、これが単一バージョンの並行実行でも起きえる逐次実行と等価な結果をもたらすログになる。

トランザクションをノードとする有向非巡回グラフ(DAG)を描けるか調べることで、あるログがone-copy serializableであるかを確認できる。 ログ\(L\)における\(k\neq i\)の各\(r_k[x_j]\)と\(w_[x_i]\)について、ある全順序関係 \(x_i< <x_j\) であるとき\(T_i\rightarrow T_j\)それ以外で\(T_j\rightarrow T_i\)を含むグラフを\(\text{MVSG}(L, < <)\)とする。 このとき\(\text{MVSG}(L, < <)\)がDAGになる全順序関係\(< <\)があることが\(L\)がone-copy-serializableの条件になる。ただし、全順序関係は存在しないバージョンのデータを読み込む順序をつくってはならない。

論文をこちらからダウンロードできます。