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 後)。

Select a repo