B - 樹數據庫加鎖歷史

前言：

作爲數據庫最重要的組成之一，併發控制一直是數據庫領域研究的熱點和工程實現中的重點和難點。之前已經在文章《淺析數據庫併發控制》[4] 中介紹了併發控制的概念和實現方式。簡單地說，就是要實現：並行執行的事務可以滿足某一隔離性級別 [5] 的正確性要求。要滿足正確性要求就一定需要對事務的操作做衝突檢測，對有衝突的事務進行延後或者丟棄。根據檢測衝突的時機不同可以簡單分成三類：

這三種策略的立足點其實是對沖突的樂觀程度，越樂觀，也就是認爲衝突發生越少，就越傾向於推遲衝突的檢測。直觀的也可以看出，越晚的衝突檢測越有可能獲得高的併發。但當衝突真正出現時，由於前面的操作可能都需要一筆勾銷，因此在衝突較多的場景下，太樂觀反而得不償失。而衝突歸根結底是由用戶的使用場景決定的，在不能對用戶場景做太多假設的通用數據庫中，毫無疑問，基於 Lock 的方式顯得更爲合適。除此之外，由於 MVCC 的廣泛應用消除了讀寫之間的衝突，使得 Lock 帶來的併發影響大大降低，也使得基於 Lock 的併發控制仍然是主流。
對數據庫的數據加鎖這件事情，本身是跟數據的組織方式是密不可分的，數據組織方式可能給加鎖帶來限制，同時利用組織方式的特性，可能也能改造和優化加鎖過程。在磁盤數據庫中，數據組織方式的王者非 B + 樹莫屬，而且已經半個世紀有餘。B 樹是 1972 年 Bayer 在《Organization and Maintenance of Large Ordered Indices》一文中提出的 [1]。其通過多叉樹的方式，實現從單個節點中索引大量子樹。從而大大降低了整個樹高，將二叉樹中大量的隨機訪問轉化爲順序訪問，減少磁盤尋道，完美契合了磁盤順序訪問性能遠好於隨機訪問的特性，以及其塊設備接口。本文主要關注的就是如何在 B + 樹上實現基於 Lock 的併發控制，限於篇幅本文暫時拋開 MVCC 的影響。

1. B+Tree

BTree 在結構上有大量變種，本文聚焦於 Bayer 1977 年在《Concurrency of Operations on B-Trees》中提出的 B+ Tree(或 B* Tree)[2]：所有的數據信息都只存在於葉子節點，中間的非葉子節點只用來存儲索引信息，這種選擇進一步的增加了中間節點的索引效率，使得內存可以緩存儘可能多的索引信息，減少磁盤訪問；除根節點以外，每個節點的鍵值對個數需要介於 M/2 和 M 之間，超過或者不足需要做分裂或者合併。

如上圖所示是樹中的一部分，每個節點中包含一組有序的 key，介於兩個連續的有序 key，key+1 中間的是指向一個子樹的指針，而這個子樹中包含了所有取值在 [key, key+1) 的記錄。

當節點中的記錄插入超過 M/2 時，需要觸發 Split，如上圖將節點 L 中 153 之後的記錄拆分到新節點中，同時需要修改在其父節點中插入一條新的 Key 153 以及對應的指針。分裂的過程可能繼續向更上層傳導。與之對應的是從樹中刪除數據時，可能觸發節點合併，同樣需要修改其父節點，同樣可能向更上層傳導。

2. Lock

首先要明確，併發控制中的 Lock 跟我們在多線程編程中保護臨界區的 Lock 不是一個東西，這個的區別會在後面講到。事務在操作數據庫時，會先對要訪問的元素加對應的 Lock，爲了更高的併發， Lock 通常有不同的 Mode，如常見的讀鎖 SL，寫鎖 WL，不同 Mode 的鎖相互直接的兼容性可以用兼容性表來表示：

如多個事務可以同時持有 SL，但已經有 WL 的元素不能再授予任何事務 SL 或 WL。數據庫通常會有一個調度模塊來負責資源的加鎖放鎖，以及對應事務的等待或丟棄。所有的鎖的持有和等待信息會記錄在一張 Lock Table 中，調度模塊結合當前的 Lock Table 中的狀況和鎖模式的兼容表來作出決策。如下圖所示：事務 T3 已經持有了元素 A 的寫鎖 WL，導致事務 T1 和 T2 無法獲得讀鎖 SL，從而在隊列中等待，直到 T3 結束釋放 WL 後，調度模塊再依次喚醒等待的事務。
《淺析數據庫併發控制》[4] 中提到了，爲了實現 Serializable，通常會按照兩階段鎖（2PL）的規則來進行加鎖，也就是將事務的執行過程分爲 Growing 階段以及 Shrinking 階段，Growing 階段可以對任何元素加鎖但不能放鎖，一旦有一次放鎖就進入了 Shrinking 階段，這個階段就不能再對任何元素加鎖了。通常的實現中，Shrinking 階段會在事務 Commit 時。可以用反證法方便的證明遵守 2PL 的加鎖規則的併發事務滿足 Seralizable。

問題

本文將要討論的就是如何在 B+Tree 數據庫上，基於 Lock 的方式，來實現高併發、高效的數據庫併發控制。我們會按照時間先後順序逐步展開，並分析每前進一步時的思路和背後的動機。即使是那些歷史的方案，筆者認爲也是很有價值進行研究的，他們其中一部分可能已經不是最初的用途，卻在新的方向上發揚光大；另一部分雖然暫時被淘汰，但在未來隨着新的硬件軟件發展，以及新的數據庫需求的出現，可能又會煥發新的生機。本文主要關注 B+Tree 加鎖策略的兩個指標：

傳統的加鎖策略

2PL

這個時期的加鎖策略認爲樹節點是最小的加鎖單位。由於 B+Tree 的從根向下的搜索模式，事務需要持有從根節點到葉子節點路徑上所有的鎖。而兩階段鎖 (2PL) 又要求所有這些鎖都持有到事務 Commit。更糟糕的是，任何插入和刪除操作都有可能導致樹節點的分裂或合併（Structure Modification Operations, SMO），因此，對根結點需要加寫鎖 WL，也就是說任何時刻只允許一個包含 Insert 或 Delete 操作的事務進行。顯而易見，這會嚴重的影響訪問的併發度。

Tree Protocol

針對這個問題，Tree Protocol[3] 應運而生，他正是利用 B+Tree 這種從根訪問的特性，實現在放鬆 2PL 限制，允許部分提前放鎖的前提下，仍然能夠保證 Serializable：

這種加鎖方式也被稱爲 Lock Coupling。直觀的理解：雖然有提前放鎖，但自 root 開始的訪問順序保證了對任何節點，事務的加鎖順序是一致的，因此仍然保證 Seralizable。Tree Protocol 實現上需要考慮一個棘手的問題：就是對 B+Tree 而言，一直要搜索到葉子結點纔可以判斷是否發生 SMO。以一個 Insert 操作爲例，悲觀的方式，對遇到的每一個節點先加寫鎖，直到遇到一個確認 Safe 的節點（不會發生 SMO）；而樂觀的方式認爲 SMO 的相對並不是一個高頻操作，因此只需要先對遇到的每個節點加讀鎖，直到發現葉子節點需要做分裂，才把整個搜索路徑上所有的讀鎖升級寫鎖（Upgrade Lock）。當兩個持有同一個節點讀鎖的事務同時想要升級寫鎖時，就會發生死鎖，爲了避免這種情況，引入了 Update Lock Mode，只有 Update Lock 允許升級，並且 Update Lock 之間不兼容，這其實是一種權衡。

仔細分析會發現，2PL 和 Tree Protocol 中面臨的最大問題其實在於：節點的 SMO 時需要持有其父節點的寫鎖。正因爲如此纔不得不在搜索過程提前對所有節點加寫鎖，或者當發現 SMO 後再進行升級，進退維谷。而之所以這樣，是由於需要處理父節點中的對應 key 及指針，節點的分裂或合併，跟其父節點的修改是一個完整的過程，不允許任何其他事務看到這個過程的中間狀態。針對這個問題，Blink Tree[7] 巧妙的提出對所有節點增加右向指針，指向其 Sibling 節點，這是個非常漂亮的解決方案，因爲他其實是提供了一種新的節點訪問路徑，讓上述這種 SMO 的中間狀態，變成一種合法的狀態，從而避免了 SMO 過程持有父節點的寫鎖。

對 Record 加 Lock 而不是 Page

上面講到的傳統的加鎖策略，認爲 Btree 的節點是加鎖的最小單位，而所做的努力一直是在降低單個事務需要同時持有的鎖的節點數，能不能更進一步提升 Btree 的併發能力呢？《Principles and realization strategies of multilevel transaction management》[8] 對這個問題進行了深入的研究，如下圖所示：

以兩個轉賬業務 T1，T2 爲例，用戶 A 和用戶 B 分別轉賬給用戶 C 一筆錢，在數據庫中的執行可以分爲三層，最高層 L2 從用戶角度看，A 和 B 的賬戶上的金額減少，C 的賬戶金額增加；中間層 L1 在記錄角度，代表 A 和 B 賬戶金額的 Record x、Record y 做了查詢以及更新操作，而代表 C 賬戶金額的 Record z 做了更新操作；最下層 L0 站在 Page 的角度，Record x 以及 y 都在 Page p 上，而 Record z 在 Page q 上，因此 Page p 以及 Page q 都被兩個事務讀寫。按照上面講到的對 Page 加 Lock 的做法，T2 必須等 T1 執行完成並釋放 p，q 兩個 Page 上的鎖。這種接近串行的併發度當然不是我們想要的。因此《Principles and realization strategies of multilevel transaction management》提出分層事務的解決方案，如果能在 L1 層，也就是對 Record 而不是 Page 加鎖，就可以避免 T1 和 T2 在 Page p Lock 上的等待，如上圖所示，T1 和 T2 對 Record x 和 Record y 的操作其實是併發執行的。而 L0 層對 Page 的併發訪問控制可以看做是上層事務的一個子事務或嵌套事務，其鎖持有不需要持續整個最外層事務的生命週期。沿着這個思路，ARIES/KVL 出現了。

ARIES/KVL 峯迴路轉

《ARIESIKVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes》[10] 提出了一套完整的、高併發的實現算法，引導了 B+Tree 加鎖這個領域今後幾十年的研究和工業實現。ARIES/KVL 首先明確的區分了 B+Tree 的物理內容和邏輯內容，邏輯內容就是存儲在 B+Tree 上的那些數據記錄，而 B+Tree 自己本身的結構屬於物理內容，物理內容其實事務是不關心的，那麼節點分裂、合併這些操作其實只是改變了 B+Tree 的物理內容而不是邏輯內容。因此，ARIES/KVL 就將這些從 Lock 的保護中抽離出來，也就是 Lock 在 Record 上加鎖，對物理結構則通過 Latch 來保護其在多線程下的安全。這裏最本質的區別是 Latch 不需要在整個事務生命週期持有，而是隻在臨界區代碼的前後，這其實也可以看作上面分層事務的一種實現。更多 Lock 和 Latch 的區別見下表：

Latch 保護物理結構

可以看出 Latch 纔是我們在多線程編程中熟悉的，保護臨界區訪問的鎖。通過 Latch 來保護 B+Tree 物理結構其實也屬於多線程編程的範疇，上述傳統的 B+Tree 加鎖方式的優化，也可以直接無縫轉化過來。只是將 Lock 換成的 Latch，其作用對象也從事務之間變成線程之間。比如 Lock Coupling 變成了 Latch Coupling；比如對中間結點先持有 Read Latch 或 Update Latch，而不是 Write Latch，等需要時再升級；又比如，可以採用 Blink 的方式可以避免 SMO 操作持有父節點 Latch。以及這個方向後續的一些無鎖結構如 BW-Tree，其實都是在嘗試進一步降低 Latch 對線程併發的影響。本文對這裏不再進一步探討，而是回到本文主要關心的事務之間併發控制上，也就是保護邏輯內容的 Lock。

Lock 保護邏輯結構

有了這種清晰的區分，事務的併發控制就變得清晰很多，不再需考慮樹本身的結構變化。假設事務 T1 要查詢、修改、刪除或插入一個 Record X，而 Record X 所在的 Page 爲 q，那麼加 Lock 過程就變成這樣：

Search（X）and Hold Latch(q);

SLock(X) or WLock(X);

// Fetch, Insert or Delete
Unlatch(q);

....

T Commit and Unlock(X)

在第一步對 Btree 的查找過程，會按照上面所說的 Latch Coupling 的方式申請及釋放對應的 Page Latch，最終持有目標 Record 所在葉子結點的 Latch，如果 Insert 或者 Delete 需要導致樹結構變化，也就是發生 SMO，只需在 Latch 的保護下完成即可，不涉及 Lock。之後在第三步向調度器申請 Record Lock，如果能馬上滿足，那麼這個 Page Latch 就可以釋放了。但如果這個 Lock 需要等待，持有 Latch 等待顯然是不明智的，會讓併發回退到之前對 Page 加 Lock 的方案。爲了解決這個問題，ARIES/KVL 採用了 Condition Lock 加 Revalidation 的方式，就是說先對 Record 加 Conditional Lock，這種 Lock 如果不能滿足會立即返回而不是阻塞等待，如果失敗則先釋放 Page Latch，再對 Record 加 Unconditional Lock 來阻塞等待。等這個 Lock 可以滿足並返回的時候，由於這段時間沒有 Latch 保護，Page 或整個樹結構都發生了變化，當然不能繼續之前的操作了。這個時候就要 Revalidation，其實就是判斷自己需要的葉子節點以及其所有的祖先節點有沒有發生變化，需要從未變化的那層重新搜索，這裏的辦法就是在之前釋放 Latch 之前先記錄這些節點的版本號，Revalidation 的時候直接找到版本號沒有變化的位置。

Key Range Locking

前面這套結合 Latch 和 Lock 方案，已經可以很好的支持對單條 Record 的增刪改查。但很多數據庫訪問並不是針對某一條記錄的，而是基於條件的。比如查詢滿足某個條件的所有 Record，這個時候就會出現《數據庫事務隔離發展歷史》[5] 中提到的幻讀的問題，也就是在事務的生命週期中，由於新的滿足條件的 Record 被其他事務插入或刪除，導致該事務前後兩次條件查詢的結果不同。這其實是要求，條件查詢的事務和插入 / 刪除滿足這個條件 Record 的事務之間，有相互通信或衝突發現的機制，最直接的想法是對所有可能的，還不存在的 Key 也加鎖，在大多數情況下，由於 Key 範圍的無限，這都是不可接受的。傳統的解決幻讀的方案是謂詞鎖 (Predicate Lock)，也就是直接對查詢條件加鎖，每次插入刪除需要判斷是否與現有的判斷條件衝突，但通用數據庫中，條件千變萬化，判斷條件衝突這件事情開銷極大。也正是因此，謂詞鎖並沒有成爲主流。在 B+Tree 上，由於其 Key 有序的特點，通常會採用 Key Range Locking，也就是對 Key 加鎖，來保護其旁邊的區間 Range，有很多中選擇，如下圖所示：

其中最常見的一種實現是 Next Key Locking，也就是上圖中最上面的一條線，通過對 1174 加鎖，來保護 1174 這個節點以及其前面和 1171 之間的 Gap。
我們來看下增加了 Next Key Lock 的加鎖過程如下。假設當前 Record X 的下一條記錄是 Y，且都在 Page q，X 和 Y 都滿足條件查詢事務 T1 的查詢條件，T1 會重複上面的加鎖過程並持有 X 和 Y 上的 Lock。這時事務 T2 嘗試在 X 和 Y 之間插入 Record M，我們看看它的加鎖過程：

Search（M，Y）and Hold Latch(q);

XLock(Y);

XLock(M);

Insert M into q

Unlatch(q);

....

T2 Commit and Unlock(M), Unlock(Y)

跟之前相比，這裏多了對 Next Key 也就是 Y 加鎖，正是由於這個鎖，可以發現持有 Y 上 SLock，並且還沒有提交的查詢事務 T1，等待直到 T1 完成 Commit 並放鎖。爲了追求更高的併發度，會有一些手段來改進 Key Range Locking：

Instant Locking

可以看到，上述加鎖過程中，Insert 需要對要插入位置的 Next Key 加 Lock，如果已經是最大則需要對正無窮加 Lock，並持有整個事務生命週期。尤其在高頻率順序插入的場景，這個 Next Key Lock 就會成爲明顯的瓶頸。Instant Locking 的方案很好地解決了這個問題。顧名思義，Instant Locking 只在瞬間持有這把 Next Key Locking，其加鎖是爲了判斷有沒有這個 Range 衝突的讀操作，但獲得鎖後並不持有，而是直接放鎖。乍一看，這樣違背了 2PL 的限制，使得其他事務可能在這個過程獲得這把鎖。通過巧妙的利用 Btree 操作的特性，以及 Latch 及 Lock 的配合，可以相對完美的解決這個問題，如下是引入 Instant Locking 後的 Insert 加 Next Key Lock 的流程：

Search（M，Y）and Hold Latch(q);

XLock(Y);
Unlock(Y)

XLock(M);

Insert M into q

Unlatch(q);
....

T Commit and Unlock(M)

可以看出，Y 上 Lock 的獲取和釋放，和插入新的 Record 兩件事情是在 Page q 的 Latch 保護下進行的，因此這個中間過程是不會有其他事務進來的，等 Latch 釋放的時候，新的 Record 其實已經插入，這個 X 到 Y 的區間已經被劃分成了，X 到 M 以及 M 到 Y，新的事務只需要對自己關心的 Range 加鎖即可。分析這個過程，可以提前放鎖的根本原因是：Insert 的 New Record 在其他事務對這個 Range 加鎖的時候已經可見。Delete 就沒有這麼幸運了，因爲 Delete 之後這個 Key 就不可見了，因此 Delete 的持有的 Next Key Locking 似乎不能採用 Instant Locking，這個時候 Ghost Record 就派上用場了。

Ghost Records

Ghost Record 的思路，其實跟之前講到拆分物理內容和邏輯內容是一脈相承的，Ghost Record 給每個記錄增加了一位 Ghost Bit 位，正常記錄爲 0，當需要刪除某個 Record 的時候，直接將其 Ghost Bit 修改爲 1 即可，正常的查詢會檢查 Ghost Bit，如果發現是 1 則跳過。但是 Ghost Record 是可以跟正常的 Record 一樣作爲 Key Range Lock 的加鎖對象的。可以看出這相當於把刪除操作變成了更新操作，因此刪除事務不再需要持有 Next Key Lock。除此之外，由於回滾的也變成了修改 Ghost Bit，不存在新的空間申請需要，因此避免了事務回滾的失敗。Ghost Record 的策略也成爲大多數 B+Tree 數據庫的必選實現方式。
當然，這些 Ghost Record 最終還是需要刪除的，其刪除操作通常會放到後臺異步進行，由於 Ghost Record 對用戶請求是不可見的，因此這個刪除過程只是對物理結構的改變，也不需要加 Lock。但 Record 的刪除會導致其左右的兩個 Lock Range 合併，因此這個過程除了需要 Page 的 Latch 之外，還需要獲得 Lock 系統中 Lock 的 Latch，在 Lock 的 Latch 保護下對 Lock Range 合併。
除了這種延遲刪除的 Ghost Record 之外，還有一種 Ghost Record 也稱爲 Fence Key，是在 Page 的末尾添加一個獨立的 Key 值記錄這個 Page 所在子樹的分隔 Key，實現上可以在 Page Split 的時候從 Parent 節點拷貝而來。這種做法最大的好處就是避免加 Next Key Lock 的時候對後繼結點的訪問需求。

Keep Going

追求更好的 B+Tree 加鎖方案的努力不曾停止，這裏就介紹他們中的一些佼佼者，以及其設計思路。

ARIES/IM

實際的數據庫中，單個表常常會有大量的二級索引，也就是大量的 B+Tree，顯然對每個 B+Tree 分別加鎖開銷是很大的。Mohan C 在文章《ARIES/IM: an efficient and high concurrency index management method using write-ahead logging》[11] 中提出了 ARIES/IM，將加鎖對象由 B+Tree 上的 Key-Value 變成了其最終指向的數據，這樣無論有多少二級索引最終都只需要加一把鎖。顯而易見的，這種做法在降低鎖開銷的同時也降低了併發度。另外，從這個例子中可以清楚地看到：對 Locking Resource 的選擇是在 Concurrency 和 Locking Overhead 之間的權衡。

KRL

Lomet D B. 在《Key Range Locking Strategies for Improved Concurrency》[13] 中分析了上面的 ARIES/KVL 和 ARIES/IM，並提出從兩個方向的改進。首先是 Range Lock 的加鎖範圍，KVL 和 IM 中的 Range 都是對 Next Key 以及中間的 Gap 同時加鎖，一定程度上限制了對 Key 和對 Gap 訪問的併發，KRL 提出將二者拆分，分別加鎖。這種選擇在提高併發度的同時，由於需要加更多的鎖而增加了加鎖開銷。第二個改進提出了更精確的鎖 Mode，包括 Intention Update，Intention Insert 以及 Intention Delete，其基本思路就是用更精確的鎖 mode 區分操作類型從而更大程度的挖掘他們之間的併發可能。

Hierarchical Locking

Hierarchical Locking 其實有非常久的歷史了，初衷是爲了讓大事務拿大鎖，小事務拿小鎖，來在事務併發度及加鎖開銷做權衡，常見的加鎖層級包括對錶加鎖，對索引加鎖，以及對 Record 加鎖。Hierarchical Locking 對高層級的加鎖對象通常採用 Intention Lock 來增加併發， 比如 Intention X Lock 自己是相互兼容的。隨着硬件發展，數據庫的表和索引也在變大，同時在上述的 Range Lock 語義下，一個事務的查詢範圍內，如果有較多的 Record，那麼就需要加很多的 Range Lock，大量的 Lock 會帶來大量的內存佔用，消耗大量的 CPU。因此 Graefe G. 在《Hierarchical locking in B-tree indexes》[14] 中提出了可以在 Table 和 Key 之間增加更多的加鎖粒度，其中探索了兩種思路，一種是利用 B+Tree 的層級關係，在中間節點的 Key 上加 Range Lock；另一種是對 Key 的前綴加鎖，這其實是更接近傳統謂詞鎖的一種方式。除此之外，《Hierarchical locking in B-tree indexes》還探索了每種方案下，隨着負載變化動態的 Lock 層級變化策略。

Early Lock Release

傳統的 2PL 爲了保證 Serializable，要求事務要持有鎖一直到事務 Commit，但如果拉長事務 Commit 的過程看，其包括進入 Commit 狀態後內存狀態的改變，以及等待 Commit Log 落盤的時間，其中等待落盤的時間通常又大大超過了修改內存狀態的時間。針對這一點，在《Efficient locking techniques for databases on modern hardware》[15] 中提出了可以在等待 Commit Log 落盤之前就釋放鎖的方案，以此來提高併發度。這個方案最大的挑戰就是 Commit Log 落盤前的 Crash 會導致該事務回滾，因此後續事務雖然可以提前獲得鎖，但還是不能早於之前的事務 Commit，這一點對寫事務是容易保證的，因爲之後的寫事務也需要寫 Commit Log，而 Commit Log 所在的 REDO 文件是連續的。難點在於讀事務，讀事務並不會寫 Commit Log，那麼就必須增加額外的機制來阻止其提前 Commit，比如《Efficient locking techniques for databases on modern hardware》中採用的對 Lock 加 Tag 以及《Controlled lock violation》[16] 中調度器對 Lock Violation 的檢查。

總結

我們看到，B+Tree 加鎖的發展歷史其實都是圍繞着我們前面提到的兩個主要問題進行的，即提高併發度和降低鎖開銷，而採用的手段通常包括：

  1. 對 Lock 對象或粒度的選擇，比如從 Page Lock 到 Key Lock，以及 Hierarchical Locking。

  2. 引入新的 Lock Mode，比如 KRL 以及沒有提到的 Increment Lock。

  3. 縮短 Lock 持有時間，比如 Early Lock Release 或 Controlled Lock Violation。

回顧整個的發展過程：

如果用橫座標表示算法的併發度，縱座標表示加鎖開銷，可以看到本文提到的算法之間的關係，如下圖所示，注意這裏只是定性的分析。通常認爲，在可接受的鎖開銷範圍內，更傾向於獲得更高的併發度。因此圖中紅框的部分是筆者認爲現代數據庫應該做到的區域。

參考

[1] Bayer R, McCreight E M. Organization and Maintenance of Large Ordered Indices[J]. Acta Informatica, 1972, 1: 173-189.

[2] Bayer R, Schkolnick M. Concurrency of operations on B-trees[J]. Acta informatica, 1977, 9(1): 1-21.

[3] Bernstein P A, Hadzilacos V, Goodman N. Concurrency control and recovery in database systems[M]. Reading: Addison-wesley, 1987.

[4] http://catkang.github.io/2018/09/19/concurrency-control.html

[5] http://catkang.github.io/2018/08/31/isolation-level.html

[6] Garcia-Molina H, Ullman J D, Widom J. Database system implementation[M]. Upper Saddle River, NJ:: Prentice Hall, 2000.

[7] Lehman, Philip L., and S. Bing Yao. “Efficient locking for concurrent operations on B-trees.” ACM Transactions on Database Systems (TODS) 6.4 (1981): 650-670.

[8] Weikum, Gerhard. “Principles and realization strategies of multilevel transaction management.” ACM Transactions on Database Systems (TODS) 16.1 (1991): 132-180.

[9] Moss, J. Eliot B. “Open nested transactions: Semantics and support.” Workshop on Memory Performance Issues. Vol. 28. 2006.

[10] Mohan C. ARIES/KVL: A key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes[M]. IBM Thomas J. Watson Research Division, 1989.

[11] Mohan C, Levine F. ARIES/IM: an efficient and high concurrency index management method using write-ahead logging[J]. ACM Sigmod Record, 1992, 21(2): 371-380.

[12] Graefe G. A survey of B-tree locking techniques[J]. ACM Transactions on Database Systems (TODS), 2010, 35(3): 1-26.

[13] Lomet D B. Key range locking strategies for improved concurrency[M]. Digital Equipment Corporation, Cambridge Research Laboratory, 1993.

[14] Graefe G. Hierarchical locking in B-tree indexes[J]. Datenbanksysteme in Business, Technologie und Web (BTW 2007)–12. Fachtagung des GI-Fachbereichs” Datenbanken und Informationssysteme”(DBIS), 2007.

[15] Kimura H, Graefe G, Kuno H A. Efficient locking techniques for databases on modern hardware[C]//ADMS@ VLDB. 2012: 1-12.

[16] Graefe G, Lillibridge M, Kuno H, et al. Controlled lock violation[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. 2013: 85-96.

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/tCxvRUTZsQaJiOdq2qTidA

猜你喜歡