儲存引擎要同時做到兩件互相拉扯的事：寫要快（所以把頁面改動先緩衝在記憶體裡批次刷回）、又斷電不能丟資料（所以每筆改動都得先落地）。緩衝池 (buffer pool) 負責前者，WAL 負責後者，ARIES 是斷電後把兩者兜回一致的演算法。
🧠 Intuition
TIP
資料庫活在兩層記憶體階層上：慢而持久的磁碟，快而易失的 RAM。緩衝池是「記憶體裡的頁面工作區」，WAL 是「先寫下來的流水帳」。規則只有一條：改頁之前，先把這筆改動寫進 log——這樣記憶體裡的工作區隨時可以在斷電後從 log 重建。
- 緩衝池 (buffer pool / page cache)：把頁面內容留在記憶體、讓改動先在快取版本上緩衝並批次寫回；要的頁不在記憶體且有空間就載入 (page in)，空間不足就驅逐某頁並刷回磁碟。
- 同步是單向的：所有改動只在記憶體，直到最終刷回磁碟——所以斷電時未刷回的改動會消失。
- WAL 補上持久性：在快取頁刷回磁碟之前，WAL 是這些改動唯一的磁碟副本；斷電後重放 log 就能把遺失的記憶體改動重建回來。
⚖️ Tradeoffs
緩衝池的頁面狀態：pinned / referenced / dirty
- dirty（髒頁）：被改過、與磁碟不同步，必須先刷回才能驅逐。
- referenced（已參照）：正被某執行緒使用，用完要 dereference；使用中不該被驅逐。
- pinned（釘住）：明確要求不要驅逐。典型用法：B-Tree 越靠近根的節點幾乎每次查詢都命中，而高層節點數量只佔一小撮，把它們 pin 常駐記憶體，查一筆就只需為未快取的低層節點打磁碟，而非走滿
h跳。
驅逐替換策略：從 FIFO 到 CLOCK / TinyLFU
- FIFO：最早載入最先驅逐；不看後續存取，根節點最先載入卻最先變成候選——不實用。
- LRU：重複存取就把該頁挪回佇列尾；但並行下更新指標、重接節點的代價高。衍生 2Q（分「最近」與「頻繁」兩佇列）、LRU-K（追蹤最近 K 次存取估存取時間）。
- CLOCK / CLOCK-sweep：LRU 的緊湊、快取友善、可並行版本。環形緩衝配一個 access bit：存取設 1；掃描時 1→0 跳過、遇到 0 就成驅逐候選。指標與內容都能用 compare-and-swap 改，免額外鎖，Linux 用其變體。
- TinyLFU：有時頻率比最近性更能預測。用頻率直方圖維護緊湊歷史，分 Admission / Probation / Protected 三段。
- ⚠️ Belady 異常：策略不理想時，增加快取頁數反而可能增加驅逐次數。
WAL：write-ahead 規則與 LSN
- WAL (Write-Ahead Log，又稱 commit log) 是僅追加、不可變的磁碟結構，所有寫入循序。
- 核心規則：任何改動資料庫狀態的操作，都必須在對應頁面被改之前先寫進 log（write-ahead）——這正是緩衝池敢在記憶體裡緩衝改動的底氣。
- 每筆記錄有唯一、單調遞增的 LSN (Log Sequence Number)。log 記錄先進日誌緩衝區 (log buffer)，靠 force 刷到磁碟；一筆交易要等它的 commit 記錄 LSN 被 force 落地，才算真的提交。
redo / undo 的表示：physical vs logical log
- 狀態變更可用 before-image / after-image、或對應的 redo / undo 操作來記。
- 物理日誌 (physical log)：記完整頁面或逐位元組變更；邏輯日誌 (logical log)：記操作本身（如「為 key Y 插入記錄 X」）。
- 實務常混用：redo 用物理（加快復原）、undo 用邏輯（提高正常運行時的並行度）。
Steal / Force：緩衝池與 WAL 怎麼協調
- Steal：允許在交易提交前，就刷回它改過的頁；No-steal：不准刷回任何未提交交易的頁。
- Force：交易提交前，把它改過的頁全部刷回；No-force：允許提交時仍有頁沒刷回。
- 取捨：No-steal 只靠 redo 就能復原，但需要較大的緩衝池；Force 復原時不必重建已提交結果，但提交較慢（多了 I/O）。通用原則不變：交易必須在 undo/redo 記錄寫進 log 之後，才能提交。
ARIES：steal + no-force 的三階段復原
- ARIES 是 steal / no-force 的復原演算法，用物理 redo（快）＋邏輯 undo（並行度高）。斷電重啟走三階段：
- ① 分析 (Analysis)：從髒頁與進行中交易的資訊，定出 redo 的起點與待 undo 的交易清單。
- ② 重做 (Redo)：重放歷史到崩潰當下，把狀態拉回斷電前——不管交易是否已提交都先重放。
- ③ 撤銷 (Undo)：逆時間回滾所有未完成的交易，回到最後一致狀態。
- 為防復原途中又斷電，undo 動作本身也會被記錄（即補償日誌記錄 CLR 的用途）。ARIES 靠 LSN 認記錄、用髒頁表追蹤進行中交易改過的頁、並搭配下面的模糊檢查點。
Checkpoint：讓 log 不必從頭重放
- 檢查點標記「到此為止的記錄都已完全落地」，大幅縮短重啟時要重放的量。
- 同步檢查點強制刷回所有髒頁——得暫停全部操作，不實用。
- 模糊檢查點 (fuzzy checkpoint)：以
begin_checkpoint/end_checkpoint兩筆記錄夾住，頁面非同步刷回，完成後更新last_checkpoint指標，復原就從那裡開始。 - 截斷 log：只有「對應的快取頁已刷回」的 log 記錄，才可以從 WAL 丟棄。
🔑 Takeaways
- 快與不丟資料的張力，由**緩衝池（批次刷回求快）＋ WAL（先落地保命）**分工化解；同步永遠是記憶體→磁碟單向，斷電只能靠 log 補回。
- write-ahead 規則（改頁前先寫 log）是一切的地基；一筆交易的提交點 = 它的 commit 記錄 LSN 被 force 落地。
- Steal/Force 決定復原要做多少事：主流是 steal + no-force，代價是崩潰後需要完整的 ARIES 三階段（分析 → redo → undo）。
- 模糊檢查點讓重啟不必從頭重放整條 log；能截斷的只有「對應髒頁已刷回」的那段記錄。
No notes yet — jot your takeaways or Q&A here.