すぴすらのろぐ

読んだもののメモとかポエムとか

ゼロ知識アボートレス並列スケジューラが存在しないことの証明

TX

0. はじめに

過去の投稿の以下の主張の条件付き証明と条件を満たさない場合の反例の存在の証明です。

以下の4つの性質のうち、最大3つまでしか同時に満たせない、という主張。

  1. スケジュールの直列化可能性
  2. トランザクションの実行の並行性
  3. トランザクションの実行の失敗回避性
  4. アプリケーションに対するゼロ知識

もしくは以下の3つの性質のうち、最大2つまでしか同時に満たせないという主張。

  1. 失敗を引き起こさない直列化可能スケジューリング
  2. トランザクションの実行の並行性
  3. アプリケーションに対するゼロ知識

この主張のイメージ図：

f:id:dev_supisula:20200425043906p:plain
The Concurrency Control Triangle
。

用語は主張の説明の記事、ゼロ知識での制約は制約の説明の記事を参照してください。

タイトルの"ゼロ知識アボートレス並列スケジューラ"とは、アプリケーションに対するゼロ知識で失敗を引き起こさないトランザクションの並列実行可能なスケジューラにつけた（適当な）名前です。

1. 準備

スケジューラへの入力

複数のトランザクションのデータベースステップが1つのキューにキューイングされるとする。スケジューラはこのキューを入力とする。

スケジューラの動作

スケジューラは、入力スケジュールの先頭のデータベースステップを取り出し、それに対するアクションを実行するかまたは実行を保留するかを選択する。

トランザクション T_1によるデータベースアイテム x_2をreadするデータベースステップを r_1(x_2)、writeするデータベースステップを w_1(x_2)と書くことにする。マルチバージョンの場合にどのバージョンをreadするかは文中で補足する。

あるトランザクションのデータベースステップの実行を保留しても、並行する他のトランザクションのデータベースステップがキューに到着すること（保留したデータベースステップの実行を他のトランザクションが待つことがないこと）は一般に期待してよい。これは前回の記事の"トランザクション間に隠れた制約がないと仮定できない"に書いた通り。

一方で実行が保留されたデータベースステップの属するトランザクションについては、新しいデータベースステップが到着することを期待できない（保留されたステップを実行しないかぎり次のステップが決定されない）。

トランザクション間の順序に関する制約

あるトランザクション T_1があるデータベースアイテム x_1にwriteした値を、別のトランザクション T_2がreadした場合、トランザクション間の順序は T_1 \to T_2という制約を満たす必要がある。この関係をreads-from関係と呼びこれによる制約を T_1 \xrightarrow{x_1} T_2とあらわすことにする。

別のトランザクション T_3が x_1にwriteしようとする場合、 T_1,T_2,T_3の直列化順序上の順序は、以下のいずれかになければならない。

  • T_3 \to T_1 \xrightarrow{x_1} T_2
  • T_1 \xrightarrow{x_1} T_2 \to T_3

逆にいうと、以下の順序があり得ない

  • T_1 \to T_3 \to T_2

T_3が間に割込むと T_2は T_3がwriteした値をreadする必要があるが、 T_2はすでに T_1がwriteした値をreadすることが決定されているためである。

これに加えてモノバージョンの場合は、 T_1が x_1にwriteした後に T_2が x_1にwriteした場合に T_1 \to T_2という制約が発生する。（それ以降のreadは T_2がwriteした x_1の値しか読めないため）

このようなミクロな制約（順序）全体からトランザクション単位での矛盾のない全順序が導かれる必要がある。

モノバージョン、マルチバージョン

モノバージョンでは、識別性のある最小単位であるデータベースアイテムの値は同時にただ1つしか存在できない。あるデータベースアイテムへのwriteを実行すると、writeしたトランザクションが実行中かcommit済かにかかわらず、以前の値をreadすることができない。

マルチバージョンでは、同じデータベースアイテムに対する複数の値（複数のバージョン）が同時に存在でき、readステップの実行の際にスケジューラはそれらの中から読む値を選択できる。

スケジューラの目標

アボートレススケジューラは 、一度実行したデータベースステップを直列化失敗を理由としてアボートさせない。
並列スケジューラは、完了していないあるトランザクション実行中に、他のトランザクションの（一部の）データベースステップを保留することなく実行したい。

あるデータベースステップを実行すると、将来の直列化失敗の可能性を排除できない場合、アボートレススケジューラはそのデータベースステップを実行できず保留しなければならない。

あるトランザクションの実行中において、到着する他のすべてのトランザクションのすべてのデータベースステップを保留する必要が生じる場合、ゼロ知識アボートレススケジューラはトランザクションを並列実行できないことになる。

2. 補題

2.1. 補題1

ゼロ知識アボートレススケジューラにおいてreadステップを実行すると、readを実行したトランザクションは、直列化順序においてreadした値をwriteしたトランザクションの 直後 に位置づけられる。

readを実行したトランザクションを T_1、 T_1がreadした値をwriteしたトランザクションを T_0、対象のデータベースアイテムを xとする。
このreadの実行により、 T_0 \xrightarrow{x} T_1という制約が生じる。

T_0,T_1以外のトランザクションに対する知識がない場合、これらのトランザクションが xに対してwriteする可能性を排除できない。そこでこれらのトランザクション Tが xにwriteすると仮定すると、reads-from関係の制約により、 Tは T_0の前か T_1の後かのいずれかになり、決して T_0と T_1の間には割込まない。

この主張が完了していないすべてのトランザクションに対して成立するので、ゼロ知識アボートレススケジューラは T_1を直列化順序上で T_0の直後に置くことしかできない。

2.2. 補題2

ゼロ知識アボートレススケジューラにおいてコミット応答済みトランザクションがwriteした値に対するreadを実行すると、readを実行したトランザクションは並行する他のすべての実行中トランザクションよりも直列化順序上において 前 となる。

readを実行したトランザクションを T_1、 T_1がreadした値をwriteしたトランザクションを T_0とする。

補題1より T_1は T_0の直後に置かれる。 T_0はコミット応答済のトランザクションであるので、ゼロ知識スケジューラは新しいトランザクションを T_0の前に置くことができない。よってその他の実行中トランザクションはすべて T_1より 後 となる。

2.3. 補題3

ゼロ知識アボートレススケジューラにおいては、あるトランザクション T_0がwriteした値をreadできる実行中トランザクションはたかだか1つである。

T_0がwriteした値をトランザクション T_1がreadすると、補題1より T_1は T_0の直後に置かれる。もし別のトランザクション T_2が T_0がwriteした値をreadしたとすると T_2も T_0の直後に置かれることとなり矛盾する。

3. 証明

3.1. 証明の方針

ある静止状態（実行中のトランザクションがない状態）において、新たにデータベースステップのシーケンスが到着する状況を考える。

ゼロ知識の仮定によりコミット完了の応答を返したトランザクションの前には割込めないので、静止状態におけるデータベースアイテムの値をどのトランザクションがwriteしたかはこれ以降のスケジューリングにおいてはもはや重要ではなく、この値を書いたトランザクションを区別せずに T_0と呼ぶことにする。

いま入力スケジュールの先頭のデータベースステップの属するトランザクションを T_1とし、入力スケジュールの先頭から T_1に属する連続した1つ以上のデータベースステップをそれぞれ実行完了した状況を考える。
実行完了したデータベースステップがcommitまたはabortで終了していた場合は T_1は他のトランザクションと並列実行されなかったので、 T_1が完了した後の最初のデータベースステップの属するトランザクションを新たに T_1と置いて議論を続ける。

以下の2通りに場合分けして証明する。

  • T_1が、 T_0がwriteした値をreadしている場合
  • T_1が、 T_0がwriteした値をreadしていない場合

1つ目は、 T_1があるデータベースアイテムへのreadステップを実行しており、かつその前に T_1による同じデータベースアイテムに対するwriteステップが存在しない場合で、つまり T_0と T_1の間にreads-from関係ができている場合である。

2つ目は、 T_1がwriteしか実行していない場合か、または実行した全てのreadステップに対してそれ以前に T_1自身による同じデータベースアイテムに対するwriteが存在した場合である。ここではこのようなトランザクションを write先行トランザクション と呼ぶことにする。

以降では T_1の実行の途中で別のトランザクション T_2のデータベースステップを取り出した場合を考える。 証明では、この T_2のデータベースステップを実行してしまうと、直列化失敗を引き起こすような（直列化の観点では意地悪な）データベースステップの到着を排除できないこと、それゆえ T_2のデータベースステップを保留せざるを得ないことを示す。

3.2. T_0と T_1にreads-from関係がある場合

T_0がwriteし T_1がreadしたデータベースアイテムを x_1とする。reads-from関係 T_0 \xrightarrow{x_1} T_1 が存在し、補題1により T_1は T_0の直後に置かれ、補題2により T_2は T_1より後になる。
T_2のデータベースステップの実行によって T_2が T_1の"前”やT_2が T_0の"直後"となってしまう可能性が排除できない場合、アボートレススケジューラはそのデータベースステップを実行できない。

現在実行しようとしている T_2のデータベースステップによって以下の5通りに場合分けする。

  1. T_1がwriteしていないデータベースアイテムに対するread
  2. T_1がwriteしたデータベースアイテムに対するread
  3. x_1以外のデータベースアイテムに対するwrite
  4. x_1に対するwrite
  5. commit or abort

3.2.1. T_1がwriteしていないデータベースアイテムに対するread

このデータベースアイテムを x_2とする。
x_2の値をwriteしたのは T_0であるので補題3よりこのreadは実行できない。

3.2.2. T_1がwriteしたデータベースアイテムに対するread

このデータベースアイテムを x_2とし、このreadステップ r_2(x_2)を実行したとする。

モノバージョンの場合

T_1がwriteした値を読むことになるが、 T_1によるユーザアボートの可能性を排除できないので、スケジューラはこのreadステップを保留する必要がある。

マルチバージョンの場合

すでに実行された r_1(x_1)と補題1,2より T_2は T_1の前に位置づけられない。よってデータベースステップ r_2(x_2)が読むべき値は T_1がwriteした値（もしくはこれ以降にwriteされる値）であるが、 T_1は実行中なのでこのreadステップをスケジューラは保留する必要がある。

3.2.3. x_1以外のデータベースアイテムに対するwrite

T_2がwrite先行トランザクションの場合である。 このデータベースアイテムを x_2とする。

補題1,2より T_2は T_1の後になるべきである。 よってスケジューラは基本的に、 T_1のデータベースステップは実行し、 T_2のデータベースステップは（先の順序に矛盾する可能性がある場合は）保留するように振舞う必要がある。

そこで今後のトランザクション T_1の実行（ T_1のステップは実行可能でなければならない）に影響があるかを確認すればよい。

モノバージョンの場合

w_2(x_2)を実行したとし、その後 T_1による x_2へのreadステップ r_1(x_2) が到着する可能性を考える。
モノバージョンであるのでこのreadステップはT_2のwriteした値、もしくはこれ以降に実行されたwriteの値を読むことしかできず、 T_0のwriteした値を読むことができない。
よってモノバージョンの場合は実行できない。

マルチバージョンの場合

w_2(x_2)を実行後、 T_1による x_2へのreadステップ r_1(x_2) が到着する可能性を考えたとしても、 T_1は T_0がwriteした値をreadすることができる。

よって着目していたデータベースステップの実行による矛盾は生じない。よってマルチバージョンの場合は実行が可能である（反例1）。

3.2.4. x_1に対するwrite

T_2がwrite先行トランザクションの場合である。

モノバージョンの場合

T_1が再び x_1をreadする可能性を考えると、モノバージョンであるため、 T_2のwriteステップ w_2(x_1)を保留する必要がある。

一度readしたデータベースアイテムの値をアプリケーションローカルなストレージに保存することで回避できるが、これは限定的なマルチバージョンであると解釈される*1。

マルチバージョンの場合

w_2(x_1)を実行したとしても、これ以降到着する可能性のあるトランザクション T_1のデータベースステップの実行に影響を与えない。
具体的には、これ以降にトランザクション T_1によるreadステップ r_1(x_1)が到着したとしても、トランザクション T_1は T_0がwriteした値をreadすることが可能である。

よってマルチバージョンの場合は実行が可能である（反例1）。

3.2.5. commit or abort

トランザクション T_2が空の場合であるが、 T_2のデータベースステップを実行することができる（反例2）。

3.3. T_0と T_1にreads-from関係がない場合

T_1がwrite先行トランザクションの場合である。
T_1がwriteしたデータベースアイテムを x_1とする。

現在実行しようとしている T_2のデータベースステップによって以下の5通りに場合分けする。

  1. T_1がwriteしていないデータベースアイテムに対するread
  2. T_1がwriteしたデータベースアイテムに対するread
  3. T_1がwriteしていないデータベースアイテムに対するwrite
  4. T_1がwriteしたデータベースアイテムに対するwrite
  5. commit or abort

3.3.1. T_1がwriteしていないデータベースアイテムに対するread

T_2がreadしたデータベースアイテムを x_2とする。
このreadステップ r_2(x_2)を実行したとすると、reads-from関係 T_0 \xrightarrow{x_2} T_2と補題1により T_2は T_0の直後に置かれ、補題2により T_1は T_2より後に置かれる。

よってこれ以降スケジューラは基本的に、 T_2のデータベースステップを実行し、 T_1のデータベースステップを保留するよう振舞う必要がある。

そこで、今後のトランザクション T_2のデータベースステップの実行（ T_2のステップは実行可能でなければならない）に影響を与えるかを確認すればよい。

モノバージョンの場合

この後、 T_2による T_1がwiteしてしまったデータベースアイテムに対するreadステップが到着すると、上の制約を満たすためには T_2は T_0がwriteした値をreadする必要がある。しかしモノバージョンの場合は上書きされているためreadできない。
よってスケジューラは r_2(x_2)を保留しなければならない。

マルチバージョンの場合

T_2が T_1より前に位置づけられたが、既に実行されている T_1のデータベースステップによっても、今後の T_2の実行は妨げられない。なぜならば T_1はまだデータベースの値を参照していない*2ためT_0以降の任意の順序に位置づけすることが可能であり、またマルチバージョンであるためすでに行われたwriteステップも T_2のread/writeの実行に影響を与えないためである。

よってマルチバージョンの場合は、このreadステップを実行可能である（反例1）。

3.3.2. T_1がwriteしたデータベースアイテムに対するread

モノバージョンの場合

モノバージョンなので T_2は T_1がwriteした値をreadするしか選択肢がないが、 T_1が実行中のためスケジューラはこのステップを保留する。

マルチバージョンの場合

マルチバージョンなので T_2は T_0がwriteした値を読むことを選択できる。 このときreads-from関係 T_0 \xrightarrow{x_1} T_2が得られ補題1より T_2は T_0の直後に、補題2より T_1は T_2の後に置かれる。

よってこれ以降スケジューラは基本的に、 T_2のデータベースステップを実行し、 T_1のデータベースステップを保留するよう振舞う必要がある。しかし3.3.1のマルチバージョンの場合と同じ議論により、マルチバージョンの場合はこれ以降の T_2のデータベースステップは実行に影響を与えない。
よってこのreadステップは実行可能である（反例1）。

3.3.3 T_1がwriteしていないデータベースアイテムに対するwrite

T_2もwrite先行トランザクションの場合である。 T_2がwriteしたデータベースアイテムを x_2とする。

モノバージョンの場合

w_2(x_2)と実行したとする。 これ以降に T_1による x_2へのreadが到着すると、 T_2のユーザアボートの可能性を考慮してこのreadを T_2の完了まで保留する必要がある。
同様に T_2による x_1へのreadが到着すると、 T_1のユーザアボートの可能性を考慮してこのreadを T_1の完了まで保留する必要がある。
両者が到着した場合、スケジューラはどちらかを実行しないといけないが、その場合失敗の可能性を排除できない。
以上よりスケジューラは w_2(x_2)の実行を保留する必要がある。

マルチバージョンの場合

w_2(x_2)と実行したとしても現時点では T_1と T_2の間の順序には何の制約もない。
よってこれ以降到着する T_1, T_2のデータベースステップの実行によってはじめて生じる順序関係の制約に従い、前に位置づけられるトランザクションのデータベースステップが実行可能かを確認すればよい。

前の議論と同様にマルチバージョンであるので、すでに実行されたwriteステップは以降のデータベースステップの実行に影響を与えない。よって今着目しているデータベースステップ w_2(x_2)は実行可能である（反例1）。

3.3.4. T_1がwriteしたデータベースアイテムに対するwrite

モノバージョンの場合

w_2(x_1)を実行したとする。これ以降に T_1による x_1のreadが到着すると、モノバージョンであるため、 T_1がwriteした値を読めなくなってしまう。よってこのデータベースステップは実行はできない。

マルチバージョンの場合

3.3.3のマルチバージョンの場合と同じ議論によりこのデータベースステップは実行可能である（反例1）。

3.3.5. commit or abort

3.2.5と同じく実行することができる（反例2）。

3.4 保留されたデータベースステップの解除条件

最後に、一度保留した T_2のデータベースステップが保留を解除され実行可能と判断されるためには、 T_1が完了する（完了が保証される）、かつその時に限ることを示す。

ざっくりいうと、保留を解除するためには、 T_1（やその他のトランザクション）がこれ以降ｘｘｘをしないことが保証されること、もしくは他のトランザクションが必ずｙｙｙをすることが保証されることが必要である*3。

ｙｙｙは他のトランザクションのユーザアボートを考慮すると保証は得られない。ｘｘｘしないことはトランザクションの完了を持ってしか保証できない。

トランザクションの完了を待ってから実行可能となるということは、インターリーブされないということであり、結局並列実行できないということになる。

ただし T_1の完了が保証される場合には以下も含まれる。
T_1のいくつかのデータベースステップを実行し、 T_2のデータベースステップの実行を保留した段階で、 T_1のcommit/abortを受け取った場合である。

このとき、 T_1の完了（commit/abort）を保留して、保留されている T_2の（一部の）データベースステップを実行することができる（反例2）。

4. まとめ

反例1は、マルチバージョンにおいてwrite先行トランザクションと並列実行しようとする場合である。
マルチバージョンの場合の順序の制約はreads-from関係によってしか生まれないので、write先行トランザクションは、先行するwrite（とそれに隠れるread）ステップを実行しても制約を生成しない。
そのため、通常のトランザクションと1つ以上のwrite先行トランザクション（の先行するwrite部分）をインターリーブして実行することができる。

反例2は、commit/abortをデータベースステップの一部であると解釈する場合に、read/writeステップと最後のcommit/abortステップの境界に限りインターリーブした実行が可能というものである。

"トランザクションが並列に実行されている"とみなす範囲を、read/writeステップだけに限定すれば反例2は反例でなくなる。
このようにすれば、モノバージョンにおいては当初の主張"ゼロ知識アボートレス並列スケジューラは存在しない"は成立する。

*1:が簡単な方法で回避できるということでもある

*2:自分がwriteしたものを除いて

*3:CSRに対するVSRの議論のように