A Dynamic Mobility Histogram Construction Method Based on Markov Chains

Size: px

Start display at page:

Download "A Dynamic Mobility Histogram Construction Method Based on Markov Chains"

ありさかつま
5 years ago
Views:

1 データベース 12: 同時実行制御石川佳治

2 トランザクション

3 トランザクション (transaction) アプリケーションにおけるひとまとまりの処理を構成するデータベース操作の集まり例 : 預金口座 A から預金口座 B へ10000 円を送金するトランザクション read(a, x) read(b, y) x := x y := y write(a, x) write(b, y) データベースに対する操作は, 究極的には read, write の組合せで表現できるため, 操作を read, write に単純化 2

4 トランザクション処理トランザクション処理 (transaction processing) もしくはトランザクション管理 (transaction management) 並行して実行されるトランザクションの競合を解決各種障害への発生への対応 ( 次章 ) ACID 特性 (ACID properties) トランザクション処理において保障することが望ましい性質 3

5 ACID 特性 (1) 原子性 (atomicity) トランザクションがデータベース処理の単位トランザクションの結果は, 以下の二者択一コミット (commit): データ操作のすべてが確定されたものとしてデータベースに反映されるアボート (abort): データ操作がすべて取り消される一部の操作のみの中途半端な実行は許されない整合性 (consistency) 整合性がとれたデータベースに対して実行されたトランザクションの実行の結果は, 整合性のとれたものとなる 4

6 ACID 特性 (2) 隔離性 (isolation) 複数のトランザクションを並行処理した場合でも, トランザクションは同時に処理されている他のトランザクションの影響を受けない複数のトランザクションの並行処理の結果は, トランザクションを何らかの順序で逐次処理した場合と一致しなければならない耐久性 (durability) いったんコミットしたトランザクション中でのデータ操作は, その後の障害などで消滅してはならない 5

7 アプリケーションにおける命令通常, アプリケーションプログラムには, read, write 以外に以下の命令を提供 begin: トランザクションの開始を宣言 commit: トランザクションのコミットを要求 abort: トランザクションのアボートを要求処理の中断に利用 begin read(a, x) x := x write(a, x) commit begin read(a, x) x := x ( 何らかの問題を検知 ) abort コミットの例アボートの例 6

8 トランザクションの状態 (1) 5 つの状態アクティブ : トランザクションを実行中コミット処理中 :commit 命令後の状態コミット済 : コミットのための処理が終了アボート処理中 :abort 命令後や, コミット処理が何らかの理由で正常に終了できないときアボート済み : アボート処理が終了 begin アクティブ commit abort コミット処理中コミット済アボート処理中アボート済 7

9 トランザクションの状態 (2) ロールバック (rollback) アボートされるトランザクションが, アクティブな状態の間に何らかのデータ更新を行っていた場合に, それらをすべて取り消す処理トランザクション開始前の状態に巻き戻す 8

10 並行処理と直列可能性

11 並行処理における不整合 (1) DBMS は複数のトランザクションを並行実行待ち時間 ( 入出力, 入力 ) を有効活用一定の規約を設けないと不整合が発生トランザクション T 1 read(a, x) x := x write(a, x) トランザクション T 2 read(a, y) y := y write(a, y) データ更新の喪失の例トランザクション T 2 が書き込んだ値をトランザクション T 1 が上書きしてしまうため, トランザクション T 2 の更新は反映されない 10

12 並行処理における不整合 (2) トランザクション T 1 トランザクション T 2 s := 0 read(a, x) s := s + x read(b, y) s := s + y read(a, z) z := z write(a, z) read(b, w) w := w write(b, w) 整合性のないデータ読出しの例トランザクション T 1 は誤った合計値を出力する同時実行制御 (concurrency control; 並行処理制御 ) により,ACID 特性に反する不整合が生じないようにする 11

13 直列可能性直列可能性 ( 直列化可能性 ; serializability) トランザクション T 1,, T n を並行処理したときの実行結果が, それらを何らかの順序で逐次処理したときの実行結果と一致すること同時実行制御の役割トランザクション T 1,, T n が並行処理された場合でも, 各トランザクション T i の直列可能性を保証する 12

14 スケジュール (1) データベースに対する基本操作の表記 R i (A): トランザクション T i による項目 A の read W i (A): トランザクション T i による項目 A の write C i : トランザクション T i のコミット A i : トランザクション T i のアボートトランザクション T 1,, T n に対するスケジュール (schedule) T 1,, T n の基本操作を, インターリーブして一列に並べたもの T i 内の基本操作の順序関係は保存 13

15 スケジュール (2) T 1 T 2 s := 0 read(a, x) s := s + x read(b, y) s := s + y read(a, z) z := z write(a, z) read(b, w) w := w write(b, w) 各トランザクションの表現 T 1 : R 1 (A) R 1 (B) T 2 : R 2 (A) W 2 (A) R 2 (B) W 2 (B) 上の実行順序に対応するスケジュール R 2 (A) W 2 (A) R 1 (A) R 1 (B) C 1 R 2 (B) W 2 (B) C 2 14

16 直列スケジュール直列スケジュール (serial schedule) 対象トランザクション群を何らかの順序で逐次処理する場合のスケジュール非直列スケジュール (nonserial schedule) 直列スケジュールでないスケジュール直列可能スケジュール (serializable schedule) 直列スケジュールと等価なもの並行処理における直列可能性の保証とは, スケジュールが直列可能となることを保証すること 15

17 スケジュールの等価性 (1) 異なる定義が存在競合等価 (conflict equivalent): 同じトランザクション集合に対する二つのスケジュール S 1, S 2 は, 以下を満たすとき競合等価 1 S 1 において R i (A)(W i (A)) が W j (A)(R j (A)) に先行するならば,S 2 においても同様の関係が成り立つ 2 S 1 において W i (A) が W j (A) に先行するならば, S 2 においても同様の関係が成り立つ write 処理に関して不整合が発生するので, write に関わる実行順序に着目 16

18 スケジュールの等価性 (2) ビュー等価 (view equivalent) 1 S 1 において R i (A) より読まれる A 値が,W j (A) によって書かれた値または A の初期値ならば,S 2 においても同様の関係が成り立つ 2 各項目 A に関して,S 1 において最後に A 値を書くのが W i (A) ならば,S 2 においても同様のことが成り立つ直観的には, 各 read が同じ値を読み, かつ最後のデータベースの状態が同じであること 17

19 スケジュールの等価性 (3) 競合等価の方がより厳しい条件例競合等価なスケジュールはビュー等価その逆は必ずしも成立しない S 1 :R 1 (A) W 2 (A) C 2 W 1 (A) C 1 W 3 (A) C 3 S 2 :R 1 (A) W 1 (A) C 1 W 2 (A) C 2 W 3 (A) C 3 S 1, S 2 はビュー等価 R 1 (A) が読む値は両者において初期値両者において最後に A を書くのは W 3 (A) しかし, 競合等価ではない S 1 では W 2 (A) が W 1 (A) に先行.S 2 ではその逆. 18

20 競合直列可能 / ビュー直列可能競合直列可能 (conflict serializable) そのスケジュールがある直列スケジュールと競合等価である場合ビュー直列可能 (view serializable) そのスケジュールがある直列スケジュールとビュー等価である場合競合直列可能スケジュールはビュー直列可能 : その逆は成立しない先の例の S 1 は直列スケジュールである S 2 とビュー等価なのでビュー直列可能しかし,S 1 は競合直列可能ではない 19

21 競合直列可能かの判定 (1) スケジュール S に対する先行グラフ (precedence graph) を作成 1 S に参加する各トランザクション T i に対し, ノード N(T i ) を作成 2 R i (A)(W i (A)) が W j (A)(R j (A)) に先行するとき有向エッジ N(T i ) N(T j ) をひく 3 W i (A) が W j (A) に先行するとき有向エッジ N(T i ) N(T j ) をひく先行グラフにサイクル ( 閉路 ) がなければ S は競合直列可能で, サイクルがあれば競合直列可能でない 20

22 競合直列可能かの判定 (2) スケジュール S の例ルール 2 ルール 2 R 1 (A) R 1 (B) R 2 (A) R 2 (C) W 1 (B) C 1 R 3 (B) R 3 (C) W 3 (B) C 3 W 2 (A) W 2 (C) C 2 ルール 2 ルール 2 先行グラフ T 1 T 2 ルール 3 T 3 サイクルがないので競合直列可能トポロジカルソートで等価な直列スケジュールが得られる R 1 (A) R 1 (B) W 1 (B) C 1 R 3 (B) R 3 (C) W 3 (B) C 3 W 2 (A) W 2 (C) C 2 R 2 (A) R 2 (C) 21

23 まとめ : 競合等価とビュー等価の比較ビュー等価の方が条件が緩いスケジュールがより柔軟に選択できる : 先の例では両方のスケジュールを選択可能計算量が NP 完全 : 実際の利用には適さない競合等価は現実的な解競合直列可能かの判定が容易柔軟性にはやや劣るビュー等価の立場で直列可能なスケジュールが競合等価の立場で直列可能とならない場合があるため, 可能なスケジュールの候補が少なくなりうる 22

24 スケジュールの諸性質 (1) これまでの議論はコミットされたトランザクションのみを対象 : しかし, トランザクションはアボートされる可能性もあるアボートに着目した場合の性質について A) 回復可能性 (recoverable) R i (A) で読まれるA 値がW j (A) によって書かれた値であり,T i がコミットするときにはC j がC i に先行するという条件が常に成立回復可能でない例 :W 1 (A) R 2 (A) C 2 A 1 T 1 が書いた A 値を T 2 が読んでコミットしているので,T 1 をアボートしても,T 2 をもう取り消しできない 23

25 スケジュールの諸性質 (2) 連鎖的アボート (cascading abort): あるトランザクションのアボートが他のトランザクションのアボートを連鎖的に引き起こす現象 W 1 (A) R 2 (A) A 1 C 2 ならば回復可能だが,T 1 をアボートすると T 2 もアボートする必要あり B) 連鎖的アボートの回避 R i (A) で読まれるA 値がW j (A) によって書かれた値であるときにはC j がR i (A) に先行するという条件が常に満たされるときトランザクションは取り消されうる値を読まない常に回復可能 : その逆は成立しない 24

26 スケジュールの諸性質 (3) C) 厳格性 (strictness) R i (A) または W i (A) よりも W j (A) が先行するときには,C j または A j がその R i (A) または W i (A) に先行するという条件が常に満たされるとき厳格なスケジュールは連鎖的アボートを回避 : 逆は成り立たない例 :W 1 (A) W 2 (A) C 2 A 1 は連鎖的アボートを回避するが, 厳格ではない厳格なスケジュールではアボート処理が簡単 T i のアボート時には,T i がwriteした値をwrite 前の値に戻せばよい厳格でない場合 ( 上の例 ) では面倒 25

27 スケジュールの諸性質 : まとめ回復可能性, 連鎖的アボートの回避, 厳格性は直列可能性とは直交例 :R 1 (A) W 2 (A) W 2 (B) C 2 R 1 (B) C 1 は厳格であるが直列可能でない各性質の関連ビュー直列可能競合直列可能回復可能直列スケジュールは常に直列可能で厳格なスケジュール直列連鎖的アボート回避厳格 26

28 ロックを用いた同時実行制御

29 ロックの概念実際の DBMS では, 何らかの機構規約を用いて同時実行を制御ロック (lock) もっとも一般的な機構単純な例 : 各項目 A に対する排他的ロック A にロックをかけることができるのは, ある時点では 1 トランザクションに限るすでにロックされている項目へのロック要求は, そのロック解除まで待ち状態となる並行性が低いという問題点 28

30 共有ロックと専有ロック (1) readのみの場合に排他的なロックをかけるのは, 並行性を必要以上に落としてしまう解決策 : 二つのロックに分ける共有ロック (shared lock, S lock) 読出しの場合に用いる共有ロック同士は両立専有ロック (exclusive lock, X lock) 書込み時に用いる排他的ロック共有 (S) 専有 (X) 共有 (S) Y N 専有 (X) N N 両立性行列 (compatibility matrix) 29

31 共有ロックと専有ロック (2) ロックの変換 (conversion) いったんデータを読み出した後, その値に応じて書込みを行うかを決定することも多いロックのアップグレード共有ロックを専有ロックに変換する処理他のトランザクションがその項目を共有ロックしていない場合のみ許可されるロックのダウングレード専有ロックを共有ロックに変換 30

32 ロッキングプロトコル例 : 図 8.2(b) のトランザクション実行例に対するロック操作 XL 2 (A) R 2 (A) W 2 (A) UL 2 (A) SL 1 (A) SL 1 (B) R 1 (A) R 1 (B) UL 1 (A) UL 1 (B) C 1 XL 2 (B) R 2 (B) W 2 (B) UL 2 (B) C 2 XL / SLはX / Sロックをかける操作,UL はロックを解除する操作を表すこの操作例は両立性を満たすが, そもそも図 8.2(b) の実行例は不整合な例ロッキングプロトコル (locking protocol) ロックをかける操作と解く操作に関する規約合法 (legal): プロトコルに従ったスケジュール 31

33 デッドロックデッドロック (deadlock): ロックを用いた場合に発生例 1 T 1 : XL 1 (A) XL 1 (B) W 1 (A) W 1 (B) UL 1 (A) UL 1 (B) T 2 : XL 2 (B) XL 2 (A) W 2 (B) W 2 (A) UL 2 (B) UL 2 (A) 問題点 :1 の XL 1 (A) の後に 2 の XL 2 (B) を実行してしまうと, それ以降の 3,4 ともにロックをかけるのに失敗してしまう対策については後述 32

34 二相ロッキングプロトコル (1) 二相ロッキングプロトコル (two phase locking protocol; 2PL) 競合直列可能性を保証するロッキングプロトコルロック操作を二つの部分に分離成長相 (growing phase): ロックをかける操作だけからなる縮退相 (shrinking phase): ロックを解く操作だけいったんロックを解いた後に再びロックをかけてはいけない成長相ではロックのアップグレードが, 縮退相ではダウングレードが許される 33

35 二相ロッキングプロトコル (2) 例 ( 先と同じ ) XL 2 (A) R 2 (A) W 2 (A) UL 2 (A) SL 1 (A) SL 1 (B) R 1 (A) R 1 (B) UL 1 (A) UL 1 (B) C 1 XL 2 (B) R 2 (B) W 2 (B) UL 2 (B) C 2 T 1 の縮退相 T 1 の成長相 T 1 は二相ロッキングプロトコルに従っている T 2 はそうでないすべてのトランザクションが二相ロッキングプロトコルに従うことが必要二相ロッキングプロトコルではデッドロックが発生する可能性あり : 先の例 34

36 厳格な二相ロッキングプロトコルアボート操作前に専有ロックを解くと回復可能性のないスケジュールが生じうる例 : 二相ロッキングプロトコルに従うT 1, T 2, T 3 XL 1 (A) R 1 (A) W 1 (A) UL 1 (A) SL 2 (A) R 2 (A) UL 2 (A) C 2 SL 3 (A) R 3 (A) A 1 T 1 がアボートするとT 3 が連鎖的にアボートされる T 2 はすでにコミット済みなので取り消し不能厳格な (strict) 二相ロッキングプロトコル縮退相における最初のロックを解く操作はトランザクションのコミットまたはアボート操作の後競合直列可能であり厳格性も満たす 35

37 デッドロックデッドロックへの対処策デッドロックの検出を行う方法デッドロックを回避する方法 ( 省略 ) デッドロックの検出待ちグラフ (wait-for graph) による方法各トランザクション T i に対してノード N(T i ) を作成 T i が他のトランザクション T j のロックが解かれるのを待っているとき, 有向エッジ N(T i ) N(T j ) を引く待ちグラフにサイクルがあればデッドロック : 犠牲者 ( victim) を選びアボートタイムアウトによる方法 : 一定時間以上待ち状態のトランザクションをアボートする 36

38 他の同時実行制御方式 ( 簡単に )

39 時刻印を用いた同時実行制御時刻印順 (timestamp ordering) 方式各トランザクションに, 発生順に一意な時刻印を与える時刻印の順にトランザクションを逐次実行する場合と等価なスケジュールが生じるように制御各項目 A に二種類の時刻印を持たせる RTS(A) / WTS(A): これまでに A の read / write を行ったトランザクションの時刻印のうち最大値項目 A の read / write の際には,RTS(A) / WTS(A) の値を見て, 実行するかアボートするかの規約に従う 38

40 楽観的同時実行制御楽観的同時実行制御 (optimistic concurrency control) 適する状況ほとんどのトランザクションが read だけ複数トランザクションの同時発生がまれアイデアとりあえず他のトランザクションと競合しないと仮定してトランザクションを実行終了時に競合がなかったかを確認 : 競合していたらアボート処理などへ進む 39

41 多版同時実行制御多版同時実行制御 (multiversion concurrency control; MVCC) 各項目 A に対し write がなされるたびに,A に対する新しい版 (version) を生成し維持管理 read/writeの際は, 時刻印などの情報を用いて版の新しさを考慮してアボート処理を制御最近のDBMS(Oracle, PostgreSQLなど ) では, ロックに基づく手法と多版同時実行制御の組合せがよく見られる 40

42 最近の動向一般の DBMS では多版同時実行制御 ( MVCC) をとるものが主流 :Oracle 等新たな問題マルチコア, マルチスレッド : 多くの競合が発生不揮発性メモリ : 入出力速度の向上トランザクション処理の速度が与える影響の割合が増大 HTAP( ハイブリッド型トランザクション / アナリティクス処理 ): 入ってきたデータをどんどん分析トランザクション処理の効率化が重要に競合によるアボート処理をどれだけ減らせるか : 楽観的手法が再び注目 41

43 余談 :SQL の同時実行制御

44 SQL の同時実行制御隔離レベルに対する 4 つのオプション非コミット読取り (read uncommitted): コミットされていないデータを読むこと ( ダーティーリード ) があるコミット済み読取り (read committed): 以前 readした項目 Aの値を再度 readしたとき, その値が他のトランザクションにより変更されていることがある再読込み可能読取り (repeatable read): ある条件で複数回検索したとき, 新たな行 (phantom; 幽霊 ) が追加されていることがある直列可能 (serializable): 直列可能性を保証多くの DBMS ではコミット読取りがデフォルト設定効率化のため :ACID 特性の I( 隔離性 ) は完全には保証されないため, 開発者側で意識する必要あり 43

45 同時実行制御の指定データの挿入更新削除 (SQL の INSERT / UPDATE / DELETE) の際に, 明示的にロックをかける必要はない DBMS が自動的にロックをかけ, 不要になれば解除明示的にロックをかける機能もあり例 :Oracle の FOR UPDATE 句更新を前提としてデータの読取りを行う場合に使用トランザクション終了まで検索結果にロックをかける SELECT * FROM TABLE FOR UPDATE 44

46 木ロッキングプロトコル (1) 木ロッキングプロトコル (tree locking protocol) 競合直列可能性を保証適用できる条件 : データベース中の項目が木構造を持ち, 複数の項目をアクセスするトランザクションが木のルートからリーフ方向にデータをアクセストランザクション T i のロック操作の条件 1 T i において最初にかけるロックは, いずれの項目 Aに対して行ってもよい 2 ロックを解く操作はいつ行ってもよい 3 ロックを解く操作はいつ行ってもよい 4 一度ロックをかけた後, そのロックを解いた項目を再びロックできない 45

47 木ロッキングプロトコル (2) 木ロッキングプロトコルに従う例実行例 : T 1 が途中までロックした時点 T 1 : XL 1 (A) R 1 (A) XL 1 (B) UL 1 (A) R 1 (B) W 1 (B) XL 1 (E) UL 1 (B) R 1 (E) UL 1 (E) T 2 : XL 2 (B) R 2 (B) XL 2 (D) R 2 (D) UL 2 (D) XL 2 (E) UL 2 (B) R 2 (E) W 2 (E) UL 2 (E) XL 2 B 木ロッキングプロトコルの特徴デッドロックは発生しない A XL 1 C D E F T 2 は B をロックする必要があるため T 1 を待つことになる T 1 T 2 というスケジュール共有ロックがある場合へも拡張可能 46

48 ロックの粒度 (1) データベース中には種々の大きさのデータ単位が存在し, 階層構造をなす例 : データベース, ファイル, レコード, フィールドデータベースファイル 1 ファイル 2 ファイル 3 レコード 1 レコード 2 フィールド 1 フィールド 2 ロックの粒度 (granularity): ロック対象の項目の大きさ 47

49 ロックの粒度 (2) 粒度をどの程度にするかは処理効率に影響ロックの粒度が細かいと, トランザクション同士の不必要な競合を減らすことができるしかし, 大量のデータの操作には多くのロック操作が必要種々のロックの粒度がある場合, ロックを認めてはならない状況が発生例 T 1 があるファイルS 中のレコードRを専有ロックしているとき,T 2 がS 全体に対する専有ロックを要求 Sにロックがかかっていないが,T 2 の要求は認められない 48

50 インテンションロックインテンションロック (intention lock): 粒度に関する問題への対処ある項目 A の下位の項目 A をアクセスする際,A の下位の項目を共有専有の目的でアクセスしていることを知らせるためのロックを A にかけるインテンションロックの種類共有インテンションロック (intention shared lock; IS ロック ): 下位項目を共有ロックの可能性あり専有インテンションロック (intention exclusive lock; IXロック ): 下位項目を専有ロックの可能性共有専有インテンションロック (shared and intention exclusive lock; SIXロック ): 部分構造を共有ロックすると同時に, 下位の項目を専有ロックする可能性 49

Chapter Two

Chapter Two Database 第 13 回 : トランザクション処理 ~ 同時実行制御 ~ 上智大学理工学部情報理工学科高岡詠子 No reproduction or republication without written permission. 許可のない転載再発行を禁止します 2012/1/12 2012 Eiko Takaoka All Rights Reserved. 1 分離レベル(isolation