###### tags: `memo` `systems` # LEC 17 Isolation Slide URL: http://web.mit.edu/6.033/www/lec/s17-partial.pdf ## 前回までの話 - トランザクションは atomicity と isolation を提供する - atomicity を実現する方法のとして以下を見てきた - shadow copies - logging ## 今回の話 - isolation の実現 - トランザクション T1, ..., TN を並行に実行する - その結果が T1,..., TN を排他的に実行した場合と同じ結果になるようにする ## 分離 以下の 2 つのトランザクション、T1、T2 を並行で実行することを考える ```sql <<T1>> begin T1.1 read(x) T1.2 tmp = read(y) T1.3 write(y、tmp + 10) commit <<T2>> begin T2.1 write(x, 20) T2.2 write(y, 30) commit ``` ### 期待すべき結果のパターン トランザクション T1, T2 を並行に実行した結果、以下のどちらかになれば OK #### (1) T1 → T2 の順 ``` T1.1 read(x) T1.2 tmp = read(y) --- tmp = 0 T1.3 write(y、tmp + 10) --- y = 10 T2.1 write(x, 20) --- x = 20 T2.2 write(y, 30) --- y = 30 --------------------------- result: x = 20; y = 30 ``` #### (2) T2 → T1 の順 ``` T2.1 write(x, 20) --- x = 20 T2.2 write(y, 30) --- y = 30 T1.1 read(x) T1.2 tmp = read(y) --- tmp = 30 T1.3 write(y、tmp + 10) --- y = 40 --------------------------- result: x = 20; y = 40 ``` ### 正しくない結果のパターン 上記 (1), (2) のどちらにも結果が一致しない実行順。トランザクション T1, T2 を並行に実行した結果、こういう風になったら NG ``` T1.1 read(x) T2.1 write(x, 20) --- x = 20 T1.2 tmp = read(y) --- tmp = 0 T2.2 write(y, 30) --- y = 30 T1.3 write(y, tmp + 10) --- y = 10 --------------------------- result: x = 20; y = 10 ``` ### ナイーブな方法 - グローバルなロックを使って、各トランザクションを排他的に実行する - ただし、スケールしない ### Conflict #### Conflict とは ``` 2 つの操作が同一のオブジェクトを対象にし、少なくとも 1 つの操作が write である状態 ``` #### Conflict order とは ``` conflict する 2 つの操作 A, B の実行順としてあり得るのは A -> B もしくは B -> A この順番のことを conflict order という ``` #### Conflict SeRializable (CSR) とは ``` スケジューリングの conflict order が直列実行時の conflict order のいずれかに一致する場合、 そのスケジューリングは conflict serializable という ``` 直列に T1 → T2 を実行した場合の conflict order ``` T1.1 -> T2.1 T1.2 -> T2.2 T1.3 -> T2.2 ``` 直列に T2 → T1 を実行した場合の conflict order ``` T2.1 -> T1.1 T2.2 -> T1.2 T2.2 -> T1.3 ``` conflict serializable ではないスケジューリング ``` T1.1 read(x) T2.1 write(x, 20) T2.2 write(y, 30) T1.2 tmp = read(y) T1.3 write(y, tmp + 10) --------------------------- The conflict order is ... T1.1 -> T2.1 T2.2 -> T1.2 T2.2 -> T1.3 ``` #### Conflict graph とは ``` conflict order を辺とするグラフを構築できる。このグラフを conflict graph という ``` 直列に T2 → T1 を実行した場合の conflict graph ![](https://i.imgur.com/lGyYiEL.png) 直列に T2 → T1 を実行した場合の conflict graph ![](https://i.imgur.com/DxBzJfC.png) conflict serializable ではないスケジューリングの conflict graph ![](https://i.imgur.com/0pkrDOh.png) conflict graph で T1 と T2 と、各トランザクションの頂点集合に注目した際に、 - T1 → T2 もしくは T2 → T1 のように辺の向きが単方向になっている場合は conflict serializable - T1 <-> T2 のように双方向になっている場合は conflict serializable ではない つまり、有向非巡回グラフであれば conflict serializable である ## 目標 conflict serializable なスケジュールを生成する ### Two-Phase Locking (2PL) いくつかパターンがある。基本は以下である ``` トランザクション内でオブジェクトを 1. read する場合は reader lock (shared lock) を使用し、 2. write する場合は writer lock (exclusive lock) を使用する ``` **Strict 2PL と 2PL はデッドロックを防げない** #### 1. Strict 2PL Strict 2PL はトランザクション内で取得した writer lock を commit 後に開放する。 また、Strict 2PL は commit 後にロックを開放するので、commit されていない書き込みを他のトランザクションに読まれることはない #### 2. (Non-Strict) 2PL こちらは Strict 2PL と違って commit 前にロックを開放してもいい。しかし、ロックを開放し始めたらそのあとはロックを開放し続けるだけ（新たにロックを取得しない）。つまり、2PL は以下の 2 つのフェーズに分割できる - ロックを取得する期間 (成長期) - ロックを開放する期間 (減退期) また、2PL は Strict 2PL に比べて cascading aborts を防げない。2PL は commit 前にロックを開放できるので以下の状況 (cascading aborts) が起きうる ``` T1 T2 BEGIN BEGIN WRITER_LOCK(A) WRITER_LOCK(B) read(A) write(A+1) UNLOCK(A) WRITER_LOCK(A) \ read(A) | → wasted work if T1 aborted write(A+1) / read(B) write(B) ARBOT —— cascading aborts ——> ``` #### 3. Conservative 2PL (C2PL) C2PL はトランザクション開始前に必要なすべてのロックを取得する。あんま使われないらしい ## その他の参考文献 - [https://ja.wikipedia.org/wiki/ツーフェーズロック](https://ja.wikipedia.org/wiki/%E3%83%84%E3%83%BC%E3%83%95%E3%82%A7%E3%83%BC%E3%82%BA%E3%83%AD%E3%83%83%E3%82%AF) - CMU Database Systems 17 ([https://15445.courses.cs.cmu.edu/fall2020/slides/17-twophaselocking.pdf](https://15445.courses.cs.cmu.edu/fall2020/slides/17-twophaselocking.pdf))