Aritalab:Lecture/Database/Transaction
Contents |
トランザクション
データの読み出し、書き込みにおける処理の単位をトランザクションと呼びます。例えば銀行の預金管理や鉄道の予約システムでは、同時並行で要求される処理を矛盾なく処理しなくてはいけません。一般にデータベースの管理システム (DBMS) は、以下の条件を（できるだけ）満たすように設計されます。
| ACID性 | 解説 | 銀行口座の例 |
|---|---|---|
| 原子性 (Atomicity) | 個々のトランザクションが原子のように分割できない塊として処理される。 | 別口座に送金する際、送金途中で処理が中断しない。 |
| 一貫性 (Consistency) | トランザクション処理はデータベースの中身に矛盾を起こさない。 | 口座の残高がマイナスになる場合は処理を中断する。 |
| 独立性 (Isolation) | トランザクションが並行して行われても、個々の結果は独立に考えてよい。 | 別口座への送金が複数同時に実行できる。 |
| 永続性 (Durability) | トランザクションが完了したら、（その結果が実際にはディスクに反映されていなくても）その結果はシステムクラッシュ等に影響されない。 | 送金が終了したら停電が起こっても残高がもとに戻らない。 |
これらの性質は頭文字を取ってACID性と呼ばれます。個々のトランザクションは正常終了 (commit)、または中断 (abort) で終わります。 トランザクションを実行する順序をスケジュールとよびます。DBMSは処理速度を上げるためにトランザクションを並列実行します。
デッドロック
DBMSがトランザクションを管理するのに使う代表的手法がロックプロトコルです。 リソースへのアクセスを適切にロック（施錠）することで、ACID性を保ちます。最も簡単なロック機構を以下に示します。
- トランザクション T がリソース A を使うときにロック LOCKT( A )
- T が終了したら全てのリソースのロックを解除 UNLOCKT( A )
| T1 | T2 |
|---|---|
| LOCK(A) | |
| LOCK(B) | |
| LOCK(B) | |
| LOCK(A) |
この機構により書き込み中のリソースを読み出したり、同一のリソースに書き込むエラーは防げますが、右の表にある順序で互いにリソースを要求しあうと動けなくなる状態（デッドロック）を引き起こします。表の行方向を時系列順とみなしましょう。 リソース A, B をそれぞれ別のトランザクションがロックした後にお互いに相手の持つリソースを要求している状況です。
デッドロックの回避法
簡単なデッドロックの対処は、タイムアウトを用いて動かなくなっているトランザクションを全て中断 (abort) することですが[1]、現実的ではありません。実際にデッドロックが生じる場面はそう多くありませんが、以下の方策が考えられます。
待ち受けグラフ
トランザクション T1 がロックしているアイテムを、トランザクション T2 が待っているとき、T1 ← T2 と矢印を引いて表現したグラフを待ち受けグラフ (waits-for graph) といいます。矢印はトランザクションの待ち受け順を意味しており、閉路はデッドロックに対応します。
ロックマネジャーはこのグラフをチェックし、閉路が生じたらいずれかのトランザクションを中断します。中断するトランザクションは例えばもっとも最近に実行されたもの、ロックするリソース数が最小のものなどです。一般にトランザクション T1 と T2 がリソースを取り合い、優先度が T1 > T2 の場合、以下の選択肢があります。
- T1 がウェイトする
- T1 はウェイトせず、優先度の低い T2 を中断して実行する
T1 がウェイトして T2 がいつか中断されるのを待つ方針を wait-die 戦略、優先度の高い T1 が決して待たない方針を wound-wait 戦略といいます。いずれにしても、トランザクションが最初に開始された時間（タイムスタンプ）を記録して、中断されたトランザクションが後で必ず実行される保証が必要です。
Conservative 2PL
（2PLの言葉の意味は以下で解説します。）各トランザクションは必要とするリソースすべてのロック要求を出し、ロックマネージャーは全要求を許可するか、全要求を不許可にする方法です。ロック要求をトランザクションの途中ですることが無いためデッドロックが起きえません。
しかしトランザクションが用いる全リソースをすべて事前に把握するのは難しく、必要以上にリソースをロックすることになります。また一つでもリソースが確保できなければ、そのトランザクションは実行を遅らせなくてはなりません。そのため、実際には利用されません。
リソースの順序付け
ロック要求するリソースに順序を導入し、各トランザクションは順位の高い順からロックを要求する方法です。待ち受けグラフで T1 ← T2 ← T3 という関係を考えましょう。T2が待つT1のリソースの順位を A 、T3 が待つ T2 のリソースの順位を B とします。T3 が待つリソースは T2 が T1 を待ち始める以前に LOCK されているはずなので、順序の高い順に LOCK するルールから A > B が成立します。ですから待ち受けグラフでデッドロックがあると仮定すると、待っているリソースの順番が A > B > ... > A とならざるを得ず、矛盾するというわけです。
この手法はリソースを必要以上にロックする必要がないとしてもトランザクションが用いる全リソースをすべて事前に把握しなくてはなりません。そのため、実際には利用されません。
ロック以外の回避法
トランザクションの並列実行をおこなうのに、リソースをロックしない方法もあります。例えば各トランザクションが正常終了 (commit) するとき、その他のトランザクションと競合 (conflict) していないかをチェックし、競合していたら新しい方のトランザクションを中止して再実行するものです。タイムスタンプは絶対的な順序を導入するため、時間順に実行すればデッドロックは起きません。
各トランザクションは実行開始時間を示すタイムスタンプを持ち、開始時間が早いものから順に終了するようにします。競合の検出には読み出しや書き込み状況を管理するメカニズムが必要で、OSの提供する critical section などを利用します。
タイムスタンプによる管理
各リソース A について、最も直近に読まれた時間を R( A ), 書き込まれた時間を W( A ) で確認できるようにします。トランザクション T が開始された時間を S( T ) とすると、以下の管理法が考えられます。
- トランザクション T がリソース A を読み込むとき
- S( T ) < W( A ) のとき
T の開始後に書き直されているため、T を中断しタイムスタンプを更新して再実行 - S( T ) >= W( A ) のとき
T は A を読み込んで R( A ) を max( R(A), S(T) )に更新
- S( T ) < W( A ) のとき
- トランザクション T がリソース A に書き込むとき
- S( T ) < R( A ) のとき
T の開始後に他プロセスが読み始めているので、 T を中断してタイムスタンプを更新して再実行 - S( T ) < W( A ) のとき
他のプロセスが書き込んだ後だが、T は中断せずにそのまま上書きする (Thomas' Write Rule) - それ以外は、T は A に書き込んで W( A ) を S(T) に更新
- S( T ) < R( A ) のとき
ここで注目すべきは、Thomas' Write Rule [2]です。
|
Thomas' Write Rule は左のようなスケジュールがあった時、トランザクション T2 の結果は他のトランザクションによって利用されていないと仮定して、T1 の上書きを許す管理方針です。つまり右のトランザクションと同値とみなします。T2（または他のプロセス）が read をおこなっていたら T1 による書き込みは中断される点に注意してください。 |
|
2相ロック
- 参考、注釈
