###### tags: `database`

# 並行管理

確保

* C (consistency)
* 資料庫的資料符合 integrity constraints，也就是一些限制
* 資料庫與使用者共同維護
* I (isolation)
* 對每筆交易都像是只有那個使用者在使用系統一樣

對於一次交易，其生命週期為:

* Begin
* Statement ends (如果有多個 statement)
* End
* Commit
* Rollback

## 交易排程


並行交易希望能達到

* Serializable schedule: 同時有 $n$ 次交易，最終結果為該 $n$ 次交易的某個排列組合
* Recoverable schedule: 當一筆交易 abort 不影響其他筆交易；一筆交易 committed 後不應該被牽連而失去該筆交易

### Anomalies

* 發生資料衝突 (Conflict) (R: read, W: write)
* WR conflict 一個先寫另一個後讀
* Dirty reads: 讀還沒 committed 的資料
* Unrecoverable schedule 或 Cascading aborts
* RW conflict 一個先讀另一個後寫
* Unrepeatable reads: 讀兩次讀的東西不同
* WW conflict 一個先寫另一個後寫
* Lost update: 先寫的會失去

## 解決資料衝突: Locking protocol

### Two-phase locking (2PL)

* 鎖種類
* shared lock (R lock)
* exclusive lock (W lock)
* 階段
1. Growing phase: 只取鎖
2. Shrinking phase: 只放鎖

鎖以 Lock table (像是 hash table) 的方式管理。


2PL 解決序列化問題，但可能發生

* Cascading rollback
* Deadlock
* Starvation (根據不良的 waiting 隊列規則可能發生)


### S2PL (S: strict)

與 2PL 唯一差別: 等到一個交易結束時一次將所有鎖放掉，其他時候不放鎖，等同於 shrinking phase 只有一瞬間。

Strict 保證不會發生 cascading abort。

### 死結處理

* Detection: timeout + rollback
* Prevention: Wait die，放棄執行時間較短者
* Conservative lock: S2PL 之上，連 growing phase 也只有一瞬間
* 需知道 r/w working set
* 適合 stored procedure
* 不適合 ad-hoc (隨當前資料情況決定交易內容)

## 鎖的顆粒度 (Granularity) 與 Multiple-granularity locking (MGL)

可以鎖的物件有階層關係。


以此為基礎的鎖: MGL，基於 2PL 鎖的種類做出調整... (多了 intention lock 意向鎖): 鎖某物件時，連同其上層的所有親代物件都使用對應的意向鎖鎖起來。

> SIX 的白話文: 為 Share ( R ) 鎖，不過讀的下層存在 X 鎖。




上解鎖的順序有講究:

* 上鎖由根往葉
* 若改為由葉往根，上鎖時如果上層被鎖就無法繼續往下鎖了。 
* 解鎖由葉往根
* 若給為由根往葉，根一解鎖馬上被鎖，可能在葉的鎖還沒釋放的情況下就被拿上層的鎖。 

## 實時動態資料庫的 Phantoms

資料可能實時 insert, update 和 delete，有機會發生讀兩次資料不同的情況。

兩招解法：

* EOF lock 或 MGL
* 如果使用 MGL 實作 phantom 避免，要去 X lock 目標上層 (高一層 Granularity) 的物件，比如要寫 block 的話去鎖 file
* 常拿去避免 insert phantom
* 但不會想去避免 update phantom，因為太損效能
* Index/predicate lock

另外，Conservative lock 依然可能遇到 phantom，要看鎖了什麼東西。

## Isolation model

* Access model: 告知 read only/rw
* Isolation level: 可放棄 serializable 的部分性質換取效能
上表為使用者角度，下表為實作角度。

## 實務上考慮 Meta structure


由於 insert 和 delete 都需要先調整 meta structure 後調整 file，如果直接把 meta structure 鎖起來，insert 和 delete 就沒有並行性了。

要避免此瓶頸，可以不用完全遵照 S2PL，而是先 lock meta 後 lock file，在 lock 到 file 後可以放掉 meta 的 lock。

對 insert/delete 來說，資料不會錯誤是因為改 meta file 完對其他交易而言，相當於已經完成 insert/delete (只是還沒真的寫上去，但看起來是)。