東京大学生産技術研究所 概念情報工学研究センタ 喜連川優

Presentation on theme: "東京大学生産技術研究所 概念情報工学研究センタ 喜連川優"— Presentation transcript:

1 東京大学生産技術研究所 概念情報工学研究センタ 喜連川優
トランザクション処理（続） 東京大学生産技術研究所 概念情報工学研究センタ 喜連川優

2 Ｓｅｒｉａｌｉｚａｂｉｌｉｔｙの意義 Serializability
If a schedule S is conflict equivalent to a serial schedule, then S is correct. オペレーションのインターリーブを可能とし、性能向上に寄与 Serializability test is quite difficult. OS 事前スケジュール 現実的ではない。 適当に実行した後にserializabilityをチェック?

3 プロトコル 現実的なアプローチ スケジュールをテストする事無くserializabilityを保証するプロトコルを考え出すこと。全てのトランザクションはそのプロトコルに従うものとする。 プロトコル Two phase lock protocol Time Stamp Multi-version

4 View Serializability これまでの議論はconflict serializability view equivalence
Two schedules S and S’ are said to be view equivalent if the following three conditions hold: The same set of transactions participates in S and S’, and S and S’ include the same operations of those transactions. For any operation ri(X) of Ti in S, if the value of X read by the operation has been written by an operation wj(X) of Tj ( or if it is the origin value of X before the schedule started), the same condition must hold for the value of X read by operation ri(X) of Ti in S’. If the operation wk(Y) of Tk is the last operation to write item Y in S, then wk(Y) of Tk must also the last operation to write item Y in S’.

5 View equivalenceの意味 個々のread操作が２つのスケジュールにおいて同じwrite操作の結果を読むのであれば、read操作は２つのスケジュールにおいて同じ世界を見る(view)ことになるので等価。 Conflict serializabilityとview serializabilityは constrained write assumptionが成り立つ限りにおいて等価 Constrained write assumption:全てのwi(X)はそれに先立つri(X)があり、それのみに依存。　 Unconstrained write assumptionにおいては　view serializabilityはより緩い。

6 より柔軟なスケジュール Conflict serializability は時として厳しすぎる
例　debit-credit トランザクション 銀行口座への預け入れと引き出し操作 Serializableで無くとも、正しい結果を生成し得る。 T1:r1(X);X=X-10;w1(X);r1(Y);Y=Y+10;w1(Y); T2:r2(Y);Y:=Y-20;w2(Y);r2(X);X:=X+20;w2(X); Sh:r1(X);w1(X);r2(Y);w2(Y);r1(Y);w1(Y);r2(X);w2(X);

7 SQLにおけるトランザクション Begin_trans文は無い。ＳＱＬ文がトランザクションの開始を意味する。 パラメータ
Access mode( read only, read write) Diagnostic area size int. Isolation level( read uncommitted, read committed, repeatable read, serializable)

8 Ｉｓｏｌａｔｉｏｎ Ｌｅｖｅｌ Isolation level Type of violation
Ｉｓｏｌａｔｉｏｎ　Ｌｅｖｅｌ Isolation level Type of violation Dirty/Read Non-repeatable-read Phantom Read uncommitted Ｙ　　　　　Ｙ　　　　　　Ｙ Read committed 　　Ｎ　　　　 Ｙ Ｙ Repeatable read Ｎ　　　　 Ｎ Ｙ Serializable　　　　　 Ｎ Ｎ　　　　　 Ｎ

9 Ｉｓｏｌａｔｉｏｎ　Ｌｅｖｅｌの意味 Ｄｉｒｔｙ　Ｒｅａｄ Ｎｏｎｒｅｐｅａｔａｂｌｅ　Ｒｅａｄ Ｐｈａｎｔｏｍ

10 Ｃｏｎｃｕｒｒｅｎｃｙ Ｃｏｎｔｒｏｌ 同時実行制御方式
Ｃｏｎｃｕｒｒｅｎｃｙ　Ｃｏｎｔｒｏｌ 同時実行制御方式 ロックに基づく方式 タイムスタンプに基づく方式 多版制御方式 楽観的制御方式

11 ロックに基づく方式 Ｂｉｎａｒｙ Ｌｏｃｋｓ：２つの状態を有する。（locked, unlocked)
LOCK(X):ロックの状態 (1,0) (locked, unlocked) lock_item(X): unlock_item(X)：

12 ロック lock_item(X): クリティカルセクションとして実装
B: if LOCK(X)=0 (*if item is unlocked*) then LOCK(X) ←1(* lock the item*) else begin wait (until LOCK(X)=0 and the lock manager wakes up the transaction); goto B end; クリティカルセクションとして実装

13 アンロック unlock_item(X): LOCK(X) ← ０；(* unlock the item*)
if any transaction are waiting then wake up one of the waiting transactions

14 Ｂｉｎａｒｙ Ｌｏｃｋ 実装：極めて簡易 ロックテーブル
Ｂｉｎａｒｙ　Ｌｏｃｋ 実装：極めて簡易 ロックテーブル <data item name, LOCK, locking transaction>　　＋　待ちトランザクションキュー

15 Ｓｈａｒｅｄ／Ｅｘｃｌｕｓｉｖｅ Ｌｏｃｋｓ
Ｓｈａｒｅｄ／Ｅｘｃｌｕｓｉｖｅ　Ｌｏｃｋｓ Ｂｉｎａｒｙ　Ｌｏｃｋは制約が強すぎる。 読む場合には多くのトランザクションが同時に読み出すことを許すべき 書き込む場合には排他制御が必須 Multi-mode Lock Shared/Exclusive Lock, 別名 read/write lock ３つの操作 read_lock, write_lock, unlock LOCK(X): read-locked(shared-lock), write-locked(exclusive- lock), unlockedの３状態

16 実装 ロックテーブル構造 <data item name, LOCK, no_of_reads,　locking_transaction(s)> LOCKがwriteの時はnoは１, readの時は待ちトランザクション数 read_lock(X), write_lock(X), unlock(X)

17 read lock__ read_lock(X): B: if LOCK(X)=‘unlocked’
then begin LOCK(X) ←‘read_locked’; no_of_reads(X)←１ 　　　　　end else if LOCK(X)=‘read_locked’ then no_of_reads(X)←no_of_reads(X) + 1 else begin wait(until LOCK(X)=‘unlocked’ and the lock manager wakes up the TR); goto B end;

18 write lock write_lock(X): B:if LOCK(X)=‘unlocked’
then LOCK(X) ← ‘write_locked’ else begin wait(until LOCK(X)=‘unlocked’ and the lock manager wake up TR); gotoB end;

19 unlock unlock(X): if LOCK(X)=‘write_locked’
then begin LOCK(X)←‘unlocked’ wakeup one of the waiting TR, if any end else if LOCK(X)=‘read_locked’ then begin no_of_reads(X)←no_of_reads(X) ー１ 　　　　　　　if no_of_reads(X) = 0 then begin LOCK(X)←‘unlocked’; wakeup one of TR, if any end;

20 lock conversion 最初にread_lock(X) , 後からwrite_lock(X)にupgrade
Read_lockを持っているトランザクションが一つだけの場合、upgrade可能、そうでない場合は待つ 最初にwrite_lock(X),後からread_lock(X)にdowngrade

21 lockとserializability
次ページの例 Unlock操作が早すぎて適正な結果を生まない。

22 Unlockが早すぎる例　（Ｃ）は誤った結果を生む

23 Ｔｗｏ Ｐｈａｓｅ Ｌｏｃｋ （２相ロック） Two phase locking protocol
Ｔｗｏ　Ｐｈａｓｅ　Ｌｏｃｋ （２相ロック） Two phase locking protocol 全てのロック操作が終了した後、アンロックする ロックフェーズとアンロックフェーズが分離 expanding/growing phase(ロック獲得）とshrinking phase（ロック開放）に分離 Lock upgradeはexpanding phaseにおいて、lock downgradeはshrinking phaseにおいて実行可

24 例の２相化 Ｔ１ Ｔ２ read_lock(Y); read_lock(X); read_item(Y); read_item(X);
　　　　Ｔ１　　　　　　　　　　　　　Ｔ２ read_lock(Y); read_lock(X); read_item(Y); read_item(X); write_lock(X); write_lock(Y); unlock(Y); unlock(X); read_item(X); read_item(Y); X:=X+Y; Y:=X+Y; write_item(X); write_item(Y); unlock(X); unlock(Y);

25 ２相ロックとserializability
全てのトランザクションが２相ロックプロトコルに従う場合、当該スケジュールは直列可能である。 ２相ロックはある程度の並行性を犠牲にしている。しかし、serializability チェック不要というメリットの代償と言える。

26 Ｖａｒｉａｔｉｏｎｓ Basic 2PL:これまでの定義 Conservative 2PL(Static 2PL) Strict 2PL
トランザクションは実行開始以前に全てのロックを取得（pre-declaration) デッドロックフリー 実際には全てを申告するのは現実的でない Strict 2PL コミット・アボート時点まで全てのexclusiveロックを開放しない。 Strict scheduleを実現 デッドロックフリーではない

27 conservative 2PL : shrinking phaseのみ rigorous 2PL: expanding phaseのみ
コミット・アボート時点まで全てのロックを開放しない。 conservative 2PL : shrinking phaseのみ rigorous 2PL: expanding phaseのみ

28 Deadlock and Starvation
T T2 read_lock(Y) read_item(Y) read_lock(X) read_item(X) write_lock(X) write_lock(Y)

29 Deadlock prevention protocol
必要なロックを実行前に全て獲得する Conservative 2PLで利用される手法 一つでもロック出来ないデータがあると、何れのデータもロックしない。一定時間待ち、リトライする。 現実的でない為実際には利用されることは無い

30 Deadlock prevention protocol(2)
データベースの全てのデータに順番を付けて、その順にロックする手法 プログラマが順序を気遣うのは非現実的

31 Transaction time stamp based methods
Timestamp TS(T) T:transaction, the starting time of the transaction T. TiがＸのロックを獲得しようとするが、Tjが既に当該ロックを有する場合の手順 Wait-die: If TS(Ti) < TS(Tj), then (Ti is older than Tj) Ti is allowed to wait; otherwise(Ti is younger than Tj) abort Ti(Ti dies) and 　 　 restart it later with the same timestamp Wound-wait: If TS(Ti) <TS(Tj) then (Ti is older than Tj) abort Tj(Ti wound Tj) and restart it later with the same timestamp; otherwise (Ti younger than Tj) Ti is allowed to wait.

32 wait-dieとwound-die Wait-die Wound-wait: wait-dieの逆 両手法ともデッドロックフリー
古いトランザクションは若いトランザクションを待つことが許される。 Wound-wait: wait-dieの逆 古いトランザクションが若いトランザクションと競合すると若いトランザクションをアボートする。 両手法ともデッドロックフリー 常に待つ方向が一定。例えばwait-dieでは古い方が若い方を待つ

33 no waiting / cautious waiting (デッドロックフリー）
If Tj is not blocked( not waiting for some other locked item), then Ti is blocked, otherwise abort Ti. No waitingの改良

34 Deadlock detection and timeouts
トランザクション間の競合が少ないと予想される場合は得策。 長いトランザクション、多くのデータを参照するトランザクションでは不適切 Wait-for graph Ti → Tj　：　トランザクションＴｉがトランザクションＴｊの有するロックを待つことを示す サイクル：デッドロック

35 種々の側面 いつデッドロック検出を行うか？ Victim selection タイムアウト ロック待ち時間が閾値を越す場合
同時実行トランザクションが一定数を越える場合 Victim selection 長時間走行し、多くの更新を行ったトランザクションを選択しないようにする。 タイムアウト 一定時間以上待ちが発生すると、デッドロックが実際に発生しているかどうかによらず、アボートする。簡単に実装可能なため良く利用される。

36 Starvation 特定のトランザクションが長時間に渡り待たされ、他のトランザクションは正常に処理される場合
フェアなスケジューリングがなされていないことによる。 プライオリティを付加しても良いが、待ち時間がたつにつれて、プライオリティを上げる 常にvictimに選択されないように、何度も選ばれるとそのプライオリティを上げるなどして回避する。

37 Timestampに基づく 同時実行制御方式
Ｔｉｍｅｓｔａｍｐ トランザクションを識別するためにＤＢＭＳによって生成されたユニークな値 (通常）トランザクション投入時刻 ＴＳ（Ｔ） ロックを利用しないので　デッドロックフリー timestampの付け方 トランザクション毎に整数を付与。１づつ増やす 時刻を利用。完全に同時に２つのトランザクションが駆動されることが無いことを保証しておく。

38 ＴＯアルゴリズム タイムスタンプ順にserializableにする。 したがって ＴＯ timestamp orderingと呼ばれる
Read_TS(X): read timestamp of itemX Xを読むことが出来たトランザクションのタイムスタンプの中で最大の値 Read_TS(X)=TS(T) T:Ｘを読んだ最も若いトランザクション Write_TS(X): write timestamp of X Xに書き込むことの出来たトランザクションのタイムスタンプの値で最大のものを指す。

39 Basic TO algorithm トランザクションＴがread_item(X), write_item(Y)を発行する時点でトランザクションのタイムスタンプと read_TS(X), write_TS(X)を比較。 トランザクションのタイムスタンプ順序が正しいかどうかをチェック。 順序が不正な場合には当該トランザクションをアボート、新しいタイムスタンプを付加して再投入 あるトランザクションがアボートするとそれの書いたデータを参照したトランザクションもアボートする必要がある（cascade rollback)

40 Basic TO Tが write_item(X)を発行すると Tが read_item(X)を発行すると 特徴：
If read_TS(X)>TS(T) or if write_TS(X)>TS(T) Then abort and rollback T Else write_item(X), set write_TS(X) to TS(T) Tが read_item(X)を発行すると If write_TS(X)>TS(T) then abort and rollback T If write_TS(X) <=TS(T), then read_item(X) and set read_TS(X) to the larger of TS(T) and the current readTS(X) 特徴：　 2PLと同様にserializable　(許容クラスはそれぞれ異なる） デッドロックフリー

41 Ｓｔｒｉｃｔ ＴＯ Strictにすることにより cascadeless
Ｓｔｒｉｃｔ　ＴＯ Strictにすることにより　cascadeless TS(T)>write_TS(X)の場合、TS(T’)=write_TS(X)なるＴ‘がコミットするまでread/writeを延期させる。 実現のためには　ロックに相当する機構が必要となる（デッドロックフリー）

42 Ｔｈｏｍａｓ‘ｓ　Ｗｒｉｔｅ Conflict serializabilityは保証されない。書き込みrejectをより少なくする効果を有する。 If read_TS(X)>TS(T) then abort and rollback T If write_TS(X)>TS(T) then do not execute write operation but continue! write_item(X) could be ignored. 問題が生じると上の条件で検出される。 If neither of the above conditions occurs, Then execute the write_item(X) operation