多版本並行控制（MVCC）

核心想法

鎖式並行控制（第 10 章）讓讀者與寫者互相阻塞。 改變規則：寫入不覆蓋舊值，而是產生新版本；每筆交易讀取一個固定時間點的快照。於是：

• 讀者永遠不阻塞寫者、寫者也不阻塞讀者（寫者之間仍需協調）。

• 唯讀交易可以看到一致的「時間切片」而不需要任何鎖——報表查詢與 OLTP 共存。

• 支援「時間旅行」查詢（Oracle flashback、CockroachDB ）。

代價是：空間（舊版本）、回收舊版本的工作（garbage collection）、以及索引必須處理多個版本。 任何 MVCC 實作都要回答三個問題：版本存哪裡？讀者如何判定可見？舊版本何時回收？

版本儲存的三種設計

版本鏈的方向也有講究：PostgreSQL 由舊指向新（oldest-to-newest），讀者可能要走過多個已死版本才到最新； InnoDB 由新指向舊（newest-to-oldest），讀最新版本是 \(O(1)\)。Wu 等人（VLDB 2017）對記憶體資料庫的實測顯示： 沒有單一最佳設計，瓶頸取決於工作負載與版本回收策略。

PostgreSQL 的 tuple 版本

回顧第 2 章的 ，MVCC 相關欄位：

只是設定 ； 是「舊版本設 xmax + 插入新版本」。這就是為什麼 PostgreSQL 的回滾幾乎零成本—— 中止的交易留下的版本因為 對應的交易狀態為 aborted 而自動不可見。

快照

快照（snapshot）描述「在取得快照的瞬間，哪些交易已經完成」。PostgreSQL 的快照由三部分組成， 以 顯示，例如 ：

• xmin（100）：所有 XID \(<\) xmin 的交易都已結束（committed 或 aborted）。

• xmax（106）：第一個尚未配發的 XID；所有 XID \(\ge\) xmax 的交易在快照時還不存在，一律不可見。

• xip（101、104）：介於兩者之間、快照時仍在進行中的交易；它們的寫入不可見（即使後來 commit 了）。

XID 102、103、105 已結束，可見與否取決於它們 commit 還是 abort——查 commit log（pg_xact），並把結果以 hint bit 寫回 tuple 省下以後的查詢。

Read Committed：每個語句開始時取新快照；Repeatable Read / Serializable：整筆交易在第一個語句時取一次快照。這就是兩個等級全部的差別。

可見性規則

對快照 \(S\) 與 tuple \(t\)（簡化版，完整版見 的 ）：

visible(t, S):
  -- 第一步：建立者是否「對我而言已 commit」
  if t.xmin == my_xid:
      if t.cmin >= my_current_cid: return false      -- 本交易稍後的命令才插入
  elif t.xmin in S.xip or t.xmin >= S.xmax: return false   -- 快照時仍在進行 / 尚未存在
  elif status(t.xmin) != COMMITTED: return false     -- 已中止
  -- 第二步：刪除者是否「對我而言已 commit」
  if t.xmax == 0 or XMAX_INVALID or LOCK_ONLY: return true   -- 沒人刪它
  if t.xmax == my_xid: return t.cmax >= my_current_cid       -- 自己刪的：之前的命令看不到
  if t.xmax in S.xip or t.xmax >= S.xmax: return true        -- 刪除者快照時未完成：仍看得到
  return status(t.xmax) != COMMITTED                         -- 刪除者 commit 了就看不到

兩個關鍵洞見：(1) 可見性只靠 tuple 本身的欄位、快照與 clog 就能決定，不需要鎖； (2) 「比較 XID 大小」在 32 位元回繞下必須用模運算（），稍後會談。

寫入衝突

兩筆交易更新同一列時，第二個到達者發現該列的 屬於進行中的交易，必須等待對方結束（這是 MVCC 中唯一會阻塞的情境之一）：

• 對方 abort：接手，正常更新。

• 對方 commit，Read Committed：PostgreSQL 重新取得該列的最新版本，重新評估 條件（ 機制）；仍符合就更新新版本。 這就是為什麼 RC 下 不會 lost update。

• 對方 commit，Repeatable Read / Serializable：丟出 （）， 因為快照中看不到新版本，繼續更新會違反快照語意——first-updater-wins。

也透過 xmax 實作列鎖；多個交易共享鎖定同一列時 xmax 指向一個 MultiXact ID（）。

HOT 與 heap pruning

Append-only 最大的痛點：每次 UPDATE 都要在每一個索引插入指向新版本的項目，即使更新的欄位沒被索引。 PostgreSQL 8.3 引入 Heap-Only Tuple（HOT）：若 (a) 沒有任何索引欄位被改動、(b) 新版本放得進同一頁， 則新版本不進索引；索引仍指向舊版本的 line pointer，讀者沿頁內的 鏈走到最新版本。 舊版本死掉後，heap pruning（任何讀寫該頁的 backend 都可能順手做）把死版本的空間回收、line pointer 改為 redirect， 整個過程不需要碰索引也不需要 VACUUM。

VACUUM

HOT 處理不了跨頁的死版本與索引項目，這是 VACUUM 的工作。一次（lazy）VACUUM 的流程：

1. 依 Visibility Map 跳過 all-visible 的頁，掃描其餘 heap 頁：prune、收集死 tuple 的 TID（存於 ，PostgreSQL 17 起改用 radix tree 大幅省記憶體）、 凍結夠老的 tuple、更新 FSM/VM。

2. 掃描每個索引，刪除指向這些 TID 的項目（index vacuum；大表最耗時的一步）。

3. 回到 heap，把死 tuple 的 line pointer 設為 。

4. 若檔案尾端全空，截斷檔案歸還 OS；更新 、。

VACUUM 不會把空間還給作業系統（除尾端外），只是讓同表的新資料可以重用； 會重寫整張表（需要 鎖與兩倍空間）， 線上環境改用 擴充套件。

XID 回繞與凍結

XID 是 32 位元，約 42 億個，PostgreSQL 把它當成環：對任一 XID，比它「小」的 21 億個是過去、「大」的 21 億個是未來。 若某個舊 tuple 的 放著不管超過 21 億個交易，它會突然變成「未來」而對所有人不可見——資料看似消失。

解法是凍結（freeze）：VACUUM 把夠老的 tuple 標為 （舊版本是把 xmin 改成常數 2），表示「對所有人永遠可見、不再比較」。

SELECT datname, age(datfrozenxid) AS xid_age,
       round(age(datfrozenxid) / 2147483647.0 * 100, 2) AS pct_to_wraparound
FROM   pg_database ORDER BY 2 DESC;
SELECT relname, age(relfrozenxid) FROM pg_class WHERE relkind = 'r' ORDER BY 2 DESC LIMIT 10;

MultiXact ID 也是 32 位元、也需要凍結（）。 PostgreSQL 內部已有 64 位元的 （含 epoch），但 heap tuple 標頭仍是 32 位元；把頁面標頭改為帶 epoch 的 64-bit XID 是社群多年進行中的工作。

Serializable Snapshot Isolation

PostgreSQL 9.1 的 SSI（Ports & Grittner 2012，基於 Cahill 2008）讓 SI 變成真正可序列化，而且不使用阻塞鎖。核心理論：

• rw-antidependency（\(T_1 \xrightarrow{rw} T_2\)）：\(T_1\) 讀了某資料，\(T_2\) 之後寫了它的新版本（\(T_1\) 看不到）。\(T_1\) 在序列化順序中必須排在 \(T_2\) 之前。

• 定理（Fekete et al. 2005）：SI 下所有非可序列化的執行，其序列化圖中都存在一條危險結構： \(T_1 \xrightarrow{rw} T_2 \xrightarrow{rw} T_3\) 兩條連續的 rw-antidependency，且 \(T_3\) 最早 commit。

• SSI 追蹤 rw 邊（用 SIREAD lock——不阻塞任何人的「述詞鎖」，記錄誰讀過哪些 tuple／頁／表），一旦偵測到危險結構就中止其中一方（）。 會有少量誤判（結構存在但實際上可序列化），但不會漏判。

實務要點：SIREAD lock 存在共享記憶體， 等參數控制上限（超過會升級為頁／表粒度，增加誤判）； 純報表交易宣告 可等到一個安全快照後完全不參與偵測； 序列化失敗率高時表示工作負載衝突多，應考慮重新設計而非只是重試。

其他系統速覽

• InnoDB：每筆列有隱藏欄 、（指向 undo 記錄）；read view 等同快照； purge thread 回收不再需要的 undo； 的 history list length 是「undo 積壓」指標； 長交易會讓 undo tablespace 暴漲，而非表膨脹。

• Oracle：undo tablespace 大小與 決定能回溯多久；超過就 。

• SQL Server：RCSI/Snapshot 把舊版本放進 tempdb 的 version store（2019 起可用 ADR 的持久版本存放區）。

• CockroachDB / TiDB：MVCC 建在 LSM 鍵值層上——鍵為 ，舊版本由 GC TTL（預設 4 小時／10 分鐘）與 compaction 清除（第 12、16 章）。