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 戦略といいます。いずれにしても、トランザクションが最初に開始された時間（タイムスタンプ）を記録して、中断されたトランザクションが後で必ず実行される保証が必要です。

Conservative 2PL

（2PLの言葉の意味は以下で解説します。）各トランザクションは必要とするリソースすべてのロック要求を出し、ロックマネージャーは全要求を許可するか、全要求を不許可にする方法です。ロック要求をトランザクションの途中ですることが無いためデッドロックが起きえません。

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

リソースの順序付け

ロック要求するリソースに順序を導入し、各トランザクションは順位の高い順からロックを要求する方法です。待ち受けグラフで T1 ← T2 ← T3 という関係を考えましょう。T2が待つT1のリソースの順位を A 、T3 が待つ T2 のリソースの順位を B とします。T3 が待つリソースは T2 が T1 を待ち始める以前に LOCK されているはずなので、順序の高い順に LOCK するルールから A > B が成立します。ですから待ち受けグラフでデッドロックがあると仮定すると、待っているリソースの順番が A > B > ... > A とならざるを得ず、矛盾するというわけです。

この手法はリソースを必要以上にロックする必要がないとしてもトランザクションが用いる全リソースをすべて事前に把握しなくてはなりません。そのため、実際には利用されません。

2相ロック

参考、注釈