Making Snapshot Isolation Serializable 再考
Making Snapshot Isolation Serializable 再考
■2013年的な位置付け
まずちょうど年度の開始なので、今年は自分的にはRDBMS関連の位置付けとか整理しておきます。去年の後半あたりからの匂いですが、NoSQL的な発展と合わせて、本格的なDB回帰が始まっている感じです。NoSQL系のほぼ致命的な弱点の一つがtransaction処理であることは指摘も多いところです。要するにデータが書き込めても不整合が発生しますね、ということになってしまいます。これではなかなか使えない、というのが現状でしょう。
なので、RDBMの最良のノウハウであるtransaction処理とNoSQL的な分散処理をちゃんと整合性とれるようにしましょう、という自然な流れは従前よりもより強い要請が働くでしょう。(できるかどうかは別ですが。) それで、そろそろなんかその手のものがRDBMSサイドや分散処理系から出てくる感じではあります。
また、オンメモリー系にも焦点があたりつつあります。何度目だ？という話はありますが、まぁ不揮発性メモリーでの処理は従前のものとは根本的に違うので別物と見るべきでしょう。（「従来のDBをそのままメモリーに乗っけました」ってのは、普通に「RDBMのキャッシュ増やしました」というものとアーキテクチャ上の違いはあんまりないので、そうでないものが出てくると思います。）
ということで時代的にはRDBMSの技術の再投入が製品として、そろそろ出てくると思います。そんな流れで、次のDBのカタチも模索が始まるのが本年だと思います。RDBMSの、というかDatabase一般の、技術の柱の一つであるTransaction処理は一回復習しておきたい。特に、Transactionの中でもここ10年でもっとも進化した感もあるものの一つが、MVCCですが、これは分散処理との親和性も高いです。そのMVCCで現在もっとも実装されていると言われているSSI(Serializable Snapshot Isolation)は、個人的に再勉強の価値あり、という感じです。
(尚、MVCCと言っただけ「重い」という認識の方は時々いますが、かなり変わってきています。)
■概略
Snapshot Isolation(以下SI)はTransaction(以下TX)のIsolationの達成手法としては、現在では伝家の宝刀に近い技術です。基本的な流れはMultiVersion Concurrency Controlに属し、その実装手法として、商用のRDBMSではかなり実装されてきています。その上に、かなりの論争にもなって来ました。曰く
赤い会社「完全にserializableですよ。」
その他大勢「いや、SIではfull-serializableにはならないし。」
赤い会社「いや、ほぼ同じだし。」
その他大勢「なんだよ、ほぼ同じってww」
赤い会社「だからこのベンチマーク（TPC-C）でちゃんとanomalyなしだし」
その他大勢「いやだから、そのベンチマークがそもそもだな・・・」
あれやこれや・・・
（以上、脚色なし）
過去、そんな論争があったのがSIですね。ま、この辺りのガチンコ勝負は、DBを真面目に取り扱った人なら周知の通りです。最近ではやっとOSS(Postgres)でも実装されるようになって、その意味でも、その界隈ではもはや常識に近いレベルにまで来ていると思います。
SIではTX開始時点で当該TXで必要なデータセット（したがって、どうphantomを除去するかという問題も考慮する必要があります・・）のsnapshotを取ってきてそのデータセット上でread/writeの処理を行います。したがってまずデータが元データから分離されているので、repeatable readになりますし、また自分でwriteしたものは当該TXのライフサイクル内部では、自分で参照できます。その上で、commit時点で、他のTXでも参照することができるように値を書き出します。ただし単純に上書きするのではなく、追加的に別のversionを生成するという書き出しをとります。したがってversionが複数できます。よって、multi-versionになります。
concurrentなTXが走っている場合は、上書きにより前のversionが後続で読めなくなるanomaly(Lost Update)が発生するので、その不整合を防ぐためにいろいろ手を打つ必要があります。通常は先にcommitした方を勝ちにして、後続の書き込みをabortさせる、First-Commit-Winsを適用することが普通です。また、このSIは理論上リードロックが発生しないため、通常のS2PLのロック機構でserializableを保証するconcurrency controlに比べて、圧倒的にパフォーマンスが良いことは、特に異論のないところです。
ただし、データのセマンティクス上では、複数のTXが走っている最中に、同一の値を参照した上で、「別々のページ」にお互いに不整合が発生する書き込み処理を、きれいにisolateして行う事ができてしまうため、常に不整合が発生する可能性があります。これは上記のFirst-Commit-Winsルールを適用しても発生してしまいます。これが一般にwrite skewといわれるanomalyで、特にSIでは厄ネタでした。
上記の赤い会社の論争は実は赤い会社のデフォのSERIALIZABLEのisolationレベルの実装がSIになっていて、（その結果、当然他社のDBのSERIALIZABLEよりも超絶ぶっちぎりで速い、だがしかしanomalyが発生するわけ・・）んで、各社が何そのプロレスみたいな反則w？とお互いに釣りネタ満載の場外乱闘になっていたわけです。
そんなこんなで、まぁ単純なSIではserializableにはなりません。無敵ではないということです。ところが、このSIをSerializableにできますよ、というの理論・実装が普及してきています。コイツはなかなか画期的で、多分この先10年はserializable実装は、よほどの事がない限りこれがデファクトでしょう。
■Serializable Snapshot Isolation
・Serializable Isolation for Snapshot Databases
http://ses.library.usyd.edu.au/bitstream/2123/5353/1/michael-cahill-2009-thesis.pdf
（引用されるのは短いバージョンの方が多いのですが、長いヤツちゃんと張って置きます。こちらのほうが読みやすい。2009年版ですが、こちらにちゃんと書かれていますが・・・）
SIで最も有名な論文はSIGMOD2008でベスト・ペーパーを取ったこの論文なのは論を待たないでしょう。DB界隈では読んでない人はいないと思います。「俺っち、Oracleプロだから！」って人に限って、どうゆうわけだがこの辺読んでない人大杉栄状態なので、まじでそーゆー人は読んだ方がいいです。・・・ところがこの論文は結構難解というか、部外者が読むには敷居が高いというか・・いや、読むには読めるのですが、肝心かなめの部分が、さらっと流れすぎている気がします。
んで、実は元ネタの論文があって、こっちが本星だったりするわけです。実際上記のCahillの論文は以下のFeketeの論文を十カ所以上に渡って引いておりまして、というか・・・そもそもそのCahillの論文指導がFeketeでして、まぁ要するにこっち読んでおかんとなんだかわからん、という話です。んでそのFeketeは某分散系のLynch学派のメンバーでして、・・・要するにそういうことです。
・Making Snapshot Isolation Serializable
http://www.cse.iitb.ac.in/dbms/Data/Courses/CS632/2009/Papers/p492-fekete.pdf
コレを読まないとなんで「r-wのanti-dependencyが2つあるとserializableじゃないriskがあるのか」ということが、分からない。（超頭のいい人は多分、わかるとは思いますが・・自分はあまり頭が良くなかったせいで、分からなかったわけですが、この論文読めばわかります。）
ここに辿り着く人が何人いるかわかんないし、辿り着いている人はもう分かってるのでそんな解説いらんわい、となると思うので、現時点想定読者は全日本的に5人程度なんですが、自分目的でメモっておきます。マニアックすぎて誰も読まねーとか言われるわけですが、自分が忘れるのでメモる感じですよ。
（あ、一応「俺はTXはガチだから」という人は絶対読んでおいた方いいと思いますよ）
前提1
MVCCとSIとではSIの方が制限的である。これがポイントのひとつ。
MVCCはTX発生時点では、そこまでにwriteされたversionを読むことが可能であって、commitの有無は理論上は直接制限されません。(SIが有名になりすぎて、MVCCと混同されている方も居ますが、MVCCはもっと広い概念です。) しかし、SIの方は明確に、「読む込む時点で直前にcommitされたversionを読む」という制限がかかります（強制）。したがって、TX開始時点で、その読む込みversionをwriteしたTXはすでにcommitを終えています。したがって、論理的には、当該開始されるTXと、開始するTXが読み込むversionをwriteするTXはconcurrentになりません。したがって、w-rまたはw-wのconflictは発生しません。つまり、仮に発生するのであれば、そのconflictは必ずr-wに制限されることになります。（この前提はFeketeの論文で詳細に書いてありますが、コレ以降の論文はほぼ全て「そんなこと知ってるだろ条件」になっているので注意しましょう）
前提2
Serializableにならない、ということはcyclicになるということです。
これはserializabilityの基本定理で、証明は背理法で行いますが、まぁ割と前提でいいかと思います。んで、conflictのグラフがcyclicになる可能性がある場合は、少なくともノードで二つエッジで存在しないといけません。そうでないと「輪」にはなりません。ただし、二つあったからといって輪になるわけではありません。したがって、r-wのantidependency二つがグラフでつながると、実はヤバい可能性が発生し、かつ、それはそのときに限ることになります。
以上が前提になります。
■Making Snapshot Isolation Serializableの概要
それで肝心の論文の構成は以下です。
1. Motivation and preliminaries
2. Transactional history theory
3. Program conflicts and static dependencies
4. Analyzing an application
5. Avoiding isolation errors in the application
6. Conclusion
以下、概略と内容です。ポイントも順番に記述していきます。
（一応、論文は片手に持っている前提で書いています）
1. Motivation and preliminaries
基本的なSIの説明をしています。その上で、問題となる二つのSkew(anomaly)を丁寧に説明しています。なので、どの種類のanomalyが発生するのか？をそのために何をするのか、を把握しています。有名なのは、Write Skewですが、MVCC固有のanomalyとして、Read-only Transaction Skewもちゃんと解説します。あとはphantomについてはなんでreadだけで、writeがないの、ということについても言及しています。以下、Skewを二つ解説します。
○Write-Skew
これは別のエントリーでも書いているので、簡単にしておきます。MVCC絡みだとそれこそ、耳タコぐらいに出てくるので、暗記している人も多いかと。
典型は、
・X+Y > 0 という制約条件
・初期値 X= 70 Y=80
・SIでのIsolation
・T1が X0とY0にアクセスして、Xから100だけ引く。
・T2が X0とY0にアクセスして、Yから100だけ引く
・それぞれのTXは成功してしまう。
R1(X0,70) R1(Y0,80) R2(X0,70) R2(Y0,80) W1(X1, -30) C1 W2(Y2,-20) C2
・んでこれは制約条件を満たさない
・First-Commiter-Winsでも検出不能
○Read-Only Transaction Skew
えっとですね。このanomalyは多分Web系の人は知っておいたほうがいい気もします。俺そっちは疎いので良くわかりませんが、普通のB2Bに比べて、readのワークロードが重いはずなんで。
SI下では、すべてのRaed onlyなTXはserializableに実行されると想定されることが多いです。というのは、
1.Read onlyはインスタント
2.TX発生時点でのcommit済みのデータを読み込む
3.commitされていないデータは見えない
・・・なので、これだけ見ると普通にserializableでしょう。ということになります。がそうではないです。
・Read Only Transaction Anomaly
・Xが決済アカウントで Yが貯蓄用のアカウント
・それぞれ初期値はX=0 Y=0
・T1でYに20だけdeposit
・T2でXから10だけ引き出す
・当座借越の金利はX+Yがマイナスになった時点で発生 金利は1とする
・T3でXとYの残高を参照する。（read only）
・さて、T1-T3をSI下でconcurrentに実行する
・R2(X0,0) R2(Y0,0) R1(Y0,0) W1(Y1,20) C1 R3(X0, 0) R3(Y1,20) C3 W2(X2,-11) C2
・T3のアウトプットは X=0 Y=20できれいに完了する。
・T2-T1でserializeすると貸越になるので、金利発生でX=-11 Y=20
・T1-T2でserializeすると貸越なしで、X=10 Y=20
・いずれにしても、T3はfinal stateとは一致しない。また、残高照会でX=0 Y=20だと、なんで金利が発生するのかわからない。・・という散々な結果。
（つまり本来はできてはいけないTXができてしまっているということです。anomalyとして検出しないといけないというわけです。）
・ちなみに、このケースは2PLで除去可能
あとはこのセクションでは、Predicate readでのanomalyの話が書かれています。特にPredicate-Based Write Skewは見ておいた方がいいでしょう。単純なSELECT FOR UPDATEでは除去できないという話です。このあたりは、「あー、やっちまったかも」的なDBAの人もいると思いますが・・・
この後のセクションで、SSIではこれらのanomalyをきっちり検出しますよ、というのが論文の目的になります。
2.Transactional history theory
まず肝心要のDependencyの話が展開されています。主要なTheoremだけコメントします。
Definition 2.1 Transactional Dependencies
インターリーブするSIのhistoryにおいて、以下、
item-write-read dependency ＝ Tm ->(i-wr)-> Tn
（mで値を生成し、nで読む。i-rwはitem read write dependencyの表記）
item-write-write dependency ＝ Tm ->(i-ww)->Tn
（mで値を生成し、immediate successorのnで別バージョン生成）
item-read-write dependencyまたは item-anti-dependency ＝ Tm->(i-rw)->Tn
（mで値を読んでおり、immediate successorのnで別バージョン生成）
predicte-write-read dependency ＝ Tm ->(pr-wr)-> Tn
（mで値を生成し、nのpredicate readで読む。ただし、nの開始前に、mでコミットされていること）
predicate-read-write dependencyまたは predicate-anti-dependency ＝ Tm->(pr-rw)->Tn
（mで値をpredicateで読んでおり、nで別バージョン生成。nのコミットは、mの開始後）
以上のdependencyをまとめて、Tm->Tn dependencyとしています。predicate writeは存在しないので、入っていません。おなじみのconflictを定義し直しただけです。
次にまず、DSGの定義が続きます。
Definition 2.2 DSG(H) Dependency Serialization Graph for history H
・有向グラフ
・マルチバージョンhistory
・頂点(ノード)はTXのコミット
・ラベルつきエッジ（TmからTn）はそれぞれに対応
という定義になります。
その上でサンプルとしてExample 2.1のグラフが提示されます。
W1(X1) W1(Y1)W1(Z1)C1 W3(X3) R2(X1)W2(Y2)C2 R3(Y1) C3
（serializable orderはT1-T2-T3になりますね。ボールドがrw-dependencyになります）
これも問題ないでしょう。グラフの記述上はr-wは重要なので時に記法を変えるということをやっています。留意すべきは、ここでのグラフは基本的にTX間のdependencyであり、このあとでprogram同士のdependencyに”lift”させる方針をとります。
次に、anti-dependencyにフォーカスします。anomalyをふくむSI historyについてSI historyのDSG(H)の非循環を示します。・・というかserializableでない時にはDSG(H)が循環する（割と特徴的な形で）ということ示します。ここからが本命。
Remarks 2.1
・TX開始時点で読めるはコミットされたものだけ
・よって Tm->wr->Tnの場合、Tmはコミットされている
・よってconcurrentではない
・Tm->ww->Tnも同様（こちらはFirst-Committer-Win）
・ただし、仮にTm->rw->Tnがあればconcurrentな場合はある。
・またはTmが完全に先行している場合
・ただし、Tnが完全に先行することはない。そーなるとanti-dependencyが成立しないので。（最も最近のバージョンを読むというルール）
その上で・・・
Lemma 2.2
・仮にTm->Tnのdependencyが存在するのであれば、TmはTnの前にスタートする。そうなると、上記Remarks 2.1より
・w-r w-wであればconcurrentではない
・r-wであればconcurrentまたはrが先行する
よって、
Lemma 2.3
「仮にTm->Tnのdependencyが存在し、かつそれらがconcurrentであれば、それはTm->rw->Tnである」
それはAnti-Dependencyと呼ばれる
要はブログの冒頭での展開です。言われてみれば、なんだ当たり前だろ、という話ですが、この瞬間にTXのSerializable判定の厄介なグラフの依存関係が一気に簡略化されたのがわかります。いわゆるSGT(Serializable Graph Testing)より格段に優れていると言われるところですね。
んで、このあと、ありとあらゆるMVCCの論文で引用されるTheoremにつながります。これも単純です。
Theorem 2.1
・HをSnapshot Isolation下で生成されたマルチバージョンのhistoryとする。かつ、Hはserializableではないとする。この時、
1 少なく一つは循環するDSG(H)が存在する
2 それらの循環の中には、三つの連続するTransactionが存在する
・ただし三つのうち最初のものと最後のもの同一でもよい
・かつ、最初のものと二番目のものはconcurrentであり edgeが存在する
・かつ、二番目ものと最後のものはconcurrentであり edgeが存在する
なお、edgeはanti-dependencyになる
Proof
Serializableでないとすると、dependencyのcycleが存在する。
（cycleがなければトポロジカルソート可能よってserializableで矛盾）
・任意のcycleをとる
・その最初にコミットタイムがくるTXをT3とする
・T2をT3の先行、T1をT2の先行とする
・ここでT2とT3がconcurrentでないとすると
・その場合、T2が最初に終わるので、T3が最初のコミットと矛盾
・または、T2が開始する前にT3が終了する場合はLemma2.2に矛盾
・よってT2とT3はconcurrentである
・したがって、それはanti-dependencyになる
・T2とT1についても同様
以上。
これも言われれば、まぁそりゃそうだになるのですが、いきなりデフォルトで話されるとなかなか辛い、というか理解不能っすよ。
このあと、SI-RW Diagramの話になります。これは、「話をわかり易くするために」今までの考え方はUser-orientedなので、Scheduler-orientedな考え方をしてみる、という流れなのですが、基本的に証明とか好きじゃない人用で、個人的にはそれは混乱するだけだろう、と思うので省略します。敢えて言えば、「実装的には、こーゆー風に考えれば、今までのTheorem理解できるよね？」という助け舟ですが、助け舟の方が難易度高い感じでアレです。いや、人によるんでしょうが、TX系をやっているひとから見ると不要ですよ。
（・・・この辺はTX系の人間の少なさの悲哀ですね。不勉強な人にも説明しないとイカンので、ちょっといろいろやってます的なアレです。わかんねーヤツはほっとけばいいと思うんですが、まーそうも行かないのでしょう。）
それよりも、ここからが真骨頂で・・・んじゃーそのご大層なTheoremで本当にanomaly検出できますか？という話ですね。
まずWrite Skew
・R1(X0,70) R1(Y0,80) R2(X0,70) R2(Y0,80) W1(X1, -30) C1 W2(Y2,-20) C2
・SI下
・TX1-TX2はconcurrent
・ここで、R2(X0)->W1(X1) R1(Y0)->W2(Y2)でanti-dependency検出
・よってDSGは循環（Tx1=Tx3の例ですね）
・よってanomaly に決定。
次にSI Read-Only serialization anomaly
・R2(X0,0) R2(Y0,0) R1(Y0,0) W1(Y1,20) C1 R3(X0, 0) R3(Y1,20) C3 W2(X2,-11) C2
・R2(Y0)->W1(Y1) R3(X0)->W2(X2) concurrentでanti-dependency(r-w)
・W1(Y1)->R3(Y1) dependency
・Tx1->Tx3->Tx2->Tx1でDSGは循環
・よってanomaly
まるで計ったかように見事にanomalyを検出します。素晴らしい。このあたりの美しさがTX理論の魅力ですね。自分でも読んでて「おおっ」と膝を打ちました。
3.Program conflicts and static dependencies
ここでは、いかにして複数のTXなプログラムが静的解析でSI下でanomalyなしである、と信頼できるか、という問題をとりあげています。んで、その実例が、4章になります。えっと、ですね。最初に上げたCahillの論文はこのあたりを批判して乗り越えてますね。要は「静的解析？いやそれ意味ないでしょう。そもそもparameterizedされたプログラムの方が多いし。てか静的解析できるDBAとか何人いるんだよ？」という話です。このあたりは前出のCahillの「俺TUEEEE」論文を読んで頂ければよいです。とはいえ、そもそもその論文での批判対象を理解しないと、なんで「俺TUEEEE」なのかわからない感じなのでアレですが。
余談ですが、Jim Grayもそうですが、TX界隈の人は「俺TUEEEE」な人が多い割には、TUEEE度合いを自分で解説しないといけない感じで、どうなんだそれは論文が多くて、趣き深いですね。
4.Analyzing an application
実際にTPC-Cのベンチマークを例にとりながらSDG(A)を構成していく、という内容です。基本的にはテーブルと取引トランザクションの内容からSDG(A)を作成して、anti-dependencyを検出するという作業を行っています。自動検出については懐疑的です。尚、現在の潮流はむしろ実行時に検出すべき、という方向が主流ですので、この論文の方法はあまり役には立たないかな、という気はしています。なのでパスしていいでしょう。・・・あ、まぁこのベンチマークの改良がこれ以降各所で話題にはなるので、一応時間がある人はサクッと読んでおいてもいいです。
まったく余談ですが、業務屋的などんな実務をモデル化したらこうなるんじゃいという感じがいつもするので、現実知らないにもほどがあるとは思うことはありますが、それなりリサーチはされているという説あるので、その辺はまぁアレで。
5.Avoiding isolation errors in the application
さて、ここからは実装的にどうやってこの手のanomalyを発生させないようにするのか？ということになります。
実は、この中のmaterializationは、結構他でも応用されている技術（例としては、global serializationのconflictを各プロセスで検出するために、「無理矢理」global conflictをlocal conflictとしてmaterializeする手法もこれにあたります。）だったりします。
尚、この辺の理屈とCahillあたりの実装の論文を読んでおかないとPostgresあたりのSSIの実装が読みづらいはずです。ポイントはあの程度の少ないコードベースで、TXの難問中の難問のserializabilityの問題を、制限があるとはいえ解決している点だと思います。
えっと、本論ですが以下
・dangerous structureの有無がわかれば、SI下ではserializableかどうかわかる。
・しかし制約条件が明示されて無くて、実行時にserializableにならないというケースもありうる。
・アプリケーションの機能を変えずに、少しの変更で、dangerous structureを避けることができるということを説明したい。
・まずはDBAはdangerous structureを特定する必要がある。
・これはvulnerableなエッジをみつけて、そのエッジへの頂点のアプリを変更して、vulnerableでなくせばよい。
ということが話の趣旨です。
5.1 Materialize the Conflict
前提として、dangerous structureはふたつのvulnerableなanti-dependencyをもっているということがスタート地点です。このvulnerableを除去するには、conflictをmaterialize(実体化）する新しいデータアイテムを作り出して、そのアイテムの更新処理に、vulnerableなプログラムを関わらせればよい、という戦術です。
例）
・適当にConflict(Id, val)のテーブルをつくる。
・それぞれの実体化したいanti-dependencyなエッジについて(X,0)[Xはエッジに固有の値]をinsertし、最後にanti-dependencyの両端のノードのアプリケーションに以下を追加する。
UPDATE Conflict SET val= val+1 WHERE Id=X ;
・これによりFirst-committer-Winsルールが働く、よってconcurrentではなくなる。これはpredicateなコンフリクトでも有効といえる。
（次のPromotionが使えないようなケース、たとえば、TX間で共通の値がない場合には、materializeが有効な手法になります。）
また、vulnerabilityを除去するのに単一の値を利用する必要はないです。conflictはプログラムそのものというよりも、与えられるパラメーターにより発生することがしばしばあるので。なので、materializeにはパラメーターを利用する方法もあります。例えばPredicateベースなWrite Skewの例では、制約のテーブルを別につくってその制約を破らないようにする方法もこれにあたります。conflict tableのように単一の値を利用しようとすると、論文のWrite Skewの例では、同時に二つのタスクを二つの別々の人間にアサインできなくなります。ただし、その変形を用いることで可能になります。たとえば、TotalHours(eid, day, total)というテーブルと作って、WorkAssignmentを更新する場合に、同時にTotalHoursも更新する方式にします。これにより、単純にvulnerableなconflictの発生をおさえます。
要するに、共有に関わるテーブルを持たせて更新処理を強制して、concurrentのTX同士において、強制的にconflictを実体化させるという手法です。引っかかればconcurrent中止で、引っかからないのであれば、そのまま処理続行ということになります。
5.2 Promotion
もっとも簡単な方法は、要するにSELECT FOR UPDATEにすることで強制writeに変更して、first-commit-winを適用させ、concurrent処理にさせないという戦術です。これをPromotionと言っています。これによりr-wのanti-dependencyが解消します。
（まぁ極論するとやばそうなTXがやばそうな値に処理を行うときは、有無を言わさずFOR UPDATEにしておけ、というなんか意図しない結論になりそうですが、まーそーゆー趣旨っぽい感じですね。）
6.Conclusion
あまりたいしたことは書いてないですね。
■まとめ
上記が、Making Snapshot Isolation Serializableの概要です。これのサマリーが今後のSSIでは頻繁に利用されます。研究の傾向としては、あとはruntimeでの検出をどうするか？という問題と負荷の問題が検討されています。より実装よりの話題が多いですね。特に問題になるのはdangerous structureの検出の仕組みについて、concurrentな3つTXの依存関係のうち、T1→T2 T2→T3のそれぞれのconcurrecyを把握しておく必要があるときに、T3が走り出す前に、T1が完了してしまう可能性があるということです。つまり、「よって、完了したT1についての依存関係をどこかに保持しておく必要」が発生します。これは、冷静に考えるとちょっと（というか場合によっては、かなり）厄介なことになります。そんな感じで実装を工夫する必要があります。
いずれにしても、静的解析ではなくてruntimeでできるだけserializableでないものは検出しましょう、ということが実現されつつあるので、（今までだとSGTなので、要するにpolynomial timeの時間がかかるわけで、大量TXになったときに死ぬ可能性が高い）これは、それなりのTXの理論的・技術的なブレイクスルーになっています。さらに延長線としては、分散環境でのSSIというやつでして、まずはベースとして、1-Copy-Snapshot-Isolationが出発点になることが多いようですが、この辺はまた別の機会にまとめます。
とりあえず、これだけ書いとけば、自分的に後で見直す時には十分なんで。
（あー間違っていたらすみませんです。一応、念のため書いておきますが。）
以上です。
