CMU15-445 數據庫系統播客：多線程下索引鎖存的并發控制
數據庫管理系統（DBMS）在處理并發操作時，需要一套并發控制協議來確保共享對象的“正確”結果。這種“正確性”可以從兩個方面來理解：
- 邏輯正確性 (Logical Correctness) ：指線程能夠看到它應該看到的數據。例如，如果一個B+樹索引插入了一個鍵值，該線程立即讀取該鍵值時，它應該能看到它，而不會得到一個假陰性（false negative）結果。
- 物理正確性 (Physical Correctness) ：指數據結構的內部表示是健全的。這意味著在多線程讀寫數據時，數據結構的完整性（例如指針和引用）必須得到維護，以避免指向無效內存位置，從而導致程序崩潰（seg fault）等問題。本次討論主要關注的是物理正確性。
鎖 (Locks) 與鎖存 (Latches) 的區別
在數據庫領域，"鎖" 和 "鎖存" 是兩個不同的概念，用于保護不同層面的數據。
鎖 (Locks)
- 保護對象 ：保護數據庫的 邏輯內容 ，如元組（tuples）、一組元組或整個表、數據庫，使其免受其他事務的并發訪問和修改。
- 持有時間 ：通常在 整個事務期間 持有。這意味著如果一個事務正在修改某個數據，它會持有鎖直到事務完成。
- 回滾需求 ：需要支持 回滾 機制。如果事務在修改過程中崩潰，DBMS必須能夠撤銷已做的更改。
- 模式類型 ：有多種鎖模式，如共享 (Shared)、排他 (Exclusive)、更新 (Update)、意向 (Intention) 等。
- 死鎖處理 ：依賴于外部的 鎖管理器 (Lock Manager) 或事務管理器 (Transaction Manager) 來檢測和解決死鎖，例如通過等待-超時 (Waits-for, Timeout) 或事務中止 (Aborts)。
鎖存 (Latches)
- 保護對象 ：保護DBMS內部數據結構（如索引、緩沖區池中的頁面表等）的 關鍵代碼段 (critical sections) 及其 物理完整性 ，使其免受其他線程的并發訪問和修改。
- 持有時間 ：只在 操作的持續期間 持有，通常是極短的時間。例如，當線程需要更新一個頁面時，它會獲取該頁面的鎖存，進行更改，然后立即釋放鎖存。
- 回滾需求 ： 不需要支持回滾 。因為鎖存保護的操作通常是原子性的，如果無法獲取鎖存，操作就不會執行，因此沒有需要回滾的更改。
- 模式類型 ：主要有兩種模式—— 讀模式 (Read Mode) 和 寫模式 (Write Mode) 。
讀模式 (Read Mode) ：允許多個線程同時共享讀鎖存，因為讀操作不會修改數據結構。
寫模式 (Write Mode) ：是排他性鎖存，只允許一個線程持有。當一個線程持有寫鎖存時，其他線程不能讀取或修改該對象。
- 死鎖處理 ： 不提供死鎖檢測或解決機制 。死鎖的避免完全取決于 編程紀律 (Coding Discipline) ，即通過良好的設計和實現來確保死鎖不會發生。
鎖存的實現方式
鎖存的實現通常基于現代CPU提供的原子比較-交換 (compare-and-swap, CAS) 指令。主要有以下幾種方法：
阻塞式操作系統互斥鎖 (Blocking OS Mutex)
- 實現方式 ：這是最簡單的方式，直接使用操作系統提供的互斥鎖（如C++標準庫中的
std::mutex）。在Linux中，futex（fast user-space mutex）是一種常見的實現，它首先嘗試在用戶空間通過自旋鎖獲取，如果失敗，則下沉到內核空間獲取更昂貴的互斥鎖，并可能導致線程被調度器掛起。 - 優點 ：使用簡單，無需額外的編碼。
- 缺點 ： 非可伸縮性 ，每次加鎖/解鎖操作可能需要約25納秒，因為涉及操作系統的調度開銷，對于高競爭系統來說，性能會成為問題。
測試-設置自旋鎖 (Test-and-Set Spin Latch / TAS)
- 實現方式 ：由DBMS自己實現，通常使用CPU的單指令原子比較-交換操作。線程會反復嘗試設置一個內存位置（例如，將一個布爾值設置為
true），直到成功獲取。如果無法獲取，線程會在一個while循環中“自旋”重試。 - 優點 ： 效率極高 ，加鎖/解鎖操作通常是單個CPU指令。
- 缺點 ： 非可伸縮性且不緩存友好 。在高競爭環境下，線程會不斷自旋，消耗CPU周期但未做有效工作，導致CPU利用率飆升。同時，這可能引起緩存一致性問題，因為多個線程在不同CPU上輪詢同一個緩存行。
- 優化 ：開發者可以根據工作負載決定是否在自旋失敗后短暫地讓出CPU（yield），或在嘗試一定次數后中止操作。由于DBMS對數據結構的使用場景有更深入的了解，因此可以比操作系統做得更好。
讀寫鎖存 (Reader-Writer Latch)
- 實現方式 ：通常在自旋鎖的基礎上實現。它通過管理讀/寫隊列和計數器來區分讀寫請求。
- 優點 ： 允許并發讀取 ，這對于讀密集型工作負載能顯著提高性能，因為多個讀取線程可以共享資源而無需等待。
- 缺點 ： 增加了復雜性 。DBMS需要管理讀寫隊列以避免寫線程饑餓 (starvation)，同時相比簡單的自旋鎖，它需要更多的元數據和存儲開銷。
哈希表 (Hash Table) 的鎖存
哈希表相對容易支持并發訪問，因為線程訪問數據結構的方式有限。
- 單向訪問 ：所有線程在從一個槽位移動到下一個槽位時都沿同一個方向（自上而下），且一次只訪問一個頁面或槽位。這使得 死鎖不可能發生 。
- 重整大小 ：在調整哈希表大小時，通常會獲取整個表的 全局鎖存 （例如在頭部頁面上），以防止其他線程在此期間讀寫表。
哈希表的鎖存策略主要有兩種。
頁面鎖存 (Page Latches)
- 特點 ：每個頁面有自己的讀寫鎖存，保護整個頁面內容。
- 權衡 ：需要存儲的鎖存數量較少（每個頁面一個），但 可能會降低并行性 ，因為即使兩個線程操作不同槽位，如果它們在同一頁面內，也可能無法同時運行。
槽鎖存 (Slot Latches)
- 特點 ：每個槽位都有自己的鎖存。
- 權衡 ： 允許更高的并行性 ，因為鎖存粒度更細。但 增加了存儲和計算開銷 ，因為線程在掃描時需要為每個訪問的槽位獲取鎖存。
B+樹 (B+Tree) 的鎖存
B+樹的并發控制更為復雜，因為它不僅涉及節點內容的修改，還涉及樹結構的動態變化（如分裂和合并）。
B+樹并發控制主要需要解決兩個問題：
- 多個線程同時修改同一個節點的內容。
- 一個線程遍歷樹時，另一個線程可能正在分裂或合并節點，導致頁面位置改變或指針失效。
解決這些問題的一種經典技術稱為 鎖存爬行 (Latch Crabbing) 或 鎖存耦合 (Latch Coupling) 。
鎖存爬行 (Latch Crabbing) 的基本思想
鎖存爬行的基本思想是：
- 獲取父節點的鎖存。
- 獲取子節點的鎖存。
- 如果確定子節點是“安全”的，則釋放父節點的鎖存。
“安全”節點定義 ：一個節點被認為是安全的，當對其進行更新操作時，它不會導致分裂 (split) 或合并 (merge)。
- 對于 插入 操作，如果節點未滿（不會分裂），則認為是安全的。
- 對于 刪除 操作，如果節點內的鍵值數量多于一半（不會合并），則認為是安全的。
查找 (Find) 操作
- 查找操作只涉及讀取，因此可以全程使用 讀鎖存 。
- 從根節點開始，獲取子節點的讀鎖存后，可以立即釋放父節點的讀鎖存，因為讀操作不會改變樹的結構。
插入 (Insert) / 刪除 (Delete) 操作
- 從根節點開始，獲取 寫鎖存 。
- 在獲取子節點鎖存后， 檢查該子節點是否安全 。如果安全，則可以釋放所有祖先節點上持有的寫鎖存。
- 如果不安全，則需要繼續持有祖先節點的鎖存，直到找到安全的子節點或到達葉節點。
- 釋放鎖存的順序 ：從性能角度考慮，應盡快釋放更高層級（更接近根）的鎖存，因為它覆蓋的節點范圍更廣，能提高并行性。
根節點爭用 (Root Contention) 問題
鎖存爬行的一個問題是，每次插入或刪除操作都必須在根節點上獲取 寫鎖存 。由于寫鎖存是排他性的，這意味著在任何給定時間，只有一個線程可以持有根節點的寫鎖存，從而形成了一個 單點瓶頸 (single point of contention) ，嚴重限制了高并發系統的并行性。
樂觀鎖存 (Optimistic Latching)
為了解決根節點爭用問題，出現了一種更優化的鎖存算法，通常稱為 樂觀鎖存 (Optimistic Latching) 或 Baron-Schlock-Nick 算法。
核心思想 ： 樂觀假設 在實際數據庫系統中，B+樹節點通常很大（如8KB或16KB），因此大部分插入或刪除操作不會導致節點分裂或合并?；谶@個假設，算法會 樂觀地假定 目標葉節點是安全的。
具體操作
- 初始遍歷 ：線程從根節點開始， 全程使用讀鎖存 進行鎖存爬行，直到到達目標葉節點。
- 獲取葉節點寫鎖存 ：到達葉節點后，線程嘗試獲取該葉節點的 寫鎖存 。
- 檢查安全并執行 ：如果此時發現葉節點是安全的（例如，有足夠的空間進行插入而無需分裂，或刪除后仍超過半滿而無需合并），則線程可以直接在該葉節點上進行修改，然后釋放鎖存。
- 失敗重啟 ：如果發現葉節點不安全（例如，需要分裂或合并），則說明樂觀假設失敗。此時，線程會 釋放所有已獲得的鎖存，并中止當前操作 。然后，它會 從頭開始，并使用悲觀策略 ，即采用傳統的鎖存爬行方法，從根節點開始全程獲取 寫鎖存 。
- 優點 ：顯著減少了根節點和中間節點的寫鎖存持有時間， 提高了并發性 。
- 缺點 ：如果樂觀假設經常失?。ɡ缭诠濣c頻繁分裂或合并的負載下），那么每次重新啟動并重新遍歷樹都會導致 浪費工作 (wasted work) ，反而可能比悲觀策略慢。但在大多數實際場景中，這種樂觀策略表現良好。
葉節點遍歷 (Leaf Node Scans) 與死鎖
在B+樹中，如果只進行自上而下的遍歷，死鎖是不可能發生的，因為所有線程都沿一個方向前進。然而，當引入 葉節點掃描 (Leaf Node Scans) 時（即在葉節點層級從左到右或從右到左遍歷），情況會變得復雜，因為此時線程可能需要獲取不同方向的鎖存，從而導致 潛在的死鎖 。
例如，一個線程可能正在從左向右掃描并持有右側節點的讀鎖存，而另一個線程從右向左掃描并持有左側節點的讀鎖存，它們可能會同時嘗試獲取對方持有的鎖存，從而發生死鎖。
如何確保不會死鎖 ：
- 鎖存不提供死鎖檢測或避免功能 。
- 依賴編程紀律 ：解決這個問題的唯一方法是依靠 編程紀律 (Coding Discipline) 。
- “無等待”模式 (No-Wait Mode) ：當一個線程嘗試獲取葉節點上的鎖存但該鎖存不可用時，它會 立即中止操作 （釋放所有已持有的鎖存），然后 重新開始操作 。
- 原因 ：由于鎖存是低級別的機制，它沒有關于其他線程正在做什么的全局信息。因此，與其嘗試推斷或等待，最簡單有效的方法就是立即中止并重試。雖然這可能導致在極端情況下線程“饑餓”或浪費周期，但在實踐中，這通常是最佳策略。
延遲父節點更新 (Delayed Parent Updates) / Blink-Tree 優化
正常的B+樹節點溢出時，需要更新三個節點：被分裂的葉節點、新創建的葉節點以及它們的父節點（用于添加新的分隔鍵）。這種多節點的更新需要復雜的鎖存管理，可能導致更多的鎖爭用和重啟。
Blink-Tree 優化 引入了一種技術，當葉節點溢出時， 延遲更新其父節點 。
實現方式 ：
- 當葉節點分裂時，線程只更新葉節點本身，并創建一個新的相鄰節點。
- 它不會立即更新父節點。相反，它會在樹的 全局信息表 中記錄一個待處理的更新，表明父節點需要添加一個新的分隔鍵。
- 下一次有線程以寫模式獲取該父節點的鎖存時，它會首先檢查并應用這個延遲的更新，從而使樹結構變得一致。
- 優點 ：這避免了在分裂時重新啟動樂觀鎖存操作，因為它不需要立即獲取并持有父節點的寫鎖存。
- 正確性 ：這種方法仍然能保證正確性，因為即使父節點尚未更新，查找操作也可以通過遍歷當前的指針（包括可能的兄弟節點指針，如果存在）來找到正確的數據。
總結
總而言之，使數據結構具有線程安全性在實踐中是出了名的困難。我們討論了哈希表和B+樹的并發控制，但其核心思想是通用的：
- 強制單向操作 （如哈希表的自頂向下掃描，避免死鎖）。
- 在遇到死鎖潛力時立即中止并重試操作 （如B+樹的葉節點掃描）。
- 樂觀地假設快速路徑 （如樂觀鎖存，大部分操作只需讀鎖存）。
這些并發控制技術在整個計算機科學和系統領域都有廣泛應用。商業數據庫系統通常會自己實現這些核心數據結構，以便根據其特定的目標操作環境進行優化。
