7
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

トランザクションのACID特性とはいうものの、これまではIsolationに関わる話しかしてこなかった。
しかしDurability(記録したデータが永続化される)という特性はDBを使う上で魅力的であり欠かすことができないものである。

Strict Two Phase Lock

2PLというプロトコルは「ロックを使うときは成長相と縮退相の2フェーズで扱え」というルールだったが、このプロトコルに愚直に従うだけではDurabilityを達成することはできない。
そこで「縮退相より前にコミット(データの永続化)を行え」という追加ルールを加える事でDurabilityを達成できる。
この追加ルールが加わった2PLをStrict Two Phase Lock(S2PL)と言う。

この説明ではピンと来ないと思うので図で説明すると

non-s2pl.png

こんな感じに、縮退相が終わったでディスクに永続化する場合、もちろんT1が終わった後でしかユーザにトランザクションの完了を報告しないので、アンロック後にクラッシュしても問題ないと考えるかも知れない。しかし例えば以下のように

non-s2pl-fail.png

赤線の場所でDBの電源が落ちた場合、先に完了したT1の結果は失われ、T1の結果書き換えられたxの内容を読んで走ったT2の結果が永続化されてしまい大変な事になる

なので「アンロックは必ずコミット後」というルールを敷く事で

s2pl_safe.png

どこでクラッシュしても「ディスクに書かれていない値に基づいたトランザクションが永続化されない」という保証は守られる。これがS2PLである。技法としては古典的であるが、新しいトランザクションアルゴリズムの正しさを議論する際にも「この手法はS2PLと等価である」などという形に証明として寄せる為に使ったり非常に便利なアルゴリズムである。
なお、この手法を愚直に使うとパフォーマンスを出すのに苦労することになるため、様々な改善手法が提案されており、それはこのアドベントカレンダーでも随時取り扱っていく。

少し理論面に立ち戻った話をすると、S2PLStrictな実行結果を生成し、SS2PLRigorousな実行結果を生成する(StrictもRigorousも辞書で英和探すと「厳格な」と出てややこしいので英語のまま)。
Strictとは「あるトランザクションによる、ある値への書き込みが他のトランザクションの読み込み・書き込みより先なら、他のトランザクションの読み書きは最初のトランザクションのコミットかアボートより後になる」というルールである。平たく言い換えると、書かれた値はそのトランザクションが終わるまで触っちゃダメ、となる。ロックの挙動と良く一致しているが、2PLに必ずしも従わなくてもこの条件を満たすことはできる、具体的にはReadするだけの要素にはロックを取らない、とか。
RigorousとはStrictの条件を守った上で「あるトランザクションによる、ある値への読み込みが他のトランザクションの読み込みより先なら、他のトランザクションの読み込みは最初のトランザクションのコミットかアボートより後になる」というルールである。
Rigorousなルールに従ったスケジュールはCSRを満たす。

このあたりの詳細は後日の記事で改めて整理する。全部まとめると割と巨大な図になる。
明日はディスクに書く際の詳細について書く。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
7
Help us understand the problem. What are the problem?