鎖與並行控制

Lock 與 Latch

第 3、4 章的 latch crabbing、buffer header 鎖都屬於 latch；本章的主角是交易鎖。

鎖模式與多粒度鎖

最基本的兩種模式：共享鎖 S（讀）與排他鎖 X（寫）。若鎖的粒度是整張表，並行度太低；若只有列鎖， 一個全表掃描要取百萬個鎖，鎖表爆炸。Gray 等人（1976）提出多粒度鎖與意向鎖（intention lock）： 在上層節點（資料庫 \(\to\) 表 \(\to\) 頁 \(\to\) 列）宣告「我打算在下層取某種鎖」。

• IS / IX：打算在下層取 S / X。要鎖某列 X 之前，先在表上取 IX、在頁上取 IX。

• SIX = S + IX：讀整張表，同時更新其中少數列。

• 全表掃描在表上取 S，就與任何 IX（有人在改某列）衝突——正確地阻止了讀到半更新狀態；而兩個 IX 相容，改不同列的交易互不干擾（列層級再判斷）。

• 鎖升級（escalation）：列鎖太多時換成表鎖以省資源（SQL Server、DB2 會；PostgreSQL 不會，因為列鎖存在 tuple 裡不佔鎖表）。

兩階段鎖

兩階段鎖（2PL）：每筆交易分為成長期（只取鎖、不放鎖）與縮減期（只放鎖、不取鎖）。 一旦釋放任何鎖，就不能再取得新鎖。

定理：2PL 產生的排程都是衝突可序列化的。證明概要：令每筆交易的 lock point 為它取得最後一個鎖的時刻； 若 \(T_i \to T_j\) 有衝突邊，則 \(T_i\) 必須先釋放該資料的鎖、\(T_j\) 才能取得，故 \(\text{lockpoint}(T_i) < \text{lockpoint}(T_j)\)。 若優先圖有環，會推出 lock point 的嚴格遞增環，矛盾。

但基本 2PL 允許在縮減期釋放 X 鎖後被別人讀到尚未 commit 的值 \(\Rightarrow\) 連鎖中止。 Strict 2PL：X 鎖持有到 commit/abort；Rigorous（strong strict）2PL：所有鎖持有到結束。 實務系統都用 strict/rigorous 2PL，代價是並行度降低與死結。

死結

偵測

維護等待圖（wait-for graph）：\(T_i \to T_j\) 表示 \(T_i\) 在等 \(T_j\) 持有的鎖。有環即死結，選一個受害者中止 （依據：已完成的工作量、持有的鎖數、重啟次數避免餓死）。

預防

以交易時間戳（越老優先權越高）決定誰等、誰死，保證等待圖無環：

• Wait-Die（非搶占）：老交易等年輕交易；年輕交易要等老交易時直接中止（die）。

• Wound-Wait（搶占）：老交易要鎖時直接把年輕持有者中止（wound）；年輕交易等老交易。

中止的交易重啟時保留原時間戳，否則會餓死。分散式系統（如早期 Spanner、CockroachDB 的某些路徑）偏好預防，因為跨節點建等待圖代價高。

Phantom 與述詞鎖

Strict 2PL 鎖住的是已存在的列。\(T_1\) 執行 鎖了符合的 10 列， \(T_2\) 插入一列 不會與任何鎖衝突——phantom 出現。解法：

• 述詞鎖（predicate lock）：鎖住條件 本身，與任何可能符合的插入衝突；判定述詞相交代價高，少有系統直接實作。

• 索引範圍鎖／gap lock：鎖住索引上 的區間。InnoDB 的 next-key lock（記錄鎖 + 前方的 gap 鎖）就是這個， 這也是 InnoDB 的 RR 沒有 phantom（對鎖定讀而言）的原因，但也帶來不少「為什麼插入會被鎖住」的困惑。

• SSI 的 SIREAD lock：PostgreSQL 的做法——不阻塞，只記錄讀過的範圍（tuple／頁／表），事後偵測衝突（第 9 章）。

PostgreSQL 的表級鎖

PostgreSQL 有 8 種表級鎖模式，名稱源自歷史，不要望文生義（ 是表級鎖，表示「我要改列」）。 每個 SQL 命令自動取得對應模式，衝突時排隊等待：

PostgreSQL 的列級鎖

• 不改主鍵／唯一鍵欄位時取 FOR NO KEY UPDATE；改鍵或 取 FOR UPDATE。

• 外鍵檢查對被參照的父列取 FOR KEY SHARE——所以更新父列的非鍵欄位（NO KEY UPDATE）不會與子表的插入互相阻塞。這是 9.3 引入這兩種弱鎖的原因。

• 列鎖記錄在 tuple 的 （多個持有者時用 MultiXact），不佔鎖表，所以鎖百萬列也不會耗盡 ，但會產生 WAL 與髒頁。

• ：拿不到立即失敗；：跳過被鎖的列——實作工作佇列的標準寫法。

WITH next_job AS (
  SELECT id FROM jobs
  WHERE  status = 'pending'
  ORDER  BY created_at
  FOR UPDATE SKIP LOCKED
  LIMIT  1
)
UPDATE jobs SET status = 'running', worker = :me
FROM   next_job WHERE jobs.id = next_job.id
RETURNING jobs.*;

Advisory lock（、）讓應用程式借用資料庫的鎖管理器協調任意資源（如「同一時間只跑一個排程器」）。

診斷鎖等待

SELECT a.pid, a.state, a.wait_event_type, a.wait_event,
       pg_blocking_pids(a.pid) AS blocked_by,
       now() - a.xact_start AS xact_age,
       left(a.query, 60) AS query
FROM   pg_stat_activity a
WHERE  cardinality(pg_blocking_pids(a.pid)) > 0 OR a.pid IN (SELECT unnest(pg_blocking_pids(pid)) FROM pg_stat_activity)
ORDER  BY a.xact_start;

列出所有鎖（ 為等待中）； 表示在等交易鎖， 則是內部閂鎖爭用（如 、、）——那是另一類問題（I/O 或 CPU 瓶頸），不是應用程式的鎖。 找到源頭後可 （取消查詢）或 （斷線）。

樂觀並行控制

Kung 與 Robinson（1981）的 OCC：交易在私有工作區讀寫（讀取階段），commit 時驗證讀集沒有被已 commit 的並行交易改過 （backward validation：與所有在我開始後 commit 的交易比對），通過才把寫集寫入（寫入階段，通常在一個短暫的全域臨界區內）。 衝突罕見時沒有任何鎖開銷；衝突多時重做成本高，且長交易容易一直被年輕交易「驗證失敗」。 記憶體資料庫（Hekaton、Silo、TicToc）與 FoundationDB 採用 OCC 變體。對照：MVCC + first-updater-wins 其實也是一種「對寫入樂觀」的策略。