ANSIによるSQL分離レベルの標準は有名な概念である.
トランザクションの概念やACID特性といった言葉を理解していなくとも,ここで示されている4つの分離レベルを暗唱できる人はそれなりにいるのではなかろうか(私はそうだった).

有名な4つの分離レベルは以下である.
ここでは,3つの 異常(Anomaly:直列実行と異なる実行パターン) を想定しており,この Anomalyのどれが発生するか によって分離レベルが決定される.

1
2
3
4
SERIALIZABLE: 直列実行と等価
REPEATABLE READ: Phantom Read Anomalyが起きる
READ COMMITTED: 上記に加えて,Non-Repeatable Read Anomalyが起きる
READ UNCOMMITTED: 上記に加えて,Dirty Read Anomalyが起きる

ここまでは知っている人も多いだろうと思う.

ここで一つ,気になることがある.この分離レベルの標準は定式化して表すことができるか?
すなわち,このレベル分けには理論的な裏打ちがあり, 「Dirty Readは起きるけどNon-Repetable Readは起きない ようなトランザクションの手法はありえない」と断言出来るか?という疑問である.
これが断言出来ないなら,そのような手法はどの分離レベルに当たるのか?

実はこのANSIの分離レベルの水準は,言外に,トランザクションを二相ロックプロトコル(2PL)で実装することを前提に置いて作られたものだと考えられている.2PLでは,コミットを行うタイミングとロックの獲得/解放順序によって,性能と一貫性のバランスを取ることが出来る.この, 2PLを実装上するうえで取りうる選択肢をそのままレベルとして表現したのがANSI SQL標準 だという話だ.2PLについての説明は詳細を省くが,実は以下のような想定が置かれている:

1
2
3
4
SERIALIZABLE: S2PL以上の実装に,ギャップロック/Predicateロック等を取る
REPETABLE READ: S2PL以上(S2PL/SS2PL/C2PLによる実装)
READ COMMITTED: 2PLによる実装.
READ UNCOMMITTED: write lockだけは取るという実装.特定のプロトコルに沿わない

となるとこの標準はもしかすれば2PLにのみ有効なものである.先に挙げた疑問にこの標準で応えることは出来ないし,他のトランザクションの実装手法に関してこの標準で議論することは不可能であるかもしれない.

有名なA Critique of ANSI SQL Isolation Levelsでは,新しい実装手法(Snapshot Isolation:SI)などを考慮した分離レベルの批判を行っている.
曰く,本来のトランザクションの直列化可能性の意義である「直列実行した際と等価な結果が得られること」には違反するが,ANSIの4つの階層レベルで考えるとSERIALIZABLEに当たる実装手法がありうる という話だ.
こちらの論文については神林さんのブログはてなの記事が詳しい.要するに,ANSI SQL標準では対応しきれないAnomalyが存在するということである.現に,分離レベルの概念は,新たな手法の登場と新たな異常の観測と共に成長し続け,このような記事まで登場している.トランザクション手法が進化すればするほど,このようないたちごっこが続いていくのはあまりにも辛い.

直列化可能性(Serilizability)とはそもそも何だったのか

さて,このような状況では当然,データベースの設定をSERIALIZABLEにすることにどれほどの意義があるのか?という話になる.
実際に,OracleはSERIALIZABLE分離レベルをANSI SQL標準に従った形で記載しており,Anomalyは起こりうるがSERIALIZABLEである という奇妙な状況を生んでいる.
PostgreSQL等のDBMSもSnapshot Isolationを実装しているが,そのために READ COMMITTEDに設定すると,確かにREAD COMMITTED相当のAnomalyは防げるが,本来のREAD COMMITTEDよりは一貫性が強い というような状況が起こってしまう.

この問題を,PODS2017で発表された Seeing is believing: a client-centric specification of database isolation という論文中では図示している.ここでは二つの実行パターンが左右に示されている.

最も理論上広く使われているConflict Serializabilityがこれらの実行パターンを全て許さないのに対して,ANSIの Anomaly Serializableは図右の実行パターンを許す.これはANSI標準に従ったOracleでも同等である.ここに至ってSERIALIZABLEという言葉がそれ自体何の意味があるのか怪しくなってきたことが分かる.

※ ちなみに,直列化可能性の理論上最も正確な答えは,左のスケジュールはAcceptsであり,右のスケジュールはNon-Acceptsである.すなわち Multiversion SerializabilityRococo が理論的には正解.

元を辿れば,トランザクションの直列化可能性を検定する方法論としてもっとも有名なものは,依存関係グラフ(Dependency Graph) を描き,それが有向非循環グラフ(DAG)であるかを検定するというものだった.依存関係が循環していないということは,トポロジカルソートが可能という意味であり,それはすなわち全トランザクションに何らかの全順序を与えることが出来るということを意味する.つまり,「直列化可能」である.この定式化は先ほどのFigure 1における Conflict Serializability(CSR) にあたる.このCSRは,トランザクションのSERIALIZABLEの意味論を議論する上でのGold Standardである..

この依存関係グラフの検定に立ち返って見れば,Anomalyとはつまり循環のパターン である.依存関係グラフで扱う依存関係は3つしかないから,そこから起こりうる組み合わせは有限であることが分かる.手法が生まれるごとに,全命令の全実行パターンの全組み合わせを検査して,新たなAnomalyの可能性を議論して,分離レベルの標準を考える,ということをやっていたのではNP完全に帰着してしまってお話にならないので,この3つの属性だけを使ったグラフの検定を使ってトランザクションを考えましょう というのが大まかな過去の方向性であり,以降のトランザクション手法の提案は殆どの論文がこのCSRの定理を用いて証明/説明されている.

Adya’s Formalism: 直列化可能性の定式化

そこで有名なAdya’s formalizationと呼ばれる定式化が登場する.
この定式化は上述したCSR(Conflict Serializability)を導出するためのものであり,Multiversion Serializability(MVSR)等の定義には対応できない.が,最も広く使われている手法であり,現実的な計算時間で実行できるトランザクション手法を検討する際のベースラインとなるものである.

先ず,全てのデータベースへのアクセスは readwrite の二つの命令から成る命令列とする.すなわち,

1
T1: SELECT * FROM table

というSQLは,SQLパーサ/プランナ/オプティマイザ等のコンポーネントを通過した結果,必ず

1
T1: read(a)read(b)...read(z)

という命令列に変換される.INSERTUPDATE などのDMLはwrite命令に変換される.

この時,read writeの命令は,以下の依存関係を生む.

1
2
3
w-r(flow dependency): Aが書いたものをBが読む
w-w(write dependency): Aが書いたものにさらにBが書く
r-w(anti-dependency): Aが読んだものにBが上書きする

これらの依存関係をもとに各トランザクションをグラフ化する.たとえば, xを読んで1足して上書き (つまりx++)というトランザクションは以下のように表せる.(微妙に定式化されているものと記述を変えている)

1
2
3
4
5
6
7
8
SQL:
BEGIN TRANSACTION;
SELECT * FROM table WHERE ...
do_some_processing()
UPDATE table SET ...
END TRANSACTION
Adya's formalism: r(x) w(x+1)

このクエリが同時並行的に走ると,以下のようなスケジュールになりうる.

1
2
3
T1: r(x0) w(x1)
T2: r(x0) w(x1)
--Execution History-->

言うまでもなくこの場合両方がCommitすることは直列化可能性の定義から言って許されない.二回x++が走ったのに結果はx=1でしたというのは明らかにオカシイ.これはどのようなAnomalyなのかというと,以下のようにグラフで表すと明らかにできる.

直感的におかしい動作であるが,どのようにオカシイのかというと,r-ww-wの依存関係が循環している,ということから説明できる.
以上がAdyaの依存関係グラフによるトランザクションのCSRの検証の雑な説明である.

興味深いのは,ANSI SQL標準にこのAdyaの依存関係グラフの概念を適用すると,SQL標準にどのような穴があったのかが読み取れるということだ.
これについてもAdya論文で整理されていて,

1
2
3
4
SERIALIZABLE: w-wとw-rの依存関係が循環しない
REPEATABLE READ: w-wとw-rの依存関係が循環しない
READ COMMITTED: w-wとw-rの依存関係が循環しない
READ UNCOMMITTED: w-wの依存関係が循環しない

ANSI SQL標準は上記のような分類となる. Non-Repeatable Read や Dirty Read といったAnomalyは,二相ロックという手法のうえで観測できる事象でしか無い. 定式化すると,ANSI SQL標準の分離レベルは,最大でも w-ww-r についての循環しかチェックしていないことが分かる.r-w の依存関係を含むグラフが循環することは考慮されていない. しかし,でも二相ロックを用いる場合には SERIALIZABLE は直列実行と等価にできる.(その理由についてはここでは詳述しない.端的に言うと,「ANSI SERIALIZABLEの二相ロック(すなわちS2PL以上)では読取りロックを獲得し,コミット完了まで手放さないため,concurrentなトランザクション同士で r-w のエッジは必ず存在しえないから」という説明になる.)

本当に求められているセマンティクスとは

Adya論文の定式化をベースに異常というものを考えた時,ひとつの問題がある.
それは,現在の分離レベルの標準が説明しているのは,トランザクションを Read 命令と Write 命令の系列とみなして,その実行が直列実行にどう違反するか であり, アプリケーションから見てどういうバグとなるのか ということに関する解釈が極めて難しいということだ.
実際にアプリケーションエンジニアは READ WRITE の系列を書いているわけではなく,SQLなどのインタフェースを用いてデータベースを操作することが大半であるわけだから,このような分離レベルの説明は,READ/WRITE系列とSQLの変換を脳内でやれと言っているようなものだ.今さっき書いたSQLを READ WRITE の命令列に変換してみろ,と言われて正確に出来る人間などほぼ居ないだろう.O/Rマッパー等のミドルウェアを噛ませていれば,なおさら難しい.

これは結果として, 「クエリを実行して得られた結果が,Anomalyなのか判断できない」 という状況を産んでしまう.自分の使っているデータベースのトランザクション手法から,どのような異常(r-ww-r? それともr-wr-wの循環?)が起こるのかは分かっても,それがアプリケーションにどのような影響を及ぼすのか,自分が書いたクエリはどのような異常を発生させうるのか,は全く見えてこない.

これではアプリケーションを記述するエンジニアにとって,「弱い分離レベルは使うな」と言っているようなものである. 現実には,多少古いデータを読んでも困らない状況や,性能のためなら数%のユーザにバグが出ることは厭わない状況などは大いにあるだろうから,やはりANSI SQL標準の分離レベルのような,「○○に設定すると☓☓が起こりえます」というわかりやすい表現は欲しい.

先に取り上げたSeeing is Believing論文では,
このように状況を整理して,かつ,「アプリケーションから見て,永続化された情報にどのような変化が起こりうるのか」 を端的に説明するような新しいIsolation Levelの標準を構築している.詳しくはこれから読む.

つまり

私も含めて,アプリエンジニアには分離レベルを見ただけで自分のアプリが起こすバグをエスパーすることは不可能である.
なので SERIALIZABLE を使うと安心安全である.とりあえずスケールさせたらバグったということは防げる.

と言いたいところだったが,世の中の SERIALIZABLE は本当に求めていた SERIALIZABLE ではなかったのである.やっぱりバグは出てしまうし,それが標準化もされているのが現状だ.これから新しいデータベースが出てくるたびに,こういう議論が起こっていたのではきりがない.

だが,データベースのトランザクションには並行性に関する保証はないものと考えて,手当たりしだいに並行性に起因するバグを潰して回るのは大変しんどいし,理論的な保証も欲しい.そして,できれば理論的な保証がされた上で,パフォーマンスが上げられる選択肢も欲しい.そこのトレードオフはアプリから見て明快なセマンティクスであってほしい.
というのがデータベース研究者が昨今妄想しているアプリエンジニアの姿である(と思う.)

前に書いたCoordination Avoidanceの夢の記事なんかもそのへんの話をしている.

以上ポエム終わり.