DEIM Forum 2019 J5-4

RAMP トランザクションの一般化における検索一貫性の問題について
徐

海燕†

古川

哲也††

史

一華†††

† 福岡工業大学情報工学部情報工学科 〒 811-0295 福岡市東区和白東 3-30-1†† 九州大学大学院経済学研究院 〒 819-0395 福岡市西区元岡 744††† 西南学院大学商学部 〒 814-8511 福岡市早良区西新 6-2-92
E-mail: †xu@fit.ac.jp, ††furukawa@econ.kyushu-u.ac.jp, †††shi@seinan-gu.ac.jp
あらまし

爆発的に増えているデータを高速に処理するためには，トランザクション処理の高性能化が重要な課題となっている．その中，分散環境で直列可能性を緩和した Read Atomic (RA) 隔離性という新たな隔離性レベルを高速に実現している Read Atomic Multi-Partition (RAMP) トランザクションがある．コーディネーションフリーで検索されるデータの一貫性を実現する RAMP トランザクションの技術をより多くのアプリケーションに適用できるようにするためには，トランザクションモデルを read only と write only トランザクションから，read と write 操作の両方を含む一般化されたトランザクションモデルへの拡張が不可欠である．本論文では，一般化されたトランザクショ
ンモデルにおいて，read from 関係で関連するトランザクションの変更結果に対する検索が fractured read にならないための RF 隔離性という RA 隔離性から拡張される性質を導入し，判定グラフや検索一貫性の性質について検討する．
キーワード マルチバージョン直列可能性 MVSR，RA 隔離性，RAMP トランザクション
る．本論文では，read from 関係でトランザクション間の関連

1 はじめに分散データベースにおいてスケーラビリティを実現するために，直列可能性を緩和した Read Atomic 隔離性という新たな隔離性レベルが提案され，それを実現する高性能な処理方式として Read Atomic Multi-Partition(RAMP) トランザクションが提案されている [1]．RAMP トランザクションはマルチバージョンに基づく効率的なプロトコルにより，Read Atomic 隔離性を保証できる．先進的なデバイスなどの適用によって，一層の高速化に関する研究が活発に行われている [4]．コーディネー
ションフリーで検索されるデータの一貫性を実現する RAMP
トランザクションの技術をより多くのアプリケーションに適用が定義される場合に， read from 関係にある複数個のトランザ
クションの変更結果に対する検索に対応するための RF 隔離性を導入する．さらに，RF 隔離性の判定方法を与え，検索一貫性を満たす性質を示し，マルチバージョン直列可能性や RA 隔離性との関係を明確にする．
本論文は次のように構成される．基本的事項についての説明を 2 章で行う．3 章では，RF 隔離性を定義し，性質分析などについては 4 章で行う．RF 隔離性を満たさせるアルゴリズムの概要を 5 章で述べる．6 章は全体のまとめである．

2 基本的事項できるようにするためには，トランザクションモデルを read

トランザクション T は，アイテム x のバージョン番号 k の

only と write only トランザクションから，read と write 操作

バージョン xk に対する検索操作 r(xk ) や変更操作 w(xk ) からの両方を含む一般化されたトランザクションモデルへの拡張がなる集合である．便宜上初期のデータベースにおいて，アイテ

不可欠である．例えば，参照整合性制約などの一貫性制約を満ム x, y, … の初期バージョン番号を 0 で表し，それ以外の場合

たすために参照しないとならないデータ項目が存在する．

は，それを変更するトランザクションの時刻印がバージョン番

本論文では，一般化されたトランザクションモデルにおい号となる．

て，read from 関係にある 2 つずつのトランザクションに対検索操作，または変更操作しか含まないトランザクションをする fractured read 現象を防ぐための RF 隔離性を導入する．

read only，または write only トランザクションという．トラン

RAMP トランザクションは，Read only と Write only トラン

ザクション集合 T = {T1 , T2 , …, Tn } 上のスケジュール H は，ザクションからなる並行実行を処理対象としているが，一つの各 Ti ∈ T の和集合である．

作業が最初にすべて決められるとは限らず，複数個のステップ［定義 1］ [3] トランザクション集合T 上のスケジュール H のからなることがあり，他のトランザクションの変更結果を参照

マルチバージョン直列可能性判定グラフ M V SR(H) は，Ti ∈ T

した上で操作を行う必要のある場合もある．生成された結果がを節点とし，次の 2 種類の枝を有するグラフである．

参照整合性制約などの一貫性制約を満たすことを確認するた

read from(rf ) 枝：

めにも，他のトランザクションの変更結果を参照する必要があ

rfw(xj ) ∈ Tj , r(xj ) ∈ Tk (j ≠ k) に対して Tj −→ Tk である．

version order(vo) 枝：

H1w(xi ) ∈ Ti , w(xj ) ∈ Tj , r(xj ) ∈ Tk (i ≠ j, i ≠ k, j ≠ k) に
vo

rf

T1

対して，i < j ならば，Ti −→ Tj ，そうでなければ，Tk −→ Ti
である．

(a)

□

H2

M V SR(H) が非巡回の場合，H は単一コピーマルチバージョ

rf

T1

るバージョンを生成するため競合しないが，同じアイテムに対

rf

T3

(b)

する変更操作と検索操作間の競合関係は定められている．本論

H3

文では，M V SR(H) に rf 枝のあるトランザクション間に rf関係があるという．

rf

T1
rf

［例 1］ スケジュール H1 ,H2 ,H3 をw(x1 ); w(y1 )T2voン直列可能という [3]．同じアイテムに対する変更操作は異な

H 1 : T1

T2

vo

vo

T2

vo
vo

T4

T3

rf

(c)

T2

r(x1 ); r(y0 )H 2 : T1

w(x1 ); w(y1 )T2r(y1 ); w(z2 )対して x1 しか読み出せてないため， fractured read 現象が生T3r(x0 ); r(z2 )じている．図 1(a) に示しているように M V SR(H1 ) には rf とw(x1 ); w(y1 ); w(u1 )vo 枝による閉路がある．本論文では，M V SR(H) における rf

H 3 : T1

図1

M V SR(H1 ), M V SR(H2 ), M V SR(H3 )T2r(x1 ); w(z2 )と vo 枝による 2 つのトランザクション間の閉路を RA 閉路とT3

w(x3 ); w(y3 )

呼ぶ．

T4

r(y3 ); r(z2 ); r(u1 )

トランザクションの変更結果に対して， fractured read 現象とする．それらのスケジュールの判定グラフ M V SR(H1 ),M V SR(H2 ), M V SR(H3 ) を図 1 に示している．M V SR(H1 )には，w(x1 ) ∈ T1 , r(x1 ) ∈ T2 より T1 から T2 への rf 枝が，r(y0 ) ∈ T2 , w(y1 ) ∈ T1 より T2 から T1 への vo 枝がある．従って，閉路が存在する．

M V SR(H2 ) には，まず w(y1 ) ∈ T1 , r(y1 ) ∈ T2 による T1
から T2 への rf 枝と，w(z2 ) ∈ T2 , r(z2 ) ∈ T3 による T2 からT3 への rf 枝からなる T1 から T3 への経路がある．次に，経路の末尾の T3 から経路の先頭 T1 へは，r(x0 ) ∈ T3 , w(x1 ) ∈ T1
による vo 枝があるため，閉路が存在する．
一方，M V SR(H3 ) には，w(x1 ) ∈ T1 , r(x1 ) ∈ T2 より T1 から T2 へ，w(u1 ) ∈ T1 , r(u1 ) ∈ T4 より T1 から T4 へ，w(z2 ) ∈T2 , r(z2 ) ∈ T4 より T2 から T4 へ，w(y3 ) ∈ T3 , r(y3 ) ∈ T4 より T3 から T4 への rf 枝がある，一方，w(x1 ) ∈ T1 , w(x3 ) ∈T3 , r(x1 ) ∈ T2 に対して，i(= 3) < j(= 1) でないため，T2 から T3 への vo 枝，w(y1 ) ∈ T1 , w(y3 ) ∈ T3 , r(y3 ) ∈ T4 , に対して，i(= 1) < j(= 3) であるため，T1 から T3 への vo 枝がある．時刻印順と逆順の枝が存在しないため，M V SR(H3 ) には閉路が存在しない．

□

が生じていないスケジュールは，RA 隔離性を満たすという[1][2]．Read Atomic 隔離性を満たせば，fractured read 現象を防ぐことができる．
トランザクションが read only, write only トランザクショ
ンモデルに限定し，検索集合が Read Subset Items-Written(RISW) に制限された場合に，RA 隔離性を満たすスケジュー
ル H は，マルチバージョン直列可能であり，MVSR(H) は非巡回である．

H1 において，T2 が T1 の変更結果に対して fractured read現象が生じているので，H1 は RA 隔離性を満たさない．一方，

H2 において，2 つ以上の検索操作を含むトランザクションはT3 のみで，T3 は T1 の変更結果に対しても，T2 の変更結果に対しても fractured read 現象が生じていない．このため， H2
は RA 隔離性を満たす．同様に H3 も RA 隔離性を満たす．

Read Atomic 隔離性を保証でき，高いスループットとスケー
ラビリティを実現できる新たな処理方式として RAMP トラン
ザクションが提案された [1]．RAMP-fast アルゴリズムをはじめとする 3 つのアルゴリズムが提案されているが，ほとんどの場合で最も高速に処理を終了できる RAMP-fast アルゴリズ
ムは，T W によって変更されるバージョン集合を，メタデータ

3 RF 隔離性

md として記憶し，処理に活用している．

3. 1 RA 隔離性［例 2］ スケジュール H1 に対して，RAMP-fast アルゴリズ

トランザクション T の検索操作と変更操作の実行結果からなる集合をそれぞれ T R ,T W と記し，それぞれトランザクショ
ン T の検索結果と，トランザクション T の変更結果という．
トランザクション T の変更結果を部分的にしか読み出せていない場合，fractured read 現象が生じているという．例えば，

H1 において，T1 の変更結果 T1w は {w(x1 ), w(y1 )} である．
T2 = (r(x1 ); r(y0 )) は T1 の変更結果 T1W = {w(x1 ), w(y1 )} にムの実行状況が次のようになる．

H 1 : T1

w(x1 ); w(y1 )x1 : md = {x1 , y1 }

y1 : md = {x1 , y1 }T2 が r(x1 ); r(y0 ) として実行される場合に，y1 ∈ x1 : md
によって，T1 の変更結果 {x1 , y1 } に対する fractured read 現象が検出され，y が再検索され，T2 が r(x1 ); r(y1 ) として実行
される．

□

3. 2 RF 隔離性でいる．

トランザクションの変更操作は，write only トランザクショ

M V SR(H) グラフから，vo 枝を除いたグラフを H の rf 関

ンのように 1 つのトランザクションのみで結果を生成する場合

係グラフという．明らかに，rf 関係グラフは有向非巡回グラフと，H2 中の T2 や H3 中の T2 のように他のトランザクション

である．有向非巡回グラフは，個々の経路における問題に分解の結果を参照した上で結果を生成する場合がある．変更結果ができる．

参照整合性制約などの一貫性制約を満たすことを確認するた

T によって検索されるバージョン集合が Ti1 を始点，Tim をめには，トランザクションは他のトランザクションの変更結果

終点とする rf 経路に及んだ場合に，検索はそれそれのアイテを検索しなければならない．本論文では，次の仮定の下で議論

ムにの最大値のバージョン番号のバージョンを生成したトラン

する．

ザクションに対する検索に細分される．問題もそれぞれのトラ

仮定：各トランザクション Ti は，Tiw と一貫性上関連するデー

ンザクションの RF 変更結果に対して fractured read 現象が生

タは TiR で検索する．

じていない問題に細分される．

□

以上の仮定の下では，複数個のトランザクションの変更結果をまとめて考える必要がある．そのための概念を導入する．

集合 {w(xik )|w(xij ) ∈ Tij , 1 <=j <= m, k = max(ij )} を，経という．
路変更結果 PiW
1 ,ik

［定義 2］ rf 関係がある Ti と Tj (i < j) に対して，

TiW ∪ TjW − {w(xk ) | w(xj ) ∈ Tj , w(xi ) ∈ Ti , k = min(i, j)}Wを，Tj の RF 変更結果 Ti,jとする.

一方，それそれのアイテムに対する変更中の最大値からなる□

すなわち，2 つのトランザクションの変更結果の和集合から，

T によって検索されるバージョン集合が複数の経路に及んだ
場合に，異なる経路変更結果に同一のアイテムが存在すれば，バージョン番号も一致しなければならない．言い換えれば，他の経路の変更結果を潜在的な検索結果として加えても，RF 変

個々のアイテムのバージョンが唯一になるように，同じアイテ

更結果に対して fractured read 現象が生じていないことを要求

ムのバージョンが 2 つ存在する場合に，バージョン番号の大きする．

W
い方，i.e.，j の方のみを残すようにしている．このため，Ti,jW
が TjW の超集合，i.e., Ti,j
⊇ TjW , である．

H2 においては，T1 の変更結果 T1W は {w(x1 ), w(y1 )} であり，T2 の変更結果 T2W は {w(z2 )} であり，T2 の RF 変更結果
W
T1,2
は，{w(x1 ), w(y1 ), w(z2 )} となる．

果に対して fractured read 現象が生じてなければ，T は RF 隔
離性を満たすという．
すべての Ti ∈ T が RF 隔離性を満たす時，H が RF 隔離性

個々のトランザクションの変更結果 TiW ，または TjW は一貫上関連する．Tj が TiW

これで RF 変更結果を対象とする RF 隔離性を導入できる．
［定義 4］ T によって検索されるバージョン集合が RF 変更結を参照している，すなわち，Ti とを満たすという．

H3 においては，T4 の検索は T3 の変更結果 T3W□= {w(x3 ),Tj (i < j) 間に rf 関係があるならば，仮定より，TjW と TiW はW= {w(x1 ), w(y1 ), w(z2 )} にw(y3 )} と T2 の RF 変更結果 T1.2

W
は TjW と TiW のまとめなので，次の一貫性上関連する．Ti,j及ぶ．両者の結果はアイテム x,y においてはバージョン番号が結果が成り立つ．

一致していないので，H3 は RF 隔離性を満たさない．

［補題 1］ トランザクションの変更結果 TjW とその RF 変更結［例 3］ H3 と T3 のみが異なる H4 においては，T1 と T2 間Wとは，一貫性上関連する．
果 Ti,j□に，T2 と T3 間に rf 関連があるので，T1 , T2 , T3 という rf

このため，RF 変更結果に対して fractured read 現象が起きW
経 路 が 存 在 す る ．T4 の 検 索 は T3 の RF 変 更 結 果 T1,3=

{w(x3 ), w(y3 ), w(z2 )} に対する検索 {r(y3 ), r(z2 )} と，T2 のていれば，一貫した結果から検索していないことになる．

W
RF 変更結果 T1,2
= {w(x1 ); w(y1 ), w(u1 ), w(z2 )} に対する検［定義 3］ rf 関係がある Ti と Tj (i < j) に対して，TkR が TjW
Wの一部を検索し，RF 変更結果 Ti,j
中バージョンを検索してい索 {r(z2 ), r(u1 )} に細分される．w どの RF 変更結果に対してWない，i.e.，r(xj ), r(yp ) ∈ Tk (p <= j, w(yq ) ∈ Ti,j , p ≠ q)，なも fractured read 現象が生じてないので，T4 ，すなわち，H4Wに対して fractured read 現象が起きているとらば，TkR は Ti,jは RF 隔離性を満たす．

□

H4 と T4 のみが異なる H5 においては，T4 の検索はトラン

H2 において，T3 = (r(x0 ); r(z2 )) は T2W から z2 を検索し，ザクション T3 の変更結果 T3W と，T0 の変更結果 T0W に留まっいう．

W
RF 変更結果 T1,2
= {w(x1 ), w(y1 ), w(z2 )} から x1 を検索してており，いずれに対しても fractured read 現象が生じていない．

Wに対して fractured read 現象が生じている．図おらず，T1,2

T4 ，すなわち，H5 は RF 隔離性を満たす．しかし，図 2(b) に1(b) に示しているように，M V SR(H2 ) には，T1 から T2 ，T2

示されているように，M V SR(H5 ) には T1 , T2 , T3 , T4 間の閉路

から T3 への rf 枝と，T3 から T1 への vo 枝がある．

が存在する．

本論文では，M V SR(H) における rf ,rf ,vo 枝による閉路

H 4 と T 4 の み が 異 な る H 6 に お い て は ，T 4 の 検 索を RF 閉路と呼ぶ．RF 閉路は，3 つのトランザクション間のW= {w(x3 ), w(y3 ), w(z2 )} に 対は T3 の RF 変 更 結 果 T1,3

rf ,rf ,vo 関係による限定された閉路である．

W=
す る 検 索 {r(y3 ), r(z2 )} と ，T2 の RF 変 更 結 果 T1,2

トランザクションの検索操作は，1 つのトランザクションの{w(x1 ); w(y1 ), w(u1 ), w(z2 )} に対する検索 {r(z2 ), r(u0 )} に

RF 変更結果に留まらないことがある．例えば，H3 における細分される．前者は fractured read 現象が生じていないが，後T4 の検索は，T3 の RF 変更結果と T2 の RF 変更結果に及ん

者は fractured read 現象が生じている，このため，H6 は RF 隔

離性を満たさない．図 2(c) に示されているように M V SR(H6 )W
ザクションの変更結果 TjW とその RF 変更結果 Ti,jとは，一には T1 , T2 , T4 間に RF 閉路が存在する．

貫性上関連する．バージョン間の一貫性情報が利用できれば，

H 4 : T1

H5

H6

□

w(x1 ); w(y1 ); w(u1 )各トランザクションによって検索されるバージョン集合間の検T2

r(x1 ); w(z2 )

索一貫性は，次のように定義できる．

T3

r(z2 ); w(x3 ); w(y3 )［定義 5］ T R 中に一貫性上で関連するバージョンに対して

T4

r(y3 ); r(z2 ); r(u1 )fractured read 現象が生じなければ，T R は検索一貫性を満た
すという．

T1

w(x1 ); w(y1 ); w(u1 )T2

r(x1 ); w(z2 )T3r(z2 ); w(x3 ); w(y3 )ての Ti ∈ T が検索一貫性を満たす時，H は検索一貫性を満たT4

r(y3 ); r(u0 )

すという．

T1

w(x1 ); w(y1 ); w(u1 )T2

r(x1 ); w(z2 )保証する基準である．補題 1 でまとめたバージョン間の一貫性

T3

r(z2 ); w(x3 ); w(y3 )上関連する情報を，検索一貫性の判定に利用できる．

T4

r(y3 ); r(z2 ); r(u0 )［定理 1］ 検索操作が本論文の仮定を満たす場合では，スケトランザクション集合 T 上のスケジュール H におけるすべ□

直列可能性は，意味論情報がない場合における検索一貫性をジュール H が検索一貫性を満たすための必要十分条件は，H
H4

rf

T1
rf

T2
rf

vo
rf

が RF 隔離性を満たすことである．
T3

rf

T4

たがって，H が RF 隔離性を満たさないことになる．矛盾で
ある．
vo

rf

T1

T2

vo

十分性：H が RF 隔離性を満たさないとすると，それは潜在的

rf

T3
rf

T4

補題 1 より検索一貫性を満たさない．後者は検索している異なる経路における検索に一致するバージョン集合が存在しない，
vo

T1

rf
vo

T2
rf
T4

検索を含まない場合と含む場合に分けられる．前者は RF 変更
結果に対する fractured read 現象が生じていることを意味し，

(b)

H6

必要性：検索一貫性を満たさないとすると，補題 1 により RF変更結果に対する fractured read 現象が生じることになる．し

(a)

H5

□

rf

言い換えれば，検索一貫性を満たす検索結果が存在しないこと
T3

rf

(c)
図 2 M V SR(H4 ), M V SR(H5 ), M V SR(H6 )明らかに，RF 隔離性を満たせば，RA 隔離性も満たす．RA
隔離性を満たさないなら，RF 隔離性も満たさない．具体的に，

H1 は RA 隔離性も RF 隔離性を満たさず，H2 , H3 と H6 はRA 隔離性は満たすが，RF 隔離性は満たさない．H4 と H5 はを意味する．いずれの場合も矛盾である．

□

4. 2 判定グラフ M V SR(H) との関係
RF 隔離性と判定グラフ M V SR(H) は，表 1 に示している
ように，関係がないように見える． RF 隔離性を満たさない

H3 の M V SR(H3 ) は非巡回であり，RF 隔離性を満たす H5 のM V SR(H5 ) は巡回である．これは，両者の基づく前提の違いによるものである．
表1

各スケジュールの性質

RA 隔離性 RF 隔離性

RA 隔離性も RF 隔離性も満たす．

M V SR(H) M V SR(H  )
非巡回

非巡回

RA 隔離性は 1 つのトランザクションの変更に対する検索に

H1

×

×

×

×

関するものであり，RF 隔離性は rf 関係のある親子トランザク

H2

〇

×

×

×

ションの変更結果に対する検索まで拡張している．検索集合は，

H3

〇

×

〇

×

個々のトランザクションの変更結果と，rf 関係のあるトランザ

H4

〇

〇

〇

〇

H5

〇

〇

×

×

H6

〇

×

×

×

クションの親子変更結果に対する検索に細分できるので， RA
隔離性の場合の RISW 制限は不必要になる．

4 RF 隔離性の性質

M V SR(H) が非巡回であることは， H が単一コピーマルチバージョン直列可能であるための必要十分条件である [3]．直列

本章では，RF 隔離性を満たす H の判定グラフ M V SR(H)

可能性は，個々のトランザクションが一貫したデータベースかの性質と RF 隔離性を満たすことの意義について議論する．

ら実行していれば，その実行されたデータベースも一貫である

4. 1 検索一貫性との関係という前提に基づいている．本論文ではその前提を設けておら

本論文の仮定の下では，補題 1 で示しているように，トラン

ず，各トランザクションが検索一貫性を満たせば，その RF 変

は，部分トランザクション TiR を含む場合と含まない場合に分更結果が一貫しているという前提に基づいている．
一方，表 1 中の H  は、潜在的な検索も含めた場合のスケジュールを意味する．例えば，H3 において，潜在的検索をけられる．
スケジュール H1 ∼ H3 ,H5 ∼ H6 は前者の例である．後者の含めると，T3 は r(y3 ); r(x3 ); r(z2 ); r(u1 ); r(x1 ); r(y1 ) になり，

例を次に示す．

M V SR(H3 ) には図 3 に示しているように RA 閉路が存在する［例 4］ スケジュール H7 の M V SR(H7 ) は図 4 に示していることになる．

ように T2 と T3 間に閉路が存在するが，T2 も T3 も 1 つの検索
H3

rf

T1
rf

vo
vo

T2
rf
rf
T4

操作しか含んでいないので，TiR を含まない閉路である．

H 4 : T1

w(x1 ); w(y1 )T3

T2r(x1 ); w(x2 )voT3r(y1 ); w(y3 )図 3 M V SR(H3 )

H7

T1

rf

T2

逆に，H5 の場合，M V SR(H5 ) に閉路が存在しても，どの

rf
vo
vo

□

T3

図 4 M V SR(H7 )トランザクションの RF 変更結果に対する fractured read 現象が生じてないので，RF 隔離性を満たすことになる．
ただし，H が RF 隔離性を満たすならば，トランザクション

前者の閉路はトランザクションの検索されるデータに問題がの変更変更に対しても RF 変更結果に対しても fractured read

あることを意味する．本論文では，定理 2 に示しているように現象が生じない．前者は，RA 閉路として，後者は RF 閉路と検索一貫性に関わる閉路を除外している．
後者の閉路については，本論文では，それが存在しても各して表されるため，次の結果が成立つ．
［定理 2］ スケジュール H が RF 隔離性を満たすための必

トランザクションの実行が検索一貫性を満たすように保証す

要十分条件は，潜在的な検索も含めたスケジュール H  のる立場である．また，検索されるバージョン集合に対しては，

M V SR(H  ) に RA 閉路も RF 閉路も存在しないことである．

Read Subset Items-Written (RSIW)[2] のような制限を設けて

□

いない．

必要性： RF 隔離性を満たさないなら，RF 変更結果に対して，

fractured read 現象が起きているか，異なる rf 経路に対する

次に，RF 隔離性と RA 隔離性の関係について議論する．

RA 隔離性は，トランザクションが read only, write only ト
ランザクションモデルに限定し，検索されるバージョン集合が検索結果が一意にまとまらないかのいずれかになる．
前者の場合は，T の変更結果を検索しており，RF の変更結RISW に制限された場合に，MVSR(H) が非巡回，すなわち単果と異なったバージョンを検索していることになる．検索すべ

一コピーマルチバージョン直列可能であることを保証していきバーションより古いバージョンを検索していれば，RF 閉路がる．代わりに，本論文で提案している RF 隔離性は，トランザ生じることになる．検索すべきバーションより新しいバージョ

クションモデルに対しても，検索集合にも制限を設けない場合ンを検索していれば，潜在的検索よる RA 閉路が生じることにに，検索一貫性を保証している．各トランザクションが検索一なる．

貫性を満たせば，一貫する変更結果と，一貫する RF 変更結果

一方，後者の場合は潜在的検索による RA 閉路が生じることになる．矛盾である．
十分性：潜在的検索によらない RF 閉路があるとすると，RF 変を生成できる．

5 RF 隔離性アルゴリズム

更結果に対して，fractured read 現象が起きているとなり，RF

まず，T W によって変更されるバージョン集合を md に，T R

隔離性を満たさない．一方，潜在的検索による閉路があるとすによって検索されるバージョンの md を rf に，メタデータとると，潜在的検索が RF 変更結果に対して，fractured read 現

して，記憶する．

象が起きていることになる。同じく RF 隔離性を満たさない．
矛盾である．

□

4. 3 スケジュールの正当性との関係
まず，RF 隔離性と単一コピーマルチバージョン直列可能性

MVSR の関係について検討する．
M V SR(H) 中の閉路を分類するために，各 Ti ∈ T を，Ti とTiR にしたスケジュール H  について検討する．H に各 Ti ∈ Tの検索操作からなる部分トランザクション TiR を加えただけなので，M V SR(H) に閉路が存在するならば，M V SR(H  ) にも閉路が存在し，その逆も成り立つ [6]．M V SR(H  ) 中の閉路

RF 隔離性アルゴリズムを付録に添付している．主な関数は
次の 2 つである．

check(v) 関数：v を終点とする rf 経路を探索し，RF 隔離性に影響しうるバージョンの集合を返す．

merge() 関数：異なる rf 経路上のバージョン集合間が合併可能かどうかをチェックし，可否を返す．
［例 5］ スケジュール H3 〜H5 についての実行状況を次に示す．

H3

T1

T2
T3

T4

w(x1 ); w(y1 ); w(u1 )only トランザクションから，read と write 操作の両方を含む

x1 : md = {x1 , y1 , u1 }, x1 : rf  = {}トランザクションモデルへの拡張した場合に，read from 関係

y1 : md = {x1 , y1 , u1 }, y1 : rf  = {}にあるトランザクションの変更結果に対して fractured read 現

u1 : md = {x1 , y1 , u1 }, u1 : rf  = {}象が生じないための RF 隔離性を導入した，RF 隔離性の判定

r(x1 ); w(z2 )問題は，判定グラフ MVSR(H) における 3 つ以内のトランザク

z2 : md = {z2 }, z2 : rf  = {x1 , y1 , u1 }ション間の閉路問題に帰着した．さらに，RF 隔離性を満たす

w(x3 ); w(y3 )ことが，各トランザクションは，自分の変更結果と一貫性上関x3 : md = {x3 , y3 }, x3 : rf  = {}連するデータは検索するという仮定のもとで，検索一貫性を満y3 : md = {x3 , y3 }, y3 : rf  = {}たすための必要十分条件にであることを示した．
各トランザクションが正しく実行できるためには，検索されr(y3 ); r(z2 ); r(u1 ) が実行される時，
W
T3,2= {x3 , y3 }たデータが一貫しなければならない．read only,Write only トW= {x1 , y1 , u1 , z2 }T2,1

ランザクションしか存在しない場合には，RF 隔離性が RA 隔

それ以上の rf 経路が存在しないので，T4 が r(y3 ) を行えば，離性に一致するが，検索操作と変更操作の両方が存在する場合

その検索は {x3 , y3 } の部分集合でなければならないため，r(y3 )には，検索するアイテムの範囲に制限を設けない状況の下で検に調整される．T4 が r(z2 ) を行えばその検索は {x1 , y1 , u1 , z2 }索一貫性を保証できる．

の部分集合でなければならないため，r(z2 ); r(u1 ) に調整されRF 隔離性を満たすことが必要十分条件となる応用例のまとめや RF アルゴリズムの実現などが，今後の課題である．

る．いずれかを選択することになる．
一方，H4 においては，T2 までは H3 と同じであるが，T3 から差が出る．

文

T3 : r(z2 ); w(x3 ); w(y3 )x3 : md = {x3 , y3 }, x3 : rf  = {z2 }y3 : md = {x3 , y3 }, y3 : rf  = {z2 }T3 : r(y3 ); r(z2 ); r(u1 ) が実行される時，
W
T3,2= {x3 , y3 , z2 }W
= {x1 , y1 , u1 , z2 }T2,1W
T1 を 始 点 ，T3 を 終 点 と す る rf 経 路 が 存 在 し ， P3,1=

{x3 , y3 , z2 , u1 } であるため，T4 がその部分集合から検索しているので，T4 は調整なしで実行できる．

H5 においては，T3 までは H4 と同じであるが，T4 によって検索されるのは T3 と T0 の変更結果である．これ以上まとめできないので，H5 は調整なしで実行される．

□

異なる終点から得られる結果は同一のアイテムが存在すれば，バージョン番号も一致する場合にしか許可しないので，次の結献[1] Bailis, P., Fekete, A., Hellerstein, J.M., Ghodsi, A. andStoica, I.: Scalable atomic visibility with RAMP transactions, SIGMOD, pp.27-38 (2014).
[2] Bailis, P., Fekete, A., Ghodsi, A. Hellerstein, J.M.,and
Stoica, I.: Scalable atomic visibility with RAMP transactions, ACM Transactions on Database Systems (TODS)
Vol. 41 Iss. 3, No. 15 (2016).
[3] Bernstein, P. A., Hadzilacos, V., and Goodman,
N.: Concurrency Control and Recovery in Database
Systems,Addison-Wesley (1987).
[4] 村田直郁，川島英之，建部修見，RDMA の適用による RAMP
トランザクション処理の高速化，情報処理学会論文誌データベー
ス（TOD） Vol. 10, No. 2, pp.19-30 (2017).
[5] 徐海燕，古川哲也：ワークフロートランザクションの隔離性，情報処理学会論文誌 (TOD) Vol.44,No.SIG 8 pp.55-64 (2001).
[6] 徐 海燕，古川哲也，史 一華：一貫性と隔離性の細分による並行実行の正当性の検証, 情報処理学会論文誌:データベース, Vol. 2,
No. 1 , pp. 22-32 (2009).

果がある．
付録

［定理 3］ RF 隔離性を満たすトランザクションからなるスケ
ジュールにおける RF 隔離性アルゴリズムに従う実行結果は，

RF 隔離性を満たす．

□

RF 隔離性アルゴリズム

証明: RF 隔離性アルゴリズムに従う得られた結果が RF 隔離

 T R で検索された全てのアイテムのそれぞれのバージョン性を満たさないとする．問題あるならば，関数 check(v) で得

Rset = {x1k1 , x2k2 , …, xmkm }られる結果にあるか，あるいは合併後の結果に問題があるかの 一貫性上関連する全対象の集合いずれかになる．check(v) 関数では，md 関連を利用して RA

Rall = {}隔離性を満足させ，rf 関連に沿っている経路を作成しながら一貫性の Check を通った検索データの集合

Rset 中のバージョンとの違いを比較し，異なる場合は rf 関連

R確定 = {}

に従って修正している．後者は，同一のアイテムが存在すれば，バージョン番号も一致する場合にしか合併してない．このため，
実行結果は RF 隔離性を満たす．

□

function main(Rset){for ( max k : xjk in Rset){Rtmp = Check(xjk )6 おわりに
本論文では，トランザクションモデルを read only と write

if (merge(Rtmp) == 0){
Print “部分 RF 隔離を満たす：” . R 確定
} else {Rall に Rtmp を追加}}
Print “RF 隔離を満たす：” . R確定}
function Check(v){Rset から v を削除，R確定 に v を追加
foreach ( xjk1 in (v : md − v) )| ki){
if ((xjki in Rset) and k1 =xjk1 を読み直す，Rset から除去
R確定 に追加，}
Rtmp に xjk1 を追加}
for（v : rf から最大バージョン xjk1 ）{if (xjki in Rset){if (k1 =| ki) {
xjk1 を読み直し，
Rset の xjki を xjk1 で替える．
}
Check(xjk1 )} else {if ( xjk2 in Rtmp){
Rtmp に xjk1 を追加}}}
Return(Rtmp)}
function merge(Rtmp){
foreach (xjk1 in Rtmp) {| k2) {
if ((∃xjk2 in Rall) and k1 =return(0)}}Return(1)}