いろんなAnomaly

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

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

## Dirty Read Anomaly

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

![dirty_read.png](https://qiita-image-store.s3.amazonaws.com/0/1716/c41c814c-e4f1-e3a6-2cfc-23337f945e99.png)

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

READ UNCOMMITTEDで起きる。

## Read Skew Anomaly

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

![read_skew.png](https://qiita-image-store.s3.amazonaws.com/0/1716/b6489fe8-a950-8124-004f-3af080b2d2e2.png)

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

READ COMMITTEDで起きる。

## Lost Update

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

![lost_update.png](https://qiita-image-store.s3.amazonaws.com/0/1716/26354b53-23ee-5ded-ff49-0f24c1615057.png)

何が問題なのかピンと来ないかも知れない。`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。

![inconsistent_read.png](https://qiita-image-store.s3.amazonaws.com/0/1716/0212e063-8448-3a7a-f78f-73aa067da791.png)

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

## Write Skew Anomaly

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

![write_skew.png](https://qiita-image-store.s3.amazonaws.com/0/1716/05dc685d-4a1b-7a58-5fc9-ce7361b743e4.png)

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

```
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](http://dl.acm.org/citation.cfm?id=1031573&dl=ACM&coll=DL&CFID=622180548&CFTOKEN=62093876)が初出のように見える。

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

![read_only.png](https://qiita-image-store.s3.amazonaws.com/0/1716/fbbd4e5a-ad32-d00d-8204-e093c438eb1d.png)

```
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**に走る未来を目指して今日も研究者は頑張っている。