Read only transaction anomaly 現代的な問題として
対象読者：
某Pjrに関わっている人全員。あとはSAPのHANAとかのHTAP系を使っている人。あとはDB系の人とかそっち系の人。
内容はRead only transaction anomalyがHTAPのなかでかなりの厄ネタになるという指摘と、その解決素案の提示になっている。前提知識はMVCC（MVTO、SSN、SSIとかその辺）。
■Read only transaction anomaly
MVが前提で発生するtransactionのanomalyのこと。整合的なsnapshotをとっていて、かつリードオンリーであるにもかかわらず、どのようなserialization orderをとっても論理的に起こり得ない状態を読み出してしまうskewを指す。
わかりやすい例をSSIの論文から持ってくる。
https://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/2009/Papers/p492-fekete.pdf
H: R2(X0) R2(Y0) R1(Y0) W1(Y1) C1 R3(X0) R3(Y1) C3 W2(X2) C2.
T1はR2(Y0)をT2コミット前にW1(Y1)で上書きする。また、T3のR3(X0)は、すでに走っているT2のW2(X2)でT3コミット後に上書きされる。
よってanti-dependencyは
yについてT2→T1
xについてT3→T2 になっている。
またR3(Y1)は直前のT1でコミットされたY1を読んでいる。
よって、通常のdependency(w-r)は yについてT1→T3 になる。
よってT1→T3→T2→T1で循環する。
このときT3について注目すると、R3(X0) R3(Y1) C3であり、yについては直前にコミットされた値と読み、xについてはT2が未コミットであるから当然コミット前のx0を読んでいる。普通にT3としては最新のコミットされた値をリードしており、なんら問題はない。・・・ように見えるが実際は「論理的に起こりえない状態」を読んでいることになってしまっている。
具体的には
H: R2(X0, 0) R2(Y0, 0) R1(Y0, 0) W1(Y1, 20) C1 R3(X0, 0) R3(Y1, 20) C3 W2(X2, −11) C2.
が例になっている。
T2が読んだ値は X=0 Y=0 で X=-11をセット
T1はY=0を読んで、Y=20をセット
仮にserialization orderを考えると、T2→T1でもT1→T2でも X=-11 Y=20 （T1→T2だと、T2ではY=0が読めないので成立しないが、concurrentで考え、T2ではY=0を読んでいるものとする）
ここでT3ではX=0 Y=20で読んでいるが、
本来T3の読む値は
T3→T2&T1であれば、X=0 Y=0
逆にT2&T1→T3であれば、X=-11 Y=20になる
仮にT2→T3→T1であれば、T3はX=-11 Y=0
T1→T3→T2であれば、T3はX=0 Y=20で読めるが、そもそもT2のY=0が読めない、というか矛盾するのでありえない。
つまり、どうやってもX=0 Y=20をT3で読むことはできない。つまり「本来読むことが論理的にできない値を読んでいる」ことになる。
以上は普通にread only transaction anomalyの話であり、ここでの論点は以下のようにHTAPでの扱いだ。周知の通り通常の範囲では、これは相当のプロトコルで排除できるというか、するので問題にならない。
■HTAPでの問題点
現状のHTAPはパフォーマンスを出すためにOLTPで処理するデータセットとOLAPで処理するデータセットの構造をかえて、変換のつなぎをsnapshotで行うことが多い。この時のsnapshotはふつうにconsistent snapshotをとる。
SIでの2大skewの、もう一方のwrite skewについてはそもそもOLTP側の更新処理で衝突するので検出が可能であり、あまり問題になる気がしない。が、OLAP側でのread only transaction anomalyは ”consistent snapshot”をとっていて、OLAP側では更新処理もおこなっていないにもかかわらず、不整合を発生させる可能性がある。そもそも作成したconsistent snapshotが、OLTPサイドではありえない状態を写している可能性があるということだ。（この点では、これはHTAP固有の問題ではなく、オンラインでsnapshotでリードレプリカをとるものはすべて問題になるとも言える。）
例示されているケースではT3がOLAPレプリカでの処理だと考える。
OLTPサイドとOLAPサイドで分けて見てみる。
- H:OLTPサイド: R2(X0) R2(Y0) R1(Y0) W1(Y1) C1[T1] W2(X2) C2.
- 時刻T1でOLTPからOLAPにlog ship。コミット済みのY1がreplicated
- 前提としてOLAPサイドでは初期のX0, Y0のsnapshotレプリカはとってある。
- H:OLAPサイド: [T1]R3(X0) R3(Y1) C3
この場合、OLAPサイドでread only transaction anomalyが起こっている。
（なお、consistent snapshotは本来閉じた系の中でのメッセージの到達・未達を考慮したうえでの一貫性のある系自体のsnapshotのことであり、ACIDの意味でのConsistencyとは関係がない。）
このanomalyをHTAPのような仕組みの中でどう防ぐか？が問題になる。
■どーすっか？
1. 非同期バッチ処理でreplicaをとる
要はconcurrentが走っているtransactionがまったくなくなった段階（quiescent）で、その隙をねらってreplicaをとるという方式。あるタイミングでtransactionの開始を一時的にストップすることができるのであれば可能ではある。普通は流量の少なくなった段階で全部キューに放り込んで待たせて(delayed write)、その間にsnapshotをとるか、そもそも本日の業務終了で受けつけないという例の夜間バッチ処理的な方法をとるかする。ただこれだと、正直HTAPである必要はあまりない気がするわけよ。
メリット：read replicaの整合性が確実に担保される
デメリット：concurrentなwriteがどかどか走ることが続くといつまでたってもreplicaが作れない。
とりあえず最終手段として残しておく案だと思う。
2. writeのabortで処理
これはOLTPサイドでのr-wの検出による形になる。ある意味一番の王道。これを検討してみる。
・単純なMVTO方式の場合
偽陽性上等で循環可能性が少しでもあれば即ハネる。通常のMVCCでのMVTO実装を考える。実装方式はいくつかあるが、lockベースか、validationベースの二つで、validationだとpre-validationか、王道のcommit時点でやるか、の2方式がある。
・もうちょっと賢くやる方式
循環の可能性をもう少し高くなったところでハネる。これはSSNの方式になると思う。この場合は偽陽性の可能性が若干低くなる。
さて、
通常のsnapshotだけととる場合や、ノード内処理に閉じる場合であれば、このふたつの案でいいと思う。ところが、HTAPの上記ようなケースではうまくいかない。
XをOLAP側で読んでいるという情報はOLTP側には行かない。なので、W2(X2)はコミットされる。よってこのままだと上記のMVTOまたはSSN方式は役に立たない。
要は、そもそも読まれているという状態をwrite側が知ることができないのでabortのしようがない。(さらにそもそも時刻同期の問題もあるが、それは置いておく) 、もちろん、リードレプリカ側で読んだ時に、これ読んでるからとwrite側に通知することはできなくはないが、それでもそもそもなんのためにリードレプリカをつくったのかわからない。全部通知する羽目になる。
また、逆にwriteの持ち回りをread replicaにもっていってコミット可能かどうかを確認してからコミットするという方法もある（言ってみれば、RSSIがこの方式である）が、ターンアラウンドがかかりすぎて無理筋すぎる。
なので、HTAPのような場合は、単ノードMVCCのようにwrite側abortだけというのは実は結構厳しい。
メリット：従来の枠組みを利用できる。
デメリット：readの通知をOLTPに送り返す必要があるため、現実的ではない。
3. readのabort
これはOLAPサイドでのr-wの結果を受けての処理になる。replica側に「今write走っているよ」というnoticeすることが前提。
この場合、まず、飛ばすwriteの通知は、snapshotを取っている「最中」のconcurrentなwriteのログだけでよい・・はずだが・・・OLTPサイドでは何がOLAPで呼ばれているかなぞ知ったことではないので、結局対応するwrite log全部送るという羽目になる気がする。（またはOLAPサイドで「今からこれ読むけど、まさか絶賛更新中じゃないよね？」という問い合わせをやる方法になるが、これは上記のように読む値を全部放り投げることになるので、無理筋。）
それでもOLTPサイドは書き込みが続行できるので、それはそれでOKで、もらったOLAPサイドの問題になる。
OLAPサイドでは、readコミット時に、timestampでチェックをして、overlapしているconcurrentな未コミットwriteがある場合は、abortするということになる。続行はどうするかはアプリケーション次第だが、普通はretryしてsnapshotの取り直しになるはず。ただし、この場合、すでにwrite logが来ているはずなので、取り直さなくても良いと思われる。
ただし、readサイドはいちいち読むたびに更新中フラグのチェックを行うことになるので、write heavyの場合は割りに合わない可能性がある。write heavyなレコードあれば、ガンガン更新がかかるので、read側は整合性確保のために、writeコミットまでウェイトかabort & retryさせる必要があるが、これだとロングバッチ処理での更新が絡んだ段階でreadがストップするので、問題になる可能性がある。とはいえ、不整合なデータを読んでも意味がない、という話もある。
メリット：writeのabortが発生しない。read replica側からOLTPへの通知が不要
デメリット：write heavyなワークロードの場合はread abortが多発する可能性が高い
4. read するときに意図的に古いversionを読む。
これはいままでのDBの手法では想定されていない手法になる、と思う。
前述の例だと、
H: R2(X0) R2(Y0) R1(Y0) W1(Y1) C1 R3(X0) R3(Y1) C3 W2(X2) C2から
anti-dependencyは yについてT2→T1 xについてT3→T2
R3(Y1)は直前のT1でコミットされたY1を読んでいる。
通常のdependency(w-r)は yについてT1→T3 。
よってT1→T3→T2→T1で循環する。ので
例えば、w-rのT1→T3をぶった切ってやればよい
T3→T2→T1ならば問題ない。すなわち、R3(X0) R3(Y1)をR3(X0) R3(Y0)にすればよい。
さて、これは表面的にはT3では「今Xの値が更新中で、このままいくと不整合が起きるから、Yの一つ前のversionの値を読め」という、一見言っていることがよくわからない、という感じになる。これはこれで対処療法としてはアリだと思うが、そもそも、場当たり的すぎる。
ということで、少し定式化してみる。
version orderを考える。
・x x0＜＜x2
・y y0＜＜y1
version orderは論理順序なので、ここで合成されたsnapshot空間Sn(xn, yn)を想定する。
初期値S0と終了値S∞を想定し、空間遷移をcommit orderで決定することができる。
commit orderがc0＜c1＜c2の条件であれば
S0(x0, y0) ＜＜ S1(x0, y1) ＜＜S2(x2, y1)
commit orderがc0
- projected H:OLTPサイド: R2(X0) R2(Y0) R1(Y0) W1(Y1) C1W2(X2) C2.
anti-dependencyはyについて、T2→T1
このときのserialization order での「論理的なcommit order」はc2
S1’:H: R2(X0) R2(Y0) R1(Y0) R3(Y0) W1(Y1) C1 W2(X2) C2 R3(X2) C3
S2:H: R2(X0) R2(Y0) R1(Y0) W1(Y1) C1 W2(X2) C2 R3(X2) R3(Y1) C3
以上で確かに可能。
なお、この場合にどこにreadを入れるか？はSの遷移のトリガーにより決定されるので、
S0 (x0, y0) ＜[c2]＜ S1’(x2, y0) ＜[c1]＜ S2(x2, y1)より
S0については、c2/c1の前であればどこでもよい。
S1’については、x2はc2の後、y0はc1の前であればどこでもよい。
S2については、c2/c1の後であればどこでもよい。
実際、S0のケースであれば、
S0:H: R2(X0) R2(Y0) R1(Y0) R3(Y0) R3(X0) C3W1(Y1) C1 W2(X2) C2以外でも、
S0:H: R3(Y0) R3(X0) C3R2(X0) R2(Y0) R1(Y0) W1(Y1) C1 W2(X2) C2とか、
S0:H: R2(X0) R3(Y0)R2(Y0) R1(Y0) R3(X0) C3W1(Y1) C1 W2(X2) C2 とかなんでもよい。
ちなみに、所与のR3(X0) R3(Y1)は到達可能ではないので、棄却される。（これは今後の課題にはなるが、MVTO的な手法とは「別の方法」でread-only transaction anomalyを検出できる可能性があるということを意味すると思う）
こんな感じで読めるversion制約は、論理的なversion orderによるsnapshot空間の遷移とトランザクションの論理制約(serialization order)を解くことで解決する。あとは遷移のトリガーとreadの実行タイミング（たぶんtimestamp）を比較して、読むべき論理空間Sを決定すればよい。
ということで別段、古いversionを読まなくても「論理的に整合性のとれるversion」を読めばいいという手法を導入することで、解決する。
これは例えば、「write heavyの処理を実行している最中でも、完全なlockフリーでread heavyなロングバッチを一貫性を担保したまま、同時に走らせることができる」ということになる。これはこれで凄いはず。
・・・ということで理屈上は解決できるが、実装上でどうするか？は結構考えないといけない。
・まずS空間とか全部挙げてたら、間違いなく即死する。
・そもそもどのタイミングでどう判定するのか？
・論理的に可能なSが実際に存在する保証が必要（というか多分自明だけど要証明。たぶん分散系のロジックで行くと思う。）
・普通に探査はNP完全の予感（そもそもこの手のグラフ系のアレ）
ということでいろいろある。
くどいようだが、上の例は、あくまで例の一種で、選択可能なsnapshotを適切に選ぶことで、anomalyを回避できるということが論理的には可能だと言っているだけである。
この延長線上には、read-onlyはともかく、OLAPサイドでなんらかのwriteを行った場合はどうなるのか？も問題になってくる。これはread-only transaction anomalyとはいえないので、別の話題にはなるが、例えば、更新処理をstreaming的にOLTPサイドで行いつつ、OLAPサイドでレポートを同時に作成するような場合、レポート作成時の値をどこに書いておき、どう整合性を持たせるか？ということも視野には入ってくる。
メリット：write abortもread abortもしなくてよい。
デメリット：理論も実装も今のところはない。論理的に可能だと思われるというレベル
■うむむ
いままでの通常の解決は1だったはず。これは一種のETL処理を間に挟むことになるわけで、期せずしてread only transaction anomalyをたまたま除去していたにすぎない。しかし、サーバ・アーキテクチャの変化とともに低レイテンシーなノード間通信が普通になってきて、HTAPのようなwriteノードとreadノードのレプリカ間のlog shipが数十msecになる現在、いままで顕在化してこなかった、こういう問題が顔を出すことになる。
write側をノンストップで更新して、readレプリカをポンポンとるような仕組みであれば本来、問題になったはずだが、なかなかそういうイケてる仕組みは環境の制約でパフォーマンスが出ずに現実的ではなかった。なので、あまり問題視されなかったのだと思う。（あるいは単に気づいてなかっただけかもしれない(白目)）・・・これはconcurrentな条件で意識的にテストケースを書かないと検出できないヤツなので、たぶん「なんか値がおかしいから、分散処理でのタイミングでのバグでしょう。もう一回やったら問題ないし」とかで実装ではスルーしている可能性が高いと思ってる。
実際の解決の方向としてはどうか？ということであれば、やはり、read abortか 適切なsnapshotの選択の二択だと思う。まぁRead Or Dieだな。読子・リードマンだ。
とはいえ、まずread abortについては、そもそもあまり理論的な枠組みがない。現行（2018年現在）のMVCC-OLTPではあくまで単ノードの立て付けで、write abortしか考えていないのが現状で、こういうHTAPでの「read-abort」も一緒に考えるという理論はまだ開発どころか、研究もされていない。普通にabort & retryがどうなるかはやってみないとわからないし、頻発する場合の手法も現状では只の力技しかないだろう。それなりになにか考えるしかないと思う。
次の選択的なsnapshotでの解決はjust ideaベースでしかないので、やるのであればこれから模索という感じになる。理論的には一番エレガントに見えるが、これ普通に実装すると即死するのは目に見えているので、実践するには別の考え方でのエンジニアリングがいると思う。
そんな感じなんで、要は、今のところはpracticalなものはない、というのが実態でしょう。選択的なsnapshotでの解決はアプリレイヤーでも実装ができそうなので、HATPを現実に使う（たとえばSAP）のような場合では、なんらかのフレームワークを実装するというが現時点の解だと思う。
■完全に私見だが
そもそもMVCCはread-lock-free / write-lock-freeが理想であり、「適切なversionをread することさえできれば（＝correct）、何をやってもいい」というのが本来の理論的な到達点のはずだと思っている。蓋し、その意味ではMVCCにおけるanomalyは、writeで発生する物理制約と、read（view）で発生する論理制約のギャップによるものにすべて還元できる。今回はその典型的な例だと思ってる。
最後の案の、適切なsnapshotを選択する、という方法は、翻って見れば、これは単一ノードにおいても、readするversionの選択が適切であれば、anomalyは除去できるということにもなる。すなわち、この限りにおいてはMVTOのプロトコルは完全に偽陽性。勿論write skewの除去は必要なので、その意味ではr-wでの追い越しでvalidationは意味があるが、SSNの指摘も含めて、やり過ぎということになる。
HTAPを契機にして、従前な形でのwrite abortだけを前提にするのではなく、readサイドでも見直しをすることで、より豊かな理論的な枠組みが得られると思う。
こんな感じ。
