A Critique of ANSI SQL Isolation Levels再読
元論文はこちら
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-95-51.pdf
詳細なスライドはこちらになります。今年の夏のクラウド温泉で発表した内容です。一回見直して、若干手直しをしています。
http://www.slideshare.net/okachimachi/a-critique-of-ansi-sql-isolation-levels
論文の解説は割と意味があると思ったので、スライド自体は割とまじめに作りました。クラウド温泉では口八丁手八丁でいろいろ話しましたが、その辺はオミットしています。この論文の解説は探せば、いろいろ巷にはあるのですが、かなり苦闘して矢尽き刀折れ状態が散見されるので、多少なりとも状況が補修できればと思っておいておきます。（尚、当然ですが、内容が正確かどうかは保証しません。）
この論文は、1995年に発表のもので、もう15年以上前のものになります。Jim GrayやPhil Bernsteinといったtransactionの大先生達の共同執筆になっており、その上でANSIの定義であるSQLの、特にIsolationレベルを豪快に批判した上で、対案やその考え方のまとめ方を提示している論文です。
transactionのconcurrencyにおけるisolationレベルの基本的な考え方をまとめている論文で、その後のtransactionの研究の前提の一つを提示しているため、今現在ですら引用されることがあります。transactionの中身を詳細に理解する人であれば、必ず読むべき論文と言っても過言ではないでしょう。実際、今日現在でもSnapshot Isolationの周りの実装を見る上で、参考にすべき論文を辿ると、最後は必ずこの論文に辿り着きます。なので、基礎をしっかり理解したい人は読んだ方がいいです。
正直15年以上前の論文ってどうよ、とは思ったのですが、意外に今現在までの潮流に連なっており、古典とはいえ馬鹿にはできないな、と痛感しています。
尚、今更という人も勿論いくらでも居ると思いますが、ま、現実にJim GrayやPhil Bernsteinの両御大が共同でANSIを豪快にdisるというも見物ではありますので、そーゆー視点読んでみるのも一興かと。
内容ですが、何も武装しないでいきなり読み込むと、最初の方はふむふむと行けるのですが、途中で怪しくなって、ギブアップするか、または、そのままのふわふわ状態のまま、最後の方のSnapshot Isolation「だけ」を見つけて、一応わかった気になって終わるという、「なんか凄かった」ということだけで終わってしまう論文なので、一応自分なりのポイントを上げておきたいと思います。ただし以下は自分の興味を中心に見ている視点でもあるので、読む場合は、個々人で最初にちゃんとした視点を持つことが肝要かと思います。
まず、読むための基本装備から・・・
・transactionにおけるcorrectnessはserializableであるということで担保される。
・two-phase-lockプロトコルは(conflict) serializabilityを提供する。
以上は、transaction処理の理論における割と常識として扱われることが多い前提なので、理解しておく必要があります。一応、論文内部に簡単な解説がありますが、ないも同然です。詳細はスライドに書いたのでそちらを参考にしてください。一応この辺は手持ちの武器でもっておく必要があります。
んで次に、読むための地図ですが・・・
1. 「isolationレベルは何々ができるという定義ではなく、何々ができないという定義である。そして“何々ができない”という場合は“必ずできない”ということが保証されなくてはならない。」という普通に考えると何言ってんだ？そりゃ？という議論が基本に展開されています。論文内でのロジック構成は、ANSIの定義では不明確なケースが出てくるので宜しくない、という論理構成になっています。
この「できない状態」すなわち「不整合が発生する状態」をanomalyとしてちゃんと定義しています。これがこの論文の一つの趣旨でもあります。（尚、これがわかっていないとtransaction系の論文はさっぱり君になってしまうので要注意です。）
よくisolationレベルの解説でおなじみの、Dirty Read, Lost Update, Inconsistent Read, Phantomといった類いです。これ以外にもRead Skew / Write Skewというものも登場します。これは特にSnapshot Isolationの書き込み競合で問題になることが多いです。
尚、論文でも指摘があるのですが、isolation levelはややもすれば誤解が発生しやすいです。特にRepeatable read。言葉自体が「繰り返し読める」という“〜できる”という言い方ですから、何回読んでも同じということですが、まったくそういうことではないのは、周知の事実でしょう。predicateな場合は、phantom発生するので、concurrentなtransactionがあると、何回読んでも同じにはなりませんね。このあたりもJim Gray大先生は凄い勢いでdisっています。
2. Snapshot Isolationの世界戦デビューだったりします。実はSnapshot Isolationの紹介自体はこの論文以前にも出ているのですが、どうもその後の流れ的にはこの論文がSnapshot Isolationの初出されることが多いようです。現状、MVCC実装のデファクトになっているのは、DB関係者であれば周知の事実かと思います。恐るべき事にこの論文(15年前！) の言い回しがそのまま、今も使われていたりするので、押さえておきましょう。
なお、全般的な言い回しに当時から現在に至るまでのDBの開発のコンテクストが垣間見えます。両巨頭のOracle・IBMへの言及もありますね。
3. 基本線としてanomalyの整理になっており、おおよそ以下の議論の線を押さえておくと、それなりに追えます。基本線はwriteを軸にしたconflictを出発点にします。これはtransaction一般にそうですが・・・・その上で、ですが
以下、自分の趣味的な見方です。
まず、transactionのanomalyの考え方は、ミドルは勿論、アプリケーション一般での非常に有用な「技術」です。誰も手製のADTを作ったり、またパフォーマンスを出すためにある種のキャッシュ・メカニズムや、バッファーの仕組みを実装したことはあると思います。そして、結果としてかなり苦労しているケースが多いのではないでしょうか。
データ・コンフリクトは別にtransactionで「だけ」で発生するわけではありません。普通にデータをキャッシュしたり、バッファリングをしたりすればバシバシ発生します。その意味でtransactionでの解決法は、それなり参考になります。特に「こういった例外をちゃんと想定しているか？」という例外ケースの摘出には有用どころか、欠かせないと思います。(concurrent処理のモデルとして排他制御ではなく、transaction技術を利用するという考え方もかなりあります。・・・とはいえ、transaction技術使ってますといいつつ中身はロックの嵐とかいうことも普通にあるので・・・それは最初から排他制御って言えよ的な(ry )
■ w-r系 Dirty Read敢えてアプリ的に言いますと、「データを読み込んで処理をしている最中に、そのデータはやっぱ取消だわ、と言われた」というケースです。ま、ありがちです。データをバファリングして処理している最中に、それ取消ね的な割り込みが来た場合です。
Dirty Read は、本来、transactionの議論の文脈から厳密言うと、writeがabortした時にのみ問題になるわけで、read committedのようにそもそもreadさせない(または、writeをコミットさせる)という解決方法をとる（論文の手法）ことが多いです。通常のserializableの議論の文脈ではコミットしたtransactionだけでのスケジューリングで検討を（入門編では）するので、そこでは単純にserializableかどうかの判定になります。この場合、conflictの順番を維持すれば特段問題にはなりません。（アプリのコンテクスト的にはそもそも取消は認めないという手当を事前にしておくという形かと）
abortを織り交ぜた問題は、本来的にリカバリー・アルゴリズムでカバーする範囲の話になります。この場合はコミットとabortの順序の問題になるので、単純な「serializabilityだけ」の問題にはなりません。論文では明確にanomalyとしてcommit-abortの関係に言及しているので、あくまでそういったコンテクストが基本になる、という理解でいいかと思います。（実際はabortの順序の問題になるので、アプリ的には、取消が来たときに、そもそも走っているこの処理をどう止めるか？考えておく必要がある、ということになります。）
■ r-w系 Inconsistent Read (Phantom)これは一般にはAnti-Dependencyと言う言い方をすることもあります。非常に厄介かつ面白いところです。MVCCでのコンテクストで語られることが多いanomalyですね。詳細は実際の論文とスライドを参照して頂きたいのですが、他のw-r系・w-w系のanomalyと違って、その場ですぐにanomalyとするか？というところまで考える必要があります。
アプリ的にはキャッシュをつくっていたら、オリジナルの更新がかかったというケースですね。無視します？更新します？こちら（キャッシュ側）の更新はオリジナルにどう反映させます？そーゆーケースですね。
そもそもreadしている時点でtransactionをオープンしているわけで、そのtimestamp時点での情報のみで処理が完結するのであれば、特段にanomalyになるわけではないです。が、他のtransactionが、当該transactionが参照している値を当該transactionの処理の最中に変更しているわけで、「場合によっては結果不整合になる」というケースです。（念のために言っておきますがロックとりゃいいじゃんという発想は負けパターンです。だって結果不整合にならないこともあるわけで、その場合はロックは無駄。只の「念のためロック」とかいいこと何もないです。）尚、snapshotは値（というかpredicateで取ってくるので値とは限らない）を一回コピーしてしまうので、当該transactionの利用データセットをisolateするという原理ですね。
当然、readはともかく、書きにいったときにconflictになるわけで、これがw-wの系と近いので、混乱モードになりがちです。ま、r-w-wですね。さらの仮に書き込みが成功しても、他の書き込みとの不正後が意味的に発生する(constrainを満たさない)ことがあるので、たちが悪い。これは実は完全にisolateしても発生します。
さてどうする。そんな話が論文の趣旨・・・というより、そーゆーことがありますよ、ということを明示してみせているというところかと。
アプリケーションでも普通にある話ですね。データをコピーして保っていたら、オリジナルが変わっていたというケースです。当然何らかの手当は必要になります。そんなのは「そもそも仕様になかったじゃな〜い」といい張るのは手段としてはありますが・・・
■ w-w系 Lost Update/Dirty Write/Write Skew
これはよくある書き込み競合のケースになります。
まずLost Updateは、同一対象でのw-wでw2(x)w1(x)のケース。transactionがオーバーラップした時に、途中の書き込みが消えるケース。ただしT2-T1のオーダーでserializeできるのであれば、anomalyにはならない。
Dirty Writeは、あまり聞かないケースですが、w1(x)w2(x)でserializeできないケース。w1(x)w2(x)w2(y)w1(y)なんてのはこれになります。
以上はだいたいserializeできない時点で検出ができるはずです。SGT万歳主義者なひとは完全にドヤ顔ですね。100%検出できますから。問題はWrite Skewで、基本的にconstraint violationでの議論になることが多い。Lost UpdateやDirty Writeとは議論のコンテクストが違います。問題はむしろこっちかと。
ここが個人的には非常に面白い。特に、業務屋視点からみると、そもそもそれはミドルで処理する内容なのか？というところに踏み込んでいるようにも見えます。data constrainは見ようによっては間違いなく「ビジネス・ロジック」と言われるものになります。例えば、Write Skewの典型でr1(x)r2(y)w1(x)w2(y)というtransactionがconcurrentにあって、それぞれisolateしているとします。このときにx=yがconstrainだったとして、普通にアプリを書くと、このviolationの検出はアプリの責務になることが多いです・・・だってミドル上は完全にtransactionは成功してしまいますからね。業務アプリを組めば「仕様で把握すべき範囲」になるでしょう。
ただ、例えば参照制約の違反なんかもWrite Skewの一例には入るわけで、これはDBの守備範囲でしょう、という話も他方であります。参照制約も典型的なdata constrainです。というわけで、実は一概には言えません。
見ていると、TX屋さんの野望は果てしなく、そのレベルまでanomalyで検出してやろう、という発想が見られます。これは凄いことですが、できるわけ無いだろう、という見方も業務屋サイドではあるわけです。面白い。勿論、論説によってはdata constrainを意図的に避けて serializableだけで議論を帰着させるというスタイルもあり、なかなか微妙だなと思います。そういう文脈で読んでいくとなかなか味わい深いところです。
ただ、得られる重要な示唆は、仮に特定ドメインに特化する業務系ミドルであれば、ある程度のdata constrainは確実に把握できるし、またミドルで当該transactionをanomalyとして検出するということは絵空事ではない、ということです。アプリケーション開発での負担を考えるのであれば、むしろ積極的に行うべきという考え方もあるでしょう。これによりアプリケーションの品質は格段に上がることが論を待たないと思います。
・まとめconflictの関係とその解決の手法の発達で、transaction系の技術・理論は発展してきたといってもよい面は確実にあるのではないかと思います。この技術は、アプリサイドを構築する場合もきわめて有効な考え方を提供することになると思います。
というわけで、この論文は未だに同時代的なアクチュアリティを保っている貴重な論文だと思います。正直transactionを全く勉強していないひとが、いきなり頭から読んで、その意義までわかるか、というアレではありますが、興味のある人には一読をお勧めします。
ま、あとはいい加減スライドを出せ出せ出せと言われていたので、とりあえず出したので、この辺で勘弁してやってください的なアレです。
あと、そのうちMVCCあたりちゃんと整理しておきます。不揮発性メモリーでの話や、分散のコンテクストでも有用な技術（一種のリプリケーションの応用なので）であるのは間違いないので、ちゃんと押さえておきたいですね。
ま、巷でも例のG先生のspannerの話もあったりで、transaction再びの機運も（想定通りに）来つつあるので、勉強、勉強ってことで。
でわでわ
