ぱと隊長日誌

ブログ運用もエンジニアとしての生き方も模索中

Transactional Information Systems 5章 MVCC勉強会 第八回 議論メモ

勉強会について

Transactional Information Systems 5章 MVCC勉強会 第八回 - connpass の議論メモです。

自分のメモをベースにまとめています。発言の聞き間違い、解釈違いの可能性があることをご了承ください。

特記の無い引用は本で議論した箇所を示しています。

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems)

5.5.3 The MVSGT Protocol

MVSGT はトランザクション (TX) の理解度を確認するためのテストになる。
MVSGT の節がすんなりと理解できれば TX を理解できているといえる。
MVSGT の節を読めないなら全然わかっていないということ。最初から勉強をやり直す必要がある。

deterministic step とは read/write の順序が一発で与えられる。
nondeterministic step は deterministic の排他関係にある。

G will contain all edges from the conflict graph plus a few additional ones,

additional なのは version order。

Assume that ri(x) arrives at the scheduler; candidates from which ti can read are t0 as well as all wj(x), which have already been scheduled.

read に何を読ませるかを考える。これまでは直前を読んでいた。ここではもっと柔軟に割り当て可能だ。

already been scheduled とは history の order が前にあるはず、と言っている。

read できるものを考えるにあたり、wj(x) ri(x) のケースを考える。

1. those tj on a path that originates from ti, since these are supposed to follow ti in an equivalent serial schedule; let us call them late;

先行している tj の write を 後続の ti は物理的には read できるが、conflict graph に ti → tj があるなら、循環を避けるために read してはいけない。

2. those tj for which a path exists from tj to another candidate tk that writes x and from tk to ti, since in an equivalent serial schedule, tk writes x after tj; let us call them early.

conflict graph に tj → tk, tk → ti がある。また、tk が write している。
tj の write を ti は read したいが、tk が割り込んでいるため read できない。

1. If wi(x) is executed, an edge of the form (tj, ti) is added to the graph for each tj for which an rj(x) has already been scheduled; in this way, G remains a supergraph of the MVSG. If G becomes cyclic, then wi(x) is not executed; otherwise the version newly written is kept.

rj(x) の後ろに wi(x) を持っていく。既に読んでいる read の RF を壊さないため。


以降、TX本の範囲を超えた議論のメモ。

MV で write - write は conflict free と考えていたが、実はそうではないかもしれない。未来で order を決めないといけないということは、それが conflict を潜在的に持っているといえるのでは、という気がする。

CSR はこの潜在的な conflict を lock によって解消(というより order を決めてしまう)しているのではないか。この conflict の order を後で決めるコストを考えると、lock で解消するのは低コストな手段の一つなのかもしれない。

これまでの lock は限られたリソースをうまく取り合うために使われてきた。
これからの lock は conflict を顕在化させるために使うことになるのかもしれない。

TX本はPapadimitriou本(※)を要約している。TXを学ぶのであればPapadimitriou本を持っておくべき。

(※)Papadimitriou本

Theory of Database Concurrency Control

Theory of Database Concurrency Control