tags: database

記憶體管理

記憶體的使用有

• 空間局部性 (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 沒救