勉強会について
Transactional Information Systems 5章 MVCC勉強会 第二回 の議論メモです。
自分のメモをベースにまとめています。発言の聞き間違い、解釈違いの可能性があることをご了承ください。
特記の無い引用は本で議論した箇所を示しています。
- 作者: Gerhard Weikum,Gottfried Vossen
- 出版社/メーカー: Morgan Kaufmann
- 発売日: 2001/05/24
- メディア: ハードカバー
- クリック: 2回
- この商品を含むブログ (2件) を見る
[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 という関数を定義し，これについての定式化を行う．
TIS Chapter 3 - nikezono
- この関数は，とりあえず「Concurrency Problemsが起きているか？」を検証するboolだと思えばよい．
- correctness が真となる限りにおいて，その関数で定義した Concurrency Problems は起こらない．
- これで，強い correctness を使えばあらゆる Concurrency Problems は起こらないし，弱い correctness がどのような Problems を含むのかも定義可能となる．
- 最も強い correctness が「直列実行したか？」である，と考えるとわかりやすいだろう．
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 ではそれができない。
Transactional Information Systems Chapter 5読み会 - nikezono
- lifting という概念を fekete がSSI論文で言ってる
- Operation による Graph を Lifting して Transaction の Graph を作っている
該当論文を示します。
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
中園さんの勉強会メモ。
