Welcome back to the TRANSACTION! - 急がば回れ、選ぶなら近道

最近、トランザクションの再勉強を始めていて、先日クラウド温泉でも発表させてもらった手前、ちょうどいいので一回まとめておく。はじめに断っておくと自分は別にDBやTXの専門家ではない。なので以下の内容の正確性については保証しない。内容については自分で勉強してくださいね。

1.「なんでまたTXなのか」
まずもって何故にTXなのか？というお話から始めます。もう枯れてんじゃないか？今頃RDBMSでもないだろう。それはそうですが、以下の流れは無視できません。

・RDBMSの特許切れ
NIIの佐藤先生の指摘にもあるように、1980-90年代のRDBMS関連の特許が切れ始めます。これにより商用一辺倒で、OSSではどうしても勝てなかったRDBMSでの技術革新や、その技術を応用した別のもの（RDBMSとは限りません）が登場してくる可能性が高いです。各ベンダーもそれを見越して、一斉にRDBMS関連への「逆張り」を始めているようです。

・分散環境の一般化に伴う、TX処理の重要性の再フォーカス
これだけ数がでて書籍・情報が出ているNoSQLがどうしても今一普及しない理由の一つはTX処理がないことによります。一般に分散環境下では本質的に“一貫性”の確保が困難であることは周知の通りです。とはいえ、そもそも“一貫性”のないシステムは到底に実用に堪えうるものではありません。それでは、どのレベルの“一貫性”が重要なのか、という話になります。当然、その背景にあるものは、そもそも“一貫性”とは何なのか？という議論を踏まえる必要があります。この議論の出発点はトランザクション処理を巡る研究・実装・実績から、まずは出ているのは論を待ちません。（もちろん、それだけではないですが）

とりあえず検討すべきビジネスコンテクストは以上。んで本論。

2. TXの大事な本質〜correctness

（最初にお断りですが、以下の議論では単一ノードでのTXを前提とします。分散環境の一貫性はまた違う要素が入ってくるため、おなじ一貫性という言葉でもカバーする範囲がさらに広がります。）

まず、最初に断言しますが、TXでもっとも重要な属性はconsistency（“一貫性”）です。いわゆるACID属性のその他の三つ（atomic, isolated, durable）はconsistencyに対する補完的な役割を満たすに過ぎません（もちろん言い過ぎですが、個人の意見なので看過願います。）

次にconsistentであることは、TXの議論のコンテクストで「データの処理がcorrect（“正しい”）である」ことを指すことがあります。勿論correctであることがconsistentであることと同値であるかどうかについて議論はいくらでもあります。が、少なくともcorrectでない場合は、consistentではない、ということ直感的にわかるかと思います。従って、まずは何がcorrectか？というところに焦点を当てた議論を見ていきましょう。

今、大上段にcorrectというワードが登場してきましたが、勿論、明確な定義が必要です。
すなわち一定のsemanticsを設定することが必要になります。手段としてTXの文法とそれを支える数学が準備されことになります。これは、consistencyそのものよりもcorrectnessの方が概念として定式化しやすく、操作しやすいということも無縁ではありません。TXを数理論理学の応用とする考え方です。

さて具体的にどうするかと言うと、厳密にはTXを構成要素、すなわちTX内部を構成するread/write/commit/abortおよびその作用対象（ページまたはオブジェクト）、またそれらのステップの順序・データの依存関係に分解して、一種の判別関数に放り込みます。その判別関数の戻り値の真偽を判定して、真ならばcorrectである、という風に考えていくことが可能になります。・・・という道具立てになります。

3. Correctnessの判断基準〜serializability

何が正しいのか、については前述のように、
・TX内部を構成するread/write/commit/abort
・その作用対象（ページまたはオブジェクト）
・それらのステップの順序
・ステップとデータの依存関係
を基準に考えます。

これらの構成要素をひとくくりにした要素（以降、スケジュールとしましょう。）を集合として扱い、どのような集合に属するか？ということがcorrectnessの判別の最初になります。もっとも基本的な集合がserializableと呼ばれるものです。日本語に無理訳すと“直列化可能性”ですね。（まったく酷いもんです。）

このコンテクストでconcurrencyとisolationの概念が導入されます。すなわち複数のTXを同時実行した場合に、どのようにしてcorrectnessが維持できるか？という問題が提起されます。複数のTXの全ステップをシャッフルして、一つのスケジュールをつくった場合に、各TXのcorrectnessが保証される、すなわち一貫性が保証されることが必要です。ただしその際に、可能な限りくみ上げられるスケジュールの数が多い事（すなわち真理集合の要素が多い事）が望ましく、かつそのスケジュールをくみ上げるルールが有限時間に計算可能かつ平易に実装できることが望ましいです。

さて、ここで基本となるserializabilityについて簡単にまとめます。端的にいうと

与えられた全てのTXのステップを含むスケジュールについて、「当該TXを順次実行した結果と同じ“解釈“が得られる」スケジュールの集合をさします。

なので、まず前提は「TXの順序実行がcorrectである」という前提があります。この前提の上で、「TXの構成要素の組み合わせ」をシャッフルしてつくられたスケジュールに、当該TXを順序実行したものと、同じ解釈が与えられるのであれば、そのスケジュール＝serializableであり、すなわち、correctだと理解してよいだろう、ということです。

ただし、そもそも論としては、順序実行したものがcorrectでない、ということは“あり得ます”。これは例えばデータの制約条件(constraint)を設けてcorrectを判別するというようなケースですね。例えばx=yという制約があるデータについて、それぞれ別々のTXがx, yにアクセスし、ちゃんとserializeした上で、TX1がx=10 TX2がy=20と更新したとします。これは結果として不整合(constraint violation)が発生します。この場合のcorrectnessは後で述べるserializabilityよりも広い範囲をカバーするということになります。

実際問題としては、一貫性=consistency=correctnessといっても、広い意味でdataのconstraintまで含める場合と、そうではなくてserializableまででとどめる場合と、いろいろ段階があるということになるかと思います。一般には、一度に全部constraintまでまとめて議論すると収拾不能になるので、serializableはわけて議論することが多いようです。が、普通にconstraintまで視野に入れることもあります。（inconsistent readは、よく考えると微妙な問題が含まれることがあります。なお、これはTXの制御だけでなくアプリケーションサイドにも踏み込み内容になり、普通はなんらかのsemanticsに基づく手当が必要になると思います。）

・・・・この辺はですね。なんというか「学派」のようなものもみられましてですね。非常に興味深いのですが、ただでさえ、潜ると深海に達するTXの世界の話です。なんというかゼウスとポセイドンの神々の戦いの様相もあります。一般民間人は見てるだけ巻き添えを食らうというレベルかと。

4. TXの解釈とは？

さて、ここで話をもどして、「TXを順次実行した結果と同じ“解釈“」の「解釈」について考えます。要は意図した通り（＝解釈）にTXが処理されてほしい、ということになりますが、これでは主観的すぎて、判別関数もへったくりもありません。ので、サクッと述語論理を導入します。

すなわち、エルブラン関数を導入します。端的にいうと「あるTXに属するwriteはそのTXに属するreadのうち、当該writeの対象をreadするステップに依存する」という関数と「あるTXに属するreadは、そのTX以前に始まっているTXの当該readが読むデータのwriteのステップに依存する」という関数を設定し、再帰的に遡れるエルブラン関数を設定します。んで、初期状態を定数とします。以上で、準備完了です！（数式は内容の割には仰々しく見えるのでパス）
これにより、一定のエルブラン領域が構築されます。（すなわち、構造がつくられます。）

これで各TXを構成するステップの論理的な依存関係を評価する土台ができました。その上で、いろいろな解釈を行うことが可能になります。これはすなわち様々なcorrectすなわち、「様々なconsistency」が存在する、ということを意味します。

4-1「最後に残ったものの状態についてのコンテクスト」を解釈の基礎とする方針。
すなわち、
・ある集合に属するスケジュールの一つがserialである。（=真である要素が最低でも一つはある）
・その集合に含まれる、個々のスケジュールの構成ステップは同一である。
・その集合に含まれる、個々のスケジュールの構成最終に残っているデータについてのエルブラン・セマンティクスが同じである。

以上の場合、その集合をfinal state serializableといい、同一の解釈に属していると考えることができます。通称FSR。

何を言っているのかというと、まず最後に残ったデータを取り上げて、そのデータへの操作を処理の逆順に追っかけて行きます。まずwriteがあった場合は、そのwriteが属するTX内部でのそのデータに対する全てのreadを捕まえます。「書く前には読んでるっしょ？」って話です。んで、そのreadから、それ以前にそのデータについて書かれた別のTXのwriteを捕まえます。「読めるのならばどっかで書いてるでしょ？」って話です。んで、このつながりを追っかけていってグラフをつくると「絵」ができます。この「絵」が同じなら、そのデータに対する操作は、おなじコンテクストでしょ？って考えるってことです。んで「同じ絵の集合のなかの一つに完全に順序実行したスケジュールがあるよ」ってことです。

（最後の状態の書き込みのステップだけが同じでFSRである、という間違った教科書も散見されますが、確実に違うので注意が必要です。仮にそうであれば、NP完全問題にはなりません。）

4-2「Readのステップについてのコンテクスト」を解釈の基礎とする方針。
・ある集合に属するスケジュールの一つがserialである。
・その集合に含まれる、個々のスケジュールの構成ステップは同一である。
・その集合に含まれる、個々のスケジュールの構成最終に残っているデータについてのエルブラン・セマンティクスが同じである。
・その集合に含まれる、readのステップについてのエルブラン・セマンティクスが同じである。

以上の場合、その集合をview serializableといい、これまた同一の解釈に属していると考えることができます。通称VSR。

これはFSRであり、かつ、すべてのreadのコンテクストが同じということを意味します。

前述のグラフの「絵」のたとえでいうと、絵の、より細かい線のつながり（つまり、すべての読み込みに関する線）まで同じであれば、同じ絵であれば同じと見なすということです。（FSRは途中で切れてる線もあるがそれは影響がないので無視するというスタンスですね）

さて、実は上記のたとえの「絵が同じ」（すなわちグラフが同一）というのは、実は機械的な判定が非常に面倒と言うか、時間がかかります。どれくらい面倒かというとNP完全なぐらい面倒です。（ある一定のpolygraphを想定して、その非循環を証明する問題です。）

よってもっと簡単に”解釈”できませんか？ということになります。

4-3 「各ステップの特にwriteの競合状態」を解釈の基礎とする方針。
上記のFSR/VSRはセマンティクスを解釈するには、非常に納得性のある指針ですが、いかんせん全部のグラフを書いていちいち解釈する必要があり、大量のTXを処理するには効率がよくありません。なので、もう少し簡単にコンテクストを解釈できる指針が必要です。

そこでデータ処理の競合関係「だけ」に注目した解釈を導入します。この競合(conflict)を特にデータの書き込みについてのみ注目します。すなわち

w-w　あるTX書き込んで、別のTXがまた書き込む
w-r　あるTXが書き込んだものを、別のTXが読み込む
r-w　あるTXが読み込んだものを、別のTXが書き込む

この競合関係が維持されていれば、同一のスケジュールとみなすという「解釈」です。まあ、ぶっちゃけr-rの関係は順序は関係ないでしょ？という発想ですね。すなわち、書き込みの競合関係が同一である集合に属していれば、そのスケジュールは、同じコンテクストであると意味です。この集合をconflict serializableといいます。通称CSR。TXのcorrectnessの議論では登場しないことはないぐらい利用されるコンセプトです。

また、CSRは判別のコストが低いです。
conflict関係を抜出し、そのTXの依存関係のグラフを作成します。すべてのステップを抜き出す必要はありません。conflictの発生するTXだけ抽出すればこと足ります。その上で「グラフが循環しない場合」はトポロジカルソートにより、TXのシーケンスな順序を作成できることが保証されますので、すなわちserializeなスケジュールが組めるということになります。

余談ですが、このconflictは、実は後段で出てくるIsolationのanomalyに（結果として）一致します。すなわち、
w-w dirty write
w-r dirty read
r-w phantom read / inconsistency read
ですね。これは有用な示唆で、incorrectな状態を発生させない（あるいはTX終了時にはinvariantを保つ）にはconflictをいかにserialな状態と同じ状態に保つか？という課題に一般に帰着するということでもあります。MVCCもそうですが、一般にTXのsemanticsの議論の出発点の一つはここになることが非常に多いです。

尚、上記のserializableの包含関係は CSR⊂VSR⊂FSRになります。
VSR⊂FSRはVSRはFSRのより制限的な形なのでわかると思います。CSR⊂VSRも、まぁ大体おなじ路線で証明できますが、割愛します。

5. CSRの拡張
以上は大体、普通の教科書に書いてる内容です。が、せっかくなので、CSRの特徴を生かしたsubクラスを定義して、その有用性を拡張していきましょう。これはTXの議論ではよくある話です。

まずTX orderとcommitの考え方を導入してみましょう。

まず通常にありがちな仮定として、abortなしで考えます。すなわち、ここではcommitをしたものだけでスケジュールを考えることをします。（実はそうしておかないと、たとえばCSRであるにもかかわらずdirty readを排除できないということにもなるからです。w-rのconflictは手前のwがabortされる（または、される可能性がある）とcorrectになりません）

5-1. OCSR
TX orderを考えましょう。TX orderはわりと大事な概念で、conflictの順序を崩さずに、TXの発生順序順にTXを終了させる（TXの実行は別に並列になってもかまわない）、というルールです。完全にserialでもなく、かといってでたらめにconcurrentでもないという状態で、言ってみれば「ユーザーから見たときに違和感のない順序＝先に走ったものから先に終わる」ですね。この順序が保証されること order preservationと言います。

TXの順序実行が保証されるという制限をつけたCSRのサブクラスをOrder-Preserving Conflict Serializablityと言います。通称 OCSR。

これは以下のような特徴をもっています。（証明とかありますけど、すげー量で泣けますので省略）

・一般的な2PLでできたスケジュール⊂OCSR　の関係になっている
さらに言うと、lockテーブルを拡張したorder sharingなlockルールで形成される2PLのスケジュール（いわゆるO2PL)と「完全に一致」します。すなわちO2PL＝OCSRになっています。

・OCSRなスケジュールは、多層レイヤーでのTX実行の基盤になる
一般に単純なTXスケジュールを拡張し、操作対象をページモデルではなく、より上位のObjectモデルを利用することでスケジューリング・パワーを拡張することが可能です。Objectモデルでは、相互の操作の順序交換可能性をベースにしたreducibilityのコンセプトを軸にserializableかどうかの判定を行って行きますが、その過程でOCSRを利用することが可能です。

5-2. COCSR
また、TX orderとは別に、commitの順序をTXのconflictの依存順序に合わせるという制限を課すルールもあります。これをcommit order preservationと言います。これは実は特にabortや障害時の処理を考えた場合に、きわめて有効なルールです。通称COCSR。非常に重要なserializableなクラスです。

これもまた以下のような特徴をもっています。（これまた証明とかありますけど、すげー量で泣けますので省略）

・Strong 2PL(SS2PL)で構成されるスケジュールと包含関係を持ちます。
2PLの中で、w/rともにロックをとりTXの終了までリリースしないルールの2PLであるStrong 2PL で生成されるスケジュールは、COCSRに完全に含まれます。
すなわちSS2PL⊂COCSR

・楽観lock実装のひとつであるforward-oriented optimistic concurrency control (FOCC)により生成されるスケジュールはCOCSRが保証されます。
すなわちFOCC⊂COCSR

・もっとも基本的なrecoveryスケジュールであるrigorousness（通称RG）のルールを守った場合は、そのスケジュールはCOCSRであることが保証されます。（これは実はRG＝SS2PLであることも背景にはあります。）
すなわち RG⊂COCSR

・global serializabilityとの関係
えっとこれはまた別の機会にまとめますが、分散TXでもserializabilityというものが存在します。このベースになるクラスとしてCOCSRが利用されることがあります。

・尚、前述のOCSRとの関係でいうと、包含関係になり
COCSR⊂OCSRになります。すなわちCOCSR⊂OCSR⊂CSR⊂VSR⊂FSR

以上のCSRのサブクラスは全てserializableです。ということはつまりcorrectであり、すなわち、consistentであるということです。一般に「一貫性がある」といっても、実に様々なルールやセマンティクスがあることがわかります。また単なるCSRではなく、それを拡張したモデルもTX処理では様々に活用できることもわかるかと思います。

6. Isolationレベルとは何か？
んで、まずserializableが明快になったところで、次に普通によくありがちなIsolationレベルの話しをもってきます。実際にRDBMでTX処理を行う場合に設定するものですね。
まぁ、要するに現実の話はどうか？という議論も加えてみましょう、ということです。

まず前提ですが、IsolationレベルがSERIALIZABLE以外のもの、すなわちREAD_UNCOMMITTED, READ_COMMITTED, REPEATABLE_READは原則として、correctではありません。

大事なのでもう一度いいますが、SERIALIZABLE以外のIsolationレベルでは一貫性は“無条件”では担保されません。大抵のRDBMSではIsolationレベルのデフォルト設定は、REPEATABLE_READに設定されており、したがって、そのまま使うと、基本的にデータ不整合が起こる可能性があります。(これは常識ではありますが、意外に忘れている人もいます）

もともとIsolationレベルの「定義」は「〜ができる」という定義ではなく、「〜という不整合は排除できない」という定義です。ややこしいことに、たとえばREPEATABLE_READあたりは、英語として、「何回読んでも同じ」という風に読めるので誤解が多いというか、たぶん誤解しかないので、非常によろしくないです。本来はphantomを排除できないレベルのIsolationという定義です。

なので、REPEATABLE_READに設定する場合は、phantomを排除できるように自分で何らかの手当がいりますよ、ということになります。「何回読んでも同じ」ということではないです。

Isolationレベルの設定は、漏れてしまうanomalyを明確に意識して手当することが主たる目的です。これもまたcorrectとアプリケーションサイドでどう担保するか？、consistencyをどう担保するか？という問題そのものです。

理想論から言うと、consistencyの確保はミドル側で行うのが基本です。一貫性の確保は可能な限りアプリケーションサイドには意識させず、透過的に処理できる基盤を提供するということが本筋です。Isolationレベルは、本来はあくまでconsistencyが担保されるレベルに設定する方が望ましいわけです。ちゃんと実装されているDBであれば、普通にserializableに設定して、やりたい処理を全部放り込めば、かっちりserializableにしてくれので問題なし！という風になるはずです。

が、DBサイドの実装が割とアレなケースだと、残念ながらr/wが偏るような場合では、パフォーマンスがよろしくないということになります。（普通はロック実装がアレなせいだと思われます。）よってserializableは利用しないというのが現実でしょう。なかなか理想的なTX処理実装は困難であるというのは、実感としてわかるかと思います。

7 まとめ
以上は単ノードでのconsistency(correctness)の話です。一般に分散処理では、これに加えて、データのレプリケーションの話が入るので、より複雑になります。ただし、分散処理においても、conflictの考え方やコンセプトは極めて有効な武器ではあるので、まずは単ノードでのコンセプトをちゃんと理解しておく必要があります。（そうしないと、たとえば、serializabilityとlinearizabilityを混乱するようなことになってしまいます）

このあたりは自分でももう一度再勉強して、ちゃんとまとめようと思っています。単純にタネンバウム本読んで、ということではなく、あくまでまずはちゃんと基本のTXを理解した上でないと、その応用に加えて、独自の考え方が加味されている分散TXは、とても「ちゃんと」理解できるものはありません。

8.どう考えていくのか？
まずもって、一貫性やらTXやらの具体的な実装や議論の前に、「何が問題なのか？、そしてその解決のために何が検討されてきて、どんな理論的な道具立てが準備されてきているのか？」ということを理解しておくことが肝要でしょう。

前述のTXの話にしても細かい話題に触れていけば、lock・MVCC・reducibility・階層処理の話も必要になります。また、当然、異常系のabort・recovery・log処理も考慮していく必要があります。これらもまたcorrectnessをどう担保するか？という問題そのものに関連してきます。

上記のような理論的な背景を考えれば、「NoSQLは一貫性がなくて、RDBMSは一貫性がある」という単純な言い方は、見方によっては、非常にナイーブな言いようになる、というはよくわかるかと思います。

最初の戻りますが、TXは非常に整理された数学的な背景をもつ技術です。それらを踏まえてた上で、その考え方を換骨奪胎し、分散処理なり、次世代のTX制御技術なりを作り上げていくことが今後必要とされるテクノロジーではないかと思います。遠すぎて死にそうな感じですが・・・

ま、そんな感じ。