この記事は「リレーショナルデータベース入門 第３版」のトランザクションの同時実行の章の一部のサーベイです。
こちらの記事の続きです
ロック法
ここでは時間の経過とともに次々と到着するトランザクションステップをあるプロトコルに従って実行させると、その結果が直列可能性を保証されているという「動的」な同時実行制御について紹介する。この目的のためのプロトコルは以下のようなものがある
・ロッキングプロトコル
・時刻印順序プロトコル
・楽観的制御法
・多版同時実行制御法
ロッキングプロトコルによるロック法から順に紹介する
ロッキングプロトコル
定義(ロッキングプロトコル)
単にこのプロトコルに従っても一般には相反直列可能性を保証しない。
つまり必ずしもDBの一貫性を保証するとは限らない。なぜならデータ項目を読んだ直後にその項目をアンロックしていることにある。
例えば、以下はロッキングプロトコルに従っているが、遺失更新異状を起こす相反直列不可能なスケジュールである。
２相ロッキングプロトコル
定義(２相ロッキングプロトコル)
以降、２相ロッキングプロトコルを2PLと略す
先ほどの例はreadの後に writeが控えてるにも関わらずunlockしているので２相ロッキングプロトコルに従っていない。
以下が2PLに従った例となる。トランザクションが必要なデータ項目をロックしていく過程を成長相、アンロックしていく過程を縮退相という。
さて、いくつか言葉の定義をする。
スケジュールが順法であるとは、すでに他のトランザクションがロックしているデータ項目を別のトランザクションがロックすることはない場合をいう。
また、ロック法では静的なスケジュール法とは異なり動的である。従って、予めトランザクション群の同時実行のためのスケジュールを立案できないので、次々と到着するステップが2PLに従って実行されるように制御するアルゴリズムが必要になり、それをスケジューラという。
スケジューラは同時実行しているトランザクション群の最後のステップが到着・実行終了時点で、全てのステップの実行履歴を出力できるが、それを静的なスケジュール法でのスケジュールとみなすことができる。2PL関係の記述でスケジュールと述べるときは、この意味で指す。
2PLに関して次が知られている。
定理
また、2PLかつ順法であれば相反直列化可能であることが知られている。
2PLに従えばとは言っても、各トランザクションがいつの時点から縮退相に入るのかを予め知るのは難しい。そこで、コミットかアボートに達しCOMMIT処理かROLLBACK処理を行なった直後に、ロックしていたデータ項目をアンロックする方法が考えられる。これを厳格な2PL という。多くのDBMSがこれを採用している。
デッドロック
2PLに従った順法なスケジュールは相反直列化可能であることがわかったが、実はデッドロックという大きな欠点がある。
例えば以下のような場合、次のread処理のためにお互いが相手のアンロック待ちになってしまう。このようなデッドロックという状況が発生すると、それ以降のトランザクションの実行ができなくなる。
このようなデットロック発生時はどちらかのトランザクションを生贄としてアボートさせるような対応が存在するが、一方でデッドロックフリーというデッドロックの発生を予防するという考え方もある。さまざまなアプローチが考案されてきたが、ここでは時刻印を使う方法を述べる、
この方法では、トランザクションTi開始時点の時刻TS(Ti)がトランザクションの時刻印として付与される。従って、トランザクションTiがトランザクションTjより先に始まれば、TS(Ti)<TS(Tj)である。このとき、TiはTjより年長、TjはTiより年下という。時刻印を用いたデッドロック防止法には次の二つの方式がある
・待つ死ぬ方式
もしTiがデータ項目xをロックしようとしたとき、それをTjがロックしていた場合
TiがTjより年上ならばTiはTjを待ち、年下ならばTiは死ぬ
アボートされたTiはアボートされる前の時刻印を付与されて再スタートする
・傷つけつ待つ方式
もしTiがデータ項目xをロックしようとしたとき、それをTjがロックしていた場合
TiがTjより年上ならば年下のTjを傷付ける、年下ならばTiはTjを待つ
アボートされたTjはアボートされる前の時刻印を付与されて再スタートする
いずれの方式もデッドロックフリーな方法である。しかしいずれも、何らかのトランザクションをアボートすることにより波及ロールバックが発生してしまい、再スタートを余儀なくされてしまう問題がある。
ロッキングプロトコルの効率改善
2つのトランザクションがデータ項目を読むとき、前述のロッキングプロトコルでは片方の実行のためにロックするともう片方がそれを読めないという考え方であった。 しかし、読むだけなら許してあげようという考え方があり、この結果TPSを向上させる。このため次の２種類のロックを導入することが考えられた
・共有ロック
・専有ロック（排他ロック）
つまりトランザクションがデータ項目を読むためにロックする場合は共有ロックをかけ、一方書くためにロックする場合は専有ロックをかける。2PLの概念はこの場合にも素直に拡張でき、今までの定理もそのまま成立する。
多版同時実行制御(MVCC)
多版同時実行制御（MVCC）とは、2PLに従った場合のように競合しているトランザクションの実行終了を待つのではなく、同じデータ項目の異なる版（version）を養牛することによってトランザクションの隔離性を向上させつつ同時実行性を高める手法である。静的なスケジュール法や2PLに従った同時実行制御では保証されないスケジュールも、MVCCでは正しい結果を保証することがありうる。
MVCCの元でトランザクションの同時実行を司るスケジューラを多版スケジューラという。まず多版スケジューラがどのようにステップ制御していくのかを見る
今、トランザクション集合{T1,...,Tn}を同時実行するためのスケジュールSが与えられたとする。 Sに従いトランザクションTiが実行を開始した時、その時の時刻をTiに時刻印TS(Ti)として付与する。 なお、トランザクションは並列でなく同時実行なので、お互いの開始時間は異なる。 つまり、時刻印を見れば先発か後発なのかが分かる。
次にデータ項目xを考える。多版スケジューラはxの版(version)を保持する。これを例えば、xi,xj,xkという具合に書く。なお初期値はx0と書く。 版はトランザクションがデータ項目に書きを実行したときに生成され、時刻印が付与される。
ではMVCCのアルゴリズムを説明する。
MVCCアルゴリズムは次の2つの規則に則り、トランザクションの読み書きを版への読み書きに変換する
このアルゴリズムでは、つまりTi:read(x)やTi:write(x)の操作を版への読み書きの形に変換しているのである。 その上でreadの変換は最新の版のデータ項目に対して行うこと、writeの変換は「自分より後発のトランザクションが自分より先発のトランザクションの書き出し結果を呼んでいるとき」は行わないことを制約としている。 このアルゴリズムの沿ったスケジュールを多版スケジュールという。
なお、MVCCに従う多版スケジュールは正当であることが知られている。
