Transactional Information Systems Chapter 5読み会
自分にわかるレベルのメモ．
今読み返すと，このときは全然分かってないな．
5.1 Goal and Overview
Commitについて
しかし世の中には「userが書くcommit」とか「データベースが発行する(system) commit」とかいろいろある
この本ではcommitはrecoveryの文脈でしか議論されない
しかし，本来はRead/Write Operationを定義する際にCommitの定義がないと困る
「データは書き終わってないしロックも取ってないけど，commitはした」という状況はありうる
そのへんの物理的な処理のレベルまで踏み込んでほしい
これは道具立てとしての抽象化だから，具体化は各DBでやればいいと思う(nikezono)
user commitは，「ある半順序集合$ T_iの定義が終わった」を意味する．つまりページモデルの何とも対応しない
system commitは，Concurrency Control...というかSchedulerが与えるもの． Versionについて
MVCCでは，ConcurrentなVersion以外は持つ必要なくないか？
静止状態を挟んだら1Vにshrinkしていいのでは？ しかし並列性を上げるには，そのような排他が要りそうな処理(shrink, GC)もしなくていいのでは
MVCCにおけるVersionはユーザにはInvisible/Transparent Version Functionについて
任意のPrevious Stepを読める，というのは自由度が高い・・・が，実際どう作るのか
$ t時点での合計が欲しいときに，latest readだと$ t-1のデータを読んでしまいうる
待てばいいんだけど，それはどう表現/実装する?
PostgreSQLのRO txnはdefferedというのがある
アプリのセマンティクス(合計が欲しいとか)を指定せずに，ReadのVersion Functionをうまく作れるのか?
結局Latestとかになるのでは?
その他
Historyってタプルごとの命令順序からどうつくるの？
Definition 5.1 Version Function
これ定義が甘い．
どんなWrite stepが読めるのか？History上でprevious，とは何か？ロック持っててもいいのか？
Definition 5.2 Multiversion Schedule
1.cはCPのために必要だが，本来はいらない
and以降のcommit の順序については完全にリカバリのため？以降のパラグラフの説明では理由付けにならない
そもそもand以前も，CPしないならいらない．
aborted transactionの値を読んでも，別にそういうscheduleは成立するよね．
multiversion commit projectable schedule...みたいなもう一段階のクラスがあるといいんじゃないかなあ(nikezono)
Definition 5.3 Multiversion schedule
特に議論なし．
5.3 Multiversion Serializability
Multiversion ScheduleのVersionはユーザには透過的．
「1V serial HistoryとEquivalent」であればよい．
Example 5.3
この本におけるconflictというtermはヒストリの順序のこと．
後述されるReads-Fromは何を読んだかということ．
これは直交している
Definition 5.5 View Equivalence
なぜFinal Transaction$ r_\inftyは存在しなくていいのか？
静止状態を挟んだら，残すバージョンは必ず各タプルひとつずつでは？
そうではない． 全バージョン残す．
Version Function$ h(r_\infty)が未定義だから考えても意味がない．
全バージョン残っていれば，Version Function次第で，どんなRFも作れる
というより，「DBがどんな最終状態になっても，それまでのReadが正しければ，どうでもいいよね」という含意がある
最後にcommitしたトランザクションの値を読むのが(現実には)常識
そうじゃないこともあるという仮定を置いてる
それはどうなの?
これもSerializabilityに含めて考えるべきでは
私見だが，最大限に悩ましいのは，Serializabilityだけを考えると，例えばRead-only transactionなら，必ず$ T_0の書いたVersionを読む，という風にしてもSerializableになること．
これを止める仕組みがいるよね，という議論．
Ex 5.5
Version Functionがよく分からない．どんなProtocolならこうなるのか．言っていることはわかる
乱数とでも考えればいい気がする(nikezono)
それはそれでどうなの
Conflict Graph
Transaction as node...でいいのか
Operationをnodeにしないとhistoryからgraphを作るということにはならない
liftingという概念をfeketeがSSI論文で言ってる
OperationによるGraphをLiftingしてTransactionのGraphを作っている
Lemma 3.1より，Step graphはTransaction Graphにcollapseできる
ので，VSRの話に飛ぶ．
3.7.2 On the Complexity of Testing View Serializability
あるヒストリがVSRであるかどうか？という問題はNP完全． A polygraph is a triple P = (V, E, C), where (V, E) is a directed graph and CS;Vx Vx Visasetofchoicessuchthat(u,v,w)ECimpliesu=1=v,u=1=w, v =1= w, and (w, u) E E.
$ V: トランザクション.vertices
$ E: Edges.
$ C: choices. 3つの distinctなトランザクションで作る．
If $ (u,v,w) \in C, then the three vertices are necessarily distinct, and in fact $ (w,u) \in A.
図が難しいが，点線２つと実践一つと三角形を作っている．
実線一つがつまりchoice.
PolyGraphのcompatibility, acyclic
第四回
休んだ
第五回
各タプルの論理的なVersionの全順序のUnion.
命令順序(Historyの順序)とは関係ない．
commit orderとversion orderは関係あるか．
ない．nikezono.icon
commit = serialization orderを決める，と考えたいとき，cの順序とversion orderの順序は関係あるのでは？
以後出てくるMVSGだと，if there exists...と１つのVOを決定できればいいことになるので，複数VOがあってもよいのだが，実際，ユーザが明にserialization orderを得たい，というときには，commit時点でversion orderを確定させていかないといけないかもしれない． まあそれはそうかな．
Version Order，total orderである必要ある？
複数のVOが取りうる状況で，その余地を残したままschedulerが進行するなら，それはtotal orderといえるのか？
証明のためには「どれか１つtotal orderを作ったとして」という仮定が必要なのでこうなっている
SchedulerはVersion Orderをいつ決める？
毎回全く別のものを決めていく?
ある程度givenなVersion Orderに継ぎ足していく?
前者が一番空間が広い，が，探索問題がヤバイ．NP-Complete.
Read Protocolがわかっていれば，SG(H)がgivenなので，とりうるMV(H,<<)もある程度わかってくるはず．なので，Version Orderの探索問題も，ある程度絞り込みできた状態で始められるのでは？ Theorem 5.4 MVSR ⇔ acyclic(MVSG(H, <<))
(if)
(only if)
the resulting graph MVSG(m', <<0) remains acyclic
とあるが，bernstein 83だとその理由は"left-to-right"というtermで説明されてる．
5.3.3 Multiversion Conflict Serializability MCSR 何回読んでも大変だ
MCSR membership testingは本当にPなのか?
いや，monoversion historyがcommuteによって作れるなら，そのmonoversion historyが使ってるVersion Orderをそのまま使うことが出来ます，っていうことなのでは？nikezono.icon
それならO(N)回のcommuteで済む
そもそも，commuteしたあとversionをdropしてmonoversion historyを作るのか？
第六回
リモート参加
5.4 Limiting the Number of Versions
無限のストレージを仮定してきたのがここまでのMVSR.
実際にはストレージ/メモリに制約がある，
1VSR から MVSR までのパラメータがあると考えられる．これをkVSRとする．
kVSRよりk-1VSRのほうが理論的に性能が低い．
kVSRでserializableと判断できて，k-1VSRではできないscheduleも存在しうる，ということ．
$ VSR = 1VSR
$ 1VSR \subset 2VSR \subset ..., \subset MVSR
ストレージの容量よりも，期間のほうが重要？
Epoch-Based Group CommitにおけるEpochのサイズとか．
2~3分はデータ持っとく・・・ぐらいが実務上ちょうどいい？
kVSRとはなにか？
kVSRのmembership testingはMVSRと同じ? => 同じ
では，kVSRの正確な定義は？
readできるversion数に制約が入る，ということ以外に違いはない? => ない
スケジュール空間が異なる，というのは，読みうるVersionが増えるから異なるとこの本では言っている
(ReadするVersionまで)givenなscheduleを考える...という状況では，スケジュール空間は異ならない？
スケジュール空間 == equivalentなserial monoversion scheduleの数，と考えると，変わらないでしょう．
5 . 5 Multiversion Concurrency Control Protocols
MVSRを満たすプロトコルの紹介/証明．
Commit-Orderを保証するMVSRプロトコルってある？
いわゆる$ COCSR \subset CSRみたいな$ COMVSR \subset MVSRを定義すべき？
いまのところこの章で紹介されているプロトコルは，おそらくcommit-orderの保証がない．
基本的にserialization order != commit orderである．
5.5.1 The MVTO Protocol
ざっくりいうと: timestampをお役所的に決めて，それに従ってR/Wするプロトコル．
Writeする側が，自分より新しいVersionにReadされてしまっている場合はAbort
Write側をabortするのって結構すごい
Read側をabortするほうが直感的にはeasy
Reads-Fromが一致 == View Equivalentなので，Read側が変なReadしたことをtrackするほうがわかりやすい
MVTOは，結果論的に，既に終わったRead OperationをAnomalyにしてしまうようなWriteをAbortする．
Timestamp,いつ決める？
最初に決めないとReadするVersionが決定できない
writeのabort条件(cond 2.(a))
read has already been scheduled...と書いてあるが，それはいつ？
readしてきたトランザクションがabortするなら，まだscheduledでないと考えてもいいよね
readするタイミングでts更新して，それをscheduledと呼ぶ？
図
個人的にはバグってると思う．$ w_2(y_2)は$ r_5(y_2)より前に来ないと
第N回
一回休んだっけ?
5.5.4 A multiversion protocol for read-only transactions
MVSRのプロトコルを作るのはしんどいが，問題を限定して考えればよい
たとえば，Read-onlyに限定するとか
transactionを２つに分ける(ROMV, read only multiversion):
update
(S)S2PLライクにロックを取る
multi-version storageの恩恵はない
read-only
MVTOライクに読む
read the most recent version that has been committed at the time of the reader's begin.
これは古いのを読める
proof
version orderはS2PLと同じなのでcommit orderとmatch．これはgiven
これでMVSGを描くとかならずacyclicである
そこの証明も欲しい・・・
update側はSS2PLでないとダメなのでは？
S2PLだと，read lockをcommit前に手放せる
commit orderとserialization orderが一致しない
read only側がやばいのを読んでしまう可能性があるかも？
しかしこの本ではS2PLでもよいと言っている
私もS2PLで問題ないと思ったが考えたい
$ r_1(x_0) w_2(x_2)c_2 w_1(y_1)c_1というupdatesがいたとして
$ c_2のあとに$ r_3(x_2) r_3(y_0)c_3が挟まるとする
これはSnapshot Isolationぽいanomaly
commit $ T_2 \to T_3 \to T_1
MVSG $ T_2 \to T_3 \to T_1 \to T_2
いや，このようなscheduleにはなりえない．
$ w_1(y_1)まで$ r_1(x_0)のread lockは手放せない
正しくは$ r_1(x_0) w_1(y_1) w_2(x_2) c_2 c_1になる
$ c_2のあとに$ T_3が来ると$ r_3(x_2)r_3(y_0)
commit $ T_2 \to T_3 \to T_1
MVSG $ T_2 \to T_3 \to T_1 \to T_2
確かに反例が容易に見つかるか・・・
実装面のissue
GC
RCU(QSBR)的なアプローチとか
タイムスタンプ管理
タプルに置くかメタデータを管理するデータ構造を設けるか
18.2 Concurrency Control in Homogeneous Federations
なぜhomoを考えるのか？
heterogeneousとhomogeneousの考え方は違う
垂直分割/水平分割にちょっと近い
18.2.1 preliminaries
distributed CSR
local historyとglobal historyを考える
local historyがすべてconflict serializableでも，global historyがそうとは限らない
そりゃそうだ
以下私見
なぜdistrubitedの章で扱うのがCSRなのか？なぜMVSRではないのか？
local historyがすべてCSRであることは，global historyがCSRであるための必要条件
ところが，local historyがすべてCSRでなくとも，global historyはMVSRたりうる
local historyがすべてMVSRでなくとも，global historyがMVSRになることもある(と思う)
つまりCSRとMVSRの差分の空間を探索しようとするとcentralizedな処理が要る
CSRでも要る(local to globalの合成)が，MVSRはもっと要る
Distributed T/Oは提案されているがDistributed MVTOは提案されていない
ここの違いがどう実装に響くのか気になる
1 8. 5 Achieving Global Serializability through Local Guaranteesにそんなこと書いてありそう