"A critique of ANSI SQL isolation levels"(http://dl.acm.org/citation.cfm?id=223785)を読んだ。 1995年にMSの人とJim GrayでANSI SQL-92を批判する論文で、いろいろなところで解説記事等を見かける。
もう20年以上の前の論文だけど、最近はてなのid:alpicolaさんがこの論文の紹介を書いている。
また、この論文を直接紹介しているわけではないけど、id:kumagiさんが書いているブログもこの論文と同じ内容をわかりやすく解説している。
さらにid:okachimachiorzさんがhttp://d.hatena.ne.jp/okachimachiorz/20121028/1351390461とhttps://www.slideshare.net/okachimachi/a-critique-of-ansi-sql-isolation-levelsで詳細に解説していて、発表スライドの方は関連部分だけに絞っているらしいが69ページもある。もはや論文の実際の発表より詳しい発表をしたんじゃないだろうか。
正直上記を読めば良いので、この記事を読む理由はないが、読んだメモをまとめるついでに公開しておく。
Abstract
ANSI SQL(92)では,ダーティリード・リピータブルリード、ファントムリードといった現象で、分離レベルを定義しているが、これはいくつかの有名な分離レベルを取りこぼしている。 その曖昧性を明確にし、より明確な分離レベルを定義する。また、mutiversionによる新しい分離レベルであるSnapshot Isolationを紹介する
Introduction
ANSI/ISO SQL-92では4つの分離レベルとSerializableな状態を壊す現象(phenomena)を定義している。
- isolation levels
- READ UNCOMMITTED
- READ COMMITTED
- REPEATABLE READ
- SERIALIZABLE
- phenomena(anomalies)
- Dirty Read
- Non-repeatable Read
- Phantom
分離レベルはロックスケジューラーの振る舞いに影響するが、いくつかのロックスケジューラーはロックのスコープや期間を変更することができるので、単純な2 Phase Lockから議論を始める。このアイディアはlocking, data-flow graphs, anomaliesの３つの方法から"Degrees of Consistency"を定義している[GLPT]で導入されたものである。
この論文では、anomalyによって分離レベルを定義しようとするアプローチの欠点を示す。 ANSI phenomenaは曖昧で、広義の解釈(broadest interpretations)をしても異常を起こす振る舞いを完全に排除できない。 さらに、ANSIによるphenomenaでは、コマーシャルシステムでは有名ないくつかの現象を区別出来ない。
2章では基本的な分離レベルの用語を紹介する。3章ではANSI分離レベルの欠点と、新しいphenomenonを紹介する。4章ではANSI SQLのphenomenaを回避するmultiversion concurrency control(MVCC)のメカニズムを紹介する。これはSnapshot Isolationと呼ばれ、完全なSerializableではない。
5章では3, 4章で紹介した分離レベルを区別する新しいanomaliesを紹介する。しかし、これらでもSnapshot isolationとCursor Stabilityを説明するのには完全ではない。
6章で、現状でのまとめと結論を述べる。
Terms
- transaction: データベースをある状態から別の状態に移す動作の集合
- history: トランザクションのセットのinterleavedな実行をそれらのアクション(read, write...)の線形な並びとしてモデル化したもの
- conflict: history中の2つの独立なトランザクションが、同じデータに対して動作を行い、さらに少なくとも一方がwriteを含んでいる状況
- dependency graph: トランザクションによる実行をノードとして、状態の変化をグラフで表現したもの。2つのトランザクションの実行によってできる dependency graphが同じであれば、それらの実行手順はequivalentであり、トランザクションを直列に実行したserial historyとequivalentなhistoryはserializableである。
ANSI SQL Isolation levels
言語による定義(English language statement)
- P1 (Dirty Read)
- P2 (Non-repeatable or Fuzzy Read)
- T1があるデータを読みだし、その後そのデータをT2が変更したり削除すること。もしT1が再度同じ値を読みだそうとした場合、最初と異なる値を読み出すことになる。
- P3 (Phantom)
- T1がある検索条件を満たすデータのセットを読みだす。その後T2がこの条件を満たすデータを挿入すること。T1が再度同じ条件のデータを読みだした場合、新しいレコードが見つかる。
Shorthand notation
言語による定義は曖昧で、起こりうるanomalyとそれを引き起こしうるphenomenaを説明しきていない。 そこで、phenomenaをPx, anomalyをAxとしてこれらを別々に定義する。 ここで、トランザクション1:T1のデータxに対する書き込みをw1[w], T2のyに対するreadをr2[y]のように表記し、phenomena, anomalyを表現する。 (commit: c, abort: a, ある検索条件を満たすデータセット:P)
- P1: w1[x]...r2[x]...( (c1 or a1) and (c2 or a2))
- A1: w1[x]...r2[x]...(a1 and c2 in any order)
- P2: r1[x]...w2[x]...( (c1 or a1) and (c2 or a2) in any order)
- A2: r1[x]...w2[x]...(c2...r1[x]...c1)
- P3: r1[P]...w2[y in P]...((c1 or a1) and (c2 or a2) any order)
- A3: r1[P]...w2[y in P]...c2...r1[P]...c1
"言語表現によるP1"を再定義すると上記のA1となる。これはP1を禁止することで防げるため、以降ではPxを広義の定義、Axを狭義の定義とする。 また、言語表現による定義では、P3はinsertのみを対象としているが、notationでは意図的にすべてのwrite(insert, update, delete)を対象としている。
ANSI SQLでは4つのisolation levelを定義しているが、これらは不整合を発生させるphonemenonを排除しているかによって区別されている。 serializabilityの定義も同様のため、この定義は不十分なものである。
Table1ではserializableをANOMALY SERIALIZABLEと表記した上でこれらの整理をしているが、このあとに再定義したTable3が紹介される。
多くのSQLプロダクトではロックベースの分離が用いられているので、ロックに基づく分類も有用である。
トランザクションはロックスケジューラにread(share)とwrite(exclusive)ロックを要求する。
2つのトランザクションが同時に同じデータにロックをかけようとし、そのどちらかでもwriteロックだった場合は、競合(conflict)が発生する。
(用語)
- well-formed write(read): write(read)を行う前にそのデータにwrite(read)ロックを要求している処理
- well-formed transaction: well-formed write(read)によって構成されるトランザクション
- two-phase locking: トランザクション中で、ロックをリリースした後に一切の新しいロックを要求しない処理
- long duration: commitかabortするまでずっとロックを保持する場合(そうでないものはshort duration)
基本的な定理として、”well-formed two-phase locking"なトランザクションはserializabilityが保証されている。 これによって発生するhistoryはserial historyと等価である。
GLPTにおける分離レベル
[GLPT]の論文で定義された分離レベルについて 省略
Analyzing ANSI SQL Isolation levels
ANSI SQLの定義にはないが、dirty readをwriteに置き換えたものも対策する必要がある。 省略記法で書くと以下。
P0: w1[x]...w2[x]...((c1 or a1) and (c2 or a2) in any order)
以降のこの章ではANSI phenomena(Ax)の定義に含まれていないHistoryを例示し、それを含めた広義の表現(broad interpretation)が必要なことを説明しているが具体例は省略。
ここまでの説明から提言
- すべての分離レベルはP0への対策を要求するべき (Remark 3)
- ANSIのそもそもの定義Axは不十分なので、広義のPxで再定義し直すべき (Remark 4)
- ANSIの定義は不十分なので、ロックによる定義を完全にしたものに再定義されるべき。また、P3も再定義されるべき (Remark 5)
これらを踏まえてIsolation Levelを再整理したものがTable 3である
table3
Cursor Stability
Cursor Stabilityはlost updateを防止するように設計される。
- P4 (Lost Update): ロストアップデートはT1がデータを読み、T2が事前に読んだ値によって、T1と同じデータを更新し、さらにT1が同じデータを更新することで起きる。
P4: r1[x]...w2[x]...w1[x]...c1
これによって、T2がcommitされたとしてもそのデータが消えてしまうという問題が起きる。
P4はREAD COMMITTEDでも起こりうる。しかし、P2を防ぐことでP4も防ぐことができるので、REPEATABLE READでは問題ない。
READ COMMITTED << Cursor Stability << REPEATABLE READ
Cursor Stabilityはカーソルが示すデータをロックし、FETCHを行うことでREAD COMMITTEDを拡張している。 Fetchを行うトランザクションはカーソルが閉じられるまで、対象の行をロックする。略記法ではこれらをrc, wc(read cursor, write cursor)と表記する。 これを使うと、P4(P4C)を防止することが出来る。
P4C: rc1[x]...w2[x]...w1[x]...c1(Lost Update)
Cursor Stabilityは多くのSQLシステムでカーソルから読み出しを行うことで、ロストアップデートを防ぐように実装されている。 いくつかのシステムでは実際、READ COMITTEDはCusor Stabilityよりも強力である。
Snapshot Isolation
Snapshot Isolationはmutiversion concurrency control(MVCC)の一種。 トランザクションの開始時とコミット時にStart-TimestampとCommit-Timestampをとり、コミットの際に競合するデータに対して、この時間内に他のトランザクションのコミットがなければコミットをするというものである。 この方法はFirst-committer-winsと呼ばれ、ロストアップデート(P4)を防止できる。
Snapshot Isolationはマルチバージョン(MV)の方法なので、single-valued(SV) historyでは時間関係を的確に表すことは出来ない。 Section 3のH1をMulti-value historyで示すと以下のようになる。
H1.SI: r1[x0=50] w1[x1=10] r2[x0=10] r2[x0=50] r2[y0=50] c2 r1[y0=50] w1[y1=90] c1
H1.SIはシリアルな実行のdataflowを持っている。また、[OOBBGM]で著者らは全てのSnapshot Isolation historiesはdataflowの依存性を保持したまま、single-valuedのhistoryにマッピングできることを示している([BHG]のchap 5でこのアプローチが説明されており、マッピングされたhistoryはView Equivalentと呼ばれる)。 このようにMV historyをSV historyに変換する方法はIsolation Snapshot Isolationを分離レベルの階層に組み込むために重要な試金石となった。
Snapshot IsolationはSerializableではない。 例えば、以下のようなSV historyを考えてみる。
H5: r1[x=50] r1[y=50] r2[x=50] r2[y=50] w1[y=40] w2[x=40] c1 c2
ここで、xとyの間にx+yを一定値とする制約があると仮定すると、それぞれのトランザクションは正常にコミットされるが、制約が守られない状態になる。こうしたConstraint violationは一般的で重要なconcurrency anomalyである。
Constraint violation
ここでは2つのconstraint violationを紹介する
- Read Skew(A5A)
- T1がデータxを読みだし、T2がx,yを書き換え、T1がyを読みだすと、制約に違反する状態のデータセットを読むことになる。
r1[x]...w2[x]...w2[y]...c2...r1[y]...(c1 or a1)
- Write Skew(A5B)
- T1がx,yを読みだし、T2がx,yを読んでxを書き換える、さらにT1がyを書き換えるとx,yの制約が守れない
r1[x]...r2[y]...w1[y]...w2[x]...(c1 and c2 occur)
Fuzzy Reads(P2)はx=yの制約があるうえでのRead Skewの縮退版である。 A5A,A5BはP2が対応されている場合は起き得ないので、これらの現象はREPEATABLE READ以下のレベルを区別するために有効である。
Classify Isolation
Snapshot Isolation(SI)に話を戻す。
SIはREAD COMMITTEDよりも強力である(Remark 8)。 SIではP0,P1は発生せず、さらにRead Skew(A5A)のアノマリーはREAD COMMITTEDでは発生するが、SIではしない。
さらに、SIはA3の現象を排除できるが、Write Skew(A5B)を排除できない。 P2を排除するとP5(A5A,A5B)は排除できるため、REPEATABLE READとSIはお互いの出来ないことが出来る関係にある。 そのため、REPEATABLE READとSnapshot Isolationは上下関係が区別できない。(Remark 9)
また、ANSI SQLで定義されたアノマリーベースの分離レベルでは、A1~A3を起こさないことがSerializableの条件のため、SIはANOMALY SERIALIZABLEよりも強いことになる(Remark 10)
Summary
この論文ではANSI SQLの曖昧な表現を指摘し、ANSI SQLでは定義されていないアノマリーを発生される現象を紹介した。 また、Snapshot Isolationを紹介し、それらの分類を行った。
Table 4では分類の結果をまとめている。
Table 4
また、Figure 2ではこれらを、排除できる現象によって階層化した結果を示している。
Figure 2
参考
"A critique of ANSI SQL isolation levels"(論文リンク)
.
