S2PL、SS2PL、C2PL
背景
先日、CSR (Conflict Serializability)について説明しました。 今回は、CSRを満たすスケジューリングを動的に生成する方法について、整理してみます。
なお、ここで書くその方法とは、2PL (Two Phase Lock)なのですが、一応念のため書いておくと、2PC (Two Phase Commit)と混同しないでください。 2PCは、複数のDBでトランザクションを管理する分散トランザクションを実現する方法の一つです。 分散トランザクションは、また別の機会に書きたいと思います。 PaxosやRaft、Spannerなど。
成長層と縮退層
2PLは、トランザクションが開始しデータにアクセスすると、そのデータにロックをかけていきます。 そして、トランザクションの終了時に、全てのロックを解除します。
ロックをかけていくフェーズを成長層 (Growing Phase)、ロックを解除するフェーズを縮退層 (Shrinking Phase)と呼びます。
2PLでは、成長層と縮退層が、それぞれ多くて一回しか存在してはなりません。 すなわち、以下のようなトランザクションはOKですが、
- Lock(x), R(x), Lock(y), R(y), W(x), W(y), Unlock(x), Unlock(y)
- Lock(x), R(x), W(x), Lock(y), R(y), W(y), Unlock(x), Unlock(y)
以下のようなトランザクションは2PLではありません。
* Lock(x), R(x), W(x), Unlock(x), Lock(y), R(y), W(y), Unlock(y)
また、必ず縮退層の前には成長層があり、逆はあり得ません。
2PLで作られたhistory (実行されたトランザクションのRead, Writeの操作の履歴)は、CSRを満たします。 以下のページでは、これを帰納法によって、証明しています。
http://www.mathcs.emory.edu/~cheung/Courses/554/Syllabus/7-serializability/2PL.html
C2PL (Conservative Two Phase Lock)
C2PLでは、トランザクション内でアクセスする全てのデータのロックを、トランザクション開始時に取得します。 トランザクション開始時に全てのロックを取ることが出来なければ、トランザクションを開始しません。 すなわち、成長層が、一瞬で終わるか、ロックが取れずに成長層のままか、のどちらかです。
ただ、トランザクション内でアクセスするデータが、トランザクション開始時に全て分かっているケースは少ないので、C2PLが可能なケースは少ない気がします。
S2PL (Strict Two Phase Lock)
S2PLは、成長層はトランザクション中のデータアクセス時にロックを順次取っていくのですが、縮退層では、Writeロックをトランザクションの終了時（コミット完了時）まで保持し続け、その後全てのロックを一気に解放します。
S2PLは、アプリ側で注意しなければ、容易にデッドロックに陥ります。
ちなみに、ReadロックとWriteロックの意味は、以下のページが参考になります。
Readロックはトランザクション終了時まで保持する必要はありませんが、2PLの定義上、Readロックを解放した後にWriteロックを取ることは無いので、トランザクションの途中で他のトランザクションのよってReadした値が書き換わることはありません。
SS2PL (Strong Strict Two Phase Lock)
S2PLに対し、SS2PLは、ReadロックもWriteロックも、全て、トランザクションの終了時（コミット完了時）まで保持し、その後一気に全て解放します。
S2PLと同様に、SS2PLも、アプリ側で注意しなければ、容易にデッドロックに陥ります。
ちなみに、複数のトランザクションを設計したときに、それらがデッドロックに陥るかどうかは、TLA+などを使うと簡単に分かります。 この話は、またいつか書こうと思います。
