本章從底層儲存結構往上，進入負責緩衝管理（buffer management）、鎖管理（lock management）與復原（recovery）的高階元件，這些是理解資料庫交易的先決條件。

ACID 特性#

交易（transaction）是資料庫管理系統中不可分割的邏輯工作單元，將多個操作表示為單一步驟。每筆交易必須滿足 ACID 四大特性：

• 原子性（Atomicity）：交易中的所有步驟要嘛全部成功，要嘛全部不執行。交易可以 commit（提交，使所有寫入變更可見）或 abort（中止，回滾所有尚未可見的副作用）。Commit 是最終操作；abort 後可以重試。
• 一致性（Consistency）：交易只能將資料庫從一個合法狀態帶到另一個合法狀態，維護所有約束（constraints）與參照完整性。一致性是四者中定義最弱的屬性，因為它是唯一由使用者（而非僅由資料庫）控制的。
• 隔離性（Isolation）：多個同時執行的交易應互不干擾，彷彿沒有其他交易同時在執行。隔離性定義了何時狀態變更可被其他交易看到。許多資料庫為了效能會使用較弱的隔離等級。
• 持久性（Durability）：交易一旦提交，所有狀態修改必須持久化到磁碟，即使斷電、系統故障或當機也能存活。

交易處理的核心元件#

在節點內部，以下元件協同工作以實現交易：

• 交易管理器（Transaction Manager）：協調、排程與追蹤交易及其各步驟。
• 鎖管理器（Lock Manager）：保護資源存取，防止違反資料完整性的並行存取。當鎖被請求時，檢查是否已被其他交易以共享或排他模式持有，在不矛盾時才授予存取。排他鎖同一時刻最多被一個交易持有。
• 頁面快取（Page Cache）：作為持久化儲存與儲存引擎之間的中介，在主記憶體中暫存狀態變更，同時快取尚未與磁碟同步的頁面。所有狀態變更先套用到快取頁面。
• 日誌管理器（Log Manager）：保存已套用到快取頁面但尚未同步到持久化儲存的操作歷史（日誌條目），以確保當機時不會遺失。日誌條目也可用於撤銷已中止交易的變更。

緩衝管理（Buffer Management）#

大多數資料庫建立在兩層記憶體階層上：較慢的持久化儲存（磁碟）與較快的主記憶體（RAM）。為了減少磁碟存取次數，頁面會被快取在記憶體中。

頁面快取（Page Cache）#

頁面快取（又稱 buffer pool）負責將從磁碟讀取的頁面快取到記憶體中。當資料庫系統當機或異常關閉時，快取內容會遺失。

頁面快取的主要功能：

• 將快取頁面內容保留在記憶體中
• 允許對磁碟頁面的修改在快取版本上緩衝並批次執行
• 當請求的頁面不在記憶體且有足夠空間時，將其載入（page in）並回傳快取版本
• 若已快取的頁面被請求，直接回傳快取版本
• 空間不足時，驅逐某個頁面並將其內容刷回磁碟

繞過核心頁面快取：許多資料庫使用 O_DIRECT 旗標開啟檔案，繞過核心的頁面快取，直接存取磁碟並使用資料庫自有的緩衝管理。這允許資料庫對 I/O 有更精細的控制，但 Linus Torvalds 曾批評此作法缺乏非同步特性與預讀機制。替代方案如 fadvise 只是建議性的，memory mapping 則會失去快取控制權。

快取語意（Caching Semantics）#

• 所有對緩衝區的變更保留在記憶體中，直到最終寫回磁碟。同步是單向的：從記憶體到磁碟。
• 儲存引擎存取頁面時，先檢查內容是否已快取；若否，則將邏輯頁面位址轉換為實體位址，載入記憶體後回傳。
• 回傳後，緩衝區被標記為已參照（referenced），使用完畢須解除參照（dereference）。
• 可透過固定（pinning）指示頁面快取不驅逐該頁面。
• 若頁面被修改，標記為 dirty（髒頁），表示內容與磁碟不同步，需刷回以保持持久性。

快取驅逐（Cache Eviction）#

頁面快取容量有限，當需要載入新頁面時，必須驅逐舊頁面。驅逐涉及多個目標的權衡：

• 延後刷回以減少磁碟存取次數
• 預先刷回以加速驅逐
• 以最佳順序選擇驅逐與刷回的頁面
• 將快取大小維持在記憶體限制內
• 避免因未持久化而遺失資料

關鍵規則：

• 若頁面內容已與磁碟同步（已刷回或從未修改）且未被固定或參照，可直接驅逐
• 髒頁必須先刷回才能驅逐
• 已參照頁面在其他執行緒使用時不應被驅逐

某些資料庫（如 PostgreSQL）使用背景刷回寫入器（background flush writer）循環檢查可能被驅逐的髒頁，提前更新其磁碟版本。

持久性方面，檢查點程序（checkpoint process）協調 WAL 與頁面快取，確保它們同步運作。只有與已刷回快取頁面相關的日誌記錄才可從 WAL 中丟棄。

鎖定快取中的頁面#

B-Tree 越靠近根部的節點在大多數讀取中都會被命中。可以透過固定（pinning）將高機率被使用的頁面鎖在快取中，減少磁碟存取。

由於每一層的節點數呈指數成長，而高層節點只佔樹的一小部分，這些節點可以常駐記憶體，其他部分依需求載入。查詢時不必做 h 次磁碟存取（h 為樹高），只需為未快取的低層節點存取磁碟。

預取與立即驅逐：頁面快取允許精細控制預取（prefetching）與驅逐。例如，範圍掃描時可預載下一個葉節點；維護程序載入的頁面在完成後可立即驅逐。PostgreSQL 對大型循序掃描使用環形緩衝區（circular buffer，即 FIFO 替換策略）。

頁面替換策略#

當快取容量已滿，載入新頁面時需驅逐舊頁面。驅逐策略（eviction policy）嘗試找出最不可能再被存取的頁面。

Belady 異常（Belady’s Anomaly）：增加快取頁面數不一定能減少驅逐次數。若使用的替換演算法不夠理想，頁面可能會在快取中互相競爭空間，反而增加驅逐次數。

FIFO 與 LRU#

• FIFO（先進先出）：維護一個按插入順序排列的佇列。最早載入的頁面最先被驅逐。不考慮後續存取，實務上不實用（例如根節點最先載入，卻也最先被驅逐候選）。
• LRU（最近最少使用）：擴展 FIFO，允許重複存取時將頁面放回佇列尾端。但在並行環境中更新參照與重新連結節點可能代價高昂。
• 2Q（雙佇列 LRU）：維護兩個佇列，初次存取放入第一佇列，後續存取移至第二個熱佇列，區分最近存取與頻繁存取的頁面。
• LRU-K：追蹤最近 K 次存取，用以估計每個頁面的存取時間。

CLOCK#

CLOCK 演算法是 LRU 的精簡、快取友善、支援並行的替代方案。Linux 使用 CLOCK 的變體。

CLOCK-sweep 在環形緩衝區中保存頁面參照與存取位元：

• 每次頁面被存取時，存取位元設為 1
• 掃描時若存取位元為 1 且頁面未被參照，則設為 0，檢查下一個
• 若存取位元已為 0，該頁面成為驅逐候選
• 若頁面正被參照，存取位元不變，使其較不易被替換

環形緩衝區的優勢在於指標與內容都可用 compare-and-swap 操作修改，無需額外的鎖機制。

LFU#

LRU 不一定是資料庫系統的最佳策略。有時使用頻率（frequency）比最近性（recency）更具預測力。

TinyLFU 是一種基於頻率的驅逐策略，使用頻率直方圖（frequency histogram）維護緊湊的快取存取歷史。元素可處於三個佇列之一：

• Admission（准入）：新加入的元素，使用 LRU 策略
• Probation（觀察）：最可能被驅逐的元素
• Protected（保護）：會在佇列中停留較長時間的元素

只有頻率高於因晉升而將被驅逐的元素的項目，才能被移入 probation 佇列。後續存取可從 probation 移至 protected。若 protected 佇列已滿，其中某個元素可能被放回 probation。

復原（Recovery）#

資料庫系統建立在多層硬體與軟體之上，各層都可能有穩定性問題。資料庫實作者必須考慮故障情境，確保「承諾」寫入的資料確實被寫入。

預寫式日誌（Write-Ahead Log, WAL）#

WAL（又稱 commit log）是一種僅追加（append-only）的磁碟輔助結構，用於當機與交易復原。頁面快取允許在記憶體中緩衝頁面變更，而在快取內容刷回磁碟之前，WAL 是唯一保存操作歷史的磁碟副本。

WAL 的核心功能：

• 允許頁面快取緩衝對磁碟頁面的更新，同時確保持久性語意
• 將所有操作持久化到磁碟，直到受影響頁面的快取副本被同步。每個修改資料庫狀態的操作都必須在相關頁面內容被修改之前記錄到磁碟
• 在當機時允許從操作日誌重建遺失的記憶體變更

PostgreSQL 與 fsync()：PostgreSQL 使用檢查點確保索引和資料檔案已更新。Linux 中 fsync 在 I/O 錯誤後仍會清除髒頁旗標，且錯誤只會回報給故障時已開啟的檔案描述符。若檢查點程序未持續開啟所有檔案，可能錯過錯誤通知，導致資料遺失或資料庫損壞。

日誌語意（Log Semantics）#

WAL 是僅追加且已寫入的內容不可變（immutable），因此所有寫入都是循序的。讀取者可安全存取至最新寫入閾值的內容，而寫入者繼續追加資料。

• 每筆記錄有唯一的、單調遞增的 LSN（Log Sequence Number），通常以計數器或時間戳表示
• 日誌記錄不一定佔滿整個磁碟區塊，其內容在日誌緩衝區中快取，透過 force 操作刷到磁碟
• 交易在其 commit 記錄的 LSN 被 force 到磁碟之前，不能視為已提交
• 部分系統在 undo 期間使用補償日誌記錄（CLR, Compensation Log Records）

檢查點（Checkpoints）#

檢查點讓日誌知道到某個標記為止的記錄已完全持久化，不再需要，大幅減少啟動時的工作量。

• 同步檢查點（sync checkpoint）：強制所有髒頁刷到磁碟。不實用，需暫停所有操作。
• 模糊檢查點（fuzzy checkpoint）：以 begin_checkpoint 日誌記錄開始，end_checkpoint 記錄結束（包含髒頁資訊與交易表）。頁面非同步刷回，完成後更新 last_checkpoint 指標。當機時復原從該處開始。

操作日誌與資料日誌#

狀態變更可以用 before-image / after-image，或對應的 redo / undo 操作來表示：

• 物理日誌（physical log）：記錄完整頁面狀態或逐位元組變更
• 邏輯日誌（logical log）：記錄需對當前狀態執行的操作（例如「為鍵 Y 插入資料記錄 X」）

實務上許多資料庫結合兩種方式：邏輯日誌用於 undo（提高並行性與效能），物理日誌用於 redo（改善復原時間）。

Steal 與 Force 策略#

這些策略決定記憶體中的變更何時必須刷回磁碟：

策略對 undo/redo 的影響：

• No-steal：只需 redo 條目即可實現復原（舊副本在磁碟頁面中，修改在日誌中）。但需要較大的頁面快取。
• Force：當機復原不需額外工作重建已提交交易的結果，但交易因必要的 I/O 而需更長時間提交。
• 一般而言，交易提交前需要有足夠資訊來撤銷其結果。無論使用哪種策略，交易都必須在 undo 或 redo 記錄寫入日誌後才能提交。

ARIES#

ARIES（Algorithm for Recovery and Isolation Exploiting Semantics）是 steal/no-force 的復原演算法，使用物理 redo（加速復原）與邏輯 undo（提高正常操作的並行性）。

當資料庫在當機後重啟，復原分三個階段：

1. 分析階段（Analysis）：識別頁面快取中的髒頁和當機時進行中的交易。髒頁資訊用於確定 redo 階段的起點；進行中的交易列表用於 undo 階段。
2. 重做階段（Redo）：重放歷史至當機點，恢復資料庫到先前狀態。對未完成與已提交但未刷回的交易都執行此階段。
3. 撤銷階段（Undo）：按逆時間順序回滾所有未完成的交易，恢復到最後一致狀態。為防止復原期間再次當機，undo 操作本身也會被記錄。

ARIES 使用 LSN 識別日誌記錄，在髒頁表（dirty page table）中追蹤被執行中交易修改的頁面，並使用模糊檢查點。

並行控制（Concurrency Control）#

並行控制是一組處理並行執行交易之間互動的技術，大致分為三類：

• 樂觀並行控制（OCC）：允許交易並行執行讀寫操作，提交前檢查是否可序列化。交易不互相阻塞，而是維護操作歷史並在提交前檢查衝突。衝突時中止其中一個交易。
• 多版本並行控制（MVCC）：允許記錄存在多個帶時間戳的版本，透過單調遞增的交易 ID 或時間戳保證一致性視圖。讀取可繼續存取舊值直到新值提交，最小化儲存層的協調。
• 悲觀並行控制（PCC）：在交易執行期間判斷衝突，阻塞或中止執行。包含鎖定與非鎖定的保守方法。悲觀排程可能導致死結（deadlock）。

可序列化性（Serializability）#

排程（schedule）是從資料庫系統角度執行一組交易所需的操作列表（讀、寫、提交、中止），其他操作被假設為無副作用。

• 序列排程（serial schedule）：交易完全獨立、無交錯地依序執行。容易推理但嚴重限制吞吐量。
• 可序列化排程（serializable schedule）：等價於某個完整的序列排程，產生相同結果，但允許並行執行以提高效能。

交易隔離（Transaction Isolation）#

隔離等級指定交易的部分何時及如何對其他交易可見。隔離帶來效能成本，因為防止不完整或暫時的寫入跨交易邊界傳播需要額外協調。

讀寫異常#

讀取異常：

• 髒讀（Dirty Read）：交易讀到其他交易未提交的變更。該交易若回滾，讀到的值從未被提交過。
• 不可重複讀（Nonrepeatable Read / Fuzzy Read）：同一交易中兩次查詢同一列得到不同結果（因另一交易在兩次讀取間提交了修改）。
• 幻讀（Phantom Read）：同一交易中兩次範圍查詢得到不同結果集。

寫入異常：

• 遺失更新（Lost Update）：T1 和 T2 都讀取 V、更新 V 並提交。T1 的結果被 T2 覆蓋。
• 髒寫（Dirty Write）：基於未提交值（髒讀）修改並儲存結果。
• 寫入偏斜（Write Skew）：每個交易個別遵守約束，但組合後違反。例如兩帳戶 A1=100$、A2=150$，要求 A1+A2>=0，T1 和 T2 各提領 200$，個別看都合法，但結果 A1=-100$、A2=-50$ 違反約束。

隔離等級#

快照隔離（Snapshot Isolation）：交易取得資料快照並對其執行查詢，快照在交易期間不變。提交時若修改的值已被改變則中止回滾。兩個交易嘗試修改同一值時，先提交者成功，另一個必須中止重試。快照隔離排除遺失更新異常，但仍可能發生寫入偏斜。

可序列化性（serializability）與線性化（linearizability）不同。可序列化性是多個操作以任意順序執行的屬性，不企圖強加特定順序。ACID 中的隔離性意味著可序列化性。

樂觀並行控制（OCC）#

OCC 假設交易衝突很少發生，不使用鎖與阻塞，而是在提交前驗證。交易執行分三階段：

1. 讀取階段（Read Phase）：交易在自己的私有上下文中執行，不對其他交易可見。完成後確定讀取集（read set）與寫入集（write set）。
2. 驗證階段（Validation Phase）：檢查並行交易的讀寫集是否有衝突。若資料已過時或會覆蓋讀取階段期間提交的值，則清除私有上下文並重新開始。
3. 寫入階段（Write Phase）：若無衝突，將寫入集從私有上下文提交到資料庫。

驗證可以是向後導向（backward-oriented，與已提交交易比較）或向前導向（forward-oriented，與正在驗證的交易比較）。驗證與寫入階段必須原子地執行。

此方法在驗證通常成功且交易不常重試時效率最高，否則重試對效能有顯著負面影響。

多版本並行控制（MVCC）#

MVCC 允許記錄存在多個版本，使用單調遞增的交易 ID 或時間戳，讓讀寫以最小協調進行。讀取可繼續存取舊值直到新值提交。

• 區分已提交與未提交版本，最後一個已提交版本被視為當前版本
• 目標是同一時間最多只有一個未提交值
• 可用鎖定、排程與衝突解決技術（如 two-phase locking）或時間戳排序實現
• MVCC 的主要用途之一是實現快照隔離

悲觀並行控制（PCC）#

悲觀方案比樂觀方案更保守，在交易執行期間判斷衝突並阻塞或中止。

時間戳排序（Timestamp Ordering）是最簡單的悲觀（無鎖）方案：

• 每個交易有一個時間戳
• 交易管理器為每個值維護 max_read_timestamp 和 max_write_timestamp
• 讀取操作若時間戳低於 max_write_timestamp，交易被中止（已有更新的值）
• 寫入操作若時間戳低於 max_read_timestamp，會與更近期的讀取衝突
• 寫入操作若時間戳低於 max_write_timestamp，可安全忽略過時的寫入值（Thomas Write Rule）
• 被中止的交易以新時間戳重啟

基於鎖的並行控制#

使用明確鎖而非排程解析。缺點是競爭與可擴展性問題。

兩階段鎖定（Two-Phase Locking, 2PL）#

將鎖管理分為兩個階段：

1. 成長階段（Growing / Expanding Phase）：取得交易所需的所有鎖，不釋放任何鎖
2. 收縮階段（Shrinking Phase）：釋放成長階段取得的所有鎖

核心規則：交易一旦釋放了至少一個鎖，就不能再取得任何新鎖。

兩階段鎖定（2PL）與兩階段提交（2PC）是完全不同的概念。2PC 是分散式多分區交易的協定，而 2PL 是常用於實現可序列化性的並行控制機制。

死結（Deadlocks）#

當兩個交易各自持有對方需要的鎖，互相等待對方釋放時，就發生死結。

處理死結的方法：

• 逾時：中止長時間執行的交易
• 保守 2PL：要求交易在執行任何操作前取得所有鎖
• 等待圖（waits-for graph）：追蹤進行中交易的等待關係，圖中的環表示死結。可週期性或連續地檢測。
• 基於時間戳的優先順序：較低時間戳通常意味著較高優先順序
  • Wait-die：高優先順序交易可等待；否則中止重啟。交易只能被較高時間戳的交易阻塞。
  • Wound-wait：高優先順序交易「傷害」低優先順序交易（使其中止重啟）；否則等待。交易只能被較低時間戳的交易阻塞。

鎖與閂鎖（Locks vs. Latches）#

交易處理中有兩個守護資料完整性的機制，分別負責邏輯與物理層面：

鎖（Locks）#

• 用於隔離與排程重疊的交易，管理資料庫內容而非內部儲存結構
• 在鍵上取得，可守護特定鍵（存在或不存在的）或鍵的範圍
• 通常儲存在樹實作之外，由資料庫鎖管理器管理
• 比閂鎖更重量級，持續整個交易期間

閂鎖（Latches）#

• 守護物理表示：葉頁面內容在插入、更新、刪除時被修改；非葉頁面內容和樹結構在分裂與合併時被修改
• 在頁面層級取得，任何頁面都必須被閂鎖以允許安全的並行存取
• 即使是無鎖並行控制技術仍需使用閂鎖
• 應持有最短可能的時間以增加並行性
• 不依賴死結避免機制，依賴程式設計者確保不會發生死結

並行操作間的干擾分為三類：

• 並行讀取：多個執行緒存取同一頁面但不修改
• 並行更新：多個執行緒嘗試修改同一頁面
• 讀寫重疊：一個執行緒修改頁面內容，另一個嘗試讀取同一頁面

讀寫鎖（Readers-Writer Lock, RW Lock）#

RW 鎖允許多個讀取者並行存取物件，只有寫入者需要排他存取。

• 兩個重疊的讀取存取同一頁面時，只需防止頁面快取從磁碟重複載入
• 當寫入進場時，需要與並行讀取和其他寫入隔離

忙等與佇列技術：管理共享存取可使用阻塞演算法（取消排程執行緒，待可繼續時喚醒）或忙等演算法（執行緒等待極短時間而非交回控制權）。佇列通常使用 compare-and-swap 指令實現，保證鎖取得與佇列更新的原子性。

閂鎖蟹行（Latch Crabbing）#

又稱 latch coupling，是一種優化技術，允許更短時間持有閂鎖。

• 讀取路徑：定位到子節點並取得其閂鎖後，即可釋放父節點的閂鎖
• 插入路徑：若子節點未滿（不會因操作產生向上傳播的結構變更），可釋放父節點閂鎖
• 刪除路徑：若子節點持有足夠元素且操作不會導致合併，釋放父節點閂鎖

此方法是樂觀的：大多數插入和刪除操作不會導致多層傳播的結構變更，實際上結構變更的機率在較高層遞減。

閂鎖升級與指標追蹤：可先以共享模式取得搜尋路徑上的閂鎖，需要時再升級為排他鎖。寫入操作先只在葉層取得排他鎖，若需要分裂或合併，沿樹向上升級。由於根節點是每個請求的必經之路，但也是最後才會分裂的節點，因此根節點可以總是以樂觀方式閂鎖。

Blink-Trees#

Blink-Trees 建立在 B*-Trees 之上，增加了高鍵（high keys）和兄弟鏈結指標（sibling link pointers）。每個非根節點有兩個指標：來自父節點的子指標和同層左節點的兄弟鏈結。

Blink-Trees 允許一種稱為半分裂（half-split）的狀態：節點已被兄弟指標參照，但尚未被父節點的子指標參照。半分裂透過檢查高鍵來識別——若搜尋鍵超過節點的高鍵，演算法判斷結構已被並行修改，沿兄弟鏈結繼續搜尋。

優勢：

• 下降到子層時不需要持有父節點鎖，即使子節點將被分裂
• 新節點可透過兄弟鏈結可見，父指標延遲更新而不犧牲正確性
• 減少競爭，防止分裂時持有父鎖
• 結構修改時持有的鎖數量為常數
• 允許讀取與結構性樹變更並行，防止並行修改向上傳播時的死結

總結#

本章討論了負責交易處理與復原的儲存引擎元件。交易處理面臨兩個核心問題：

• 效率：需要允許並行交易執行
• 正確性：需要確保並行執行的交易保持 ACID 特性

頁面快取負責減少磁碟存取：在記憶體中快取頁面，允許讀寫存取。快取滿時驅逐頁面並刷回磁碟。為確保未刷回的變更不因當機而遺失，並支援交易回滾，使用預寫式日誌（WAL）。頁面快取與 WAL 透過 force/steal 策略協調，確保每筆交易都能高效執行與回滾而不犧牲持久性。

並行控制方面，並行交易可能導致各種讀寫異常，不同隔離等級描述與限制這些異常的存在與否。OCC、MVCC、PCC 等方法決定交易如何被排程與執行。在 B-Tree 的物理層面，閂鎖（特別是透過蟹行與 Blink-Tree 等技術）確保並行操作的安全性同時最大化吞吐量。