CMU15-445 數據庫系統播客：樂觀并發控制 - 時間戳排序（TO）與樂觀并發控制（OCC）
在數據庫系統的世界里，ACID 中的“I”——隔離性（Isolation）是確保多用戶環境下數據一致性的基石。為了實現隔離性，數據庫管理系統（DBMS）必須采用并發控制協議（Concurrency Control Protocol）。其中， 兩階段鎖定（Two-Phase Locking, 2PL） 作為一種 悲觀 策略，是我們最先接觸也是最經典的協議之一。它如同一個謹小慎微的管家，假設事務之間總是會發生沖突，因此在任何操作前都要求先獲取鎖，即“先請求許可”。
然而，在許多真實世界的場景中，事務間的直接沖突并非那么頻繁。悲觀鎖的開銷——鎖的獲取、等待、釋放以及潛在的死鎖——可能會成為性能瓶頸。因此，數據庫研究者們提出了另一類 樂觀 的并發控制思想，它們更像是“先斬后奏，出了問題再處理”。
本文將深入探討兩種主流的樂觀并發控制協議： 時間戳排序（Timestamp Ordering, T/O） 和 樂觀并發控制（Optimistic Concurrency Control, OCC） ，并介紹其衍生和面臨的共同挑戰。
時間戳排序 (Timestamp Ordering, T/O)
時間戳排序協議的核心思想極其優雅： 如果能為每個事務預先分配一個全局唯一且遞增的時間戳，那么我們就可以強制所有事務的執行效果等同于按照時間戳順序的串行執行 。
時間戳的源泉
為了實現這一目標，時間戳必須具備兩個關鍵特性：唯一性 和 單調遞增性 。DBMS 通常采用以下幾種方式生成時間戳：
- **系統時鐘 (System Clock)**：直接使用機器的物理時鐘。這種方式簡單直觀，但在分布式系統中面臨時鐘同步的難題，且可能因夏令時等因素導致時鐘回撥，破壞單調性。
- 邏輯計數器 (Logical Counter) ：在內存中維護一個原子遞增的計數器。它速度極快且無鎖，能完美保證唯一性和單調性。但缺點是可能存在回卷（wrap-around）問題，雖然在64位系統上這幾乎不可能發生。
- 混合方法 (Hybrid) ：結合物理時鐘和邏輯計數器。例如，將時間戳的高位賦予物理時間，低位賦予一個在該物理時間單位內遞增的邏輯計數器。這是目前最主流和穩健的實現方式。
基本時間戳排序協議 (Basic T/O)
在 Basic T/O 協議中，我們不再需要鎖，而是為數據庫中的每個數據對象（例如，一個元組）附加上一些元數據：
- 讀取時間戳 (Read Timestamp, R-TS) ：記錄了成功讀取該對象的、所有事務中 最大 的時間戳。
- 寫入時間戳 (Write Timestamp, W-TS) ：記錄了成功寫入該對象的事務的時間戳。
事務 在執行讀寫操作時，將遵循以下規則：
讀操作規則
寫操作規則
優化：托馬斯寫入規則 (Thomas Write Rule)
Basic T/O 的挑戰
盡管設計精巧，Basic T/O 協議也存在一些顯著缺點：
- 高昂的開銷 ：為每個數據對象維護和更新時間戳，以及將數據拷貝到事務的私有工作空間，都會帶來不小的性能開銷。
- 長事務饑餓 (Starvation) ：一個長時間運行的事務，其時間戳相對較早，很容易與后續的短事務發生沖突，導致它被反復中止和重啟，難以完成。
- 可能產生不可恢復的調度 (Non-recoverable Schedules) ：一個事務可能讀取了另一個尚未提交事務寫入的數據。如果前者先提交，而后者最終中止，數據庫將陷入不一致狀態，且無法通過簡單的回滾恢復。
樂觀并發控制 (OCC)：終極的樂觀主義者
如果說 T/O 協議是在每一步都檢查時間戳，那么 樂觀并發控制 (Optimistic Concurrency Control, OCC) 則將這種樂觀精神發揮到了極致。OCC 的核心假設是： 事務間的沖突是小概率事件 。因此，它完全省去了操作過程中的任何檢查，讓事務自由地在“沙箱”中執行，直到準備提交時，才進行一次性的沖突總檢查。
OCC 的事務生命周期分為三個階段：
- 讀階段 (Read / Work Phase) ：事務讀取數據，并將所有 寫操作 記錄在自己的 私有工作空間 中。所有修改對其他事務都是不可見的。在此階段，系統會記錄下事務的 讀集 (Read Set) 和 寫集 (Write Set) 。
- 驗證階段 (Validation Phase) ：當事務發起提交時，它進入此關鍵階段。DBMS 會在此刻為該事務 分配一個時間戳 。然后，系統會驗證該事務的讀寫集是否與 近期已提交的 或 正在并發驗證的 其他事務存在沖突，從而保證可串行化。如果驗證失敗，事務將 中止 ，其在讀階段所做的所有工作全部作廢。
- 寫階段 (Write Phase) ：如果驗證成功，DBMS 將把事務在其私有工作空間中的所有修改 原子性地 應用到數據庫中，使其對所有后續事務可見。
OCC 的適用場景與瓶頸
OCC 在以下場景中表現極其出色：
- 讀密集型工作負載 ：大部分事務是只讀的，沖突概率自然很低。
- 事務訪問不相交數據 ：事務傾向于操作數據庫中完全不同的部分。
在這些情況下，OCC 幾乎沒有并發控制的開銷，性能非常高。
然而，在高沖突的工作負載下，OCC 的性能會急劇下降：
- 大量工作被浪費 ：由于沖突檢測被推遲到最后，一個事務可能執行了大量復雜操作后，才在驗證階段被告知需要中止，造成了巨大的計算資源浪費。
- 驗證階段的瓶頸 ：盡管邏輯上沖突可能不多，但驗證階段本身需要檢查并發事務的讀寫集。這個過程通常需要在一個臨界區內串行執行，以保證數據結構的一致性。在高并發下，保護這個臨界區的 閂鎖 (Latch) 可能會成為新的性能瓶頸。
尋求平衡：分區時間戳排序 (Partition-based T/O)
為了解決 OCC 驗證階段的瓶頸問題，同時避免 Basic T/O 的高昂開銷，業界提出了一種巧妙的混合方案—— 分區時間戳排序 。
其核心思想是將數據庫 水平分區 (Partitioning / Sharding) ，每個分區由一個獨立的線程負責，并遵循以下規則：
- 分區內串行執行 ：在單個分區內部，所有事務嚴格按照其時間戳順序 串行執行 。因為是單線程處理，所以分區內不再需要任何鎖或閂鎖來進行并發控制。
- 跨區并行處理 ：不同的分區可以并行地處理各自的事務隊列。
- 原地更新 (In-place Updates) ：由于分區內執行是串行的，事務可以直接修改數據，而無需像 OCC 那樣復制到私有工作空間，從而降低了開銷。系統會維護一個撤銷日志（Undo Log）以便在事務中止時回滾。
執行流程 ：一個事務在開始時被分配時間戳，并聲明它需要訪問的所有分區。然后，它必須獲取所有這些分區的“分區鎖”。一旦獲取成功，并且它在所有相關分區的等待隊列中都擁有最小的時間戳，它就可以開始執行。
分區 T/O 的優勢與挑戰
優勢 ：對于 單分區事務 ，其性能無與倫比，幾乎能以“裸金屬”的速度運行，因為它消除了所有并發控制的開銷。
挑戰 ：
- 多分區事務 變得復雜且可能成為瓶頸。一個跨區事務會“鎖定”多個分區，可能導致這些分區在等待該事務時處于閑置狀態。
- 該方案高度依賴于 預先知曉事務的訪問模式 。DBMS 必須在事務開始前就知道它將觸及哪些分區。這對于通過 存儲過程 (Stored Procedures) 執行的事務來說是可行的，但對于交互式、即席查詢的事務則非常困難。
所有協議的共同難題：幻讀 (The Phantom Problem)
無論是悲觀的 2PL，還是樂觀的 T/O 和 OCC，它們在處理一個棘手問題時都會遇到麻煩，那就是 幻讀 。
為什么元組級別的并發控制無法解決幻讀？ 因為你無法對一個“尚不存在”的數據加鎖或設置時間戳。傳統的并發控制機制只能作用于已存在的數據項。
解決幻讀的常用方法有：
- 謂詞鎖定 (Predicate Locking) ：對查詢的
WHERE條件本身加鎖。這在理論上最完美，但因其實現復雜度和巨大開銷，在商業系統中極為罕見。 - 索引鎖定 (Index Locking) ：一種實用的謂詞鎖近似方案。通過鎖定索引中的相關范圍或 間隙 (Gap) ，來阻止滿足條件的新數據被插入。這是目前主流數據庫解決幻讀問題的標準方法。
- 分層鎖定 (Hierarchical Locks) ：通過請求一個更粗粒度的鎖（如表鎖）來阻止任何插入，但這會嚴重犧牲并發性。
結論：沒有銀彈，只有取舍
通過今天的探討，我們深入了解了數據庫并發控制的“樂觀”派系：
- 時間戳排序 (T/O) ：通過預先定義的時間順序來保證可串行化。它是一種“主動預防”的樂觀策略，在每次操作時都進行檢查，但容易導致事務中止。
- 樂觀并發控制 (OCC) ：將沖突檢查推遲到最后一刻，是“事后驗證”的終極樂觀策略。它在低沖突場景下性能極佳，但在高沖突時則因工作浪費而表現糟糕。
- 分區時間戳排序 ：一種結合了分區思想的混合策略，旨在為特定類型的工作負載（尤其是單分區事務）提供極致性能。
最終，并發控制協議的選擇沒有絕對的優劣之分，它是一個基于應用 工作負載 的復雜權衡。是選擇 2PL 的穩健與可預測性，還是擁抱 OCC 在低沖突環境下的高效，亦或是采用分區 T/O 這樣的特化方案，都取決于我們對數據訪問模式的深刻理解。作為數據庫開發者和使用者，掌握這些協議的內在機理，將使我們能更好地設計和優化我們的系統。
