ぱと隊長日誌

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

トランザクション理論における polygraph と History の VSR 判定

目的

トランザクション理論における polygraph とは何かを説明し、それを利用して History の VSR (View Serializability) 判定に利用できることを示します。

略語

本エントリ内では以下の略語を使います。

  • TX本:Transactional Information Systems

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)

  • Papa論文:The Serializability of Concurrent Database Updates

https://www.cs.purdue.edu/homes/bb/cs542-11Spr/SCDU-Papa-79.pdf

  • Papa本:Theory of Database Concurrency Control

Theory of Database Concurrency Control

Theory of Database Concurrency Control

  • Ullman本

http://infolab.stanford.edu/~ullman/dscb/vs-old.pdf
Database Systems: The Complete Book の "Materials from First Edition Deleted in Second" がPDFとして公開されています。

  • MVCC勉強会:Transactional Information Systems 5章 MVCC勉強会 第三回

Transactional Information Systems 5章 MVCC勉強会 第三回 - connpass

polygraph の定義

TX本から polygraph の定義を引用します。

A polygraph is a triple P = (V, E, C), where (V, E) is a directed graph and C ⊆ V × V × V is a set of choices such that (u, v, w) ∈ C implies u ≠ v, u ≠ w, v ≠ w, and (w, u) ∈ E.
引用:TX本 3.7.2 章

V = Vertex, 頂点
E = Edge, 枝・辺
C = Choices, ※直訳すれば選択肢

polygraph とは以下の定義ということです。

  • 異なる V の u, v, w があるとする。
  • (w, u) が E となる directed graph (有向グラフ)になる。
  • (u, v, w) で C を作る。

f:id:pato_taityo:20181223223416p:plain

TX本 Figure 3.6 で E は直線辺として表現されています。また、C を作るための (u, v), (v, w) は破線辺で表現されています。結果として直線辺1つと破線辺2つで C が作られます。
※「直線辺」「破線辺」は本エントリで独自に定義した用語です。

f:id:pato_taityo:20181223230354p:plain
引用:TX本 3.7.2 章

実は Figure 3.6 とほぼ同じ図がPapa論文 (FIG 2(a)) やPapa本 (Figure 2.4. (a)) でも登場しています。というより、発表年度から並べると、Papa論文(1979) < Papa本(1986) < TX本(2001) の順序であり、TX本の Figure 3.6 はPapa論文/Papa本のコピーといえます。

ここで注意すべき点として、Figure 3.6 には複数の u, v, w が存在しますが、同じ名前でもそれぞれ関係ないということです。各 V は独立しています。
これはPapa論文やPapa本を見るとわかります。Papa論文では各 V に対して v1 - v7 まで割り当てています。Papa本では名前さえついていません。このことから、各 V が独立しているとわかります。
u, v, w は先に引用した polygraph の定義と対応させるために名付けたものと思われます。

Figure 3.6 に対し、私は3つの疑問点を持っています。これらはまだ解消できていません。
説明に用いるため、Figure 3.6 の各 V に対して v1 - v7 を割り当てます。
f:id:pato_taityo:20181223231902p:plain

なお、本エントリの公開後に各疑問に対して デヴすぴスラ (@dev_supisula) さんがコメントしてくださいました。コメントを各疑問に追記させて頂きました。

【疑問1】

(v6, v4) の直線辺は何を意味しているのか?これはMVCC勉強会でも話題に挙がりました。
実はPapa論文に (v6, v4) の直線辺はありません。これが登場するのはPapa本からです。ですが、Papa本にもこれに関する説明はありませんでした。
MVCC勉強会では著者 (Christos H. Papadimitriou) の気まぐれなのではないか?という意見も出ていました。

デヴすぴスラさんのコメントです。

疑問1について:(v6,v4)という実線辺があってもそれを破線辺とするchoiceが無いわけではないよ、という事のために追加されたのでは。

https://twitter.com/dev_supisula/status/1077771808105852928

確かにその可能性がありそうです。
また、この例のように実線辺と破線辺が重なった場合、polygraph を history に適用するならば、(v5, v6, v4) の C は (v6, v4) で決まります。後程説明しますが、C の破線辺はどちらか一方を選択すればよいからです。

【疑問2】

TX本では C が4つあるとしています。これは (v1, v3, v2), (v5, v3, v4), (v5, v6, v4), (v5, v7, v4) のことと思われます。
ですが、C は他にも存在しうるように見えます。例えば (v1, v3, v4) です。なぜこれがカウントされていないかはわかりませんでした。

デヴすぴスラさんのコメントです。

疑問2:私も疑問でしたが後に出てくるヒストリから得られるpolygraphでも、reads-fromの実線辺とその他全ての頂点とのchoiceを考えているわけではなく(実線辺に対応するitemへの)writeを含むトランザクションしか考えていない。だから全ての頂点がchoiceになる訳じゃないよ、と示したかったのでは。

https://twitter.com/dev_supisula/status/1077772404036784128

コメントいただいた通りで、実線辺に対して C が必ず存在するわけではないことを示唆しているように思われます。特に (v4, v1) はその意図を感じました。

【疑問3】

(v7, v6) が (v, v) となっています。
先に述べたように各 v は独立しているとはいえ、polygraph の定義と対応させるために名付けたとしたのであれば違和感があります。直線辺であることを踏まえると、(w, u) であるのが適切にも思えるのですが…?

デヴすぴスラさんのコメントです。

疑問3:(v7, v6) を実線辺とするchoiceをここでは考えていないからでは。

https://twitter.com/dev_supisula/status/1077772844224806912

疑問2と同様と考えています。

polygraph と directed graph の関係

polygraph と directed graph は compatible か否かを判定できます。TX本、Papa本共に compatible の定義を説明していますが、Papa本のほうが分かりやすいため、Papa本から引用します。

Suppose that P = (V, A, C) is a polygraph, and let D = (V, B) be a directed graph with the same set of nodes. We say that D is compatible with P if A ⊂ B, and for each choice (u, v, w) ∈ C either (u, v) ∈ A or (v, w) ∈ A. Polygraph P is called acyclic if there is an acyclic directed graph D that is compatible with P.
引用:Papa本 2.5 章

polygraph (P) と directed graph (D) が compatible であるかの判定は以下の通り行います。

  • P と D の Vertex が同じであること
  • P の Edge が D の Edge に全て含まれていること
    • P の破線辺(P では Edge として扱わない)が D では Edge になったりする
    • TX本では直線辺を "normal" edges、破線辺を additional edges と指している
  • 各 choice (u, v, w) の (u, v) もしくは (v, w) が D では Edge になること

Now a polygraph P is called acyclic if there exists a directed acyclic graph (DAG) G that is compatible with P.
引用:TX本 3.7.2 章

polygraph と compatible な directed acyclic graph (DAG) が存在すれば、その polygraph は acyclic と呼ぶとしています。

polygraph と compatible な graph は複数存在しうること、またそのうちの一つでも acyclic なら polygraph はacyclic と呼ばれることに注意してください。
TX本 Figure 3.7 はこれを表しています。いずれも Figure 3.6 の polygraph と compatible な graph ですが、左は cyclic、右は acyclic です。acyclic な graph があるので、この polygraph は acyclic といえます。

f:id:pato_taityo:20181223232239p:plain
引用:TX本 3.7.2 章

polygraph の単語の意味を調べると「うそ発見器」等と出てきますが、"poly-" は「多くの」等の意味を持つ連結詞(ランダムハウス英和大辞典 第2版)と理解したほうがよさそうです。polygraph と compatible な graph が複数存在しうることを "poly-" と表現していると思われます。

polygraph の History への適用

polygraph を transaction (TX) history に適用するためのルールを説明します。

Schedule と History の違いは以下の記事を参照ください。
History - nikezono

Our next goal is to associate a polygraph with a given history. To this end, we will assume for the remainder of this subsection that our history under consideration contains committed transactions only, and is equipped with initializing transaction t0 and final transaction t. Let s be a history such that trans(s) = T ∪ {t0, t}. The Polygraph P(s) = (V, E, C) associated with s is defined as follows:

1. V = trans(s)
2. E = {(t0, t) | t ∈ T} ∪ {(t, t) | t ∈ T} ∪ {(t, t') | t' reads some data item from t}
3. C = {(t', t'', t) | (t, t') ∈ E ∧ t' reads x from t ∧ some w(x) from t'' appears somewhere in s}

引用:TX本 3.7.2 章

V, E, C はそれぞれ以下のように割り当てられます。

  • V : history s 内のTX(t0 及び t 含む)
  • E : 以下に該当する V 間に直線辺を引く
    • 1. t0 → 各 TX (t)
      • 初期状態 (t0) は全ての TX より前にあることを示している。
    • 2. 各 TX (t) → t
      • 最終状態 (t) は全ての TX の後にあることを示している。
    • 3. item x に値を書いた TX (t) → その値を読んだ TX (t')
  • C : choice は以下の V 間で作る
    • 1. item x に値を書いた TX (t) → その値を読んだ TX (t')
      • これが直線辺に相当する。
    • 2. item x から値を読んだ TX (t') → x に値を書き込んだ他のTX (t'')
    • 3. item x に値を書き込んだ他のTX (t'') → x に値を書き込んだ TX (t)
      • 2.3.が破線辺に相当する。

polygraph を用いた VSR 判定

polygraph を利用して history が VSR であるか否かを判定できます。

「item x に値を書いた TX (t) → その値を読んだ TX (t')」とは Reads-From (RF) の関係を表しています。

TX本 THEOREM 3.2 より 2つのスケジュールが View Equivalence であるということは RF も同じということです。今は polygraph を利用して VSR であるか否かを判定したいのですから、既存の RF の関係を壊してはならないとわかります。

同じ item の write - read の間に別の write が入ると、RF の関係が変わってしまいます。既存の RF の関係を壊さずに新しい write を挿入するには以下のいずれかを選ぶ必要があります。

  • write - read の前に write を挿入する (write - write - read)
  • write - read の後に write を挿入する (write - read - write)

これが polygraph の Choices として現れます。

f:id:pato_taityo:20181223223747p:plain

t1 が書いた値を t3 が読んでいます。この RF 関係が直線辺であらわされています。

同じ item に対し t2 が書き込んだとすると、RF 関係を崩さないためには以下のいずれかを選びます。

  • t1 の前に t2 が書き込む
  • t3 の後に t2 が書き込む

これが破線辺で示されています。

TX本では以下の history s が与えられています。
s = w0(x) w0(y) c0 r1(x) w2(y) w1(y) c1 r3(y) c3 w2(x) c2 r(x) r(y) c

これを polygraph であらわしたものが Figure 3.8 となります。

f:id:pato_taityo:20181223232331p:plain
引用:TX本 3.7.2 章

次に polygraph を compatible な directed graph に変換していきます。

polygraph から directed graph に変換する際に、Choices はいずれかの破線辺のみが Edge となります。なぜなら、両方存在するということは Graph が循環するということであり、トポロジカルソートできない、つまり TX の順序が決まらないということになるからです。

また、Choices に t0 もしくは t を含む場合は以下の特別ルールが適用されます。Ullman本から説明箇所を引用し、次に解説を行います。

Suppose Tj is the source of a read ri(x), and Tk is another writer of X. It is not allowed for Tk to intervene between Tj and Ti, so it must appear either before Tj or after Ti.

(中略)

(a) If Tj is T0, then it is not possible for Tk to appear before Tj, so we use an arc Ti → Tk in place of the arc pair.

(b) If Ti is Tf, then Tk cannot follow Ti, so we user an arc Tk → Tj in place of the arc pair.

引用:Ullman本

(a) Choices に t0 を含む場合

f:id:pato_taityo:20181223225356p:plain

t0 を含まない Edge が選択されます。上図の場合、(t1, t2) が選択されます。
t0 は初期状態であり、ある history 内のトランザクションが t0 より前に存在しえないからです。

(b) Choices に t を含む場合

f:id:pato_taityo:20181223225412p:plain

t を含まない Edge が選択されます。上図の場合、(t2, t1) が選択されます。
t は最終状態であり、ある history 内のトランザクションが t より後に存在しえないからです。

これを踏まえて Figure 3.8 の polygraph から compatible な directed graph に変換した結果が下図となります。

f:id:pato_taityo:20181223225425p:plain

循環が存在し、VSR ではないと判定できました。

次にTX本の Figure 3.13 で VSR と示された history s4 を同じ手法で判定します。
初期状態 w0(x) w0(y) c0、最終状態 r(x) r(y) c を追加します。

s4 = w0(x) w0(y) c0 w1(x) w2(x) w2(y) c2 w1(y) c1 w3(x) w3(y) c3 r(x) r(y) c

s4 に対応する polygraph を示します。

f:id:pato_taityo:20181224064932p:plain

(t3, t) の横に "x, y" と記載があるのは x, y の RF 関係による直線辺であることを示しています。よって、x もしくは y に write する TX はこの直線辺に対して Choices を検討することになります。これが破線辺で示されています。

なお、どの item に対する RF 関係なのかを直線辺に併記するアイディアは Ullman本 Figure 19.1, 19.4 から得ました。

この polygraph を compatible な directed graph に変換した結果が下図となります。

f:id:pato_taityo:20181224064948p:plain

循環がないため、VSR と判断できます。

どのような serial history と等価になるかは directed graph をトポロジカルソートすることで得られます。ここではトポロジカルソートに Linux の tsort コマンドを利用します。

# tsort << EOF
> t0 t1
> t0 t2
> t0 t3
> t1 t3
> t2 t3
> t1 tf
> t2 tf
> t3 tf
> EOF
t0
t2
t1
t3
tf

t0 → t2 → t1 → t3 → t の serial history と等価であることが分かりました。

更新情報

2019/01/03

以下の置換を行いました。
P論文 ⇒ Papa論文
P本 ⇒ Papa本

Ullman本を「略語」セクションに移動しました。これに伴い一部説明を書き替えました。

Ullman本から特別ルールに関する記述箇所を引用しました。

デヴすぴスラさんからの本エントリに対するコメントとそれに対する私の意見を追記させていただきました。

E の初期状態及び最終状態からの直線辺について補足を追記しました。

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

勉強会について

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

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

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

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)

[memo]は私のメモです。勉強会で議論された内容ではないことにご注意ください。
また、関連資料・引用・リンクを適宜挿入しています。

5.2 Multiversion Schedules

An example of a monoversion schedule is
m = r1(x0)w1(x1)r2(x1)w2(y2)r1(y2)w1(z1)c1c2

monoversion (1V) は version が1つだけ。read は直前に write したものを読む。

1V と serial schedule を混同してはいけない。これらは異なる。

5.3 Multiversion Serializability

devising a notion of view serializability and investigating whether it is feasible. Not surprisingly, it will again exhibit an NP complete decision problem, which motivates to look for a notion of conflict serializability.

View Serializability (VSR) はNP完全で、実用上は(計算量を減らすために)更なる制限が必要となる。
次回の勉強会では VSR の証明を行う。

1V は conflict serializability (CSR)、Multiversion (MV) は VSR が理論の中心となっている。

View を考える際には write したけど read されないものをどう扱うかも考える必要がある。

5.3.1 Multiversion View Serializability

when making serializability precise for multiversion schedules, we have to keep in mind that we are here taking about transparent versioning, that is, versioning that is not visible to the outside world, in particular to application programs or even the user. Thus, from a user's point of view a "correct" multiversion schedule should be equivalent to an ordinary serial schedule without versions. To make equivalence precise, conflict equivalence of the usual style (i.e., according to Chapter 3) is not an appropriate candidate

ユーザやアプリケーションに対しては version を見せずに "correct" multiversion schedule を作らなければならない。そうなると、conflict equivalence はマッチしない。
この例が EXAMPLE 5.3 で示されている。

EXAMPLE 5.3
Consider serial (monoversion) schedule s = w0(x)c0w1(x)c1r2(x)w2(y)c2.
A multiversion schedule exhibiting the same "step syntax" is
m = w0(x0)c0w1(x1)c1r2(x0)w2(y2)c2
Notice that while s shows three different conflicts (between w0(x) and w1(x), between w0(x) and r2(x), and between w1(x) and r2(x)), m exhibits only one conflict, the one between w0(x0) and r2(x0), since t1 now writes a new version of x.
(後略)

1V では r2(x0) を実現できない。1V では直前の write を read することになるため。

commit を含めた schedule で conflict を議論することは正しいのか…?ここで commit を含めたのは r2(x0) を強調したかった意図が見える。だが、commit を抜きにした方が concurrent に見えるし、適切に思える。

m では w0(x0), r2(x0) だけが conflict となる。異なる version を read していることを conflict とは言わない。

conflict には2種類ある。
(1) r-w の conflict は operation レベル。
(2) Reads-From (RF) の conflict は transaction (TX) レベル。T1 が T2 の結果を読んでいる、ということ。
本では(1)(2)を一緒くたにしている。これが意図的なものかはわからないが…。


[memo]
勉強会では DEFINITION 3.3 Herbrand Semantics of Steps の簡単な解説がありました。Herbrand Semantics についてまとめた記事のリンクを貼っておきます。
エルブラン・セマンティクス(Herbrand Semantics)理解メモ - ぱと隊長日誌

Herbrand Semantics 以外の semantics があってもよいのではないか?
version を上手く導入したい。

DEFINITION 5.4 Reads-From Relation
Let m be a multiversion schedule, ti, tj ∈ trans(m).
The reads-from relation of m is defined by
RF(m) := {(ti, x, tj) | rj(xi) ∈ op(m)}

この定義では commit / abort について触れていない。

"(ti, x, tj)" はTX、"rj(xi) ∈ op(m)"は operation。
つまり、TXの関係を導くために operation を使っている。

TX の依存関係は Herbrand Semantics につながる。

物理的に read できる or できないことを RF とは言わない。

ここでは r を考えていない。
最終状態が何であれ、そこまでの RF が正しければ equivalent と言って良い。r が x0 (初期状態)を read したってよい。r がそれ以降 overwrite されることはないため。

DEFINITION 5.5 View Equivalence
Let m and m' be two multiversion schedules such that trans(m') = trans(m).
m and m' are view equivalent, abbreviated m ≈v m', if RF(m) = RF(m').

"if" なので RF が等価なら View Equivalence ということ。

一旦 fix した TX の集合があるとする。ここに新たな TX 集合が来た時、新しい TX 集合も含めて reschedule するだろうか?そんなことをしたら、いつまでたっても状態が決まらない。
どこかで区切るという制約を考えればよいのでは?元の集合が新たな集合に対する初期値となる。

Linearizability とは TX が concurrent な間は入れ替え可能ということ。逆に concurrent な区間が終わると古い値は読めない。
[参考]
Linearizability については熊崎さんのスライドでも解説されています。

r1(x2)w2(x2)c2c1 を考える。
r1(x2)w2(x2) は物理的に成り立たない(write する前に read しているから)。
だが、commit order も含めた全体で考えれば、論理的には成り立つ。であれば、論理が成り立つように物理を入れ替えてやればよいのではないか?

A difference between this notion of view equivalence and the one introduced in Chapter 3 for monoversion schedules is that a consideration of final write operations is now irrelevant, for the simple reason that two multiversion schedules with identical sets of transactions always have the same final writes (since writes produce versions that are not erased anymore).

"final writes" が複数形であることからみて、過去の write は全て残っていて、read protocol でどの write を読むかが1つに決まるということではないか?

"since writes produce versions that are not erased anymore" は過去の write が全て残っているということ。

r(∞) は無視するという宣言であり、コミット後の version は複数あってよいということ。r(∞) は全ての write が read できて、read protocol 次第で read する値が1つに決まる。実際の read protocol を考えると、commit された latest な値となりがち。


[memo]
この箇所について神林さんと個別にお話をさせていただきました。
r(∞)で MV が収束しないとすると、以下の問題がありそうだと提起されていました。

  • どのタイミングで version を削れるかがわからない
  • 意図的な epoch 跨ぎ(バッチ処理を想定)で生成された version と、今後利用される可能性が低い使用済みの version という異なる意味のものが混在してしまう



EXAMPLE 5.5

Let m = w0(x0)w0(y0)c0r1(x0)r1(y0)w1(x1)w1(y1)c1r2(x0)r2(y1)c2.

If each ri(xj) occurring in m is replaced by an ri(x), and correspondingly each wi(xi) by a wi(x), the following monoversion schedule results:

s = w0(x)w0(y)c0r1(x)r1(y)w1(x)w1(y)c1r2(x)r2(y)c2.

Both schedules are serial; however, in s, transaction t2 reads data item x from t1, while in m, it reads x from t0.

m は serial order だが TX2 が x0, y1 を read している。これは 1V である s と異なる結果になる。
このことから、View Equivalence は reads-from から判定する必要があるとわかる。

ここで挙げている例は説明として適切でない。read protocol の整合性が取れていない。これでは version function が乱数で決まっているようにすら見える…。もっと整合性の取れた例で議論したい。

This example-driven discussion leads directly to the following correctness criterion:

ここでの correctness は3章の correctness 関数と同じことを指している。

すなわち, correctness という関数を定義し,これについての定式化を行う.

  • この関数は,とりあえず「Concurrency Problemsが起きているか?」を検証するboolだと思えばよい.
  • correctness が真となる限りにおいて,その関数で定義した Concurrency Problems は起こらない.
  • これで,強い correctness を使えばあらゆる Concurrency Problems は起こらないし,弱い correctness がどのような Problems を含むのかも定義可能となる.
    • 最も強い correctness が「直列実行したか?」である,と考えるとわかりやすいだろう.
TIS Chapter 3 - nikezono

DEFINITION 5.6 Multiversion View Serializability

Let m be a multiversion history. Then m is called multiversion view serializable if there exists a serial monoversion history m' for the same set of transactions such that m ≈v m'.

Let MVSR denote the class of all multiversion view-serializable histories.

ここまでは operation の話だったのに、ここで serial monoversion の話が出てくるのはなぜか?
serial multiversion history の世界を考えればもっと広がる可能性はあるが、それを考えきれないので 1V に絞ったのでは?

5.3.2 Testing Membership in MVSR

m = w0(x0)w0(y0)c0r1(x0)w2(x2)w2(y2)c2r1(y0)c1

m は Inconsistent Read。TX1 の間に TX2 が入っている。


[memo]
この例は Inconsistent Read Anomaly というより Read Skew Anomaly のほうが適切に思えます。
いろんなAnomaly - Qiita

ですが本では

this schedule is the canonical example of an inconsistent read

としています。
また、c2 の後に r1(x) があれば Inconsistent Read になることを考えると、ここで厳密に区別する必要はないのかもしれません。



The previous theorem implies that the membership test for MVSR can intuitively not be easier than the one for VSR, since MVSR is a relaxation of conditions over VSR; in other words, additional restrictions (in VSR) over MVSR, we obtain an NP complete decision problem.

VSR でも難しいのに、MVSR が簡単なわけがない。

THEOREM 5.2 の Proof の読み解き方。
まず、problem が 多項式時間で解けるため NP (NP complete とは異なることに注意)であるといっている。
そして、VSR が NP complete なのだから MVSR も NP complete であるといっている。
もし、MVSR が簡単に解けるのであれば、MVSR より制限された VSR も簡単に解けるはずである。だが、VSR が NP complete なのだからそれはありえない。よって、MVSR は NP complete といえる。

"3.7.2 On the Complexity of Testing View Serializability" で VSR が NP complete であることを証明している。

1V と MV における Conflict Graph と Serialization Graph の違いについて。

グラフは G=(V,E) で表され、V は頂点(vertices)の集合、E は頂点と頂点をつなぐエッジ(edges)の集合である。形式的には、グラフ G は順序対 G=(V,E) で定義され、V は有限の集合、E は V から選んだ2つの元からなる集合の集合である。

グラフ (データ構造) - Wikipedia

DEFINITION 3.15 Conflict Graph (Serialization Graph)

Let s be a schedule. The conflict graph, also known as the serialization graph, G(s) = (V, E) of s, is defined by

V = commit(s),
(t,t') ∈ E ⇔ t ≠ t' ∧ (∃p ∈ t) (∃q ∈ t') (p, q) ∈ conf(s)

1V では Conflict Graph と Serialization Graph が同じ。

DEFINITION 5.8 Multiversion Serialization Graph (MVSG)

For a given schedule m and a version order <<, the multiversion serialization graph MVSG(m, <<) of m then is the conflict graph G(m) = (V, E) with the following edges added for each rk(xj) and wi(xi) in CP(m), where k, i, and j are pairwise distinct: if xi << xj, then (ti, tj) ∈ E, otherwise (tk, ti) ∈ E.

MV では Conflict Graph と Serialization Graph を分けて考える必要がある。

Conflict Graph は operation レベルの話であり、Serialization Graph は TX レベルの話である。

1V では Conflict Graph がそのまま TX に map できるが、MV ではそれができない。

  • lifting という概念を fekete がSSI論文で言ってる
  • Operation による Graph を Lifting して Transaction の Graph を作っている
Transactional Information Systems Chapter 5読み会 - nikezono

該当論文を示します。
http://db.cs.berkeley.edu/cs286/papers/ssi-tods2005.pdf
Making Snapshot Isolation Serializable
3.1 Lifting Paths from SDG(A) to DSG(H)

参考

Transactional Information Systems Chapter 5読み会 - nikezono
中園さんの勉強会メモ。

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

勉強会について

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

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

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

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)

[memo]は私のメモです。勉強会で議論された内容ではないことにご注意ください。
また、関連資料・引用・リンクを適宜挿入しています。

勉強会の目的・方針

write に強い DB を作りたい。現状は write が遅い。

Multi Version (MV) なら Write Lock をとらずに write できるはず。だが、現状の実装に Write Lock をとらないものはない。この状況を変えたい。

今回の勉強会は読むよりディスカッションを重視したい。

5.1 Goal and Overview

So far the underlying assumption has been that data items exist in exactly one copy each.

この本でここまでは1つのコピーが前提だった。

concurrent な間は MV だが未来永劫 MV なわけではない。commit したら Single Version (SV) になる。

read は read from、つまり何を読むかが大事。

It will turn out that versioning demands some reasonable extensions of serializability theory, and, as will be shown in Part Ⅲ, versioning is connected to recovery, as versions of modified data (before images or after images, or both) are sometimes maintained in some form by a recovery manager anyway.

recovery でも version の考え方を導入しないといけない。例えば、write の before / after を利用して recovery するのは実質 MV ともいえる。
だが、本来は recovery と Concurrency Control (CC) を分けて考えないといけない。この点を意識して本を読み進める必要がある。

昔(本が想定している時代)と今では commit の前提が変わっているのではないか?
昔の commit はどこまで recovery しなければならないかを示すものだった。
今は oneshot request / group commit が前提となっている。また、write の実行順序の制御に commit が利用されるようになってきていると思われる。

w1w2c2c1 というスケジュールを SV では実現できない。w1 を w2 で上書きした後、c2 よりも後に c1 が来ているからだ。だが、MV なら可能だ。

We will also look at the storage space needed to hold multiple versions.

Storage Space とはどこを指しているのか?
本の時代はディスクベースでメモリはバッファとして利用していた。
現在はメモリベースとなっている。
この前提で考えた時にどうか?

While theoretical considerations tend to assume space to be an unlimited resource, it turns out that the picture changes significanty should this not be valid anymore. In particular, we will show how multiversion serializability is affected by limiting the (total) number of versions around.

commit した後も version の保存は必要なのだろうか?recovery ができるのであれば、必要としているより古い version は捨ててよいのではないか?

MVは resource というよりデータ構造が議論の的になるのではないか?

lost update は view の anomaly だ。update の事実が lost しているわけではない。MV なら何も考えずに write を行うことができるので、writeを lost するということもない。

w0(x)c0r1(x)r2(x)w1(x)w2(x)c1c2
このスケジュールの問題点は t1 も t2 も update するつもりなのに、同じ item の同じ version を t1 / t2 が read していることではないか?

An important assumption we will make in this chapter is that versioning is transparent to the outside world. In other words, users or applications will not be aware of the fact that data items can appear in multiple versions.

ユーザーサイドに version を意識させることはない。でも、一部例外はある。
version のデータベースがある。MVCC とそれを混同してはならない。


[memo]
version のデータベースにはバージョン管理システムSubversion, Git 等)のようなものも含むのか?

この点について記事を公開後にコメントをいただきました。version database は従来の relational database の機能に加え、version の概念も取り込んだ database とのことです。

One alternative is to use a source code version control system like git or svn to manage dataset versions. However, source code version control systems are both inefficient at storing unordered structured datasets, and do not support advanced querying capabilities, e.g., querying for versions that satisfy some predicate, performing joins across versions, or computing some aggregate statistics across versions [12].
(中略)
To answer this question we develop a system, ORPHEUSDB1 , to “bolt-on” versioning capabilities to a traditional relational database system that is unaware of the existence of versions. By doing so, we seamlessly leverage the analysis and querying capabilities that come “for free” with a database system, along with efficient versioning capabilities.

http://www.vldb.org/pvldb/vol10/p1130-huang.pdf


CASE (computer-aided software engineering) とはモデルを描くだけでコードが生成されるような古のツールのこと。
Computer Aided Software Engineering - Wikipedia

The discussion in this chapter continues to consider unaborted transactions only.

unabort を前提にするのはよくない(考慮すべき)。

ここでの abort は system abort ではなく user abort を指している。
serializable であるかの validation に失敗した時は system abort となる。

system commit とはDBが決める commit のことだ。この本の "commit" の前提でもある。
user commit とはユーザーが意思表示する commit のことだ。


[memo]
user commit はクライアント側が発行する commit のことであり、system commit は DB 側が CC を実現するために実行する commit のことと理解すればよいか?DB は CC のためにクライアント側の commit 要求の順序を変更することが可能なため。

これからの DB は 1 SQL 1 commit でよくないか?つまり、インタラクティブな操作を認めない。AutoCommit のイメージ。そうでないと速くすることはできない。

5.2 Multiversion Schedules

EXAMPLE 5.1
※一部を抜粋

s = r1(x)w1(x)r2(x)w2(y)r1(y)w1(z)c1c2
s ∉ CSR
r1(y) is "too late" for making the schedule that already has conflict (on x) between t1 and t2 an acceptable one.

Now suppose that the old value of y (in this the initial value of y) were still available when r1(y) arrived.
s' = r1(x)w1(x)r1(y)r2(x)w2(y)w1(z)c1c2
s' ∈ CSR

s の r1(y) を前に持っていくだけでCSRになるのであれば、何とか実現する方法があるのではないか?

read で何を読むかを決めなければいけない。

先に進むには Conflict Serializable (CSR) を理解しておく必要がある。
CSR の conflict の定義とは r-w, w-r, w-w であり、つまり2つの transaction (TX) が同じ item を操作する際に一方が write であるということだ。

データ処理の競合関係「だけ」に注目した解釈を導入します。この競合(conflict)を特にデータの書き込みについてのみ注目します。すなわち

w-w あるTX書き込んで、別のTXがまた書き込む
w-r あるTXが書き込んだものを、別のTXが読み込む
r-w あるTXが読み込んだものを、別のTXが書き込む

この競合関係が維持されていれば、同一のスケジュールとみなすという「解釈」です。まあ、ぶっちゃけr-rの関係は順序は関係ないでしょ?という発想ですね。すなわち、書き込みの競合関係が同一である集合に属していれば、そのスケジュールは、同じコンテクストであると意味です。この集合をconflict serializableといいます。

Welcome back to the TRANSACTION! - 急がば回れ、選ぶなら近道

SV の conflict をイメージしすぎると MV で混乱することになる。

実装はCSRでもMVSRでも両者ともどもエッジグラフでのvalidationになるので、結果としては「同じ」read-setとwrite-setのintersectionの話になっているところがややこしい。やっていることは似ているが、導かれているクライテリアは異なるということだ。

Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道

本の P99 に CSR で許される並び替えルール (C1 - C4) が記述されている。

Our presentation initially considers only totally ordered schedules since these are closer to the "algebraic" nature of the following commutativity rules for page model data operations. In these rules "~" means that the ordered pair of actions on the left-hand side can be replaced by the right-hand side, and vice versa.
Rule C1: ri(x)rj(y) ~ rj(y)ri(x) if i ≠ j
Rule C2: ri(x)wj(y) ~ wj(y)ri(x) if i ≠ j, x ≠ y
Rule C3: wi(x)wj(y) ~ wj(y)wi(x) if i ≠ j, x ≠ y

This additional rule simply states that two unordered operations can be arbitrarily ordered if they are nonconflicting. We refer to this rule as the ordering rule:
Rule C4:
oi(x), pj(y) unordered
↝ oi(x)pj(y) if x ≠ y ∨ (o = r ∧ p = r)

View Serializable (VSR) は Herbrand Semantics で表現できる。
Serializablitiyとは? 2. View Serializabilityについて - Qiita

read-from が変わらないことは CSR であることの一つの条件である。
C1 - C4 のルールを破ると read-from が壊れてしまう。正確には壊す可能性があるということであり、厳密にはrを考える必要がある。

Basically, a read step of the form r(x) reads an (existing) version of x, and a write step of the form w(x) (always) creates a new version of x (or overwrites an existing one).

r(x) の existing を最新の version の事とは断言していない。複数 version が存在する可能性を残している。
例えば group commit で w-r-w を考えると、read は通常であれば前の write をreadするが、後の write を read することにしても良い。
PostgreSQL には DEFERRABLE READ ONLY があるが、これは後の write を読むのと同じことを実現しているように思える。

この本での history とは逐次実行の事である。verify で並べ替えるのはまた別の話となる。

MV では read 発行時に version が決まることはない。取りうるスケジュールは複数ある。Rule C4 は半順序から全順序を生成するルールとなる。

  • C4だけが特殊なルールとして存在する.
    • C1,C2,C3は暗黙的にスケジュール/ヒストリの命令列に全順序があることを要求している.
    • しかしConcurrency Controlではタプルごとの命令の半順序しか得られないことが多い.
    • 半順序から全順序を生成するルールが以下のC4.
Reducibility - nikezono

DEFINITION 5.1 Version Function
Let s be a history with initialization transaction t0 and final transaction t. A version function for s is a function h, which associates with each read step of s a previous write step on the same data item, and which is the identity on write steps.

read version の決め方にはいくつもある。例えば、
・自分の write
・直前の write
・commit 済みの write
のようにいくつも取りうる。

Commit, Install, TX の order はそれぞれ異なる。

DEFINITION 5.1 で h は Herbrand をイメージしているのではないか?history に h ではなく s を割り当てていることからもうかがえる。

the result of applying a version function to a read operation could be any of (1) the associated write operation, (2) the version assigned for reading, or (3) the "versioned" read operation. Since all three possibilities are basically equivalent, this should not cause any confusion.

(1)~(3) が equivalent とは?なぜあえて説明しているのか?そこにどんな意図があるのか?
(2) は read そのものが version を指定する場合。
(3) は TX そのものの version を read の version に適用する場合。

w1w2c1
latest なものを read するのであれば w2 の version となる。
だが、commit したものを read するのであれば w1 のversion となる。

本で想定している実装は貧弱。なので、全体的に実装を避けて書いているようにも見える。

参考

Transactional Information Systems 5章 MVCC勉強会 第一回に参加 - Yabu.log
yuYabu さんが勉強会のメモを早々にまとめられていました。仕事が早い!

Transactional Information Systems Chapter 5読み会 - nikezono
中園さんの勉強会メモ。

デヴすぴスラ (@dev_supisula) | Twitter
デヴすぴスラ さんが Twitter で勉強会の内容を踏まえた考察を重ねられています。

更新情報

2018/11/29

version database について追記しました。
中園さんの勉強会メモのリンクを追記しました。