Yabu.log

ITなどの雑記

トップ > DB > Theory of Database Concurrency Control Papadimitriou 読書会 第2回ノート

Theory of Database Concurrency Control Papadimitriou 読書会 第2回ノート

DB 勉強会 Transaction

人身事故の影響で開始時間が遅れたため、あまり進んでいません(まだ1章を読み切っていない) P8 SchedulesからP12 Proposition 1.1まで読みました。

Theory of Database Concurrency Control

Theory of Database Concurrency Control

connpass.com

Schedules

トランザクション中のdatabase step(read|write)を並び替えたシーケンスのこと。

An interleaved execution of several transactions is termed a schedule.(p8) (略) Formally, a schedule of the transaciotns A1,A2,...,Ak is a sequence of steps in the shuffle A1 * A2 * ... * Ak of the transactions

shuffleされた順列の中にはinterleaveされていないスケジュールも含まれる。特にこれは Serial Schedule と呼ばれる特別なものになる。

A Serial Schedule is a schedule consisting of a succession of transactions, without any interleaving.(p9)

1つのtransactionはcorrectなので、それが直列に並んだSerial Scheduleもcorrectになる。 Serial Scheduleと同じ性質をもつScheduleもまたcorrectになる...という点を次章(2章)で踏み込む。

2章ではSerializabilityをFSR,VSR,CSRの観点から論じる。 必要な道具(エルブランセマンティクス/interpretation)の準備は終わっていると思うので、2章冒頭のFSRが待ち遠しい。

読書会中には

  • transactionはcorrectなのか？
  • transactionがdatabase step以外の(アプリ側から見た)依存関係を持っていた場合は？
  • Nested Transactionはどうなのか?

と言った議論が起こった。この本では

  • transactionはconsistencyの単位とする
  • hidden restrictionがある場合はマージして1つのトランザクションにする

と言った前提をTransactionの節で引いているので、私個人はシンプルに文面を信じて読み進めています。

interpretationの拡張

p6で定義したinterpretationの定義を拡大して一般的にトランザクション界隈でエルブランセマンティクスと同等のものにまで広げている。*1

※interpretation(エルブランセマンティクス)はFSRを定義する際に重要になってくるので、 本書やWeikum本、kumagiさんのAdvent Calendarなどと比較しつつ単独で記事を書こうと思っています。 今回はざっくりした内容にしておきます。

  • あるentity Xに対するreadはXに直前にwriteで書き込んだ値になる。
    • ただしreadの前にwrite stepがない場合は初期値を読む
  • あるentity Xに対するwriteはそれまでにreadした値を引数にとる関数(ドメインの値に写像)の結果を書き込む

という風な規則を付け加えることでscheduleとinterpretationで計算処理を初期状態と関数の組み合わせで表現することができる。

Schedulers

スケジューラーはDB内で同時実行制御の責務を持つ。

The scheduler is the part of the database system which is responsible for concurrency control.

  • 入力:ユーザーが実行したdatabase stepのstream
  • 出力:適当な順に並び替えたstream

streamは厳密な(一般的な)定義がないという議論になった。本書ではarriving requestsなどと書かれている点から、 non deterministicでアプリサイドから次々と到着してくるdatabase stepのrequestの流れ程度の理解で問題ないと思う。

  • streamは毎度コンテキストに合った定義を用意する必要がある。
  • micro batchの塊はstreamではない
  • 最初から最後まで切れないものがstream(windowが作れない)
    • 例:映像
  • データ工学では最初にあるのがデータではなくクエリ、というのがstreamという定義がある
  • ストリームとデータのJoinができるシステムの例:PSoup

Sirish Chandrasekaran, Michael J. Franklin: PSoup: a system for streaming queries over streaming data. VLDB J. 12(2): 140-156 (2003)

スケジューラーは一貫性の保護と高い並列性の実現を目標に設計される。

The goal of the scheduler is to safeguard the consistency of the database by outputting only correct schedules.(p9)

The goal of the scheduler is to preserve consistency while maintaining a high level of parallelism or performance.(p10)

スケジューラーの優劣がわかる指標のようなものをChapter5で定義している。 現在のデータベースのベンチ周りではこの指標の定式化ができていないので、 deterministic*2という前提を引いているため、ワークロードが変わると優劣が大きく変わったりするらしい。

余談ですが、Calvinというシリアル実行していると解釈もあるシステムもある。

abstractとconclusionsしか読めてないが、

  • 分散ストレージでpaxos-baseのconsistencyを持つ
  • トランザクションをサポート
  • TPCCの結果が結構良い

というものらしい。

Calvin: Fast Distributed Transactions for Partitioned Database Systems

graph

第一章末にはAppendixとして本書で必要となる数学的な知識、グラフ理論や複雑姓クラスのちょっとしたまとめがある。 今回はグラフ理論を半分くらい読んだ。

  • vertex:グラフの頂点(ノードのこと)
  • edge:2つのvertexから構成される辺のこと

グラフはvertexの集合Vとedgeの集合Eのペア。

A graph is a pair G = (V,E), where V is a finite set of nodes or vertices, and E is a set of subsets of V of cardinality two, (p11)

f:id:yuyubu:20190519010908p:plain:w500
graphの例 p11から抜粋

上記グラフは以下のようになる

G = (V,E)
V = {v1,v2,v3,v4,v5,v6}
E = {[v1,v2],[v1,v4],[v1,v3],[v2,v4],[v3,v4],[v3,v5],[v3,v6],[v4,v6],[v5,v6]}
  • walk

隣接している頂点を繋いだ経路のことをwalkという。本書では私の要約より厳密に定義されている。

A walk in a graph G = (V,E) is a sequence [v1,...,vn] of vertices in V, such that for i = 1,..., n-1,[vi,vi+1]∈E (p11)

  • walkの中でnodeの繰り返しがないものをpathという
  • walkの中で第一nodeと最終nodeが一致しているものをcycleという

A walk in which there is no repetition of nodes is a path; if only the first and last nodes coincide, whe have a cycle.(p11)

  • degree

ノードから何本edgeが生えているかをdegreeという。

directed graph

上記の無向グラフの定義を拡張して有向グラフ(directed graph)を定義する。各要素に以下の変更点が加わる

  • edge → 呼称をarcに変える。矢印の根本をtail,矢印の先をheadと呼ぶ。
  • degree → ノードがarcのtail側、head側それぞれを区別したdegreeを新たに定義する。
    • ノードから生えているtailの数:out-degree
    • ノードに刺さっているheadの数:in-degree

orderdとcycleの関係

本書では以下が同値と見なされている

  • DAGであること
  • グラフの頂点が順序付けが可能であること(can be ordered)
Proposition 1.1: A directed graph is acyclic if and only if its vertices can be ordered so that for all arcs the tail comes before the head.(p12)

対偶として以下が成り立ってしまう点で長い議論が発生した。

  • 順序付け不可能である ↔︎ Cycleが存在する

様々なCycle

f:id:yuyubu:20190519010841p:plain:w300
Cycle?の例

  • Cycleを個別に定義せずに、順序付けできない(トポロジカルソートができない)ことからCycleの定義を導いてしまう書籍、論文だと(2)もCycleと見なしているケースがある
  • (2)のようなグラフは以下の論文に乗っているこのstep graphが該当している(勉強会後に神林さんに聞きました)

Making Snapshot Isolation Serializable

f:id:yuyubu:20190519010412p:plain
Making Snapshot Isolation Serializableのp504から抜粋

okachimachiorz.hatenablog.com

ちなみに以下の本ではCycleは3ノード以上で成り立たないとしているので、(1),(2)双方ともCycleではない。

Handbook of Graph Theory (Discrete Mathematics and Its Applications)

Handbook of Graph Theory (Discrete Mathematics and Its Applications)

knot

  • Cycleを定義している本は少ない。的な話からknotの話になった。
  • 安易にデッドロックやAnomalyの定義をサイクルに頼るのではなく、検出に必要な性質を整理した上でknotのようなcycleより厳密なグラフ構造を定義している本や論文もある。

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems

  • RICHARD C. HOLT (1972)Some Deadlock Properties of Computer Systems

  • あるリソースモデルではWFGに存在するcycleを検査するだけでは不十分なのでより厳密なknotというものの有無を検査する

  • knotはpathのクロス(結び目っぽく見える)とは関係ない
  • knotとCycleは単純に比較できないが、あえて言及するならcycle ⊃ knot
    • kontが存在する場合はknotを構成しているvertexからなるcycleが存在している。
    • cycleがあるからといってknotがあるとは限らない

yuyubu.hatenablog.com

今回はp12のProposition 1.1まで読みました。次回は1.1のProofからです。Complexity(NP,NP complete)の話がが長くなるような予感がしています。

関連:

同回他参加者のブログなどのリンクを貼っておきます

  • ぱと隊長のブログ

taityo-diary.hatenablog.jp

scrapbox.io

*1:ちなみにですが、私の身の回りではinterpretationよりエルブランセマンティクスという名称の方が一般的

*2:database stepが開始時に決まり途中で変化しないというのが現時点の私のdeterministicの理解。分岐処理や対話的な処理をトランザクションで表現できない