2PLでもS2PLでもロックを獲得・開放する順序の話を規定しているだけで、そのままカジュアルに走らせると悲惨な問題に直面する。デッドロックである。
Tx1: Write(x) Write(y)
Tx2: Write(y) Write(x)
という2つのトランザクションは、2PLに沿ってロックを記述すると
Tx1: Lock(x) Write(x) Lock(y) Write(y) Unlock(x) Unlock(y)
Tx2: Lock(y) Write(y) Lock(x) Write(x) Unlock(y) Unlock(x)
このようにLockがそれぞれ書き込みの前に追加される。
この二つのトランザクションが並行して走ると、無事にどちらも完走する場合もあるが、停止して動かなくなることもある。
Tx1: Lock(x) Write(x) Lock(y)
Tx2: Lock(y) Write(y) Lock(x)
それぞれのトランザクションがここまで進んだ段階で、Tx1はLock(x)を握りしめたままLock(y)が獲得可能になるのを待ち、Tx2はLock(y)を握りしめたままLock(x)が獲得可能になるのを待つ事になる。これが典型的なデッドロックである。
Dead Lock Prevention
デッドロックが起きる際には必ずロック獲得待ちが発生している。
なので獲得待ちが発生した瞬間にアボートしてしまえば、デッドロックは起きなくなる。
その一方で、本当はあと1クロック待てばロックが取れたかも知れない場合であっても構わずアボートしてしまうため、常に最善かというとそうでもないが、実用上馬鹿にできない速度が出ることも多い。
有名なものはWait-DieとWound-Waitで、これらはそれぞれ「ロックを取りながら走るが、取ろうとしたロックがすでに専有されていた場合にどうする」という挙動を表している。トランザクションがそれぞれ開始時にタイムスタンプを獲得するという前提を置いている事が多い。
Wait-Die
進行中のトランザクションが獲得しようとしたロックが既に他のトランザクションによって専有されていた場合、そのロックを握っているトランザクションのタイムスタンプと自分のタイムスタンプを比較し、自分のタイムスタンプのほうが古い（≒完了までの優先度が高い）場合に 該当ロックが解放されるまで待つ プロトコル。そうでない場合、つまり自分のタイムスタンプのほうが若かった場合は即座にアボートする。
注意して欲しいのは、これはデッドロックが起きていなくてもアボートするという事である。
単純に全体がこのルールに従って動けば、全員が待つという状態に陥らないという事を保証してくれる。
ちなみに実測した感覚で言うとアルゴリズムとして簡単に記述できるお陰かベンチマークによってはもう全部これで良いんじゃないかと言える程度に優秀な成績を残すこともある。
Wound Wait
進行中のトランザクションが獲得しようとしたロックが既に他のトランザクションによって専有されていた場合、そのロック握っているトランザクションのタイムスタンプと自分のタイムスタンプを比較し、自分のタイムスタンプのほうが古い（≒完了までの優先度が高い）場合に 相手トランザクションをアボートさせる プロトコル。そうでない場合、つまり自分のタイムスタンプのほうが若かった場合は開放されるまで待機する。
「撃っていいのは撃たれる覚悟のある奴だけだ」の言葉にもあるように、自分以外のトランザクションをアボートさせる、ということは自分自身も突然アボートさせられる可能性もあるので適宜自分の状態を監視しながらトランザクションを実行させる必要があり、実装がこっちはやや面倒である。
Wait-DieとWound-Waitは混在させて使う事ができない。もし混在させた場合、タイムスタンプの古いトランザクションT1が若いトランザクションT2が抱えたロックをWait-Dieに従って待つ一方で、トランザクションT2が年上のトランザクションT1の抱えたロックが解放をWound-Waitに従って待ってしまいデッドロックが発生する。
ちなみに上記の2つの説明ではタイムスタンプを用いたが、亜種として「より多くのロックを抱えているトランザクションが優先」「より多くのアボート回数を重ねてきたトランザクションが優先」などなど様々な優先度の基準があり、それらを適当な割合で組み合わせた亜種なども存在しうる。
No-Wait
ロックを獲得しようとtry-lockした際にロックが取れなかったら即アボートするというスキームである。実装が単純ゆえか割と侮れない性能が出て新しいデッドロック回避プロトコルを開発する研究者を困らせる事がある。これはWait-DieやWound-Waitと混在させて使ってもデッドロックを引き起こさない。
待ちグラフ
よくデータベースの教科書に出てくるデッドロック回避手段である。
僕はこれに関して詳しくないので詳しくは書かないが、自分が獲得したいロックが何なのかを他スレッドから見れるようにする必要があるのでオーバーヘッドはそれなりにありそうである。詳しく調べて書きたくなったら追記するかも。
DreadLocks
2008年の論文で提案された技法である。(Dreadlocksという言葉自体は髪型の一種で、それに引っ掛けた名称と思われる）
- 基本的にはSpin-Lockだが、ロックを獲得した際にビットを立てるのではなく自スレッドのロック情報へのポインタへとロックを書き換える。
- 確保済みロックを後から獲得しに来た別のスレッドは、ロックが獲得されているのを見て、ロック情報ポインタを辿る。
- 辿ったロック情報ポインタの中に自分が所有済みのロックが含まれていたらabort
という手順で、Spin-Lockに多少の追加コストで可能としている。
基本がTATAS-Lockなのでマルチスレッド向けにスケーラブルにするのは大変そうである。
ロックの種類についての話を書きそびれていた事に気づいたのでそのあたりは後日のアドベントカレンダー記事にする。
Conservative Two Phase Lock
トランザクション開始時にそのトランザクションが必要とするロックをすべて獲得してしまう作戦。獲得すべきロックがすべて明らかになっているならば、その獲得したいロック群から何らかの順序で（例えばメモリ上でのアドレス順とか）でロックを獲得すれば、全トランザクションが同じ順序でロックを獲得することになるのでデッドロックは発生しない。
とはいえ、トランザクション開始時に必要なロックが全てわかっている状況というのはあまり一般的ではない上、開始時から握る手前ロック獲得期間が間延びしがちで並列度があまり上がらない欠点もある。
後述するOptimistic Concurrency Controlでも同様の作戦を取る事でデッドロックを回避することがあるが、長くなるので後日記述する。