Database Concurrency Control Papadimitriou 読会(41回)

Theory of Database Concurrency Control

Christos Papadimitriou

https://www.amazon.co.jp/Database-Concurrency-Control-Christos-Papadimitriou/dp/0881750271/ref=sr_1_1?ie=UTF8&qid=1552962178&sr=8-1&keywords=Papadimitriou

<目的>

Theory of Database Concurrency Control（Christos Papadimitriou）以下Papa本を丁寧に読むことにより、トランザクション理論をできる限り厳密に理解し、今後のMVCC/メニーコア/大容量メモリー/低遅延分散での新しいDBの流れ/実装・理論について、周りの割と適当な雰囲気に流されるのではなく、批判的に評価しかつ新しい理論・実装を行う基礎を習得することを目指す。

<ご案内>

現在、データベースのトランザクションを学ぶのであれば、まずTransactional Information Systemsは基本になります。いわゆるWeikum本とかTX本とか言われるものですね。 https://www.amazon.co.jp/Transactional-Information-Systems-Algorithms-Concurrency/dp/1558605088/ref=sr_1_1?ie=UTF8&qid=1552962116&sr=8-1&keywords=transactional+information+systems

確かにこの本は基礎からMVCC、リカバリーまですべてを網羅して、その理論までしっかり解説しています。しかしながら、その一方でこの本は、特に「厳密性」という意味では多少適当に目をつぶっている嫌いがあります。これはそこまでやるとちょっとやりすぎという配慮もあると思われます。

他方、実際のデータベースの開発状況を見ると、現在データベースは、その成立以来の大幅な環境の変化、すなわちディスクベースのアーキテクチャから、メモリーベースのアーキテキクチャへの変更を迫られており、その理論も大きなゆさぶりを受けています。ディスクベース/シングル（少数）コア/単一ノードの前提は、monoversion/CSRと表裏一体であり、また、メモリーベース/メニーコア/分散ノードは、multiverion/MVSRがその枠組みになります。基本のMVの理論は、monoversionからの延長でできており破綻気味になっています。本来であればmultiverionの制限版としてmonoversion/CSRが検討されるべきですが、そのようにはなっていないのが現状です。

このような状況で、仮に大幅な理論の改訂があるのであれば、すなわちTX本の大幅改訂レベルの理論の更新があるのであれば、それは相応に厳密な考え方・表記に裏打ちされ、理解・整理されることが必要です。特にメモリーベースの考え方の表裏一体としての分散処理の立ち現れがあるのであれば、なおさら理論の厳密さが要求されます。エンジニアリングでどうにかするという話は「そのあと」の話です。

Papa本は、誤解/語弊出まくり前提でぶっちゃけていえば“数学的な厳密さを基本”にしています。（とくに数学関係者には比較的受けがよい印象がある。・・・ということはそれ以外の人にとってどういう印象になるかは推して知るべし）著者のPapadimitriouはcomputational complexity theoryの教科書でつとに有名で、むしろTxというよりもそっちの人です。この本も実態としては、Phil BernsteinのCC本の理論的土台の提供が目的でしょう。論文やいろいろ参照するに、MVCC系はP.B.とPapaの両者で作ったという方が解釈の方がよい気がします。

ということで、こいつを丁寧に読みます、というか丁寧に読まないとなにがなんだかわかりません。P.B.のCC本にしろ/WeikumのTX本にしろ、面倒な証明のところは全部Papaのパクリ（含む図まで＋なんかちょっと間違ったというか、理解できないままでの引用っぽいのだが。まじか。）なので、そういう位置づけです。

基本隔週の水曜日に決め打ちでやりますが、多少事情でスキップがあります。 来たい人来てください。