ゼロ知識モデルでできなくなること
前回のポストで書いた、アプリケーションに対するゼロ知識がどれくらい強い制限なのかについての補足です。
ちなみに、前回のポストのメインの主張（以下）には反例がありそうでした。こちらは後日まとめたいと思います。
アプリケーションプログラムに対する知識（前提）をスケジューラが持たない場合、アプリケーション（複数）が発行する各トランザクションを、直列化可能なスケジュールで並行にかつ常に成功裡に実行・完了させることはできない。
反例とは、アプリケーションに対する知識がゼロであっても、直列化可能で直列化失敗を引き起こさないスケジューリングが、部分的には並行に（インターリーブ）できるという意味です。
概要
アプリケーションに対するゼロ知識を仮定すると何ができなくなるかについて、いくつか例を挙げて補足します。
- スケジューラの判断でトランザクションをリトライできない
- トランザクションはダーティリードできない
- トランザクションのリードセット/ライトセットを事前に知ることができない
- アクセス対象のデータベースアイテムを事前にロックできない
- トランザクション間に隠れた制約がないと仮定できない
- コミット応答済トランザクションの前に新しいトランザクションを追加することができない
用語
（トランザクションの）ユーザアボート、システムアボート
アプリケーション（クライアント、ユーザ）による、自発的なアボートを ユーザアボート（user abort） と呼びます。
同様に、スケジューラの判断による（ここでは直列化失敗の検出による）アボートを システムアボート（system abort） と呼びます。
（トランザクションの）ユーザリトライ、システムリトライ
アプリケーション（クライアント、ユーザ）による、自発的なアボートとそれに続くトランザクションのリトライを、トランザクションの ユーザリトライ（user retry） と呼びます。
これに対しスケジューラの判断によるアボートとそれに続くトランザクションのリトライを、トランザクションの システムリトライ（system retry） と呼びます。
システムリトライは、アプリケーションからは観測できません（実装によって観測できても良いが、観測できることを期待してはいけない）。
読込み専用トランザクション、書き込み専用トランザクション
トランザクションを構成するデータベースステップの（commitを除く）アクションが read だけの場合、そのトランザクションを 読込み専用トランザクション（read-only transaction） と呼びます。
同様に、トランザクションを構成するデータベースステップのアクションが write だけの場合、そのトランザクションを 書込み専用トランザクション（write-only transaction） と呼びます。
ダーティリード
コミットされていないトランザクションによって write されたデータベースアイテムの値を read することを ダーティリード（dirty read）と呼びます。
（トランザクションの）リードセット、ライトセット
トランザクションに含まれるデータベースステップによって read されるデータベースアイテムの集合を、そのトランザクションの リードセット（read set） と呼びます。
同様に、トランザクションに含まれるデータベースステップによって write されるデータベースアイテムの集合を、そのトランザクションの ライトセット（write set） と呼びます。
（トランザクション間の）隠れた制約
例えばトランザクションの間に、スケジューラが関与しない形で事前に順序が決められていたり、あるトランザクションの結果がデータベースの外部で別のトランザクションへ影響を及ぼしているような場合、それらのトランザクションの間には、直列化可能なスケジューリングに対する制約が存在することになります。このような制約を、トランザクション間の隠れた制約（hidden restriction）と呼びます*1。
直列化順序
直列化可能なスケジュールにおいては、等価なものとして参照されるある直列スケジュールが存在します。 その直列スケジュールにおいて定義される、トランザクション間の順序を 直列化順序（serialization order） と呼びます。
1. スケジューラの判断でトランザクションをリトライできない
アプリケーションに対するゼロ知識を仮定すると、スケジューラがスケジューラの判断でリトライできなくなる（システムリトライできなくなる）ことを示します。
トランザクションがリトライ可能であるためには、トランザクションの実行に必要なすべての情報をスケジューラが持っている必要があります。
一方スケジューラに与えられる情報は、トランザクション、つまりデータベースステップのシーケンスのみです。これには、アクセスする対象を識別する情報とアクションの種類、そしてアクションに対する引数（writeアクションであれば書込む値）のみです。
リトライすることによってトランザクションが read する値が変わる可能性がありますが、その変わった値をもとに次にどんな値を write すればいいか、という情報（計算方法、関数）は、ゼロ知識モデルではスケジューラの知るところではありません。そのため、スケジューラはトランザクションをシステムリトライできません。
書き込み専用トランザクション
トランザクションが書込み専用だとします。トランザクション間に隠れた制約がないという前提があれば、書込み専用トランザクションが write する値はリトライしても変わらない定数であると解釈できます。つまりリトライ可能になりますが、後述するようにゼロ知識モデルを仮定すると、トランザクション間の隠れた制約の可能性を排除できません。
読込み専用トランザクション
同様にトランザクションが読取り専用だとします。トランザクション間に隠れた制約がないという前提を置くと、読込み専用トランザクションが read した値は何の効果も及ぼさないと解釈できます。そのためリトライ可能、もしくはそもそもそのトランザクションの実行を nop に代えることも可能です。しかし同様にゼロ知識モデルを仮定すると、トランザクション間の隠れた制約を排除できないため、read を実行する必要があります。
トランザクションのリトライによって read する値が変わる可能性がありますが、その内容によっては、続く read ステップがアクセスするデータベースアイテムが変わったり、または write ステップが発生する可能性があります（トランザクションを発行するアプリケーションに条件分岐がある場合*2）。
よって、やはりスケジューラが知り得ている情報だけで読込み専用トランザクションをリトライすることはできません。
2. トランザクションはダーティリードできない
アプリケーションに対するゼロ知識を仮定した場合、トランザクションによるダーティリードを許すと、アボートせざるを得ない状況が発生することを示します。
直列化可能な観点において直列化失敗することがないと確認できるトランザクションがあったと仮定します。この場合スケジューラは、このトランザクションが write した値（未コミット）を別のトランザクションに先行して read させる戦略をとることができます。
一方で、アプリケーションに対するゼロ知識を仮定すると、ユーザアボートの可能性を排除できません。
ユーザアボートが発生した場合、ダーティリードしたトランザクションは存在しないトランザクションの結果を read したことになる、つまり等価な直列スケジュールが存在しない状況になり、結果、直列化失敗によるシステムアボートが発生します。
3. トランザクションのリードセット/ライトセットを事前に知ることができない
アプリケーションに対するゼロ知識を仮定すると、トランザクションのリードセット/ライトセットを事前に知ることができなくなります。
ゼロ知識を仮定しているので、リードセット/ライトセットの情報は与えられないと考えます。
トランザクションの実行をシミュレートしてリードセット/ライトセットの情報を取得するという方法が考えられますが、これが可能なのはトランザクションがシステムリトライ可能な場合のみです。
前述のようにゼロ知識モデルではシステムリトライはできないため、リードセット/ライトセットの情報を得ることはできません。
4. アクセス対象のデータベースアイテムを事前にロックできない
リードセット/ライトセットの情報を事前に得ることができないため、アクセス対象のデータベースアイテムをすべて事前にロックし、安全に操作できる状況を作り出すことができません。
具体的には、リードセット/ライトセットが分からない状況下では、都度発生しうる新たなデータベースアイテムをロックしていくやり方となり、デッドロックの可能性を排除できません。
5. トランザクション間に隠れた制約がないと仮定できない
アプリケーションに対するゼロ知識モデルを仮定すると、コミット応答済トランザクションとそれ以降に開始されるトランザクションの間に、隠れた制約があると判断せざるを得ないことを示します。
実用上はトランザクションの間に隠れた制約が存在することがあります。これは、実世界において読込み専用トランザクションが意味を持って存在していることからも明らかです。
隠れた制約の存在について
トランザクション間に隠れた制約がないとすると、読込み専用トランザクションが read した値は、他のトランザクションに影響を与えていないことになります。前述のように nop に置換えても問題ない、という解釈になります。
一方で、読込み専用トランザクションが意味を持って存在しているという事実は、読込み専用トランザクションが read した値が、そのトランザクションの外側に影響を与えているという証拠と考えることができます。
トランザクションの外側に影響を与えているイコール、別のトランザクションに影響を与えているということにはなりませんが、別のトランザクションに影響を与えている可能性を排除することはできません。
隠れた制約の成立条件
アプリケーションに対するゼロ知識モデルを仮定すると、ある2つのトランザクションの間に隠れた制約が存在するかを判断することができません。
そのため、可能なトランザクションのすべての組について、隠れた制約が存在すると仮定する必要があります。
隠れた制約を仮定する必要がある条件は、
としたとき、
が成立つすべてのトランザクションA,Bの組合せ
です*3。
条件の説明
この条件は、以下のように解釈に基づいています。
- あるトランザクション（A）が外部に影響を及ぼすのは、そのトランザクションのコミットが確定した後以降のみである
- あるトランザクション（B）が外部から影響を受けるのは、そのトランザクションが開始する以前のみである
これは、以下の可能性を排除していることになります。
- あるトランザクション（A）のコミットが確定する前に、例えば read した情報が他のトランザクションに影響を与えている
- あるトランザクション（B）が開始した以降に、他のトランザクションの結果をそのトランザクションに反映させる
これらを排除してよいとする根拠は、この2つの振る舞いはどちらも、アプリケーションが自らトランザクションの分離（isolation）を破っているためです。
一方、これらの可能性を考慮することにすると、これらのトランザクションは本質的に直列化可能ではないため、スケジューラはインターリーブするトランザクションがあれば、最初の1つを残して残りをすべてアボートする必要があります。並行性はゼロです。
6. コミット応答済トランザクションの前に新しいトランザクションを追加することができない
アプリケーションに対するゼロ知識モデルを仮定すると、直列化順序においてコミット応答を返したトランザクションの前に別のトランザクションを追加できなくなることを示します。
前述のように、条件を満たす2つのトランザクションの間には隠れた制約があるとみなす必要があります。
そのためスケジューラは、コミット応答を返したトランザクション（A）より（直列化順序における）前に、それ以降に開始した別のトランザクション（B）を位置づけることができません。
つまり、コミット応答を返した時点で、これまでコミット応答を返したトランザクション集合の順序は決定されていて変更できず、かつ続いて開始されるトランザクションは、それらの後にしか位置付けられないということです*4。
まとめなど
通常、可能であると思われているるもので、ゼロ知識モデルにおいては不可能になるものをいくつか集めてみました。
これを読むと、アプリケーションに対するゼロ知識を仮定することが、かなり強い（強すぎる）制限だと思うのではないかと想像します。
実世界では、ここで不可能だとする理由を、アプリケーションによる宣言やインターフェイスの制限などによって回避していることがあると思います。
6の隠れた制約がないとは言えない、というのは、実際には（スケジューラにとって）強すぎる制限です。
コミット時刻＜開始時刻となるほとんどのトランザクションの組合せには、通常は隠れた制約はないはずです*5。
トランザクション間に隠れた制約があること、および隠れた制約がないことを宣言する方法があり、アプリケーションがそれを適切に運用することが可能であれば、これらの制限を回避することが可能です。
一貫性のモデルで、同一セッション上だけで順序関係を保証する、といったものはそれを実現していると思います。
一方で、linealizability or external consistency を提供するシステムは、コミット時刻＜開始時刻の順序関係の制約を守っているといえます。linealizability等を実現するためのコストを無視するなら、アプリケーションにとっては分かりやすい、簡単なモデルです。
前回のポストで参照した書籍（The Theory of Database Concurrency Control）においては、トランザクション間に隠れた制約はない、としていました。
もしそのような制約があるならば、制約があるトランザクション同士を1つのトランザクションにまとめることができる、というのがその根拠です。
ゼロ知識原理主義的な考え方に基づくと、前述のように、条件を満たすトランザクション間に隠れた制約があることを否定できません。
この場合トランザクション間に隠れた制約が存在しないようにトランザクションを統合していくと、最終的にすべてのトランザクションは1つになり、並行性が失われます*6。
統合によって隠れた制約をなくしていくアプローチには次の欠点もあります。
通常トランザクションには、アトミックとしてほしい一連の操作の単位として、および他のトランザクションとの分離の単位としての役割が期待されていると思いますが、統合するアプローチはこれに加え、順序をコントロールする役割を担わせようとします。
順序をコントロールするために統合することによって、本来はアトミックとする必要のない操作群をアトミックにする必要が生じます。分離についても同様です。
よって、トランザクション間の隠れた制約の存在を前提としつつ、必要であればその制約がないことをシステムに伝える方法を用意することが、実用上、有用であると考えます*7。
*1:papa本より
*2:つまりスケジューラが観測したのは結果的に読込み専用だったに過ぎないトランザクション
*3:分散環境において、コミット応答を返したノードと開始を受け付けたノードが異なる場合にどういう条件になるかは検討していません
*4:厳密には、インターリーブしたトランザクションC,Dの直列化順序における関係がC<Dだった場合に、コミット応答の時刻がC>Dとなることがあり得ます。この場合、Dの応答が返った後、Cの応答が返ることによりCがDの前に割込むように見えますが、ここではこれも含めて順序が決定されていると考えます。気になる場合はコミット応答の時刻を直列化順序と一致させる必要があります。
*5:これらに制約があると仮定するのは、バタフライエフェクトを考えているようなもの
*6:ずっと実行中なトランザクションがいればそれらは統合されないかも
*7:実際のシステムはすでにそうなってると思いますが
