ぱと隊長日誌

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

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.2 The MV2PL Protocol

MV2PL protocol

committed versions, which have been written by transactions that are already committed,

the current version of a data item, which is the committed version of that data item written by the transaction that was committed last,

uncommitted versions, which are all remaining versions (created by transactions that are still active).

ここでの "current version" が「最新の "committed version"」であることに注意する。通常でいうところの "current version" といえば "uncommitted version" に相当する。

EXAMPLE 5.9 でみるように、この Protocol は TX 開始時点で read する version が決まっているように見える。

final step、つまり commit 直前の step だけが特別扱いとなる。

ここでは commit が concurrent に進む前提としている(SILOのような group commit は前提としていない)。


step は以下のルールに従う。

1. step が final step でないとき。

1.(a)
read は current version or uncommitted version を読む。

the most recently committed version (but not any other, previously committed one), or by assigning to it an uncommitted version of x;

この "or" は read protocol 次第でいずれかに決まる。"or" をどちらでも read してよいと解釈することもできるが、そうすると結局どちらを read するのか?都合が悪ければ変えることができるのか?(勉強会ではこれを「神の read protocol」と呼称していた)と考えることになる。

1.(b)
uncommitted な w(x) があるとき、後続の w(x) は待たされる。事実上 write lock している。

2. 次のルールに該当する tj が commit されるまで ti の最後のステップは delay する。これは commit protocol のようにも見える。

2.(a)
ti が overwrite しようとする item の current version を read する tj が commit するまで待つ。これは w-r の間に ti の w を入れたくない、つまり RF を壊さないためのルールとなっている。

2.(b)
ti が read した version を write した tj の commit を待つ。これは ti 自身の RF を維持するためにある。

このように RF で考えたほうが整理しやすい。


EXAMPLE 5.9 を見ていく。

"following sequence of steps" なので、s はスケジュールではない。単に operations をキューに積んでいるイメージだ。

step 3. では uncommitted version を read している。
step 5. では committed version を read している。
この違いを合理的に解釈するには TX 開始時点で read する version が決まっている、つまりスナップショットであると解釈すればよいのではないか。

final step の判定をどう行うのか?w2(x) の時点ではそれが final step かはわからず、w2(x)c2 までこないとわからない。

step 7. の後には step として c1 が入っているはず。省略しているだけと思われる。

2PL の要素は "wait" だ。最後まで引っ張って "wait" を開放する。

2V2PL protocol

リカバリーの為に before image を持っているのであれば、それを使えばうまくいくといっている。だが、これは MV といえるのか?また、実際に使われている DB はこのレベルを実現しているにすぎない。

"2V2PL uses three kinds of locks on data items (i.e., not on individual versions)" とあるが、2V なので 2 versions はあり、それぞれがロックを持っているように見える。

2V2PL は read の後の write を1つまでは wait させない、だから 1V より有利としている。

Figure 5.4 の式の例は間違いが多い。例えば wl2(x) の後に w2(x) がない。他にも複数の間違いがある。