ポエム
トランザクション
More than 1 year has passed since last update.

Optimistic Concurrency Control

コミットまでロックを獲得せずに実行する方式の並行制御方式。
まず、更新のたびにバージョン番号が増加する複数のデータを読む際、読んだデータのバージョン番号とデータのペアで手元で保持しておけば、再度読んだ時にバージョン番号の変動を確認すれば値が書き換わっていないかを検出できる。

read.png

この図の中の緑色の領域の中で値が変わっていない事をバージョン番号から保証できる。
これは対象となるデータがいくつに増えても同様である。

ssread.png

こうすれば複数の値を論理的に一瞬で読めた事になる。これを一般にスナップショット読み出しと言う。
これに2PLを組み合わせる事で、トランザクション中で読み書きする値に一切ロックをかけずにコミット時のバージョン比較で代用できることになる。

Optimistic Concurrency Control(OCC)はこの考え方を拡張したもので、トランザクション実行中は

  • 値を読み出す時はバージョン番号とセットでローカルに複製
  • 値を書き込む時は書き込まずにローカルに保存

という手順で実行し、コミットする段階になった際に

  1. 書き込み対象のデータのLockをすべて獲得する
  2. 読みだした値のバージョン番号をすべて確認
  3. 一致した場合に限り書き込みを行う
  4. アンロック

という順番で実行する。この1.と2.の順序が肝心で「ロックを取ってからアンロックするまではAtomic操作になる」というロックによる一斉書き込みと「バージョン番号を取得してから再度同一のバージョン番号を確認するまでの間は変更が無いことが保証できる」という2つの一貫性保証の保証範囲をうまく重ねている。

occ.png

この図の緑の領域がスナップショット読み出しで、青の領域が2PLで守られた一貫性保証ゾーンで、この二つが重なる領域が発生するのがOCCにおける最重要なポイントである。

なお、他にもデータ毎にLockを持たずに単一のロックを全体で共有する実装など、さまざまな亜種はあり、ここでは良く応用される典型的なパターンを説明している。OCCの原典「On optimistic methods for concurrency control」とも少し違う。

比較的枯れたテクニックではあるが

  • Webアクセスなどを支えるDBは読み出しが書き込みの10倍以上あることはザラ
  • Readがキャッシュラインを汚さないので、コア数に対して性能が伸びやすい

という技術的な素性によって最近提案されるアルゴリズムはOCCから改良したものである事は多い。
また、この考え方自体は汎用的なので、理解しておくと思わぬところで役に立つかも知れない。