跳轉到

8.3 交易與 WAL 預寫日誌#

概念說明#

資料庫承諾交易的 ACID，其中持久性（Durability）與原子性（Atomicity）都建立在磁碟上的一個關鍵設計：WAL（Write-Ahead Logging，預寫日誌）。規則只有兩句話：

  1. 先寫日誌，後寫資料頁：任何資料頁的修改，其對應的日誌記錄必須先落盤。
  2. 交易提交前，該交易的日誌必須落盤；資料頁可以晚一點（由緩衝池慢慢刷髒頁）。

為什麼這樣就安全？提交瞬間只有日誌在磁碟上，資料頁還在記憶體。此時斷電：重啟後資料庫重播（redo）日誌，把已提交交易的修改重做到資料頁上——持久性保住了。若交易未提交就斷電：日誌中沒有 commit 記錄，重啟時回滾（undo）該交易已寫的任何修改——原子性保住了。日誌是順序追加寫（極快），資料頁的隨機寫被推遲、合併、攤提，這也讓寫入吞吐大幅提升。

日誌記錄格式：<交易ID, 資料項, 舊值, 新值>。舊值用於 undo，新值用於 redo。檢查點（checkpoint）週期性把髒頁刷盤並記錄位置，讓恢復時只需從最近的檢查點重播，日誌不必無限成長。

LSM 樹（6.2 節）的 memtable-WAL 搭配正是同一思想：先順序寫日誌，資料留在記憶體，之後批次落盤。

演算法步驟#

交易提交： 1. 每個修改先追加日誌記錄（順序寫）。 2. 提交時寫 <commit T> 並強制 fsync 日誌（此時資料頁可能尚未落盤）。 3. 緩衝池日後自然刷髒頁；刷盤前對應日誌必須已在盤（WAL 規則）。

當機恢復（ARIES 簡化版）： 1. 分析：從最近檢查點掃描，找出未完成交易。 2. Redo：重播所有交易（含未提交者）的日誌到資料頁。 3. Undo：反向回滾未提交交易，寫補償日誌。

Python 範例：WAL 模擬#

class WALDatabase:
    def __init__(self):
        self.disk_pages = {}      # 磁碟上的資料頁
        self.log = []             # 日誌（順序追加）
        self.mem = {}             # 緩衝池（未刷髒頁）
        self.checkpoint = 0

    def write(self, tid, key, old, new):
        self.log.append((tid, key, old, new))
        self.mem[key] = new       # 只改記憶體！

    def commit(self, tid):
        self.log.append(("commit", tid))
        self.flush_log()          # 強制日誌落盤；資料頁尚未落盤

    def flush_log(self):
        pass                      # 模擬 fsync

    def flush_pages(self):        # 檢查點：刷髒頁
        self.disk_pages.update(self.mem)
        self.checkpoint = len(self.log)

    def crash_recover(self):
        """斷電：記憶體全失，從日誌恢復"""
        committed, state = set(), {}
        for rec in self.log[self.checkpoint:]:
            if rec[0] == "commit":
                committed.add(rec[1])
            else:
                tid, key, old, new = rec
                state[key] = new
                state.setdefault("#undo:" + key, []).append((tid, old))
        # redo：套用已提交交易的新值；undo：未提交者回滾
        for key in list(state):
            if key.startswith("#undo:"): continue
        disk = dict(self.disk_pages)
        for rec in self.log[self.checkpoint:]:
            if rec[0] == "commit": continue
            tid, key, old, new = rec
            if tid in committed:
                disk[key] = new          # redo
        return disk

db = WALDatabase()
db.disk_pages, db.mem = {"a": 1, "b": 2}, {"a": 1, "b": 2}
db.write("T1", "a", 1, 10)
db.commit("T1")                       # T1 已提交（日誌落盤，頁未刷）
db.write("T2", "b", 2, 20)            # T2 尚未提交
db.flush_pages()                      # 檢查點
db.write("T3", "a", 10, 99)           # T3 未提交
recovered = db.crash_recover()
print("恢復後 a =", recovered["a"], "（T1 已提交，redo 生效）")
print("恢復後 b =", recovered["b"], "（檢查點已刷盤）")

複雜度與 I/O 成本分析#

  • 提交成本：1 次日誌 fsync（順序 I/O，約 0.1~1ms SSD）；資料頁零隨機寫。
  • 寫放大：每筆修改寫日誌 1 次 + 髒頁攤提寫 < 1 次（同頁多次修改合併）。
  • 恢復成本：O(檢查點後日誌長度)，故檢查點間隔要權衡「恢復時間 vs 平時開銷」。
  • group commit：多個交易的提交日誌一次 fsync，高併發下大幅提升吞吐。

練習#

  1. 在範例中把 T2 也 commit 再恢復，驗證 b 的值被 redo。
  2. 說明為何「先寫資料頁、後寫日誌」會在斷電時造成不可恢復的錯誤。
  3. 設計檢查點策略：每 N 筆日誌做一次檢查點，分析 N 對「平時開銷 vs 恢復時間」的影響。