昨日様々なトランザクション分離レベルに付いて書いた。
AnomalyとはSerializableでない実行を引き起こす異常状態パターンのことを言う。
弱い分離レベルほどAnomalyが起きやすい。

これから図を交えながらAnomalyについて説明する。
図中の「W(x)」は「xに何らかの値を書き込む」、「R(x)」は「xの値を読む」をそれぞれ意味する。
分かりやすいようにReadは青、Writeは赤色で統一する。
また、Anomalyの被害に遭うのは常にT1に統一する。
Cはコミットを意味する。

Dirty Read Anomaly

未コミットな値を読んでしまうAnomalyの事。Readがロック関係なしに値を読んでしまう場合などに起きる。

T1が書き換えられる最中のxの値を読んでしまっている。もしT2が途中でアボートしたらT1はどこにも存在しない値を読んだ事になってしまう。

READ UNCOMMITTEDで起きる。

Read Skew Anomaly

複数の値の間で不一貫な状況を読んでしまう事。

T1はxとyの値を読みたかっただけなのに、xを読んでからyを読むまでの間にxとyに書き込みが起きてしまいT1は一貫性のあるx,yのスナップショットを取ることが出来なかった。

READ COMMITTEDで起きる。

Lost Update

せっかく書き込んだ値が他のトランザクションによってなかった事にされる(Dead Stepと呼ぶ)もの。

何が問題なのかピンと来ないかも知れない。xのエルブランセマンティクスをこの図から抽出すると

x = F2(x0)

となっており、F1の結果が完全に消えている(Dead Stepしている)ため、Lost Updateと呼ぶ。
も2つのトランザクションがSerialに走った時、xの最終状態が取りうるエルブランセマンティクスは

x = F2(F1(x))

か

x = F1(F2(x))

のどちらかしか許されないはずである。よってVSRではない。
REPEATABLE READでは起きないがREAD COMMITEDでは起こりうる。
CURSOR STABILITYレベルであればFOR UPDATEで回避できる。

Inconsistent Read Anomaly

同じ値を2回読んだ時に値が変わっているAnomaly。

T1はxを2回読んだが2回目に読む値はT2の書いた結果になっている。
REPEATABLE READでは起きない。

Write Skew Anomaly

読んでいない値に書き込む際に他のトランザクションの読んだ値に書き込んでしまうこと。

図からはピンと来ないかも知れない。
例えば図中の個々のトランザクションがそれぞれ

T1: y = x + 1
T2: x = y + 1

という動作を行おうとしていた場合を想像してみると良い。初期状態がそれぞれx=y=0だったとして、最終状態はx=y=1になってしまう。
エルブランセマンティクスを整理すると

x = F2(y0)
y = F1(x0)

という状況になってしまう。Serializableな実行であれば

x = F2(F1(y0))
y = F1(y0)

か

x = F2(x0)
y = F1(F2(x0))

のどちらかにしかならないはずなのに、である。
これはSnapshot Isolationの時に起きることで有名である。

Read Only Anomaly

これは比較的近代見つかったモノなので知らない人も割といる。
ざっと調べた所、SIGMOD2004のAlan FeketeらのA read-only transaction anomaly under snapshot isolationが初出のように見える。

Snapshot Isolation上で問題のないと思われていた実行パターンでも、観測者としてRead Onlyなトランザクションが加わるとAnomalyになるという興味深い例である。初期状態をx=y=0として

T1: xとyの値を読んでユーザに報告する
T2: xに5を足す
T3: x == yの時にyから10を引く

という動作が為された時、T1が居ない状態であればT2とT3のトランザクションはSerializableな実行がされたとみなして構わない。
逐次実行として順序を整理するとT3の後にT2が起きたという順序で決着が付く（図中のCommitの順序と逆転している所が非常に面白いのだがこの話は後日）。

しかし、T1が観測した値はx==5かつy==0であり、これはT3の前にT2が起きないと説明が付かない。つまりトランザクションによって観測される順序が変わっておりSerialに実行されたとは言えない。

今日はAnomalyに関して説明した。
なお、Anomalyは起きないに越した事はないが本当に起きるかは運の他にユーザのプログラムによっても依存される。
極端な話、一切の書き込みを行わない使い方をするのであればREAD UNCOMMITTED分離レベルであってもSerialな実行結果しか生まない。

もう少し現実の話をすると、TPC-Cというトランザクション性能を測るベンチマークにおいてはWrite SkewおよびRead OnlyのAnomalyは構造上発生し得ない。そのためTPC-Cの測定をSnapshot Isolationで実行しても一切のAnomalyは起きないので、OracleはSnapshot Isolationで問題なくTPC-Cを測定しているという話は有名である(アカデミックな意味でSerializableでない設定の上で走らせるのはフェアではないのではないかという意見もある)。
アカデミックな分野ではトランザクションのクエリ文を全部与えると静的に発生しうるAnomalyを検知できるツールなども研究されており、いずれユーザは何も意識しなくても勝手に最速なSQL文実行が可能な限り緩い分離レベルでSerializableに走る未来を目指して今日も研究者は頑張っている。