トランザクション1 : ACID性, 2相ロック, 階層ロック

# トランザクション1 : ACID性, 2相ロック, 階層ロック

この記事は大学の期末試験勉強のために作成したものです。間違い等は悪しからず。

## <font color="DarkRed">トランザクションとは</font>

>データベースに対するアプリケーションプログラムレベルでの一つの原子的な作用（wikiより）

- 複数の利用者がデータベースを共有する
- 故障や以上が生じた場合にも内容を失わない

※SQLでは、複数の SQL 文によるデータ更新を1つの処理としてまとめてデータベースに反映させること

- 貯金の振替処理の例：口座AからBへの送金を考える。
    - 口座Aの残高から１万円引く 
    - 口座Bの残高に１万円加える 

これらを実行するには二つのUPDATE文が必要 -> この一部のみを実行すると不整合が生じるので、操作をまとめるための原則が必要。 

## <font color="Darkred">トランザクションの性質</font>

- 処理の論理的単位
    - <font color="Red">COMMIT</font>: 成功して終了 
    - <font color="Red">ROLLBACK</font>: 失敗して終了
    
SQLでは、トランザクションはCOMMIT文やROLLBACK文が実行されることで終了する。逆に言えばこの文が実行されるまでは、書かれたトランザクションの内容はDBには反映されない。このときCOMMIT文ではトランザクションの内容をDBに反映し、ROLLBACK文では書かれたトランザクションの内容、すなわちデータの変更を全てキャンセルする。

以下SQLの記法

```SQL
BEGIN WORK
...(contents_of_transaction)
COMMIT WORK
```
このときトランザクションの内容は外部から参照不可

```SQL
BEGIN WORK
...(contents_of_transaction)
ROLLBACK WORK
```
このときトランザクションの内容は何も残らない

## <font color="Darkred">トランザクションのACID性</font>
>信頼できるトランザクションが持つべき性質。ジム・グレイが定義。

### 原子性（Atomicity）

- トランザクションに含まれるタスクは、全て実行されるか、全く行われないことを保証する性質。
- 前述の銀講座の例では、二つのUPDATE文が全て実行されなければ銀行全体の預金残高に矛盾が生じる。

### 一貫性（Consistency）

- トランザクション開始と終了時にあらかじめ与えられた整合性を満たすことを保証する性質。

###  分離性（Isolation）

- トランザクション中に行われる操作の過程が他の操作から隠蔽される性質
- トランザクション履歴が直列化されていることを保証

銀行口座送金の例では、次の時点のうち外部からは**送金前**と**送金後**のみ参照可

| 時点 | 口座A | 口座B |
|:------:|:--------:|:---------:|
|送金前|100万円|200万円|
|実行中|99万円|200万円|
|送金後|99万円|201万円|

### 持続性（Durability）

- トランザクション操作の完了通知をユーザが受けた時点で、その操作は永続的となり、結果が失われない声質
- 他のトランザクションの明示的な変更がない限り、システムに障害が発生しても永続的に残る

## <font color="darkred">直列実行性</font>

> 同時実行制御における正当性の基準
> 直列に行えば**分離性**が担保できる

同時に実行したトランザクションの結果が、直列に実行したトランザクションの結果と等しいこと。**変更消失**が起こらないようにする。実行の順番は問題としない（実行された順番に問題が依存するなら分離性云々の問題ではない）

直列実行を実現するための手段として以下が考えられる。

#### シーケンシャルな実行のためにトランザクションをスケジューリング

- あるトランザクションTaが終了するまで、次のトランザクションTbは待機させる
- **同時**実行制御ではない

#### ロックによる解決

- DBという資源にロックをかけることで直列かつ同時制御な実行を可能に

## <font color="darkred">ロックと直列実行</font>

> データベースでは、ロックはトランザクションの同時性を保証する手段として使うことが出来る。すなわち、トランザクション処理が並行して行われるとき（インタリービング式トランザクション）、ツーフェーズロックを使ってトランザクションの並行実行が直列化されたトランザクションと等価であることを保証する。

>しかし、データベース内のロックの副作用としてデッドロックが発生することがある。デッドロックはロック順序を事前に定義しておくことで防いだり、待ち状態グラフを使って検出したりする。データベースの一貫性のためにロックを使う以外の手段として、完全に順序が決定されるグローバルなタイムスタンプを使用することでデッドロックを防ぐこともある。

### ２相ロック（ツーフェーズロック）

ロックの過程をロックフェーズとアンロックフェーズに分けることで直列化

<img src="https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcRXpilNvm5hi8aIICs-j-OJGY5FnHX-dExPLMFDPiBYu3nh9q1J">

### デッドロック（DeadLock）

> 特に計算機科学において、**2つ以上のスレッドあるいはプロセスなどの処理単位が互いの処理終了を待ち、結果としてどの処理も先に進めなくなってしまう**こと

#### 発生

データベースにおいては、トランザクションT1がDB資源S1を保有し、かつS2を必要としていて、同時にトランザクションT2がDB資源S2を占有し、かつS1を必要としている場合。（お互いがロックの解放を待ちあっている）

#### 検出

- 時間監視：タイムアウトによる検出
- 待ち状態グラフTWFGによる検出

#### 解消

-  いずれかのトランザクションが**アボートすること**

#### 回避

- Atomic Lock（各自調べて）
- **優先順位の導入**

## <font color="darkred">ロックの種類と階層化</font>

### X (eXclusive) 

- <font color="blue">資源を占有することを宣言。**WRITEロック**（fgetsで"w"するイメージ）</font>

### S (Share）

- <font color="blue">資源を共有することを宣言。**READロック**（fgetsで"r"するイメージ）</font>

このとき、**共有ロックをかけると、「自他共にREADはできるけど、WRITEができない」**状態になり、**占有ロックをかけると、「自分はREAD・WRITEできるけど、外部からはどちらもできない** 状態に。

デッドロックはこの概念により生じる。具体的には共有・占有or占有・占有が同時発生している時におこる。-> **もっと階層化**　-> 複数粒度ロック（MGL）

> 厳密な (Strict) ツーフェーズロックなどの他のロック手法にもある共有 (Shared) と排他 (eXclusive) だけでなく、MGLでは Intention Shared と Intention eXclusive というロックも使用する。ISロックは Xロックと衝突し、IXロックは Sロック/Xロックと衝突する。

> あるノードをS(またはX)でロックするためには、MGLはその上位ノード全体をIS(またはIX)でロックしてから、対象ノードをS(またはX)でロックする。従って、他のトランザクションはその上位ノードをX(またはSとX)でロックすることができない。

<参考> https://ja.wikipedia.org/wiki/%E8%A4%87%E6%95%B0%E7%B2%92%E5%BA%A6%E3%83%AD%E3%83%83%E3%82%AF


### IS (Intention Share)

- <font color="blue">そのものがXでロックされること以外はOK</font>
- 最も許容量の大きいロックである。

### IX (Intention eXclusive)

-  <font color="blue">そのものがS, SIX, Xでロックされること以外はOK</font>

### SIX (Share and Intention eXclusive)

- 次にISでロックされることのみOK

下の図は、左端のモードでロックされているノードに、上端のモードでロックしようとした場合にロックできるかを示している。(両立関係）

|     | N | IS | IX | S | SIX | X |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| **N** | o | o | o | o | o | o |
| **IS** | o | o | o | o | o | x |
| **IX** | o | o | o | x | x | x |
| **S** | o | o | x | o | x | x |
|**SIX**| o | o | x | x | x | x |
| **X** | o | x | x | x | x | x |

## <参考>
- https://oss-db.jp/dojo/dojo_01
- https://ja.wikipedia.org/wiki/ACID_(%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E7%A7%91%E5%AD%A6)
- https://qiita.com/daiching/items/835fa37de22b397eece0