Database Concurrency Control Papadimitriou 直近3回分くらい参加メモ
整理やtexの変換が終わってないが、ここはそういう雑なものを置いておく場所なのでとりあえず投稿。
- 読んだ範囲p103 "Exclusive and Shared Locks"~
排他ロックと共有ロック
- 2つのトランザクションが同時にロック(片方が排他)を獲得していないスケジュールはlegal
- writeにがあったentityには排他ロックを獲得している
- readがあったentityには排他・共有どちらかのロックを獲得している
ロックの粒度
議論:楽観ロックと悲観ロック
- 悲観ロック
- スタベーション(abortし続ける)
- 悲観ロック
個別にロックを取るか、まとめてロックを取るか
- まとめてロックを取る:まとめて=粒度
- 個別に複数ロックを取るのと同じ
- まとめてロックを取る:まとめて=粒度
class $\Gamma \subset E$
$e \in E$
${e} \in \Gamma$
任意のG1,G2∈Γに対して共通部分が存在する場合、片方が新部分集合になっている
- $G_1 \cap G_2 =\emptyset $ or
- $G1 \subset G2$ or
- $G2 \subset G1$
chain of $\Gamma$
- chain $$
この構造は木構造そのもの
access lock,intention lockのrule
議論:javaのsynchornizedの仕様が微妙
- safe,unsafe的な用語では無いのか
2020/10/07
- p107~The path Protocolから
- p108 1行目「travery nsactions」はタイポ(多分transactions)
Path Protocol
entityに順番にアクセスすることを前提とできるとき、two-phase lockよりも柔軟なlockプロトコルを考えることができる
- entityに対してlinear orderを定義するx1,x2,...,xn
- 例えば以下のtransactionsがそれに該当する
- T1=A(x2)A(x3)
- T2=A(x3)A(x4)A(x5)A(x6)
ルール
- 最初に操作対象のentityをlockする
- 操作対象のentityにaccessする
- 次の操作対象のentity xiをlockする際、前回操作対象だったxi-1のentityをunlockする
L(x3)A(x3)L(x4)U(x3)L(x4)A(x4)L(x5)U(x4)...
- 上記のtransactionはpath protocolに従っている
- two phase lockingではない
- unlockの後にlockしている箇所があるため
- two phase lockingではない
- 上記のtransactionはpath protocolに従っている
path protocol は safe
- 証明略
- 用語の定義
- triangulated/chordal:任意の3より長いcycleが含むより短いcycleのこと(長さ3のcycle)
- path:in-degree
TIMESTAMP SCHEDULERS
2020/11/04~の範囲
p111~
- output,arrirvedなどの概念がややこしいと思った。
- 以下をテストするとConflict Serializableなスケジュールが得られる
implementation
- timestampを使う
- のでtimestamp schedulerと呼ばれる
- 各activeなトランザクションには数字(timestampを割り当てる)
- 最初のステップが到着したtimestampを各トランザクションに割り当てる
- papa本では最初のstepはbegin transaction stepとしている
- 実際のシステムでbegin transactionの時間をccに使っているものはないのではないか?という議論があった。
- papa本では最初のstepはbegin transaction stepとしている
- 最初のステップが到着したtimestampを各トランザクションに割り当てる
entityのタイムスタンプという概念を考える
- entityに対する最後のwrite,read操作をreadのタイムスタンプ、writeのタイムスタンプと定義する
- xのwriteのentityタイムスタンプよりr(x)のtransactionタイムスタンプが大きい時、r(x)は続行できる
- xのread,writeのentityタイムスタンプよりw(x)のtransaction timestampが大きい時、w(x)は続行できる
- entityに対する最後のwrite,read操作をreadのタイムスタンプ、writeのタイムスタンプと定義する
dynamic modeで動作可能だが、デッドロックにあるパターンがある。p112のExample 4.3~
p113 5行目:”Notice that A2: W(x) ended up joining the queue~"とあるが、A2ではなくA1の間違い(typo?)
Conflict Graph Schedulers
- p113~
- conflict graphを使ったcc
- conflict graphに新しいstepが追加した際、acycleな場合にstepをすすめることができる。
- csrなスケジュールが得られる
- theorem 4.11: the set of schedules output by the conflict graph scheduler is precisely the set of conflict serializable schedules.
Theory of Database Concurrency Control
- 作者:Papadimitriou, Christos
- 発売日: 1986/07/01
- メディア: ハードカバー
次回はp116 Theorem 4.12から
*1:A step can proceed if all conflicting steps of older active transactions have already been output