###### 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 沒救