SSI論文のメモ

Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道

で紹介されている2つの論文を読んだのでメモ。

Making Snapshot Isolation Serializable 

Alan Feketeの論文。

 

okachimachiorzさんが詳しく書いているので引っ掛かったところだけメモ。

 

用語について

• Predicate Read
  名前（Identifier）によって特定された対象に対するReadではなくて、比較演算等の述語が真かどうかを評価、選択してReadする操作を特別にPredicate Readと呼んでいる。
  こちらが普通だと思っていた。通常はIndexによって一本釣りできることが前提になるから述語の評価による選択に敢えて名前がついているのかな。
• First Commiter Winルール
  同じ対象をWrite使用とするとき最初にCommitしたトランザクションが有効になるルール。First Updater Winルールも出てくる。
• Write Skew
  Anomalyの1つ。Snapshot Isolationで除去できない。2つのrw-dependencyによって起こる。
• Lost Update
  Anomalyのひとつ。メジャなやつ。
• Phantom Read
  Anomalyのひとつ。ANSIにも出てくる。PostgreSQLの実装が頭にあるとNon-repeatable Readとの違いがわからなくて困った。

 

Typo/誤り

• Example 2.1
  H1:W1(X1) W1(Y1) W1(Z1) C1 W3(X3) R2(X1) W2(Y2) C2 R3(Y1) C3
  
  上記のヒストリはSerializableである（T1→T2→T3の順）と書いてあるが、Serializableではない。T2⇒T3のrw-dependencyとT3⇒T2のrw-dependencyが存在し、サイクルになってしまう。
  この例のままではアイテムZが出てくる意味がないので、正しくは恐らく以下のヒストリ。
  
  H1:W1(X1) W1(Y1) W1(Z1) C1 W3(X3) R2(X1) W2(Y2) C2 R3(Z1) C3
  
  ざっと検索したところ、以下の論文で上記とほぼ同じ例がZ1に変えて載っていたので誤りでよいと思う。
  

 

Nonserializable executionを引き起こすためには依存関係のサイクルが必要だが、サイクルに2つの連続したrw-dependencyが必要、の直感的な解釈

• 依存関係でサイクルを作るためには、どこかで時間を逆行するような依存関係が必要
• Snapshot Isolation下では、トランザクションbegin時のバージョンをRead/Writeするので、Read/Writeが起こった時刻より前のバージョン（時刻）に対して依存関係の時刻の起点がある。Snapshot Isolationに潜在的に時間の逆行がある。
• ただしWriteが有効になるのはトランザクションのcommit時なので、Writeを起点とする依存関係はWriteの後にしか起こらない（逆行しない）。
• よって時間を逆行するのはReadを起点とする依存関係でそれは、Read-Write dependencyのみ。
• 1つのrw-dependencyを含みサイクルを作ろうとすると、もう1つの依存関係が必要だが、時刻の関係から、この依存関係に関わるトランザクションはconcurrentであることがわかる。
• Concurrentなトランザクション間の依存関係はrw-dependencyにしかならないので、結果的に2つのrw-dependencyがいることになる。

 

 

 

Serializable Isolation for Snapshot Databases

Michael Cahillの論文

 

内容について

• Non-serializable executionの検出をDBMSの内部でやろうとする話。
• ただし依存関係のサイクルの完全な検出ではなく、連続した2つのrw-dependencyを検出する（そしていずれかのトランザクションをabortする）ことでnon-serializable executionを排除する。
• そのため、偽陽性（False Positive）、サイクルになってないのにabortすることがある。
• それを改善したアルゴリズムを提示されている。
• 2つの方法でrw-dependencyを検出している。
• 2つある理由は、rw-dependencyを構成するRead,Write処理が、1）ReadがWriteに先行する（ReadしたVersionã‚’Writeする）場合と、2）ReadがWriteの後に起こる（ReadするVersionã‚’Writeする）場合があるため。
• Read先行に対しては、Rowロックに新たなロックモードSIREADを追加する方法をとる。
• ロックモードであるがSIREADは他のどのロックモードとも競合しない。
• SIREADとEXCLUSIVEが同じRowに対して為されたことは、rw-dependencyの存在を表す。
• Write先行に対しては、Read時に、ReadしたVersionより新しいVersionが存在するかどうかをチェックすることで行う。
• 基本的なアルゴリズムは上記の通りだが、このままではPhantomに伴うrw-dependencyが検出できない。
• InnoDBに対するプロトタイプ実装では、InnoDBに（Phantom Read対策のために？）実装済である、gapロック、next-keyロックに、同様にSIREADロックモードを追加することで行う。

Typo/誤り

• Fig 2.3(a)
  TinとTpivotの生存区間がオーバラップしていないように描かれている（concurrentになっていない）ので、rw-dependencyが存在しなくなってしまう。
  正しくは、b_in < c_pivot となるように描かれるべき。

 

PostgreSQLについて思ったこと（論文には書いていない話）

• MVCC実装はタイムスタンプベース（そのバージョンを作成/削除したトランザクションID）で行っているので、Phantom Readの除去とNon-repeatable Readの除去は同じ仕組みで行われている（と思っている）。
• なので、PostgreSQLにはgapロック、next-keyロックは（SSI以前は）なかった、と想像される。
• Serializable Snapshot Isolationの実装にともなってgapロックが実装されたのだろうか。。？
• （PostgreSQLのSSI論文見ればきっと書いてある。）