誰にも見えないブログ

雑なメモ。まとまってない文章等

Papadimitriou - Theory of Database Concurrency Control読書会18回:バージョン関数

ついにマルチバージョンに入りました。今回は主にVersion Functionのところで議論が紛糾し、あまり進捗はない(2ページ+α)感じです。今回のVersion FunctionはWeikumの"Transactional Information Systems"などで既に学習している人にとっても取っ付きにくい記述になっているようです。(わかった後は概ね好評な感じ)

マルチバージョンを考えたときのcorrectnessはシングルバージョンより広く、許容するスケジュールも広く(MVSR ⊃ VSR)高い性能が期待できます。理論はこの本にある通り、30年近く前から考案されてきましたが、メモリが貴重な時代だったので実装は先送りされていたらしいです(周りの人の話聞くとそんな感じ)。

Chapter3冒頭からp59の"Example 3.1"まで読んだ。次回はp59の"A schedule together with~"から

では箇条書をメインに概要をまとめていく。

※以後、memo:~という文字に続く一文は私の私見というか心の声なのでそのつもりで。

  • memo:今回は黒板の撮影を忘れてしまった。

3.1 Mutiple Versions

  • 上書済みの(普通なら消えているはずの)ページを読めることにすると、VSRより広く柔軟なcorrectnessを考えることができる。
A1:R(x)W(x)        R(y)W(z)
A2:        R(x)W(y)
  • これはVSRでもFSRでもない
  • A2のW(y)がA1のView(読み取りデータの整合性)を破壊している。
    • そこで上書きされて消えているはずの古いversionを読めると仮定すると以下のスケジュールと同等のものを実現することができる
A1:R(x)W(x)R(y)        W(z)
A2:            R(x)W(y)
  • 第3章で上書きされたバージョンが読めるMultiversionを厳密に定義していく

Version Functions

Version Functionというreadがどのwrite結果を読むのかを決めたり、writeが上書きするwrite(つまりwriteの上書き順がわかるようなもの)を示すmap関数を考える。

  • 基本的にはread,writeに対して先行するwriteを対応付る。writeに対しては対応付けられないケースが2パターンあるのでこれに対して特殊な値λ,νを考える。

定義

  • Version Function V

    • V(s):Step s∈\hat{s}から w∈\hat{s}またはSymbol λ,νへの写像関数
    • readを引数に与えた場合:V(r)
      • V(r):rの以前の同じentityに対するwrite step
    • writeを引数に与えた場合V(w)
      • case1:引数wに先行する同じentityに対するwrite
      • case2:先行するwriteを指定できない場合Symbol λ,νのどちらかを割り当てる
        • case2-1:overwriteできない場合λを割り当てる
          • λを割り当てるwrite(x)の結果xはDBMSに保持されない。*1
            • つまりλが割り当てられているwriteを読むreadは存在することができない。後述のSymbolの特性(1)はこれを示している。
        • case2-2:overwriteできるversionがない場合νを割り当てる
          • A_0のwriteなどはoverwriteできるwrite結果が存在しないのでこのνが割り当てられる
          • memo:
            • A_0以外ではGCなどで読まれないwrite結果の削除が行われ、新しいentityのversionが発生した場合にこれが割り当てられるのではないか?
            • A_0以外でνを割り当てるケースは読み進めると出てくるかもしれない
    • Symbolの特性
      • (1):V(V(a))\ne λ
        • λが割り当てられる保存していないwriteに対してはreadすることもoverwriteすることもできない。
          • つまりλの後にバージョンが積み重なることはないのでVersion Functionを2回適応した結果λが出てくることはない。
      • (2):V(a) \neq V(w)
        • write wとそれに先立つstep aに対するVの結果が一致することはない。
        • memo:未来のバージョンは読めないという制約を入れているように読める(この点に不満がある人がいた)
    • 備考
      • V(A_0)は先行するwriteが存在しないので、必ずSymbol ν,λのどちらかに写像される。
        • memo:A0がλに写像されるケースは謎だが(そんなマルチバージョン使い物になるのか?)一般的にはA_0はνに写像されるものだと思う。
  • 概念

    • overwrite: writeに対して適応できる概念。新しく作ったページを保持する
    • create: 新しくversionを作る。overwrite先のwriteをversion functionでは表現できないためνに写像する
  • 上記の条件から次のことが言える

    • 保持していないバージョンに対するoverwriteはできない。*2
    • 既にoverwriteされている

memo:備考weikumのversion functionと比較

一般にトランザクションのversion functionはreadが中心、例えばあweikum本にはwriteに関するVersion functionは考えていない、という話題が出た。あまり他の本との比較みたいなのを掘り下げる気はないが念のため確認。興味無かったら読み飛ばしてください。

Let s be a history with initalization 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.

  • 1.h(ri(x)) = wj(x) for some wj(x) <s ri(x), and ri(x) reads xj,

  • 2.h(wi(x)) = wi(x), and wi(x) writes xi.

気になる違い

  • writeに対しては同じ適応したwriteと同じwriteになる"h(wi(x)) = wi(x)"つまり恒等写像になっているように読める
    • なぜこのような違いがあるかはよくわからない。

standard version function

  • A0を除くすべてのread,writeに対して直近のwrite stepを割り当てるversion functionをstandard version functionという。*3
  • standard version functionはスケジュールが与えら得られると一つ決まる(unique)これをV_sと表記する。

Example 3.1

本記事冒頭に登場したスケジュールのVersion Functionを考える

※A1のR(x)をR1(x)と表現する

A1:R(x)W(x)        R(y)W(z)
A2:        R(x)W(y)
  • R1(x)→W0(x)

  • R2(x)→W1(x)

  • R1(y)→W0(y)

もちろんこれはR1(y)を直近のyに対するwriteであるW2(y)に対応付けていないのでstandard version functionではない。

誤字

"All write steps are mapped on the last write step on the same entity , except of course that steps of A0 are mapped to λ"(p59)

とあるが、λではなくνだと思われる。

  • λへの上書きはできない等、それまでの文章に散々書いてあるためνでないと意味的におかしい。

Theory of Database Concurrency Control

Theory of Database Concurrency Control

  • 作者:Christos Papadimitriou
  • 出版社/メーカー: Computer Science Pr
  • 発売日: 1986/07/01
  • メディア: ハードカバー

*1:V(w)=λ that the write step is ignored, and no record of the value written is kept.

*2:p59:we cannot read or overwrite a version that was never kept

*3:p59"If V maps each read and write step in s^ (except A0) to the write step on the same entity that immediately precedes it in s^, then V is called the standard version function."