Aritalab:Lecture/Database/Transaction

トランザクション

データの読み出し、書き込みにおける処理の単位をトランザクションと呼びます。例えば銀行の預金管理や鉄道の予約システムでは、同時並行で要求される処理を矛盾なく処理しなくてはいけません。一般にデータベースの管理システム (DBMS) は、以下の条件を（できるだけ）満たすように設計されます。

ACID性	解説	銀行口座の例
原子性 (Atomicity)	個々のトランザクションが原子のように分割できない塊として処理される。	別口座に送金する際、送金途中で処理が中断しない。
一貫性 (Consistency)	トランザクション処理はデータベースの中身に矛盾を起こさない。	口座の残高がマイナスになる場合は処理を中断する。
独立性 (Isolation)	トランザクションが並行して行われても、個々の結果は独立に考えてよい。	別口座への送金が複数同時に実行できる。
永続性 (Durability)	トランザクションが完了したら、（その結果が実際にはディスクに反映されていなくても）その結果はシステムクラッシュ等に影響されない。	送金が終了したら停電が起こっても残高がもとに戻らない。

これらの性質は頭文字を取ってACID性と呼ばれます。個々のトランザクションは正常終了 (commit)、または中断 (abort) で終わります。 トランザクションを実行する順序をスケジュールとよびます。DBMSは処理速度を上げるためにトランザクションを並列実行します。

デッドロック

DBMSがトランザクションを管理するのに使う代表的手法がロックプロトコルです。 リソースへのアクセスを適切にロック（施錠）することで、ACID性を保ちます。最も簡単なロック機構を以下に示します。

1. トランザクション T がリソース A を使うときにロック LOCK_T( A )
2. T が終了したら全てのリソースのロックを解除 UNLOCK_T( A )

デッドロックをおこす例

T1	T2
LOCK(A)
	LOCK(B)
LOCK(B)
	LOCK(A)

この機構により書き込み中のリソースを読み出したり、同一のリソースに書き込むエラーは防げますが、右の表にある順序で互いにリソースを要求しあうと動けなくなる状態（デッドロック）を引き起こします。表の行方向を時系列順とみなしましょう。 リソース A, B をそれぞれ別のトランザクションがロックした後にお互いに相手の持つリソースを要求している状況です。

デッドロックの回避法

簡単なデッドロックの対処は、タイムアウトを用いて動かなくなっているトランザクションを全て中断 (abort) することですが、現実的ではありません。実際にデッドロックが生じる場面はそう多くありませんが、以下の方策が考えられます。

待ち受けグラフ

トランザクション T1 がロックしているアイテムを、トランザクション T2 が待っているとき、T1 ← T2 と矢印を引いて表現したグラフを待ち受けグラフ (waits-for graph) といいます。矢印はトランザクションの待ち受け順を意味しており、閉路はデッドロックに対応します。

ロックマネジャーはこのグラフをチェックし、閉路が生じたらいずれかのトランザクションを中断します。中断するトランザクションは例えばもっとも最近に実行されたもの、ロックするリソース数が最小のものなどです。一般にトランザクション T1 と T2 がリソースを取り合い、優先度が T1 > T2 の場合、以下の選択肢があります。

• T1 がウェイトする
• T1 はウェイトせず、優先度の低い T2 を中断して実行する

T1 がウェイトして T2 がいつか中断されるのを待つ方針を wait-die 戦略、優先度の高い T1 が決して待たない方針を wound-wait 戦略といいます。いずれにしても、トランザクションが最初に開始された時間（タイムスタンプ）を記録して、中断されたトランザクションが後で必ず実行される保証が必要です。

２相ロック

（２相ロックは以下で更に解説します。）各トランザクションは必要とするリソースすべてのロック要求を出し、ロックマネージャーは全要求を一度に許可するか、全要求を不許可にする方法です。ロック要求をトランザクションの途中ですることが無いためデッドロックが起きえません。一般に２相ロックという場合、「全要求を一度に許可」するプロトコルではなく、全てのロック要求を、ロック解除より前におこなうプロトコルを指します。この場合、２相ロックでデッドロックを回避できません。

トランザクションが用いる全リソースをすべて事前に把握するのは難しい作業です。そのため、必要以上にリソースをロックすることになります。また一つでもリソースが確保できなければ、そのトランザクションは実行を遅らせなくてはなりません。デッドロックを回避するためにロック要求を一括しておこなう制約は、実際には用いられません。

リソースの順序付け

ロック要求するリソースに順序を導入し、各トランザクションは順位の高い順からロックを要求する方法です。待ち受けグラフで 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) )に更新
• トランザクション T がリソース A に書き込むとき
  • S( T ) < R( A ) のとき
    T の開始後に他プロセスが読み始めているので、 T を中断してタイムスタンプを更新して再実行
  • S( T ) < W( A ) のとき
    他のプロセスが書き込んだので、 T を中断　(ここで、T は中断せずにそのまま上書きする方針を Thomas' Write Rule と呼ぶ）
  • それ以外は、T は A に書き込んで W( A ) を S(T) に更新

ここで注目すべきは、Thomas' Write Rule です。

T1 T2 read(A) write(A) commit write(A) commit

Thomas' Write Rule は左のようなスケジュールがあった時、トランザクション T2 の結果は他のトランザクションによって利用されていないと仮定し、T1 の上書きを許す管理方針です。つまり右のトランザクションと同値とみなします。トランザクションの中断を少しでも防げる点が利点です。 二相ロックによって直列化可能となるトランザクションではないところに注意してください。 また T2（または他のプロセス）が read をおこなっていたら T1 による書き込みは中断される点に注意してください。

T1 T2 read(A) commit write(A) commit

整列化可能性

スケジュール S T2: LOCK B T1: LOCK A T2: UNLOCK B T1: LOCK B T1: UNLOCK A T3: LOCK A T3: UNLOCK A T1: UNLOCK B T2: LOCK A T2: UNLOCK A

整列化可能性 (serializability) とは、（実行命令がインターリーブされた）トランザクションスケジュールを、実行結果を変えることなくトランザクション毎にまとめたスケジュールに変換できるかという概念です。例えば、左に示すスケジュール S を考えましょう。LOCK 命令と UNLOCK 命令が実行される時間順に示されています。（write や read 命令はすべて省略されていると考えてください。）しかし、T1 ∼ T3 の中身が入り乱れていて、実行内容が明らかではありません。T1, T2, T3 または T2, T1, T3 のようにトランザクション毎に分けて考えたくなります。しかし、整列化の順序は 3! = 6 通りあり、全通りを検証することはとても面倒です。 ここでは、スケジュールが整列化可能であるか判定するためのグラフと、整列化可能性を保証する2相ロックプロトコルを紹介します。

整列化可能性判定グラフ

整列化可能性判定グラフは、各トランザクションを頂点とし、各リソース R について、T_i:UNLOCK R ... T_j:LOCK R という命令列 (i < j) のたびに T_i から T_j に有向辺を引いたグラフです。各辺は、T_i → T_j の順番が守られねばならないという関係を意味しています。

スケジュール S
T2: LOCK B T1: LOCK A T2: UNLOCK B T1: LOCK B T1: UNLOCK A T3: LOCK A T3: UNLOCK A T1: UNLOCK B T2: LOCK A T2: UNLOCK A

定理：判定グラフに閉路があれば整列化は不可能、なければ可能

もし閉路がない場合、グラフの出力辺しか持たないトランザクション i が必ず存在します。そのトランザクションを実行列に加え、グラフから頂点 i およびそこから出る辺を消去します。この操作を繰り返せば、整列化が終了します。

先のスケジュール S を例に考えます。ボールド体で示した命令列に注目すると T2 → T1, T1 → T3, T3 → T2 という閉路が成り立ちます。よってこのスケジュールは整列化可能ではありません。

仮にスケジュール S が整列化可能であると仮定しましょう。例えば T2 を最初に処理すると仮定します。しかし可能性判定グラフには、T3 → T2 という辺があり、T2 が LOCK A する前に T3 の処理があります。 T2 を先に処理すると T3 のリソース A に対する処理が反映されないため、整列スケジュールは元のスケジュール S と等価になりません。同様に、いずれのトランザクションも先に独立して処理を終えられません。

２相ロック

現実のデータベースでは、トランザクション列が動的に追加・処理されるので、いちいち判定グラフを作って判断できません。そのため整列化可能性をプロトコルで保証します。その代表例が２相ロック (two-phase lock; 2PL) です。

２相ロックとは、各トランザクションにおける全ての LOCK 文を全ての UNLOCK 文より先に行うだけです。LOCK フェイズと UNLOCK フェイズの 2 段階に分かれるため、２相ロックと呼ばれます。

定理： ２相ロックに基づくスケジュールは整列化可能

判定グラフは初期スケジュール内の時系列 UNLOCK R ... LOCK R に注目して作成されます。従って時系列に注意してみると、閉路がある場合は必ずどこかの頂点で UNLOCK 文が LOCK 文に先行しています。逆に言うと、全ての LOCK 文が必ず UNLOCK 文に先行していれば閉路ができません。よって整列化可能になります。

先のスケジュール S を例に考えます。トランザクション T2 に注目すると UNLOCK B が LOCK A に先行していることがわかります。この順序を入れ替えてみましょう。そうするとT1, T2, T3の命令列をどのように組み合わせても、整列化可能性判定グラフに閉路が生じません。

スケジュール S のトランザクション（変更前） T1 T2 T3 T1: LOCK A T1: LOCK B T1: UNLOCK A T1: UNLOCK B T2: LOCK B T2: UNLOCK B T2: LOCK A T2: UNLOCK A T3: LOCK A T3: UNLOCK A

スケジュール S' のトランザクション（変更後） T1 T2 T3 T1: LOCK A T1: LOCK B T1: UNLOCK A T1: UNLOCK B T2: LOCK B T2: LOCK A T2: UNLOCK B T2: UNLOCK A T3: LOCK A T3: UNLOCK A

整列化可能≠デッドロック回避

整列化可能性とデッドロックとは別の概念です。例えば整列化可能なトランザクションからなる以下のスケジュール S' はデッドロックになっています。T2 と T1 が互いにリソース A, B を要求しつづける点に注意しましょう。この場合、T2 を中断して後回しにします。T2 を後回しにしても、整列化可能性から実行結果の同一性が保証されます。しかし T1 を後回しにすると、T3 の実行結果が初めのスケジュールと異なる可能性が生じます。また、ロック要求を一括しておこなう厳しい２相ロック (conservative 2PL) を実施する場合、デッドロックを回避できます。

デッドロックを起こす スケジュール S' T2: LOCK B T1: LOCK A T2: LOCK A T1: LOCK B T1: UNLOCK A T3: LOCK A T3: UNLOCK A T1: UNLOCK B T2: UNLOCK B T2: UNLOCK A

左のスケジュールについて整列化可能性判定グラフを作ると T1 → T3 となる。

厳しい2PLに基づく スケジュール T2: LOCK A, B T1: LOCK A, B (ここでT1は中断され後回し） T1: UNLOCK A T3: LOCK A T3: UNLOCK A T1: UNLOCK B T2: UNLOCK B T2: UNLOCK A

参考、注釈