使用した資料をココに置いておく

Chapter 18
concurrency control Techniques
本章の内容
並列制御を行うために...
 lockを使用するプロトコル
 timestampを使用するプロトコル
 multiversionプロトコル
 validationプロトコル
 data
item,lockの粒度について
 Index使用時に発生する並列制御に関する問題
 その他の並列制御に関する問題
Binary lock

シンプルな仕組みのロック
X
0
→Xはロックされていない
X
1
→Xはロックされている



と定義する。
ロックされていたらロックが解除される(0になる)まで待つ。
ロックされていなかったらロックをして(1に変更)からXを操
作。Xに対する操作が終わったらロックを解除(0に変更)
Binaly lockは1つのトランザクションしかitemにアクセ
スできない。 →効率が悪い
Shared/Exclusive(Read/Write) lock

Binaly lockの効率の悪さを改善

特徴
 Readはitemの状態を変更しないのでreadをするトランザクション同士
なら共有できるようにする。Writeはitemの状態を変更するので排他
的(ひとつのトランザクションしかロックがかけれないよう)にする。
 readするときに行うロックをRead(Shared) lock, writeするときに
行うロックをWrite(Exclusive) lockという。
 Read lockしているトランザクション数を記憶するようにする。
Transaction_0
Transaction_1
Transaction_2
X:Read_lock_count: 3
1
2
0
Lock Conversion

ロックの状態を変更することもできる。
ただし、変更するための条件がある。

Read lock→Write lock (upgrade)

Transaction_0
Transaction_1
X
Transaction_2

1つのトランザクション
しかReadしていない
場合のみupgrade可能
Write lock→read lock (downgrade)
Transaction_2
X
もともと1つのトランザク
ションしかロックして
いないのでいつでも
downgrade可能
直列化可能性の保証
トランザクションを並列に実行し
たときとある順序によって逐次実
行したときで結果が同じになるこ
とを直列化可能性という。
→並列処理ではこの直列化可能性を
保証することが非常に重要


右のスケジュールはa→b又はb→a
といった具合に並び替えることは
出来ない。

aがYを読み取るのが早すぎて
bの変更が反映されていない

Binary lock, Read/Write lock
ではこのような誤ったスケジュールが
生じる可能性がある。
Transaction_a
Transaction_b
read_lock(Y)
read_item(Y)
unlock(Y)
read_lock(X)
read_item(X)
unlock(X)
write_lock(Y)
read_item(Y)
Y <- X+Y
write_item(Y)
unlock(Y)
write_lock(X)
read_item(X)
X <- X+Y
write_item(X)
unlock(X)
Two phase lock(2PL, 2相ロック)

ロックを解除する前に全てのread lockとwrite lockを
済ませる。
Transaction
X
X
Y
Y
Z
Z
expanding phase:
read,write lock,(upgrade)


shrinking phase:
ロック解除,(downgrade)
スケジュールをチェックしなくても直列化可能性が保証される
その代わり、使い終わったitemでもロックし続けるので並列
性を損なう(トレードオフ)
様々な2PL

conservative 2PL
 read-set,write-setをあらかじめ宣言し、ロックしてからトランザクション
を開始する。→ shrinking phaseからスタートする形になる。
 deadlock-free
 しかし、実際はあらかじめ宣言した集合以外のモノも後で必要になることが
多々あるので実用上、使えない。

strict 2PL
 実用でよく使われる方式。strict scheduleを保証。
 deadlockに陥る可能性がある。
 トランザクションがcommitかabortされるまでwrite lockを全く解除しない。

rigorous 2PL
 strict 2PLを更に制限的に。strict scheduleを保証。
 こちらもdeadlockに陥る可能性がある。
 トランザクションがcommitかabortされるまでread/write lockを全く解除
しない。→トランザクションが終わるまで、ずっとexpanding phase
Deadlock

ロックを使用することで生じる新たな弊害
例
transaction_a
transaction_b

read_lock(Y)
read_item(Y)
read_lock(X)
read_item(X)
write_lock(X)
write_lock(Y)

トランザクションaはXをロックして
いるbを待ち、トランザクションbは
Yをロックしているaを待つ。
お互いを永遠に待つ続ける現象。
Deadlock 防止プロトコル


deadlockを防ぐ方法のうちのひとつ。
conservative 2PLで使用した(非現実的な)方法もこれに含まれる。

他にもいくつかのdeadlock防止
プロトコルがある

deadlockを起こすかもしれない2つのトランザクションをどう処理す
るのか決定する。ロックが衝突したら...
→Wait-die &
Wound-die
Wait-die:古いトランザクションが新しいトランザクションを待つ。
 Wound-die:新しいトランザクションが古いトランザクションを待つ。



最終的にWait-dieでもWound-dieでも新しい方のトランザクション
をabortする。
deadlock-freeだが、必要以上にトランザクションのabortや
restartを発生させるかも。
Deadlock 防止プロトコルその2

Wait-dieやWound-dieでは古いトランザクションか新しいトランザク
ションか知らないとできないので、トランザクションが生成された順番
に関する情報(transaction timestamp)が必要になる。

このような情報が不要な手法
 no waiting:待たされるようなら即abort。その後しばらくして、
restart。 →abortが多発するおそれがある。
 cautious waiting:no waitingよりも不要なabortを減らすため
に提案された手法。2つのトランザクションaとbがあり、bがある項目X
を先にロックしていると仮定すると以下の規則に従う。


bが他のトランザクションにブロックされてなければaは待機可能。bがブ
ロックされていたらaをabort。

この規則により、ブロック時間の大小でトランザクションの順序づけが
可能となる。→deadlock-free
しかし、Deadlock防止プロトコルは非現実的な想定やオーバーヘッドが大
きいため実用ではあまり使われない。
Deadlock Detection,Timeout

実際によく使われるのはDeadlock DetectionやTimeoutを使う方法

Deadlock Detection
 Deadloｃｋを検出するためにwait-for
graphというグラフ
を構築する。
例 2つのトランザクションa,bがitem X,Yをそれぞれロックしようとする。
1. aが先にXをロック
2. bがYをロックし、Xをロックしようとしてaを待つ
3. aがYをロックしようとしてbを待つ
wait-for graph上で
輪っかが出来た
X
a
b
Y
deadlockが発生している
Deadlock Detection,Timeout

Deadlock Detection(のつづき)




deadlockの発生が検知されたらabortさせる
トランザクションを選択する。
abortさせるトランザクションを選ぶことを
victim selection(いけにえの選択)と呼ぶ。
通常は軽いトランザクションの方をabortさせる。
X
a
b
Y
Timeout
 システムで定義された時間よりもトランザクションの待機時
間の方が長かったらabortさせる。
 単純でオーバーヘッド小なので実用的。
Starvation
あるトランザクションが実行している間、もう一方の
あるトランザクションが全く実行できなくなる現象。原因として…


トランザクションに割り当てる優先度が不正
victim selectionが毎回同じトランザクションを選ぶ
が挙げられる

回避方法


公平な優先度の割り当て
abortしたトランザクションの優先度を次回から徐々に上げていく賢い
victim selectionの導入
Timestamp Ordering(TO)

トランザクションが生成された日付時刻情報を基にトラ
ンザクションを実行していく手法。
ロックを使用しないのでdeadlockが起きない。

Basic TO



トランザクションの実行順番に矛盾がないかチェックするために各
itemにそのitemをread,writeしているトランザクションの中で最も
大きい(=新しい)timestamp値を持たせるようにする。
実行してるトランザクションTのtimestampよりitemが持っている
timestampの方が新しかったらどこかで矛盾が生じたことになるので、
Tをabort。
→Tが書き込んだitemを使用する予定のトランザクションも
abortしなければならない!(cascading rollback)
Timestamp Ordering(TO) その2


Basic TOはスケジュールが復元可能であることを保証しないという問題
点がある。これに対処する代替案がいくつかある。
Strict TO



Basic TOの改良型。
readやwrite命令をすぐに実行せず、他のトランザクションがコミット
完了するまで遅延して発行させることでstrict scheduleであること
と競合直列可能であること両方を保証
Thomas's Write Rule


こちらもBasic TOの改良型。
競合直列可能であることは保証しないが、write命令時のチェックを
改良することにより、write命令の排除の発生数に抑えている。
競合直列可能とは?

二つのトランザクションが同じ項目を操作しようとしていて
更に片方がwriteしようとしていたら”競合する”という。
transaction_a
read(X)
write(Y)
transaction_b
X
Y
write(X)
read(Y)

更に競合する基本操作の手順が同じなら競合等価であると
いう。

競合直列可能→並列に実行されるスケジュールがある順序
で逐次実行されるスケジュールと競合等価なことを指す。
Multiversionプロトコル


itemに対して複数のバージョン(履歴)を持つ。
適切なバージョンを選ぶことでスケジュールを直列化可能にする。

複数のバージョンを保持するために多くの記憶領域が必要となる。
しかし最近では他の手法もリカバリーのためにいくつかの履歴を
保持しているのであまりに大きなデメリットというわけではない。

timestampがベースになっているものと2PLがベースになってい
るもの計2種類ある。
TOベース,2PLベースのMultiversion

TOベース




writeしたらversionを+1する
writeしたトランザクションがabortしてもその後ろに控えているトラン
ザクションはabortせず、適切なversionをreadする。
しかし、これだけではcascading rollbackの完璧な対策にならず、
結局writeするトランザクションがコミット完了するまで他のトランザク
ションが待つ必要がある。(書き込む前に他のトランザクションが読み込
んだらマズイ!)
2PLベース



read/writeにcertifyモードを加える。
itemに2つのバージョンを持たせ、片方をread時に提供することでread
lockとwrite lockを共有化(ただしwrite lock同士は共有できない)
トランザクションのコミット時にwriteした全てのitemのcertify lockを
取得し、read時に提供しているitemのversionを上げる。(certify
lockは他の2つのlockと排他的)
Validation(Optimistic) プロトコル

3つの段階からなる
Read Phase


Validation Phase
Write Phase
read～validation phaseまでのオーバヘッドは極めて小さ
い(というかRead以外に何もしてない)
validationでトランザクションの衝突がなかったかチェックし、
してなかったらwriteを実行。していたらabortし、再実行。
→衝突がほとんど起こらないと言うことを期待しているので楽観的な
(Optimistic)プロトコルと呼ばれる。
data item,lockの粒度

↑小
data itemの大きさ(=粒度)は数種類ある



↓大





recordのフィールド単位
record単位
ディスクブロック(ページ)単位
ファイル単位
DB全体
ロックをかけるdata itemが大→並列性が損なわれる。
ロックをかけるdata itemが小→並列性は高まるが、より多くのlock命令や
unlock命令が発行され、itemを操作するためのオーバーヘッドが大きくなる。
並列性とシステム全体にかかるオーバーヘッドはトレードオフの関係にある。
→bestな粒度はトランザクションの内容によって決まるので大抵のDBMSには
複数の粒度レベルでロックがかけられるようになっている。
複数の粒度レベルが存在する場合の問題点

粒度が小さいものに対してロックをかける(ロックの粒度小)
 例.recordにロックをかける
 そのrecordを保有するディスクブロック(更にそのディスクブロックを持つファ
イル)に排他ロックがかかっていないかチェックする
 チェックする数は少ない

粒度が大きいものに対してロックをかける(ロックの粒度大)
 例.ファイルにロックをかける



ファイルが保有する全てのディスクブロック、更にそのディスクブロックが保有
するrecord全てに排他ロックがかかっていないかチェックする必要がある
チェックする数が多すぎ
このままでは実用にならない。
→そこでintension lock
Intension lock

itemの粒度順にtree構造にした
階層図を作成し、このtree上の目
的のnodeからrootまでのpathに
どのようなロックがかかっているの
かトランザクションに知らせることで
(大量の)チェックを省く。
DB
file
page
file
page
record
page
record
record
record

Shared/Exclusiveの2つ以外に3つのlockモードを追加。



Intension Shared(IS) :ノードの子からShared lockを要求されてる
Intension Exclusive(IX) :ノードの子からExclusive lockを要求さ
れてる
Shared-intension Exclusive(SIX) : 上記2つが混ざった状態
Index使用時に発生する並列制御に関する問題

Index...データの検索速度を向上させるために、どの行がどこ
にあるかを示した索引のこと。

このIndexに対してtwo-phase lockをかけることもできる。

しかし、Indexの検索は前ページの木構造のrootから開始する。

小さなrecordをwrite 又は insertしようとするとrootに排他
ロックをかけることになり効率が非常に悪い。
Index使用時に発生する並列制御に関する問題
もう少し効率を上げるには?
page
1. rootを排他ロック
2. 子ノードに空きが無ければ
その子ノードも排他ロック。
DB
file
record
3. 子ノードに空きがあればrootの排他
ロックを解除して他のトランザクション
がすぐアクセスできるようにする。
page
page
record
4. そしてそのノードの子としてrecordをinsert。
(分割が発生するようならば親のノードに再び排
他ロックをかけて分割作業を行う)

file
record
record
その他の手法として同じ階層のノードとリンクする構造を持つB-link treeの
利用などがある。

この手法ではleafの分割を招くようなinsertとsearchを並列に走らせても
searchが成功するかもしれないというメリットを持つ。
その他の問題

phantom probrem

以下のようなスケジュールがあるとする
transaction_a
transaction_b
select * from A;
insert into A values(..,..);
select * from A;

トランザクションbの最初の
selectと次のselectで結果
が異なる→index lockで対
処できる
interactive transaction



まだコミットされてないトランザクションの値を対話式デバイスを介して読
み込み、それを他のトランザクションに書き込んだりしたときに不整合が発
生する問題のこと→コミットされるまで対話式デバイスへの入出力はしない
ようにする。
Latche

瞬間的な排他ロック。例えばメモリー上のバッファからdiskに書き込む際等
に見られる。→ロックと同様にパフォーマンス低下の原因となる。

Download Report