MySQLはともかくPostgreSQLはあまり詳しくないのだが、PostgreSQLの述語ロック(Predicate Locks)が気になったので調べた。
述語ロック
一般的にロックには粒度とモードという概念がある。前者はレコードロックとかテーブルロックとかロックの範囲に関わるもので、後者は排他ロックだとか共有ロックだとか両立性に関わるものである。述語ロックは前者に属する概念であると理解している。
述語ロックがなにの役に立つのか？それはファントムの防止である。粒度ロック(典型的にはレコードロックとテーブルロック)が存在するシステムにおいて2相ロック:Two-Phase Lock(2PL)に従ってレコードロックしているだけでは、ファントムのようなAnomalyが防止できることは保証できない。リレーショナルデータベース入門には「SQLのSERIALIZABLEという隔離性水準は、2PLに加えて、述語ロックをかけて幽霊現象の発生を抑えるところまで求めた水準である」と書いてある。
これは単にレコードをロックしていくだけではレコードとレコードの間への書き込みを阻止できないからである。したがってレコードロックのように、そのとき実在するレコードだけでなくレコードとレコードの間もロックできる必要がでてくる。ちなみにテーブルロックもこの条件に当てはまるが今度はパフォーマンスの問題が出てくるのでロックの粒度はなるべく小さくしたい。
レコードロックがwhere句に対応するレコードに対してロックをとっているのに対して、述語ロックはいわばwhere句そのものにロックをとるイメージである。つまりc = 2、3というレコードがあったとして where 1 <= c and c <= 5でロックをとろうと思ったとき、レコードロックは存在する2と4にしかロックをとらないが、述語ロックは1 <= c <= 5という範囲にロックをとることが求められる。
さて述語ロックについて重要な性質の一つに実装が困難なことがある。ロックの両立性を考えるとき述語ロックは<t, lock mode, predicate>のような組で考えることができる。tはトランザクションで同じトランザクション同士ならば両立する。lock modeは共有ロックか排他ロックか。predicate(述語)はwhere句だと思えば良い。異なる二つの述語が真になる集合に共通の要素があるかどうかを判定するのはSAT問題であるからこれを実装するのは容易ではない。述語が単純である場合は比較的簡単に実装できるらしいが、実際どういう述語=where句ならば現実的に実装できるのかは詳しくない。
したがって現実的には述語ロックではなく、もうすこし単純化した手法でレコード間へのロックを防ぐことになる。その実装がMySQLでいえば、あの有名なギャップロックである。ギャップロックは述語ロックより大きめの範囲をロックすることで処理を容易にしている。またMySQLの場合はネクストキーロックという仕組みでロックをとっている。解説はネット上にいくらでもあるのでそちらを参照して欲しい。MySQLのコードを読むとMySQLのロックの粒度やモードはtype_modeで表現されることがわかるが、ロックのtypeはtableとrecordしかない。では、ギャップはどのように表現しているのかというと、record typeに対してのフラグで表現されている。ネクストキーロックはレコードを識別子(レコードが定まればギャップが一意)にできるので、テーブルロックとレコードロックという2種類の粒度しかないロックテーブルの実装においてもフラグという形でギャップという概念を導入できるし、レコードロックのわずかな拡張でロッキングプロトコルを実装できる。と、理解している。
そういう事情があるのでPostgreSQLには述語ロックがあると聞いたとき、どうやって実装したのかが気になったという次第である。前述したとおり「述語が単純である場合比較的簡単に実装できるらしいがあまり詳しくない」というのがあったので、述語(where句)が単純な場合は完全な述語ロックが、そうでない場合はなにかしらの近似が実装されていることを期待した。
PostgreSQLの述語ロック
まずPostgreSQLの述語ロックはリソースに対するアクセス制限を課すような普通のロックではない。この辺はロック(というかロックマネジャー)の仕組みが一つしかないMySQLとは対照的だと思う。PostgreSQLの述語ロックはどちらかといえばトラッカーというイメージである。トランザクションが触った部分に対してマークをつけておきコミットするときに違反が起きてないかチェックする。いわゆる楽観的ロックの類いだと思っている。トランザクション中に読みこんだレコードがあればそれを表現する部分にSIReadLockを取得していきコミット前に矛盾がないかチェックし、abortかcommitかを決定していく。ロックマネジャーもMySQLのように1つしかないわけではなく、専用のロックマネージャーをメモリ上のハッシュテーブルとして持っている。
各トランザクションがどういうデータの触り方をしたらabortすべきかは長くなるので省く(ヒドい)が、述語ロックではrw-antidependenciesだけ防げれば良い(それ以外のデータ依存性については他の仕組みでカバーされている)。rw-antidependenciesだけ考慮すれば良いのでSIReadLockはあってSIWriteLockはない理由だろう。書き込みをマークする必要ない。
で、どのように述語ロックを表現するかというとこれは単純にレコードにマークするだけである。あとからきたトランザクションが競合するかどうかは単純にレコードの間かどうかで判定する。また読み混んだレコードすべてにマークをつけていくとメモリを使いすぎるのでマークをつけたレコードが多くなりすぎたらより大きい粒度へ昇格(escalation)していく。はじめはレコード、次にページ、次にテーブルというように。この辺の粒度を荒くしてパフォーマンスを上げる方法はネクストキーロックと同じものを感じる。max_pred_locks_per_pageなどのパラメータが昇格の閾値を決めるパラメータである。昇格によってロックの範囲が広くなればabortする必要のないトランザクションもabortすることになるがそれは諦めているっぽい。
結局最初のモチベーションは
前述したとおり「述語が単純である場合比較的簡単に実装できるらしいがあまり詳しくない」というのがあったので、述語(where句)が単純な場合は完全な述語ロックが、そうでない場合はなにかしらの近似が実装されていることを期待した。
だったが、そういう感じではなかった。が、MySQLとの違いを知れて楽しかった。
参考本
述語ロックは以下が詳しい。
特に述語ロックからネクストキーロックの説明に入ってるのは「トランザクション処理」しか知らない(覚えてない)。MySQLの実装時にも参考にされた本なので一度読むとMySQLのコードがめちゃくちゃ読みやすくなる。翻訳版はまぁまぁ手に入らない
PostgreSQLには詳しくないので以下のサイトで学んだ。
あとPostgreSQLは解説が親切。
この記事ではMVCCとか分離性一般の話はしなかった。長くなるので。その辺の話は
あたりがおすすめだが、分散データベースを意識してるし、記述されている範囲が広いので初めて学ぶMVCCという感じではないかも知れない。ウェブ上であれば以下のシリーズがおすすめ。
MySQL使ってるのであれば以下が一番読みやすいと思う。
教科書的で良いのであればリレーショナルデータベース入門。
