數(shù)據(jù)庫管理系統(tǒng)（DBMS）在處理并發(fā)操作時，需要一套并發(fā)控制協(xié)議來確保共享對象的“正確”結(jié)果。這種“正確性”可以從兩個方面來理解：

• 邏輯正確性 (Logical Correctness) ：指線程能夠看到它應(yīng)該看到的數(shù)據(jù)。例如，如果一個B+樹索引插入了一個鍵值，該線程立即讀取該鍵值時，它應(yīng)該能看到它，而不會得到一個假陰性（false negative）結(jié)果。
• 物理正確性 (Physical Correctness) ：指數(shù)據(jù)結(jié)構(gòu)的內(nèi)部表示是健全的。這意味著在多線程讀寫數(shù)據(jù)時，數(shù)據(jù)結(jié)構(gòu)的完整性（例如指針和引用）必須得到維護，以避免指向無效內(nèi)存位置，從而導(dǎo)致程序崩潰（seg fault）等問題。本次討論主要關(guān)注的是物理正確性。

鎖 (Locks) 與鎖存 (Latches) 的區(qū)別

在數(shù)據(jù)庫領(lǐng)域，"鎖" 和 "鎖存" 是兩個不同的概念，用于保護不同層面的數(shù)據(jù)。

鎖 (Locks)

• 保護對象 ：保護數(shù)據(jù)庫的 邏輯內(nèi)容 ，如元組（tuples）、一組元組或整個表、數(shù)據(jù)庫，使其免受其他事務(wù)的并發(fā)訪問和修改。
• 持有時間 ：通常在 整個事務(wù)期間 持有。這意味著如果一個事務(wù)正在修改某個數(shù)據(jù)，它會持有鎖直到事務(wù)完成。
• 回滾需求 ：需要支持 回滾 機制。如果事務(wù)在修改過程中崩潰，DBMS必須能夠撤銷已做的更改。
• 模式類型 ：有多種鎖模式，如共享 (Shared)、排他 (Exclusive)、更新 (Update)、意向 (Intention) 等。
• 死鎖處理 ：依賴于外部的 鎖管理器 (Lock Manager) 或事務(wù)管理器 (Transaction Manager) 來檢測和解決死鎖，例如通過等待-超時 (Waits-for, Timeout) 或事務(wù)中止 (Aborts)。

鎖存 (Latches)

• 保護對象 ：保護DBMS內(nèi)部數(shù)據(jù)結(jié)構(gòu)（如索引、緩沖區(qū)池中的頁面表等）的 關(guān)鍵代碼段 (critical sections) 及其 物理完整性 ，使其免受其他線程的并發(fā)訪問和修改。
• 持有時間 ：只在 操作的持續(xù)期間 持有，通常是極短的時間。例如，當(dāng)線程需要更新一個頁面時，它會獲取該頁面的鎖存，進行更改，然后立即釋放鎖存。
• 回滾需求 ： 不需要支持回滾 。因為鎖存保護的操作通常是原子性的，如果無法獲取鎖存，操作就不會執(zhí)行，因此沒有需要回滾的更改。
• 模式類型 ：主要有兩種模式—— 讀模式 (Read Mode) 和 寫模式 (Write Mode) 。

讀模式 (Read Mode) ：允許多個線程同時共享讀鎖存，因為讀操作不會修改數(shù)據(jù)結(jié)構(gòu)。

寫模式 (Write Mode) ：是排他性鎖存，只允許一個線程持有。當(dāng)一個線程持有寫鎖存時，其他線程不能讀取或修改該對象。

• 死鎖處理 ： 不提供死鎖檢測或解決機制 。死鎖的避免完全取決于 編程紀(jì)律 (Coding Discipline) ，即通過良好的設(shè)計和實現(xiàn)來確保死鎖不會發(fā)生。

鎖存的實現(xiàn)方式

鎖存的實現(xiàn)通?；诂F(xiàn)代CPU提供的原子比較-交換 (compare-and-swap, CAS) 指令。主要有以下幾種方法：

阻塞式操作系統(tǒng)互斥鎖 (Blocking OS Mutex)

• 實現(xiàn)方式 ：這是最簡單的方式，直接使用操作系統(tǒng)提供的互斥鎖（如C++標(biāo)準(zhǔn)庫中的 std::mutex）。在Linux中，futex（fast user-space mutex）是一種常見的實現(xiàn)，它首先嘗試在用戶空間通過自旋鎖獲取，如果失敗，則下沉到內(nèi)核空間獲取更昂貴的互斥鎖，并可能導(dǎo)致線程被調(diào)度器掛起。
• 優(yōu)點 ：使用簡單，無需額外的編碼。
• 缺點 ： 非可伸縮性 ，每次加鎖/解鎖操作可能需要約25納秒，因為涉及操作系統(tǒng)的調(diào)度開銷，對于高競爭系統(tǒng)來說，性能會成為問題。

測試-設(shè)置自旋鎖 (Test-and-Set Spin Latch / TAS)

• 實現(xiàn)方式 ：由DBMS自己實現(xiàn)，通常使用CPU的單指令原子比較-交換操作。線程會反復(fù)嘗試設(shè)置一個內(nèi)存位置（例如，將一個布爾值設(shè)置為 true），直到成功獲取。如果無法獲取，線程會在一個 while 循環(huán)中“自旋”重試。
• 優(yōu)點 ： 效率極高 ，加鎖/解鎖操作通常是單個CPU指令。
• 缺點 ： 非可伸縮性且不緩存友好 。在高競爭環(huán)境下，線程會不斷自旋，消耗CPU周期但未做有效工作，導(dǎo)致CPU利用率飆升。同時，這可能引起緩存一致性問題，因為多個線程在不同CPU上輪詢同一個緩存行。
• 優(yōu)化 ：開發(fā)者可以根據(jù)工作負載決定是否在自旋失敗后短暫地讓出CPU（yield），或在嘗試一定次數(shù)后中止操作。由于DBMS對數(shù)據(jù)結(jié)構(gòu)的使用場景有更深入的了解，因此可以比操作系統(tǒng)做得更好。

讀寫鎖存 (Reader-Writer Latch)

• 實現(xiàn)方式 ：通常在自旋鎖的基礎(chǔ)上實現(xiàn)。它通過管理讀/寫隊列和計數(shù)器來區(qū)分讀寫請求。
• 優(yōu)點 ： 允許并發(fā)讀取 ，這對于讀密集型工作負載能顯著提高性能，因為多個讀取線程可以共享資源而無需等待。
• 缺點 ： 增加了復(fù)雜性 。DBMS需要管理讀寫隊列以避免寫線程饑餓 (starvation)，同時相比簡單的自旋鎖，它需要更多的元數(shù)據(jù)和存儲開銷。

哈希表 (Hash Table) 的鎖存

哈希表相對容易支持并發(fā)訪問，因為線程訪問數(shù)據(jù)結(jié)構(gòu)的方式有限。

• 單向訪問 ：所有線程在從一個槽位移動到下一個槽位時都沿同一個方向（自上而下），且一次只訪問一個頁面或槽位。這使得 死鎖不可能發(fā)生 。
• 重整大小 ：在調(diào)整哈希表大小時，通常會獲取整個表的 全局鎖存 （例如在頭部頁面上），以防止其他線程在此期間讀寫表。

哈希表的鎖存策略主要有兩種。

頁面鎖存 (Page Latches)

• 特點 ：每個頁面有自己的讀寫鎖存，保護整個頁面內(nèi)容。
• 權(quán)衡 ：需要存儲的鎖存數(shù)量較少（每個頁面一個），但 可能會降低并行性 ，因為即使兩個線程操作不同槽位，如果它們在同一頁面內(nèi)，也可能無法同時運行。

槽鎖存 (Slot Latches)

• 特點 ：每個槽位都有自己的鎖存。
• 權(quán)衡 ： 允許更高的并行性 ，因為鎖存粒度更細。但 增加了存儲和計算開銷 ，因為線程在掃描時需要為每個訪問的槽位獲取鎖存。

B+樹 (B+Tree) 的鎖存

B+樹的并發(fā)控制更為復(fù)雜，因為它不僅涉及節(jié)點內(nèi)容的修改，還涉及樹結(jié)構(gòu)的動態(tài)變化（如分裂和合并）。

B+樹并發(fā)控制主要需要解決兩個問題：

1. 多個線程同時修改同一個節(jié)點的內(nèi)容。
2. 一個線程遍歷樹時，另一個線程可能正在分裂或合并節(jié)點，導(dǎo)致頁面位置改變或指針失效。

解決這些問題的一種經(jīng)典技術(shù)稱為 鎖存爬行 (Latch Crabbing) 或 鎖存耦合 (Latch Coupling) 。

鎖存爬行 (Latch Crabbing) 的基本思想

鎖存爬行的基本思想是：

1. 獲取父節(jié)點的鎖存。
2. 獲取子節(jié)點的鎖存。
3. 如果確定子節(jié)點是“安全”的，則釋放父節(jié)點的鎖存。

“安全”節(jié)點定義 ：一個節(jié)點被認(rèn)為是安全的，當(dāng)對其進行更新操作時，它不會導(dǎo)致分裂 (split) 或合并 (merge)。

• 對于 插入 操作，如果節(jié)點未滿（不會分裂），則認(rèn)為是安全的。
• 對于 刪除 操作，如果節(jié)點內(nèi)的鍵值數(shù)量多于一半（不會合并），則認(rèn)為是安全的。

查找 (Find) 操作

• 查找操作只涉及讀取，因此可以全程使用 讀鎖存 。
• 從根節(jié)點開始，獲取子節(jié)點的讀鎖存后，可以立即釋放父節(jié)點的讀鎖存，因為讀操作不會改變樹的結(jié)構(gòu)。

插入 (Insert) / 刪除 (Delete) 操作

• 從根節(jié)點開始，獲取 寫鎖存 。
• 在獲取子節(jié)點鎖存后， 檢查該子節(jié)點是否安全 。如果安全，則可以釋放所有祖先節(jié)點上持有的寫鎖存。
• 如果不安全，則需要繼續(xù)持有祖先節(jié)點的鎖存，直到找到安全的子節(jié)點或到達葉節(jié)點。
• 釋放鎖存的順序 ：從性能角度考慮，應(yīng)盡快釋放更高層級（更接近根）的鎖存，因為它覆蓋的節(jié)點范圍更廣，能提高并行性。

根節(jié)點爭用 (Root Contention) 問題

鎖存爬行的一個問題是，每次插入或刪除操作都必須在根節(jié)點上獲取 寫鎖存 。由于寫鎖存是排他性的，這意味著在任何給定時間，只有一個線程可以持有根節(jié)點的寫鎖存，從而形成了一個 單點瓶頸 (single point of contention) ，嚴(yán)重限制了高并發(fā)系統(tǒng)的并行性。

樂觀鎖存 (Optimistic Latching)

為了解決根節(jié)點爭用問題，出現(xiàn)了一種更優(yōu)化的鎖存算法，通常稱為 樂觀鎖存 (Optimistic Latching) 或 Baron-Schlock-Nick 算法。

核心思想 ： 樂觀假設(shè) 在實際數(shù)據(jù)庫系統(tǒng)中，B+樹節(jié)點通常很大（如8KB或16KB），因此大部分插入或刪除操作不會導(dǎo)致節(jié)點分裂或合并?；谶@個假設(shè)，算法會 樂觀地假定 目標(biāo)葉節(jié)點是安全的。

具體操作

1. 初始遍歷 ：線程從根節(jié)點開始， 全程使用讀鎖存 進行鎖存爬行，直到到達目標(biāo)葉節(jié)點。
2. 獲取葉節(jié)點寫鎖存 ：到達葉節(jié)點后，線程嘗試獲取該葉節(jié)點的 寫鎖存 。
3. 檢查安全并執(zhí)行 ：如果此時發(fā)現(xiàn)葉節(jié)點是安全的（例如，有足夠的空間進行插入而無需分裂，或刪除后仍超過半滿而無需合并），則線程可以直接在該葉節(jié)點上進行修改，然后釋放鎖存。
4. 失敗重啟 ：如果發(fā)現(xiàn)葉節(jié)點不安全（例如，需要分裂或合并），則說明樂觀假設(shè)失敗。此時，線程會 釋放所有已獲得的鎖存，并中止當(dāng)前操作 。然后，它會 從頭開始，并使用悲觀策略 ，即采用傳統(tǒng)的鎖存爬行方法，從根節(jié)點開始全程獲取 寫鎖存 。

• 優(yōu)點 ：顯著減少了根節(jié)點和中間節(jié)點的寫鎖存持有時間， 提高了并發(fā)性 。
• 缺點 ：如果樂觀假設(shè)經(jīng)常失?。ɡ缭诠?jié)點頻繁分裂或合并的負載下），那么每次重新啟動并重新遍歷樹都會導(dǎo)致 浪費工作 (wasted work) ，反而可能比悲觀策略慢。但在大多數(shù)實際場景中，這種樂觀策略表現(xiàn)良好。

葉節(jié)點遍歷 (Leaf Node Scans) 與死鎖

在B+樹中，如果只進行自上而下的遍歷，死鎖是不可能發(fā)生的，因為所有線程都沿一個方向前進。然而，當(dāng)引入 葉節(jié)點掃描 (Leaf Node Scans) 時（即在葉節(jié)點層級從左到右或從右到左遍歷），情況會變得復(fù)雜，因為此時線程可能需要獲取不同方向的鎖存，從而導(dǎo)致 潛在的死鎖 。

例如，一個線程可能正在從左向右掃描并持有右側(cè)節(jié)點的讀鎖存，而另一個線程從右向左掃描并持有左側(cè)節(jié)點的讀鎖存，它們可能會同時嘗試獲取對方持有的鎖存，從而發(fā)生死鎖。

如何確保不會死鎖 ：

• 鎖存不提供死鎖檢測或避免功能 。
• 依賴編程紀(jì)律 ：解決這個問題的唯一方法是依靠 編程紀(jì)律 (Coding Discipline) 。
• “無等待”模式 (No-Wait Mode) ：當(dāng)一個線程嘗試獲取葉節(jié)點上的鎖存但該鎖存不可用時，它會 立即中止操作 （釋放所有已持有的鎖存），然后 重新開始操作 。
• 原因 ：由于鎖存是低級別的機制，它沒有關(guān)于其他線程正在做什么的全局信息。因此，與其嘗試推斷或等待，最簡單有效的方法就是立即中止并重試。雖然這可能導(dǎo)致在極端情況下線程“饑餓”或浪費周期，但在實踐中，這通常是最佳策略。

延遲父節(jié)點更新 (Delayed Parent Updates) / Blink-Tree 優(yōu)化

正常的B+樹節(jié)點溢出時，需要更新三個節(jié)點：被分裂的葉節(jié)點、新創(chuàng)建的葉節(jié)點以及它們的父節(jié)點（用于添加新的分隔鍵）。這種多節(jié)點的更新需要復(fù)雜的鎖存管理，可能導(dǎo)致更多的鎖爭用和重啟。

Blink-Tree 優(yōu)化 引入了一種技術(shù)，當(dāng)葉節(jié)點溢出時， 延遲更新其父節(jié)點 。

實現(xiàn)方式 ：

1. 當(dāng)葉節(jié)點分裂時，線程只更新葉節(jié)點本身，并創(chuàng)建一個新的相鄰節(jié)點。
2. 它不會立即更新父節(jié)點。相反，它會在樹的 全局信息表 中記錄一個待處理的更新，表明父節(jié)點需要添加一個新的分隔鍵。
3. 下一次有線程以寫模式獲取該父節(jié)點的鎖存時，它會首先檢查并應(yīng)用這個延遲的更新，從而使樹結(jié)構(gòu)變得一致。

• 優(yōu)點 ：這避免了在分裂時重新啟動樂觀鎖存操作，因為它不需要立即獲取并持有父節(jié)點的寫鎖存。
• 正確性 ：這種方法仍然能保證正確性，因為即使父節(jié)點尚未更新，查找操作也可以通過遍歷當(dāng)前的指針（包括可能的兄弟節(jié)點指針，如果存在）來找到正確的數(shù)據(jù)。

總結(jié)

總而言之，使數(shù)據(jù)結(jié)構(gòu)具有線程安全性在實踐中是出了名的困難。我們討論了哈希表和B+樹的并發(fā)控制，但其核心思想是通用的：

• 強制單向操作 （如哈希表的自頂向下掃描，避免死鎖）。
• 在遇到死鎖潛力時立即中止并重試操作 （如B+樹的葉節(jié)點掃描）。
• 樂觀地假設(shè)快速路徑 （如樂觀鎖存，大部分操作只需讀鎖存）。

這些并發(fā)控制技術(shù)在整個計算機科學(xué)和系統(tǒng)領(lǐng)域都有廣泛應(yīng)用。商業(yè)數(shù)據(jù)庫系統(tǒng)通常會自己實現(xiàn)這些核心數(shù)據(jù)結(jié)構(gòu)，以便根據(jù)其特定的目標(biāo)操作環(huán)境進行優(yōu)化。