###### tags: `database`

# 段考速記


## 架構

### 請求層 (Query Interface)

### 存儲層 (Storage Interface)

#### RecordFile 和存儲單位

* Block: OS 讀寫的最小單位
* Page: 將資料從檔案載入記憶體的記憶體最小單位

#### Metadata

* 以 Catalog table 儲存

## 伺服器與執行緒

### Thread or Process

伺服器管理的最小可執行單元可能為 thread 或 process，各有優缺，考量兩者的差異：

* Open files, heap mem
* Process 內至少一個 thread

通常使用 Thread，這是因為管理 global/share resource (open file, heap mem) 交由 DBMS 來處理較方便、高效，且 thread 的建置較 Process 快。

### Kernel & user thread

Thread mapping 模型的選擇

* 多對一
* 簡單
* 一個 blocking system call 就大家一起等
* 一對一
* 無 blocking problem
* 建置 User thread 可能成本高
* 可善用 thread pool 解決每次 user thread 請求就建 kernel thread 的必要
* 當今個人電腦的 OS 常用
* 多對多
* 善用 kernel thread 資源
* Mapping 複雜
* 當今大型電腦 OS 可能會用
* 負荷過大時效率可能會降級至一對一 (加上 mapping 會更慘)

## 處理的請求步驟

收到 SQL query 時...

### Parsing (syntax-based)

* 根據語法，是否合乎 SQL 的文法
* 步驟
* 用 lexical analyzer (詞彙分析器) 將 SQL tokenize
* 根據文法分類內容
* 用 parsing algo 建構 parse tree
* algo 分為遞迴與否

### Verification (semantic-based)

根據語意，語意是否合理

### Plan

* 以定義好的運算子規劃如何完成請求
* 實際 Scan 前先預估某運算決策的效率，選擇最優決策
* 根據輸出 record 數與 value histogram
* 由於都訪問 metadata，都暫存於記憶體而沒有 I/O，故 Plan 實際上比起 Scan 很快

### Scan
* 完成請求
* 分為兩種模式
* Pipelined
* 容易實作
* 部分情況低效
* 如 Sort 時，每尋找一個元素需走遍所有子節點
* Materialized
* 預先將經過運算後的表格存入暫存檔，需要時取用
* 額外時間空間消耗
* 但可使用 External Sorting 等功能

## 存儲層


三種資料

* File: table info, record file
* Metadata
* Index

資料庫的 ACID 分別由 concurrency manager 和 recovery manager 實現。

### 硬碟三時間

* seek (沿直徑方向移動資料臂)
* rotational (平均轉半圈)
* transfer (根據資料量而不同)

### OS 提供的資料訪問方法

#### Block level

* Sector 是資料最原始的單位
* OS 將 Sector 的概念隱藏於 Block
* Block size 由 OS 決定
* 使用時將 Block 映射到 Memory Page

#### File level

* OS 將 Block 的概念隱藏
* 一個檔案為一系列 logical block 組成
* 管理這些 logical block 的 schema 多多，比如 contigous, linked, indexed, multi-level
* 將 Page 的概念隱藏為 I/O Buffer

#### File v.s. block

* Block 難實作，File 簡單方便
* 可控程度
* Block 可根據資料庫的使用需求客製化要緩存的資料
* File 對 page replacement 難以控制
* 比如某些 Query 可能會在一段時間後訪問 File 之前訪問過的 Page，OS 可能會因其他因素將其 swap 掉，但 DBMS 可預測未來存取資料的行為，選擇性的將其留在記憶體更久一點
* Block 無 OS 的限制，比如限制檔案大小
* 面對 OS 提供的 Block 層服務大多與 OS 本身掛鉤，影響移植性
* 根據 File System 的實作可能影響正確性 (e.g. WAL)，因為 File System 沒有義務實現 ACID

> 最後 Vanilla DB 使用妥協策略：在 File Level 下直接訪問 logical block
> * 優點
> * 簡單
> * Block 內的資料存放邏輯可客製化
> * Flush 與否自己控制，滿足 ACID
> * 需注意不要讓 OS 主動幫我們管理緩存
> * 缺點
> * 只能操縱 logical block 層級
> * 即使將資料循序放也無法確保 disk 能循序放資料

## 記憶體管理

記憶體的使用有

* 空間局部性 (Spatial locality)
* 時序局部性 (Temporal locality)

對於 DBMS，不應該依賴 VM，swap 與否應自行管理。其好在

* 可管理 swap
* meta-write for logs

另外，Log 不需用 buffer pool，因為其只會恆定的使用一個 buffer，且永遠只有 append 和反向讀取兩種操作。

### 使用 Buffer pool 減少 I/O...

> Vanilla DB 將 page 以 buffer 包裝，buffer 由 buffer manager 管理。

使用 Block 時透過 pin 一個 page buffer，pin 有以下幾種可能：

* Hit
* 有剩餘 buffer 就拿來用
* 沒有且存在 unpinned 的 buffer，用 replacement algo 找候選 buffer
* 需 flush dirty page
* 商用可能會為 buffer 分類以幫助 replacement algo
* 所有 buffer 都被 pin，等待至有 buffer

注意到 buffer 和 page 都應該是 thread safe 的。

### Replacement algo

常見算法

* linear search (naïve)
* FIFO
* LRU: 換掉最久沒用的
* Clock: 從上次掃描到的地方掃描，取第一個沒在用的

也可採用混合算法，比如 Oracle DBMS 使用 cold 時 LRU、hot 時 FIFO。

### Deadlock

* 遇死結時放所有 pinned 後回去睡，之後一個個重新 pin
* Self-Deadlock 沒救


## 資料管理

### Table records 於 file 中的存法

* homogeneous: 整個 table 的所有 record 都放同個 file
* 單表格的請求很高效
* heterogeneous: table 放在不同檔案
* 可進行 cluster，適合 schema 有階層關係的情況
* 沒有 cluster 的請求可能變慢

### Spanned v.s. unspanned records


* Spanned: 如果某筆資料塞不下當前 block，將該筆資料切分放在不同 block
* 優點
* 硬碟空間不浪費
* block size 不會限制 record size
* 缺點
* 讀一筆資料可能需要讀不只一個 block

### Field 索引方法


* Variable length: record 長度可變
* 最善用空間
* 如果長度超過當前 block 大小，會移至 overflow block
* Indexed: 資料長度可變，以指標指向資料本體
* 頗善用空間，不過指標佔部分額外空間
* 訪問資料要訪問兩次
* 適合 `text` 這種肥大且不定長的資料
* Fixed length: 配置空間固定大小
* Random access 的實作簡單
* 內部碎裂嚴重，浪費空間

### Column/row oriented store

要以 column 還是 row 為基礎存資料？
* Column
* 對同 column 讀取較快
* 加速同 column 的運算 (比如 group by 和一些 aggregation fn)
* 比較速度較快
* 適合 OLAP (線上分析處理)
* Row
* 加速各筆資料的訪問速度
* 對寫資料友善
* 適合 OLTP (線上交易)

### 綜合判斷

* OLTP 情境常用
* Homogeneous files
* Unspanned record
* Fixed length record
* row oriented store
* Page layout
* 考量刪除 record 的情境
* 需額外資料，比如一個 bit 決定一筆資料是否被刪掉
* free space 高速查找的實作
* chaining
* meta page
* meta file

## 並行管理

確保

* 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 (只是還沒真的寫上去，但看起來是)。

## 資料復原

可能需要復原的時機:

* 以交易為單位
* logical: 資料不存在、overflow、輸入錯誤等
* System: deadlock
* 以系統為單位
* 軟硬體 bug

Rollback 成功的依據：Write-Ahead-Logging (WAL)，在所有寫資料操作前先寫一 log，commit/abort 操作完成後再寫一個 log。

> 相當於搞一個寫進檔案版本的 CS

### Physical logging (段考範圍末)

Log 內容有以下幾種:

* start
* commit
* rollback
* update
* checkpoint

Rollback 操作從 log 末尾開始蒐集...


且需確保在 flushing 的 buffer 不會被修改，修改中的 buffer 也不該被 flush，可由 latch 保證。


至此我們有 rollback undo 的演算法如下。


一個例子:


### Undo-redo recovery

每完成一筆交易都需要 flush dirty buffer 至 disk 的效率實在不怎麼樣。透過紀錄修改新舊值訊息的 log，我們可以延緩 flush 的時機，如果在還沒 flush 之前系統出事，可透過 log 把還沒 flush 進 disk 的資料都 redo 一遍。

#### 概念澄清

* Force 與否
* Force: committing 時，當 buffer 還沒 flush 完之前不會 return 至 user
* No-force: committing 時只把 log 寫好，flush 可以晚點做
* Steal 與否: 也就是允許 swap + flush 與否
* Steal: commit 之前 buffer 可以 swap，期間須把中間資料 flush 回 disk
* No steal: commit 之前 buffer 不能 swap，需保持被 pin 著，也不能 flush

#### 有趣的想法: Force + No steal

Redo 本身是因為採用 no force 導致 commit 後寫的資料不會即時 flush 回 disk，如果 force 的話就規避了 redo 操作。

那麼 undo 本身會存在即因為 steal: flush 了中間結果而非最終結果，若採用 no steal，是否就規避了 undo 操作？

也就是 Force + no steal 就使 log 沒有必要存在了 (no redo & no undo)？

答案是錯的，此法有兩點問題。

* No steal 不現實: buffer 在未 commit 前都需被 pin 的話並行性會大幅降低
* Flush 時系統仍有可能出錯，沒寫 log 還是等著抽搐

#### Force undo-redo recovery



特別注意到這些 log rollback 操作都是 idempotent (每次做都得到一樣的結果) 的。

#### No-force undo-redo recovery

更進一步的，no-force 版的更激進，在 rollback 時不需要將 dirty pages flush 掉，更不需要寫入 `<ROLLBACK>` 進 log，因為重啟後重新 rollback 的結果都是 idempotent 的!

這帶來了另一版本的 rollback 演算法：


此時 undo journaling 一定要先於 redo! 不然 undo 的部分可能蓋掉 redo 的。

#### 比較

undo-only 的
* 優點 <主要反映在非服務時期>
* recovery 時加速
* 不需要 redo 的 "log"
* 缺點 <主要反映在服務時期>
* commit 和 rollback 時較慢

明顯 undo-redo 版的對服務時期比較友好，更佳適合採用。

### Checkpoint

降低每次 rollback undo/redo 的成本，適合在離峰時進行。

#### Quiescent 版

1. 停止接受新交易
2. 等待現有交易結束
3. Flush 所有 dirty buffer
4. 新增 (Quiescent) checkpoint 至 log 並將其 flush 回 disk
5. 恢復接受新交易


但第二步不知道要等多久...

#### Nonquiescent 版

1. 停止接受新交易
2. 紀錄正在進行的交易 $T_1 \sim T_k$
3. Flush 所有 dirty buffer
4. 新增 `<NOQCKPT, T1, T2, ..., Tk>` 至 log 並將其 flush 回 disk
5. 恢復接受新交易


但由於 checkpointing 時仍有交易在進行，他們可能也要寫 log，故在上述 3~4 步時需要 latch log file + all blocks (始於 3 前，終於 4 後)。