データベースシステムⅠ 第9回今日の話題 • 同時実行制御 – ロックとデッドロック • 障害回復 – 障害の分類 – ログを用いた障害回復デッドロック（dead lock） • ロックを用いる同時実行制御を行う場合、複数のトランザクションが互いのアンロックを延々と待ち続け一切処理が進まない状態になってしまうことがある – これを「デッドロック」という • ロックを用いるデータベースシステムでは、デッドロック状態にないかどうかをチェックしたり、デッドロック状態を解消したりする機構を持つ必要があるデッドロックの例 • データベースにA、Bの２つの項目が格納されているとする – トランザクションT1がAにロックをかけ、 Bがアンロックされるのを待っている – トランザクションT2がBにロックをかけ、 Aがアンロックされるのを待っているという状態になると、デッドロックである • 二相ロッキングプロトコルを使っていたとしても、デッドロックは起こりうるデッドロックが起こるスケジュールの例 • トランザクションT1 XL1（A） W1（A） XL1（B） W1（B） UL1（A） UL1（B）ここでデッドロックが起こる • トランザクションT2 XL2（B） W2（B） XL2（A） W2（A） UL2（A） UL2（B）デッドロック状態ロック中 A T1 アンロック待ちアンロック待ち T2 B ロック中デッドロックの検出法 • 待ちグラフ（wait-for graph）による方法 – どのトランザクションがどのトランザクションのアンロックを待っているかをグラフにしたもの – トランザクションTjがロックしている項目がアンロックされるのをトランザクションTiが待っているときTi→Tjの有向エッジをひく – 待ちグラフにサイクル（閉路）ができたらデッドロック状態 • タイムアウトによる方法 – トランザクションが一定時間以上アンロック待ちになったら、「デッドロックの可能性がある」として、強制的にアボートする待ちグラフの例 T2 T1 T1 T3 T2 デッドロックの回避法 ① 一括ロックする方法 ② データを順序付ける方法 ③ トランザクションを順序付ける方法 ① 一括ロックする方法 • ロックする必要のある項目を、それぞれのトランザクションがその開始時に一括してロックする方法 • すべてのロックがとれなかったら、一切ロックせず、しばらく待ってから再度ロックを試みる • この方法と二相ロッキングプロトコルを組み合わせたものを「保守的二相ロッキングプロトコル（conservative two phase locking）」という通常の二相ロックトランザクション開始ロックの量コミット成長相縮退相保守的二相ロック厳格な二相ロック開始コミット時間 ② データを順序付ける方法 • 項目にある種の順序をつけておき、各トランザクションがロックをかける順序はこの順序を守るようにする方法ロック中 T1 1 2 3 アンロック待ち × T2 ③ トランザクションを順序付ける方法 • トランザクション開始時刻の時刻印（timestamp）を使ってトランザクションに順序を導入し、待ち関係のサイクルができないようにする方法 – ウェイト・ダイ方式 – ワウンド・ウェイト方式 • 以下、トランザクションTiの時刻印をTS（Ti）と書くウェイト・ダイ（wait-die）方式 • トランザクションTiがある項目をロックしようとしたとき、それと競合するロックが別のトランザクションTjによってすでになされていたら、 – TS（Ti）＜TS（Tj）であれば、 TiはTjがアンロックするのを待つ – TS（Ti）＞TS（Tj）であれば、 Tiはアボートする • すなわち、Tiの開始が先ならアンロックされるのを待ち（wait）、そうでなければTiはアボートする（die）ウェイト・ダイ方式 Ti ロック Ti は Tj のアンロックを待つ Tｊロック Ti Ti はアボートするロック Tｊロックワウンド・ウェイト（wound-wait）方式 • トランザクションTiがある項目をロックしようとしたとき、それと競合するロックが別のトランザクションTjによってすでになされていたら、 – TS（Ti）＜TS（Tj）であれば、 Tjをアボートさせる – TS（Ti）＞TS（Tj）であれば、 TiはTjがアンロックするのを待つ • すなわち、Tiの開始が先ならロックを持っているTj をアボートさせ（wound）、そうでなければTiはアンロックされるのを待つ（wait）ワウンド・ウェイト方式 Ti Tj をアボートさせるロック Tｊロック Ti ロック Tｊロック Ti は Tj のアンロックを待つ ③ トランザクションを順序付ける方法 • ウェイト・ダイ方式でも、ワウンド・ウェイト方式でも、最小の時刻印を持つトランザクション（実行中のトランザクションのうち、一番最初に始まったトランザクション）はアボートされることがない • したがって、アボートされたトランザクションに元と同じ時刻印を与えて再実行すれば（いつか必ず最小の時刻印になるので）、いずれはアボートされることなく実行されることが保証されるアプリケーションプログラムのデッドロック対策 • デッドロックが発生するといずれかのトランザクションが強制的にアボートされる • また、デッドロックを回避するためにトランザクションが強制的にアボートされることもある • したがって、アプリケーションプログラムは原則として、強制アボートが起こったらトランザクションを再開するようにプログラミングされる必要がある • デッドロックの発生頻度を下げるため、トランザクションを小さくする（こまめにコミットするようにする）という手法はよく使われる障害回復 • トランザクションのACID属性を完全に実現するためには、データベースシステム稼働中に何らかの障害が起こった場合の対処が必要となる • このような機能のことを障害回復機能という障害の分類 • トランザクション障害 • システム障害 • メディア障害トランザクション障害（transaction failure） • 個々のトランザクションが何らかの理由でコミットに至る前に異常終了するケース • 以下のような場合がある – 何らかの理由でトランザクションが自主的にアボートする場合 – アプリケーションプログラムの実行時エラーにより強制的に終了させられる場合 – デッドロックによりトランザクションの続行が不可能な場合、などシステム障害（system failure） • ハードウェアあるいはソフトウェア上の問題からシステムダウンが発生し、その時点でのすべてのトランザクションが異常終了してしまうケース • 障害発生時のすべての主記憶上のデータは消滅するが、ディスクから障害発生直前の状態のデータを読み出すことは可能であるので、これを用いて復旧するメディア障害（media failure） • データベースを格納したディスクに障害が発生し、データの読み出しができなくなるケース • 復旧にはバックアップとログを用いる（後述）トランザクションと障害回復 • トランザクション障害が発生した場合は、トランザクションはアボートされる – したがって、もしそのトランザクションが障害発生前にデータベースに書き込みを行っていたら、それを元の値に戻す処理をしなければならない • システム障害が発生した場合には、リスタート処理が行われる – 障害発生時点でコミット済であったトランザクションとそれ以外のトランザクションによる基本操作を区別し、その後始末を行う必要がある – コミット済のトランザクションによるデータの書き込みは確実にデータベースに反映しなければならない – コミット済でないトランザクションは確実にアボートさせなければならない基本操作とバッファリング • アプリケーションはデータベースシステムに対して read/writeの基本操作を要求する • データベースシステムは、効率よく処理するため（ディスクアクセスの回数を減らすため）バッファリングを行う – バッファの内容をディスクに書き戻す処理を「フラッシュ（flush）」という • したがって、アプリケーションがwriteを実行したからといって、必ずしもその時点でその内容がディスクに書き込まれているとは限らない • バッファリングされた内容がディスクに書き込まれる前に（フラッシュされる前に）障害が起こると問題となる基本操作とバッファリング read / write バッファ（主記憶）アプリケーションプログラムデータベースデータベースシステムアプリケーションのread/writeとデータベースシステムのread/writeのタイミングは一致しないシステム障害発生時 read / write バッファ（主記憶）アプリケーションプログラムデータベースデータベースシステム障害が発生すると、バッファの内容がすべて失われるシステム障害のケース begin read（A, x） read（B, y） x := x – 10000 y := y + 10000 write（A, x） write（B, y） commit AからBへの送金・ Aから出金・ Bに入金ケース（１）ここで障害が起こった場合ケース（２）ここで障害が起こった場合ケース（１） write（A, x）の直後に障害 • writeは終わっているのでｘの値はバッファに書き込まれているが、障害が発生する前にそれがディスクに書き戻されていたかどうかが問題となる • ディスクに書き戻されているとすると、Aからの出金は終わってるのにBへの入金が終わっていないことになる→不整合状態 • ディスクに書き戻されていないとすると、Aからの出金も終わっていないことになる • いずれにせよ、システムリスタート時には、トランザクション開始前の状態に戻す必要があるケース（２） commitの直後に障害 • write（A, x）、write（B, y）は終わっているのでx, yの値はバッファには書き込まれたが、障害が発生される前にそれがディスクに書き戻されていたかどうかが問題となる • トランザクションはコミット済であるので、たとえディスクに書き戻される前に障害が発生していたとしても、システムリスタート時の処理でデータベースがコミット後の状態になることを保証しなければならないログを用いた障害回復 • 障害回復を実現するために最も一般的に用いられるのはログ（log）を用いる手法である – ログのことをジャーナル（journal）ということもある • ログとは、すべてのトランザクションのすべての基本操作の内容をディスク中に記録したものである – ログの個々の操作の記録を「ログレコード（log record）」という • ログを見ると、いつ、どのトランザクションが、データベースのどの項目に対してどういう操作を行ったか、がわかる • 障害が発生したら、システムリスタート時にこのログを使ってデータベースを正しい状態に戻す処理を行うログレコードの内容 • トランザクションTiの開始： begin [ B: Ti ] • トランザクションTiによる書き込み： write（A, x） [ W: Ti, A, Old, New ] • Old: Aの更新前の値（ビフォアイメージ（before image）） • New: Aの更新後の値（アフターイメージ（after image）） • トランザクションTiによる読み出し： read（A, x） [ R: Ti, A ] • トランザクションTiのコミット： commit [ C: Ti ] • トランザクションTiのアボート： abort [ A: Ti ] • なお、それぞれのログレコードには、LSN（log sequence number）という番号を順に付けるトランザクションの実行とログトランザクションT1 トランザクションT2 begin read（A, x） begin write（B, 150） commit read（B, y） write（A, 200） commit この例では、トランザクションが始まる前のAとBの初期値はともに「１００」としている（before image) ログ 1: 2: 3: 4: 5: 6: 7: 8: [ B: T1 ] [ R: T1, A ] [ B: T2 ] [ W: T1, B, 100, 150 ] [ C: T1 ] [ R: T2, B ] [ W: T2, A, 100, 200 ] [ C: T2 ] これがLSN スケジュールとログレコード • ログレコードの種類はB（begin）、R（read）、W（write）、 C（commit）、A（abort）の5種類 • ここで、「厳格な二相ロッキングプロトコル」などにより、トランザクションのスケジュールが厳格であることが保証される場合を考える • すると、「あるトランザクションがアボートする結果として同じ項目をreadしている別のトランザクションを連鎖的にアボートさせる」ということが起きないので、障害発生時にreadのことを考慮する必要がなくなる • 以下ではそのような状況を考え、readは無視し、write だけ考えることとするログ先書きプロトコル（write ahead log protocol, WAL） • 基本操作write（A, New）が行われた場合、Newの値がバッファリングされ、やがてその内容がディスク内のデータベースに書かれる • この操作が行われるとき、ログレコード [ W: Ti, Old, New ] が記録されるが、この記録もディスク上のファイル（ログファイル）に書かれる • 障害発生時にOldの値が必要になる可能性があることを考えると、データベースにNewを書くよりもさきに、ログファイルに上記のログレコードが先に書かれている必要がある • この方式を「ログ先書きプロトコル」というログファイルとバッファリング • 通常、ログファイルへのログレコードの記録もバッファリングされる – 毎回ファイルに書き込むのではなく、必要な時にまとめてフラッシュする • データベースシステムではLSN（log sequence number）を用いて現在どのログレコードまでがディスクに書き込み済みかを管理する障害回復の方式 • no-undo/redo方式 • undo/no-redo方式 • undo/redo方式 • 障害発生後の回復処理（リスタート時の処理）で、実行中だったトランザクションの基本操作を元に戻す処理を「undo」、やり直す処理を「redo」という no-undo/redo方式 • 障害回復（リスタート）時にはredoのみ行い、undoは行わない方式 • トランザクション中でのwrite操作はログにのみ記録し、そのトランザクションがコミットするまでデータベース本体への更新は一切行わない • どの段階で障害が発生しても、コミット済でないトランザクションの操作はデータベースに書き込まれていないので、障害回復時にundoの必要がない（したがってビフォアイメージの記録の必要がない） • 障害回復時には、コミット済であるのにデータベースに書き込みが終わっていなかった処理を、redoする no-undo/redo方式通常時：トランザクション実行中 read / write × アプリケーションプログラム実行時にはデータベースには書き込まず、ログにのみ記録を残すデータ用バッファ [ B: Ti ] [ W: Ti, ・・・] データベース × ログ用バッファデータベースシステムログファイル no-undo/redo方式通常時：コミット時① read / write アプリケーションプログラムコミット時にはまず、ログの内容をログファイルに記録する（これにより、コミット済状態となる）データ用バッファデータベース [ B: Ti ] [ W: Ti, ・・・] [ C: Ti ] ログ用バッファデータベースシステムログファイル no-undo/redo方式通常時：コミット時② read / write アプリケーションプログラムその後、バッファをフラッシュしてデータベースを更新するデータ用バッファデータベース [ B: Ti ] [ W: Ti, ・・・] [ C: Ti ] ログ用バッファデータベースシステムログファイル no-undo/redo方式障害回復時：コミット済でない場合 read / write アプリケーションプログラムコミット済でない場合データベースには何も書き込まれていないので、回復処理で何もする必要がないデータ用バッファデータベース [ B: Ti ] [ W: Ti, ・・・] [ C: Ti ] ログ用バッファデータベースシステムログファイル no-undo/redo方式障害回復時：コミット済の場合 read / write アプリケーションプログラムコミット済の場合データベースの更新が終わっていない可能性があるので、ログを使って redoするデータ用バッファデータベース [ B: Ti ] [ W: Ti, ・・・] [ C: Ti ] ログ用バッファデータベースシステムログファイル undo/no-redo方式 • 障害回復（リスタート）時にはundoのみ行い、redoは行わない方式 • no-undo/redo方式の逆 • トランザクション中でのwrite操作はすべてデータベースに対して更新し、そのトランザクションがコミットする前にすべてのデータベース本体への更新を行う • どの段階で障害が発生しても、コミット済のトランザクションの操作はデータベースへの更新が終わっているので、障害回復時にredoの必要がない（したがってアフターイメージの記録の必要がない） • 障害回復時には、コミット済でないトランザクションが行ったデータベースへの更新をundoする undo/no-redo方式通常時：コミット時 read / write アプリケーションプログラムコミット時にはデータベースへの更新を行い、ログもログファイルに記録する（これにより、コミット済状態となる）データ用バッファデータベース [ B: Ti ] [ W: Ti, ・・・] [ C: Ti ] ログ用バッファデータベースシステムログファイル undo/no-redo方式障害回復時：コミット済の場合 read / write アプリケーションプログラムコミット済の場合データベースの更新はすべて終わっているので、何もする必要がないデータ用バッファデータベース [ B: Ti ] [ W: Ti, ・・・] [ C: Ti ] ログ用バッファデータベースシステムログファイル undo/no-redo方式障害回復時：コミット済でない場合 read / write アプリケーションプログラムコミット済でない場合データベースの更新が終わってしまっている可能性があるので、ログを使ってundoするデータ用バッファデータベース [ B: Ti ] [ W: Ti, ・・・] [ C: Ti ] ログ用バッファデータベースシステムログファイル no-undo/redo方式と undo/no-redo方式 • どちらもシンプルな方式ではあるが、「コミット済になるまでバッファをフラッシュできない（no-undo/redo方式の場合）」、あるいは、「コミットする前には必ずすべての更新をデータベースに対して行わないといけない（undo/no-redo方式の場合）」という、制約がある • そのため、実際には次に説明するundo/redo 方式を採用するのが主流となっている undo/redo方式 • 障害回復（リスタート）時に必要に応じてundo処理もredo処理もどちらも行う方式時間ログ B1 B2 C1 障害発生 – T1は障害前にコミットしているので必要に応じて redoする – T2は障害前にコミットしていないので必要に応じて undoする undo/redo方式の詳細 • トランザクションの開始： begin – ログレコード [B: Ti ] をログ用バッファに書き込む • トランザクションによる書き込み： write（A, x） – ログレコード [ W: Ti, Old, New ] をログ用バッファに書き込む – データ用バッファで A を含むページを更新する • このページをディスクに書き込む場合は、その前にログ用バッファを書き込む（ログ先書きプロトコル） • トランザクションのコミット： commit – ログレコード [ C: Ti ] をログ用バッファに書き込んだ後、ログ用バッファをフラッシュする • これにより、トランザクションは「コミット済」状態となる • トランザクションのアボート： abort – ログレコード [ A: Ti ] をログ用バッファに書き込んだ後、ログの内容に基づきそのトランザクションが行ったwriteのundo処理を行う undo/redo方式の例（１）トランザクションの開始アプリケーションプログラムログ用バッファに [ B: Ti ] を書き込む Old Old データ用バッファデータベース [ B: Ti ] ログ用バッファデータベースシステムログファイル undo/redo方式の例（２）トランザクションによる書き込み write アプリケーションプログラムログ用バッファに [ W: Ti, Old New ] を書き込み、新しい値 Newをデータ用バッファに書き込む New Old データ用バッファデータベース [ B: Ti ] [ W: Ti, O, N] ログ用バッファデータベースシステムログファイル undo/redo方式の例（３）トランザクションのコミット write アプリケーションプログラムログ用バッファに [ C: Ti ]を書き込み、ログ用バッファをフラッシュする New Old データ用バッファデータベース [ B: Ti ] [ W: Ti, O, N] [ C: Ti ] ログ用バッファデータベースシステム [ B: Ti ] [ W: Ti, O, N] [ C: Ti ] ログファイル undo/redo方式の例（４）障害回復処理 write アプリケーションプログラムログを使って undo/redo処理する New Old データ用バッファデータベース [ B: Ti ] [ W: Ti, O, N] [ C: Ti ] ログ用バッファデータベースシステム [ B: Ti ] [ W: Ti, O, N] [ C: Ti ] ログファイル障害のタイミングと undo/redo処理の詳細以下の例で考えてみるトランザクションT1 トランザクションT2 begin read（A, x） begin write（B, 150） commit ケース１： read（B, y）ここで障害発生 write（A, 200） commit ケース２：ここで障害発生ログ 1: 2: 3: 4: 5: 6: 7: 8: [ B: T1 ] [ R: T1, A ] [ B: T2 ] [ W: T1, B, 100, 150 ] [ C: T1 ] [ R: T2, B ] [ W: T2, A, 100, 200 ] [ C: T2 ] ケース（１）トランザクションT1 トランザクションT2 begin read（A, x） begin write（B, 150）ログ 1: 2: 3: 4: [ B: T1 ] [ R: T1, A ] [ B: T2 ] [ W: T1, B, 100, 150 ] • この場合、ログから T1、T2ともにコミットしていないことがわかる • したがって、4: [ W: T1, B, 100, 150 ] をundoするケース（２）トランザクションT1 トランザクションT2 begin read（A, x） begin write（B, 150） commit read（B, y） write（A, 200）ログ 1: 2: 3: 4: 5: 6: 7: [ B: T1 ] [ R: T1, A ] [ B: T2 ] [ W: T1, B, 100, 150 ] [ C: T1 ] [ R: T2, B ] [ W: T2, A, 100, 200 ] • この場合、ログから T1がコミットし、T2がにコミットしていないことがわかる • したがって、4: [ W: T1, B, 100, 150 ] をredoし、 7: [ W: T2, A, 100, 200 ] をundoするチェックポイント（checkpoint） • undo/redo方式に基づく障害回復処理（リスタート時の処理）では、システム起動時から障害発生時までのログが必要になるが、これは膨大な量になる – 障害回復時にこれをすべてundo/redoするのでは時間がかかる • そこで、一定周期でバッファの内容をディスクに書き込み（フラッシュし）、障害回復時にはその時点以降のみundo/redoすればよいようにするのが普通である – これを「チェックポイント（checkpoint）」という単純なチェックポイント処理手順 • 以下の手順により、チェックポイントを作る ① 新たなトランザクションの開始を禁止する ② アクティブな（実行中の）トランザクションがすべてコミットするかアボートするまで処理を続ける ③ アクティブなトランザクションが無くなったら、まずログ用バッファをフラッシュし、続いてデータ用バッファをフラッシュする ④ ログ用バッファにログレコード [ CHECKPOINT ] を書き込み、もう一度ログ用バッファをフラッシュする • これにより、CHECKPOINT以降に発生した障害の回復処理は、CHECKPOINT以降のログのみを undo/redoすればよくなるメディア障害と対策 • データベース本体や、ログファイルを保存しておくディスク装置が故障するのがメディア障害である • メディア障害に対する対処としては以下のようになる – 定期的にデータベース全体のバックアップをとる – バックアップ時以降のログを使って回復する • どんな障害でもログが失われると回復処理が不可能になるので、ログは異なる装置に二重・三重に記録を取るようにする成績評価 • 期末試験で60点以上取得し、かつ、実習課題のレポートの本提出をすることを、単位の条件とする • 合格者の評点（Ａ～Ｃ）は、期末試験の結果と、実習課題、レポート内容から決定する期末試験について • 期末試験は、6月26日（木）に7C202（実習室３）で行う • 試験時間は5限（15時15分～16時30 分、75分間）に行う – 終わった人から提出し、退席してよい • 試験は、教科書・資料等の持ち込み可、端末の使用可、ネットでの検索・閲覧可とする – 問題の分量が多いので、事前に予習をしっかりしておくこと – メール、チャット、SNS、Yahoo!知恵袋等の利用は不可とする • http://wombat.cc.tsukuba.ac.jp/dbsystem1/ に模擬試験問題とその解答例・解説を載せておくので、参考にすることレポートについて • レポートの締め切りは「本提出」と「再提出」の 2回がある – 本提出締切： 6月21日（土） 19時 – 再提出締切： 7月10日（木） 19時 • どちらも manaba で提出すること • 本提出締切には必ず提出すること（単位の要件の一つ） • 再提出は必須ではないが、提出すればプラスに評価するレポートの本提出について • 以下の内容を含めること – 実体関連図 – MySQLで作成したスキーマ（create table、create indexなど SQL文のリスト） – PHPのプログラムリスト – （PHPプログラムが完成している場合には）実行したPHPプログラムの主要なWeb画面のコピー（3～5画面程度） • 以下については、これまでの実習での提出後に加筆・修正を行った場合には、本提出のレポートに含めること – 機能一覧、画面フロー設計、画面設計、入出力項目の洗い出し、データベース設計 • 作業したものをそのまま束ねて提出すればよい – 全体のつじつまがあってなかったり、完成していない部分があってもよいレポートの再提出について • 以下の内容を含めること – （本提出より完成度を高めた）PHPのプログラムリスト – 実行したPHPプログラムの主要なWeb画面のコピー（3～5画面程度） • 作業したものをそのまま束ねて提出すればよい – 全体のつじつまがあってなかったり、完成していない部分があってもよい