Serial Safety Net 再考

SSN
Serial Safty Net
原論文は以下
https://pdfs.semanticscholar.org/ecf9/821e0c4f1f28fb7eb42c5eaa8a92cf16ade9.pdf

Txのserializabilityを判断する、いわゆるcertifierになる。実際はDBのTx処理のvalidatorの実装として組み込まれることが通常だと思う。ERMIA(
http://www.cs.sfu.ca/~tzwang/ermia.pdf
)ではそうなっている。想定としては下位レイヤーにSI(Snapshot Isolation)またはRC(Read Committed)な実装を想定している。

原理はTxのdependencyをトラックして、コミット時点でvalidationを行い、dependency cycleが発生する可能性が高いかどうか判断する。リードが大半を占めるようなケースでも、過剰なトラッキングを行わないため、いろいろなワークロードでパフォーマンスを劣化せずにserializablityのテストが可能になる。

個人的な観点としては・・・現状のMVCC/OCCの現状の最大のボトルネックはabortの高さだ。パフォーマンスを落とさずに、このabort率をどう低減させるのかが最大の課題だ。個人的にはCicadaのようなpre-validationが有効だと思っている。その意味ではSSNのようなものをpre-validationに利用することが効果が高いのではと思っている。

ざっくりまず理解にするに当たってのガイドラインを書いておく。念のために断っておくが論文自体はものすごく丁寧にかかれて詳細まで検討されている。が、その分「暗黙の理解」が省かれているので、なんとなくわかった感じで読み進めると、なにがなんだかさっぱり君になる難解さを持っている。

尚、近年のTxはOCCとMVCCまたはその中間的な議論が多く、SSNはそのなかでは若干異色の存在になっているように見える。ただし、この仕組みは理論的な実りが多く、今後のMVCCを見て行くにはさまざまヒントがあちこちに見て取れる。今後専門的にDBに関わる人間であれば、内容の理解を強く勧める。2016/2017年で間違いなくTx理論では、トップエンドの内容だと思うので、普通の人は特にわからなくともいいと思う。

■ガイドライン的な

1. commit orderと dependency orderが正順（P.Bernstein流に言うと「左から右に一直線に」）になっている場合はdependency graphは循環しない。よってserializableになりうる。というか
「serializableではない可能性がない」（←これ大事）

2. すなわち「serializableではない可能性がある」のは、少なくともgraphのひとつは「commit orderと dependency orderが逆順である」ことである。すなわちdependency orderとは逆順の commit orderが存在する必要がある。これが可能なのはr-wのdependencyにおいて、そのコミット順が逆であること、すなわちリードしている最中に別の書き込みのコミットが先にあった場合「だけ」になる。

2-1 w-rにしろw-wにしろ、先行がwの場合は先コミットが先行のwでなければならない。ここはmulitiversionが暗黙の前提になっていて、w-rが逆コミット順（逆順）だとrは別のversionを読む羽目になるし、w-wの場合はそもそも順序が逆になるだけになる。つまり、commit orderに正順のdependency orderをつくることになってしまう（というか勝手にできる）。かつ、r-wが逆順の場合はそもそも2.のケースになる。r-wが正順の場合は、循環もへったりくりもないのは自明だ。つまり、「serializableではない可能性がある」ことになるのは2の場合だけだ、という結論になる

2-1-1 w-rのコミット順については、表面上はw1r2c2c1が可能であるが、これはRCを満たさないのでアウト。一般にはcommit dependencyの形をとることが多い。理屈ではdirty readの防止ということになるが、理論上はリカバリーのコンテクストで要件とされることが多い。一見、正常系のserializableの理論では現れない黙示の制約になることが多い。留意が必要。

3.ただし、2があったからといって、それが「serializableではない」かというとそうではなくて、循環する可能性があるだけであり、それだけでは広すぎて偽陽性になる（これがMVTO）。なので、もう少し狭める条件があるはずだ、ということでSSNが以下を提案している。

4.validationするTxについて、そのr-wエッジの先端のTxのコミットタイムをπ（T）とし、通常のdependecyエッジの先端のTxのコミットタイムをη（T）とすると、Txのdependencyで先行するTxのUについて、　π(T) < c(U) < η(T)であれば、「よりserializableではない可能性がある（＝循環グラフをつくることができる）」条件を絞ることができる、という理屈だ。これがSSNになる。

3-1.　ということで3を見ただけでも、SSNがMVTOよりもスケジューリングパワーが広いことがわかる。ただし、下位のCCスキームが刎ねてしまえば、元の木阿弥でなんの意味もない。

○概説
以下、論文に沿ってSNNを概説していく。手元に論文があることが望ましい。

■大枠
一応前提らしきものを提示しておく
・SIまたはRC(Read committed)レベルのconcurrency controlがあること。
・SSNはdependencyをトラッキングしてコミット可能かどうか判断する。ただし偽陽性がある。
・2PLやSSIよりもRC＋SSNやRCL（RC w/lock-base）+SSNの方がconcurrencyが高い。
・既存のディスクベースでも可能ではあるが、一応multi-versionのメモリーベースの実装を想定している
・global なユニークなtimestamp。できればcentralizedがいいが、centralから一括で割り当てられたものをローカルで振り当ててもよい。

一応特徴としては・・・
・下位のRCLやRCLの実装バグからフリー
・phantomも除去可能
・read mostlyで重い処理でも、別段read setの中の最近更新されていないレコードをトラッキングする必要がない
等々
・低い競合状態でもCCの邪魔はしないし、高い競合（write-intensiveでもread-onlyでも）パフォーマンスを劣化させない。

□SSNは主に以下のふたつのパーツで構成されている
・π(T)の計算
通常Tのあとにserialization orderが来るべきだが、Tの前にコミットされてしまうdangerousなtxの最小基準値（ts）をさす。SSNでは low watermarkと表現している。

・validation test
あるTをコミットするとき(c(T))に、(本来はTの後にコミットされるべきだった)Uがすでにコミットされており、Tとconflictを持っているとすると、π(T)<=c(U)

  • T read a version Ti created (Ti ←w:r T)
  • T overwrote a version Ti created (Ti ←w:w T)
  • T must be serialized after Ti

普通の依存関係、書いたものを上書きするか、書いたものを読む。
Serialization orderはTi -> T

2. T ←r:w Tj (read anti-dependency)

  • T read a version Tj overwrote
  • T must be serialized before Tj

Anti-dependency：読まれているversionを上書きする。
Serialization orderは T -> Tj

Notation
T ← U : serial dependency
T ←w:x U or T ←r:w U 表記として TはUのdirect predecessor UはTのdirect successorとする。通常の教科書的な表記と向きが逆になっていることに注意。

この依存関係でグラフ(G)を形成する。
GにおいてTi < TjというときにはTiはTjの前にorderされている。すなわち　Ti ←…← Tjが成立している。
このとき、TiはTjのpredecessor で、TjはTiの successorになる。
それで、Ti < Tj < Tiになったときに、serialization failureになる。

Failureの最も単純な類型は以下の三つになる
T1 ←w:x T2 ←w:x T1 : T1とT2がお互いのwriteを読む（あるいは書く）
T1 ←w:x T2 ←r:w T1 : T1はT2のwriteを読んでいるが読んでる端からT2が書いてる
(T1 ←r:w T2 ←w:x T1は単に順番の入れ替え)
T1 ←r:w T2 ←r:w T1 : お互いに読んで書いているものが循環している(write skew)

Tがpre-commitに入った時刻をC(T)とする。コミットタイムで全順序で、グラフGについて、
predecessorが先にコミットした場合はforward edge
successorが先にコミットした場合はbackward edge
とする。
ややこしいのですが、要はdependency orderとコミットorderは違うものですよ、ということです。

forward edgeの時は、T ←w:x or r:w Tでどのタイプでもよい T ←f T
(コミットされたものでなければ読めないし、書けない)
backward edgeの時は、必ずT ←r:w Tのanti-dependency　T ←b T
(コミットされたものを読むわけではない)

forward / backward edgeは簡略ができて
T ←f T ←f T ….. ←f T ←f T であれば T ←f* T
T ←b T ←b T ….. ←b T ←b T であれば T ←b* T

(論文ではこのあと引き続きRC/RCL/SI/SSIを説明するが、既知でいいと思うので省略)

以上で道具立て。

■SSN:
Serial Safety Net

Dependency graphにおいて潜在的な循環をつくるようなコミットを防止する。
前提ではあるがRCが保証されていることが下位レイヤーに要求される。

・Preventing dependency cycles
SSNはC(T)に加えて、π(T) η(T)を利用する。

π(T)：Tの、backwardなエッジをたどって到達できる最も古いsuccessorのU、そのUのコミットタイムをπ(T)とする。

すなわち
π(T) = min(c(U) : T ←b* U)

これを再帰的に適用することができるので
π(T) = min( (π(U) : T←b U) ∪ c(T) )

したがって、π(T)を求めるにはdirect successorだけを見ればよくて、いちいち再計算する必要はない。

留意点はπ(T) < c(T)であり、Tのコミットが決まった段階で、c(T)が決まりπ(T)も決定する。πは変更されない、なんとなればTはコミットされるので、そのsuccessorはforward エッジしか発生しないから。

DEFINITION 1. A dependency edge U ← T in G (or alternatively, transaction U) violates the exclusion window of T if π(T) <= c(U) < c(T).
すなわち、SSNは、Tがコミットする場合にdirect predecessor Uのexclusion windowから外れた場合はコミットさせない

不等号条件は、先にコミットされるTのpredecessorのUがTのsuccessorになる可能性の排除になる。（排除しないと循環）。実装上は、処理を簡潔にするために二つの手法を使う

1. T以前にコミットされたpredecessorのみを対象とする、というのはTのpre-commitの最中にチェックが完了するから。
2. T以前にコミットされたpredecessorのうちで最新のもののみ見ればよい。これはη(T)を使い、π(T) <=η(T)であれば、Tをabortする。すなわち

η(T) = max (c(U):U←f T)∪(-∞))

以下、順番に論文のFigを解説する。図は縦軸がcommit order（すなわち時間軸）で横軸がdependency order（すなわち理論上の依存順序）を表している。普通はtが横軸で、dependency orderは正順での依存記述になるので、いろいろ逆向きに書いてあるが、要は基準となるwatermarkをhorizontalに表現したかったのではないかと思う。これはこれでまぁ慣れればわかりやすい（というか慣れればなんでもわかりやすい）ので、いいかなとは思うが。


forward edgeが下向きになる。コミット順。T5 ← T1
backward edgeは上向きになる。dependencyがあとのものが先にコミット。 T4 ← T3
T1がT2のexclusion windowに違反している。

チェック対象はT2 (T5, T4, T1, T3 と来て次がT2 : commit order)
1よりT2のpredecessorであるT1を対象
π(T2)はc(T5)で　η(T2)はc(T1)　になる。π（T2）＝c(T5) < c(T1) = η(T2)
より、π（T2）< η(T2) よってT2はabort

イメージ的にはr-w r-w・・・r-wのdependencyで最後のwが最初のコミットになっていたとして（C(T5)）、最初のr-wのrが読んでいるTxが、C(T5)すなわち最後のwを書いているものよりも、後にコミットしているとそれを読んでいる（または上書き）可能性があると、コミットのチェーンが循環する可能性があるので、まずい、ということになる。


T2については、それ自身の情報のみで判断できる。T1のpredecessorを知らなくてもよくて、単純にT1がsuccessorになるかも知れないということが想定できればよい。


これは問題のないケース。π(Tx)より先にT3がコミットされている。よってTxのsuccessorになることはできないので、Txで循環をクローズすることはできない。


これは偽陽性。T3は循環が生じる可能性がないが、abortになる。ただし、T1のpredecessorがT4にdependencyをもつとアウトなので危険といれば危険。

・Safe Retry
Tが、Uがexclusion windowに違反するためにabortした場合で、ただちにT’としてretryした場合、T開始前にUはすでにコミットされているので、その場合T’はUが作ったversionをanti-dependencyではなく読むことができる。よって、UはT’のabortの原因にはならない。

この手のsafe retryの属性はもっと注目されるべき。2PLだとdead lockになる可能性（前でdeadlockでabortしたとして、今度はそのdead lock winnerとdead lockになる）もあるし、OCCではread setのvalidationでまたこける（writeのoverwriteが終わっていない場合もありうる）可能性もある。

・Correctness
SSNの正当性の証明

・serial dependency graphが循環しなければserizaliable　(これは前提でよい)
・下位にRCレベルのCCスキームをもつので、lost updateとdirty readは防止できている
・あるスケジューラーがserializableでないスケジュールを生成するとして、そのスケジュールのdependency graphにある、SSNのターゲットになるdangerous edgeを特定し、そのエッジが該当スケジューラーが生成する任意のdependency graphに存在することを証明する。すなわち、あるスケジューラーがserializableでないスケジュールを生成する場合は、必ずdependency graphの中にexclusion windowに違反するエッジが最低一つはある、ことを証明する。（対偶の証明）

証明
あるスケジュールがserializableでないとすると、それは最低でも2以上のTxを含み、かつ循環をもつ。
その循環の最初のTxにおいて最初にコミットされるものTnとする。
すなわち、Tn←T1←T2←...←Tn-1←Tnになる。
このとき、Tnは最初にコミットされているので、T..←Tnのエッジはbackwardになる。
ここで、Tk ←b* Tnになる最小のkを選ぶとすると、π(Tk) <= c(Tn)になる。
さらに、Tkのpredecessor、すなわちTk-1(またはk=1の場合はTn）へはforward エッジになる。
以上により π(Tk) <= c(Tn) <= C(Tk-1) < C(Tk)
よって、常にTkが存在し、Tkのexclusion windowsに違反するpredecessorが存在する。
すなわち、あるスケジューラーがserializableでないスケジュールを生成する場合は、必ずdependency graphの中にexclusion windowに違反するエッジが最低一つはある

  • TkからTnへのdependencyに注意：r-wのbackward edge
  • U←Tにおけるπ(T) <= c(U) < c(T)で見ると、UがTnで、TがTkになる
  • Tnがコミットされていて、次にTkがコミットしようとする、という流れを想定できる

・追加的な議論のポイント
他のCCのスキームとの比較を図で行う


SSNは当然許可。2PLも問題ない。すべてのCCスキームで処理できる。


2PLのみアウト。2PLはbackward edgeが許容されない。SSNでも問題ない。


SSIがしばしば棄却する。通るのはbackward edgeの最後がread onlyでかつ十分に古い（コミットオーダーが、少なくともforward edgeの二番目にTxの更新より前）であるとき。
SSNは通す。


SSIではアウト。backward edgeの終端の前に、forward edgeのTxがコミットしている。


SSIでは問題ない（r-wの段階で先行は全部コミット済み）。SSNも通る。


SSIでは、Tがその前のpredecessorがdependした段階で、r-w/r-wの持ち回りのチェックでアウトになる。SSNでもアウト。これは擬陽性

次は時系列の分析

(a)については、破線を越えた段階でたいていのCCではどれかがabortになる。
（たいていはt1w(A)がt3r(A)で読んでいるものを上書きしているのでアウト）
SIであれば問題ない
(b)はSI下での(a)の図示
(c)は同じくSIだが、T3が先にコミットのケースでSSNではアウト
(d)はRCでのケース

2PLのデッドロックについて
デッドロックの例としては、(a)を書くと・・・
・T1がBをリード
・同時にT1はT2（Bを書きにいく）をブロック
・T2はT3（Bを読む）をブロック
・一方、T1はAの書き込みをブロックしようとして・・・
・T3はAにリードロックをとっている

SIベースだとどうなるかというと、T3のBのリードはT2が書く前versionを読む。よって
・T3 ←b T2　T1も同じなのでT1 ←b T2
・SIの場合は、単一のbackward edgeでabortするので、すくなくとも一つはabort
・SSIの場合は、T3 ←r:w(A) T1 ←r:w(B) T2で、かつT2が先にコミット（Bの書き込み）して、T3がリードオンリー（Bを読む）なので、dangerous structureができてabortする。

一方、SI＋SSNだと、これは(b)のdependency graphになって実行可能
もっともこれは完ぺきではなく、たとえば、T1がT3の後の最後にコミットしようとすると、
π(T1) <= c(T2) < c(T3) < c(T1) になるので、exclusion windowに引っかかってアウト。これは(c)のケースになるが、実際はserializableである。

RC+SSNの場合は、dependencyグラフは(d)になるが、
・T3のリードは、T2のコミット済みのものを読む
・なのでdependency graphはT2 ←f T3
・またT3 ←b(A) T1 ←b(B) T2 よってπ(T3) = c(T2) になる
・T2はT3のpotential successorなので　π(T3)=c(T2)

  • まず前提的に

・multi-versionを前提
・versionとTxの、SSN用のメタデータを格納する必要がある
・single versionのCCのオーバーレイとしてversion管理のためのlock制御が必要になることがあるかもしれない。lock-basedなSSNについてはとりあえず置いておく

必要な空間と計算量は実行中のw/rのフットプリントにほぼ線形で比例し、かつversionごとに追加で一定のスペースが必要。dependencyの管理はtimestamp(以下TS)を利用する。実行中および最新コミットのTxについてのTSはTxのコンテクストに格納されるが、それ以前の古いTxについてのTSはversionの中に保存される。

Tx Tがversion Vをつくるときに　Tx RとTx WがそれぞれVを読む、または　書く（上書き）するとすると、以下が定義できる
c(V) = c(T)
π(V) = π(W)
η(V) = max({ c(R) : T ←f R} ∪ c(T))
これらのversionについてのTSの情報はversionに記録される。なお、dependencyの情報は複数のTxが同時に存在した場合、特にvalidationでかぶったときのみ必要になる。

VersionとTxのメタデータ以下になる

なお、versionのメタデータはversionが有効な間は保持される、またTx自体はTxが完了すれば必要ない。

  • 下位CCレイヤーとの連携

下位レイヤーではTxが読むべきversionを特定する。したがって、SSNのread/writeでは引数として下位CCが返すversionをとる。このversionのスレッド間の同期はCCの責任になる。たとえばSIがCCの場合は、versionトラバースをして最新のversionを返す責任はSI実装側にある。SI実装によっては、未コミットのversionを返すこと（その場合はc(V)にはversionを作成したTxIDを格納することが多い）もあるが、その場合は読んでいるversionをスキップして次をとりに行く。コミットする場合は、versionを生成するTxがTx-IDを実際のTSに書き換える。なので、SSN側では常にコミットされてimmutableなversionを読む。

SSN側のwriteは時にconcurrent writeをハンドルする必要もない。下位のCCが新しいversionの追加できるかどうか、たいていはversion chainのラッチかTxのTSの比較によって、判断する。

成功した場合はCCのwriteのプロトコロとして、v.prevに上書きされたversionへのポインタをセットする。それからTxがSSNのwriteを利用してTSを更新する。下位のCCレイヤーではTx最中の新しいversionを見せないようにすることを保証する必要がある。（例えば生成TxのTx-IDをc(T)に埋め込むとかして）

なお、commitについてはread/writeと違ってTx間で適切な同期処理が必要になる

  • Read


vは下位のCCから取得する。Tx tが読むべきversion vになる。

・tのwriteセットとreadしたvが交差している場合はrepeated readなので処理はしない。(自分で書いたversionを読んでいるだけ)　以下交差していないことが前提。

書かれたversionを読んでいるので、vはコミット済み。そのvについて
・η(t) < v(c) ならばη(t)を更新する。自分のforward edgeが伸びる。w-rの依存になる。
・さらにそのwriteの上書きがある場合とない場合
ない場合はv.successorがないので、π(v) = inf　これはそのままreadセットに追加する。
ある場合はv.successorが存在して、π(v)には値がある。コミット済みのvを読んだ時に、同時にそれに更新をかけているTxがあるということ。すなわちr-wのanti-dependency（自身はr）が起きている。wが先にコミットの場合はπ(v) < π(t) になるのでπ(v)を自身にセットする。自分の backward edgeが伸びる。r-w依存になる。

注意：後続がない場合の普通のr-wで考える。vをrして、同時にvをoverwriteするのみとする。
v.c(T)はセット済み。vのsuccessorはないとすると、v.sstamp = t.cstamp = c(T)がセット済み。overwriteしているtwがコミットする段階で、overwriteするversionが作られて、post-commitで v.prev.sstamp = tw.sstampでセットされる。すなわち、最初の読まれたvのsstampが更新される。

最後にexclusion windowのチェックを行う

  • Write


普通にversion(v)を加えるだけ、pstampは前のものの方が新しければ引き継ぐ。ただし、コミット時点で他のTxへanti-dependencyを引き起こす可能性があるので、そのためにwriteセットを保持する。

  • Commit

commitはpre-commitとpost-commitに分かれる

  • pre-commit

π(T)とη(T)を確定して、コミット可能かexclusion windowのテストをする。以下のステップで処理する
・c(T)の取得
・c(T)確定以降はread/writeは禁止
・π(T)の計算（c(T)の前にoverwriteされているリード対象のVのπ(V)のみ考慮すればよい）
・η(T)の計算
ただしdependencyとしてはreadとoverwriteの二種類になる
overwriteの場合は、他のreadに対してdependencyを発生させることに注意
・π(T) < η(T)のチェック
・問題がなければステータスをcommitに変更

  • post-commit

・versionのc(V)を更新
・π(V)の更新
・η(V)の更新

  • Latch-free parallel commit

上記のpre-commit/post-commitは基本Latchベースになっている。これはin-memory型の仕組みではスケールしない。なので、latch-freeにする
main-memory OLTP systemsが前提。全部のワーキングセットがメモリー上で、Txの処理は単一スレッド内部で完結する。また、メニーコアが基本で中央管理的なロック機構は使わない。

  • Finalizing π

Latchベース

Parallelベース

latchベースだと、v.sstampの取得にロックがかかる。すなわちconcurrentなwriteからのv.sstampのoverwriteが許容されない。ロックフリーの場合は、リードしている最中にconcurrentにどんどんoverwriteされることがある。この場合overwrite側のc(T)は、リード側のc(T)よりも前か後ろのどちらの可能性もある。overwrite側が早い場合は、リード側はsstampを（overwriteした側のsstmapで）更新する。

下位CCがSIの場合、Tx-IDがversionのcstampにセットされないと読み出せない。overwriteの場合は、上書きのversionのinstallが終わった段階で、overwriteしたVのsstampに自分のTx-IDをセットしないといけない。SSNだとpost-commitでのv.prev.sstamp = t.sstampの処理になる。んで結果として、concurrentなリード側は正しいsstampとTx-IDが読める。（先に終わるまでspinして待つ。注意：一種のcommit dependencyの処理だと思う）

尚、シングルスレッドの場合はSSNのコミットプロトコルではTxのステータスは別段concurrentなTxに提供する必要はない。順序実行されるだけなので。
尚、上書きのc(T)がTxのc(T)よりも遅い場合は、ウェイトせずにそのまま実行しておしまい。

  • Finalizing η

Latchベース

Parallelベース

まず基本的な違いは、Tの処理中に、V(T書き込むv)については最大で一つoverwriteがありうるということ。（当たり前だが複数はない、それはoverwriteのoverwrite。）

また、prev.v(書き込む前のversion)を読んでいるreaderは複数で、そのpstampを更新する必要がある。とくに、自身の前にコミットしているもの(r.cstamp < t.cstamp)についてはSSNではreaderトレースの実装としてはarrayではなくbitmapを利用している。(注意：r-wのdependency)

  • 具体例として、三つのスレッドを考える


Thread1 v1を作成してコミット済み
Thread0 はappendしてv2を作成しているが、まだpre-commitに入っていない。
Thread2 v1をリードして、v1.readerの最後から3ビット目のフラグを立てる。
Thread0がコミットしようとする時点で、v1.readerからThread2がリードに入ってることがわかり、
かつ、Thread-Tx mapping tableからv1のcstampもわかる。
尚、versionのreaderからcstampを取得して自身のpstampを更新することができる。このときのbitmapからのThreadIDの取得は実装としては、BSR(Bit Scan Reverse
War on Theism: x86 Instruction Set Reference
)利用している。

上書きをする場合は、前のversionのreaderのpre-commitが終わってcommit tsを取得するまでspin-waitする。それからそのversionのcstampを利用して、自身のpstampを更新する。
尚、bitmapの場合は本当にreaderが存在するかどうかが保証はされないため、concurrentなリードを見に行く必要がある。この場合はηはより大きくなる可能性があるのでその分偽陽性の可能性もあがる。この確認のコストよりもbitmaを利用する方がメリットが大きい。（注意：通常は多分TSでソートしてポインタを張る）

  • Post-commit


π・ηがクローズしたあとは、exclusion testをして必要ならabortする。問題なければpost-commitを行い、
読んでいるversionのpstamp/stampを更新し、新しいversionのための初期化を行う

ちょっと整理：後ろがTになる
r-wでc(r) < c(w) 通常のDependency finalize η(自分が書いているvを読んでいるrを確定)
w-rで c(w) < c(r) 通常のDependency finalize Π(自分の読んでるwに割り込みのwがあるかどうか)　-> なければpost-commitのみ
w-wで c(w) < c(w) 通常のDependency finalize ηでそのまま抜ける　post-commitのみ
r-w で c(w) < c(r) anti-Dependencyの上書きをする側 finalize ηで if ( r.cstamp < t.cstamp)でヒットしないので抜ける

■オーバーヘッドの削減

スケールのさせかたとmultiversionとヘテロワークロードへの対応についての考慮。

SSNはπとηのメタデータのコストがかかる。ほぼTx（readとwrite）の量に比例してかかる。特に、read-onlyやread- mostな場合にリードセットの確認のコストが馬鹿にならない。基本的な最適化の方針は、read-onlyに対するdependency trackingの除去とread-mostlyに対するコールドデータのtrackingの除去になる。

1.既存の利用

まず基本的にどんなMVCCでも、cstamp (c(T))とv.prev(前のversionに対するポインタ)は必ず実装されているので、追加で必要になるのはv.pstampとv.sstampになる。pstampはversionができた時点でセットされ、上書きがされる前にすべてのリーダーにより更新される。上書きがされた時点で更新はできない。一方、sstampは上書きする側のはコミット時点に更新され、そのリーダーは自身のsuccessorのtimestampの更新に利用する。つまり、pstampとsstampは単一のwordに格納することができる。

また各Txはpre-commit終了時点でcommittedと見なせるので、visibleになる。このときリーダーはTのTIDでステータスを取得し、利用可能ではある。

2.Safe snapshots and read-only queries

• Safe snapshots: (Serializable Snapshot Isolation in PostgreSQL)
http://vldb.org/pvldb/vol5/p1850_danrkports_vldb2012.pdf

A read-only transaction T has a safe snapshot if no concurrent read/write transaction has committed with a rw-antidependency out to a transaction that committed before T’s snapshot, or has the possibility to do so

という定義になっている。実装上は単純でsnapshotを作る段階でr-wのTxを全部記録して、そのTxが全部終わったらread-onlyの処理を走らせるという仕組みになっている。現実にはconcurrentとは言いがたいと思うが、一種のバッチ処理的な扱い。

これに対してSSNはより”active”な処理をしている。まずsnapshotの取得は普通にリードのTxと見なす。当然concurrentなwriteについてはanti-dependencyになるので、write側は普通に処理する。snapshotの対象のversionも普通に更新できるが、snapshot前のversionにr-wのanti-dependencyが発生する場合はabortする。ってこれ普通にread-only anomalyの除去でしかない気がするので、何か別に特別なことをやっているわけでもなんでもないと思われる。

注意：要はread-onlyの時のリードのオーバーヘッドが軽減されるか？ということなんだが、一応、We adapt the safe snapshot to free read-only transactions from dependency trackingって書いてあるんだが、そうは読めないので、今度本人に聞いてみる。普通にtrackingしてる気がする。

3.Read-mostly transactions

要は大半はリードだが、ちょこっとだけ更新する場合の処理。SSNではアルゴリズムを見るようにreadセットを全部チェックする必要があるのでコイツが面倒事になる。なので、その負担を減らす。

ポイントのひとつは、この場合の大抵のリードセットはかなり大きく、そのうちconcurrentに更新されるレコードはそれほど多くないということ。（注意：と言っているがそうでもない。単純にリアルタイム集計を考えればわかるがガンガン更新はかかる。ガンガン更新がかかるからリアルタイム更新の存在意味があるわけで。更新があまりないなら適当なタイミングでの定期バッチでも業務的には十分。）そこで、まず、最近上書きされていないversionはstaleと見なす（thresholdあり）。それでread trackingを行わない。こういう戦術をとる。

この場合問題点は二つで、

1. readがトラッキングしないので、write側は最新のpredecessorのステータス、pstampがわからない。
2.read側からはconcurrentなwriteがわからなくなる。また、これはreadのsuccessorがserializableにならない可能性を残したままreadのコミットができることになる。

ここでRead-mostlyはあくまで一つのスレッドで処理される、という点を利用する。各versionにstampすることなくコミットできるようにする。その代わりにスレッドそれ自体にcstampを記録させる。（図のtransaction tabaleのlast cstampを利用する）

・・・自分自身のThreadに自分のcstampを記録する。がvの値は更新しない。→結果πは大きくなる→偽陽性になる

1.　T（thread t1）がtrackingなしでVを読む
2.　Tはv.readersのビットフラグをセットしてt1のlast cstampを更新してコミットする。このときにビットフラグはリセットしない
3.　Tが「コミットした後で」U(thread t2)がVをoverwriteする
4.　このときすでにthread1は別のTx Rを走らせているとし、かつRのフットプリントはTまたはRに重ならないとする
5.　Uはpre-commitの時点でv.readerをチェックしてRを見つけて、abortする可能性がある。これはもちろん擬陽性になる。

このあたりはパフォーマンスと偽陽性判定によるabortペナルティーとの完全なトレードオフに見える。現実的には選択実装の形にした方がよいと思う。このスタイルの利用はおそらく応用性が高い。個人的にはSSNの中ではもっとも「なるほど」と思ったところではある。とはいえ、実際どのくらいの効果があるかは、アプリケーションとより具体的なワークロードに依存する。

■ロックとphantom除去について

SSNでは階層ロックとロックエスカレーション、これに加えてキーとpredicate lockを利用した方式が親和性が高い。

dependency trackについては階層ロックの仕組みを利用する。
readの場合：tableの大部分を読むような場合は、R-lockをとってtableのpstampを更新する。
writeの場合：tableについてIW-lockをとり、個別レコードでW-lockをとる。v.sstampを更新するだけだが、tableとversionの両者のpstampを確認してconflictを検出する。

  • Predicates and phantoms

Phantomの検出については、scanの場合はとにかくtableをみてR-lockとIW-lockがconflictしていないかどうか確認して検出する。
あとはgap-lockをSSNに利用する方法もある。この場合は、キーのレンジとgapのペアをどう処理するかによる。キーとgapのペアごとでconflictの検出に利用する。

まぁざっくりこんな感じ。あとはsimulationの話とパフォーマンスの実測の話になっている。
SSNの大枠の理解（理論とアルゴリズム）はこんな感じいいと思う。

本人も言っていたが、やはりCCの下回りの実装がポイントなることがあるようだ。どちらかというとcertifierというよりも、実装として組み込んでしっかりしたDBとしてintegrateした方が、パフォーマンスもでると思う。考え方と実装のヒントはこんな感じなので、これをどう扱って行くかが、今後のポイントになると思う。

そんな感じ。

一発go throughして簡単にわかる内容ではないので、折に触れて読み返すといいと思う。自分もそのつもり。
特に実装部分についてのParallelな処理は、今後いろいろ参考になると思う。