## 課程目標(biāo)

課程目標(biāo)圖

https://wx2.sinaimg.cn/large/dfe0c359gy1h6jba8gefxj20me0cctab.jpg

Observation 圖

https://wx3.sinaimg.cn/large/dfe0c359gy1h6jba8xm70j20ow0g3n1l.jpg

主要是為了討論如何用多線程去訪問數(shù)據(jù)結(jié)構(gòu)，并且保證線程安全

VoltDB 和 redis 是使用單線程來訪問的，但他們依然可以獲得良好的性能

VoltDB 雖然是一個多線程引擎，但它是以某種方式將數(shù)據(jù)庫分割，每個 B+ Tree 只能由一條單線程來訪問

因此它們也不會使用 latch 鎖

但缺點(diǎn)是拓展到多核或者多臺機(jī)器上時(shí)情況就會變得復(fù)雜

## 并發(fā)控制(Concurrency Control)

并發(fā)控制圖

https://wx3.sinaimg.cn/large/dfe0c359gy1h6jba95ug4j20mc0de422.jpg

強(qiáng)制所有訪問數(shù)據(jù)結(jié)構(gòu)的線程都使用某種協(xié)議或者某種方式來解決并發(fā)訪問的問題(主要是為了保護(hù)數(shù)據(jù)結(jié)構(gòu))

并發(fā)控制不僅僅用于某個數(shù)據(jù)結(jié)構(gòu)，它同時(shí)也可以用在 tuple/index/page table/buffer pool 等場景

并發(fā)控制主要關(guān)注 2 種正確性類型(Correctness Type)

1. 邏輯正確性(Logical Correctness): 所見即所期望得到的

2. 物理正確性(Physical Correctness): 比如在多線程并發(fā)訪問一個 B+ Tree 的時(shí)候，我們經(jīng)常在遍歷它的時(shí)候用到指針，如何保證在使用這個指針的時(shí)候，這個指針指向的那個數(shù)據(jù)沒有被修改過呢(萬一這個指針指向的是一個無效的位置那么就糟糕了)?

## Locks Vs. Latches

Locks Vs. Latches 圖

https://wx3.sinaimg.cn/large/dfe0c359gy1h6jba9cqk3j20n60enq61.jpg

再談 Locks 和 Latches 的區(qū)別

1. Locks 是一種更高層面的概念，它保護(hù)了數(shù)據(jù)庫中的邏輯內(nèi)容(一個 tuple、一個 tuple 的集合、一張表、一個數(shù)據(jù)庫)，當(dāng)同一時(shí)間有其他事務(wù)在運(yùn)行時(shí)，我們會使用這些 Locks 來保護(hù)這些邏輯內(nèi)容。我們會在整個事務(wù)的執(zhí)行期間持有這些 Locks(雖然這種方式并不完全正確)，這個時(shí)候如果要將這些邏輯內(nèi)容進(jìn)行回滾，而在同一時(shí)間又有其他事務(wù)在運(yùn)行，那么這些邏輯內(nèi)容可能會遭到修改，所以需要用 Locks 來保護(hù)。

2. Latches 是一種低級層面的概念，對于 OS 來講，它會把所謂的 Latches 看作 Locks/Mutex，Latches 負(fù)責(zé)保護(hù)的是數(shù)據(jù)庫系統(tǒng)中的關(guān)鍵部分，即 Latches 可以保護(hù)內(nèi)部數(shù)據(jù)結(jié)構(gòu)免受其他線程對該數(shù)據(jù)結(jié)構(gòu)或?qū)ο笤谕粫r(shí)刻進(jìn)行讀寫所帶來的問題。我們只會在一小段時(shí)間內(nèi)持有 Latches，并且只會在對關(guān)鍵部分執(zhí)行所需要的操作時(shí)持有這些 Latches。執(zhí)行這些操作時(shí)，不需要去回滾做任何的修改，因?yàn)?Latches 要保護(hù)的操作都是原子性的。

? ? ```

? ? 操作開始? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 操作結(jié)束

? ? ? ?↓---> 獲取 Latch ---> 修改數(shù)據(jù) ---> 釋放 Latch --->↑

? ? ```

? ??

? ? 如果沒有這些 Latches，也沒法進(jìn)行上述的修改操作，那也沒必要進(jìn)行回滾了

? ??

一些其他的區(qū)別

https://wx2.sinaimg.cn/large/dfe0c359gy1h6jba9kaulj20sf0e8wiw.jpg

應(yīng)對死鎖問題時(shí)，我們會依賴某些外部協(xié)調(diào)器(Lock 管理器、事務(wù)管理器)來解決

Latches 只有 2 種模式: 讀和寫

## Latch 模式

1. 讀模式: 允許多線程在同一時(shí)間讀取同一個對象

2. 寫模式: 一次只允許一條線程能持有這個 Latch

## Latch 實(shí)現(xiàn)

### 使用 Blocking OS Mutex

Blocking OS mutex 的原理是，它使用了 Futex 即 Fast Userspace Mutex，它是在 Userspace 中的，也就是某個進(jìn)程的地址空間里面，它會占用一點(diǎn)內(nèi)存，比如 1 bit 或者 1 byte 的大小，通過這個內(nèi)存的這個位置來嘗試進(jìn)行一次 CAS 操作，用以獲取這個 Latch。但如果你沒能獲取到它，那么它就會退一步使用速度更慢的的 Mutex(注意此時(shí)的 mutex 是在 Kernel space 中的)。為什么? 因?yàn)?OS 此時(shí)知道你沒能拿到這個 Latch，它就會將你此刻的操作放入一個等待隊(duì)列中，等待調(diào)度器調(diào)度。

> CAS 即 Compare And Swap

> Futex 是一個 spin latch，也就是自旋鎖

所以要盡可能地避免使用 OS 層面的 mutex

### 使用 Test-and-Set Spin Latch

第二種方式就是使用一個 TAS(Test-And-Set) 的 spin latch

這種方式會很快，因?yàn)楝F(xiàn)代 CPU 中有一個指令，這個指令可以在一個內(nèi)存地址上進(jìn)行單次 CAS 操作，即檢查這個內(nèi)存地址上的值是否和期待的值相等，如果相等，那么就允許將它原來的值變?yōu)樾碌闹?就不用自己寫 if else 了，這條指令就幫你做了這件事)

上圖中，如果想要獲取到這個 latch，就必須使用 `while` 循環(huán)，如果 `latch.test_and_set(...)` 為 `true`，則證明拿到了這個 latch，需要跳出循環(huán)

如果沒拿到則需要一直 spin 等待，一直執(zhí)行 `latch.test_and_set(...)` 直到能拿到 latch

但缺點(diǎn)是 CPU 的使用率會上升

雖然效果跟 OS 中的 Mutex 差不多，但是 OS 中的 Mutex 并不是一直無限循環(huán)做 TAS

可以通過 TAS 的次數(shù)來判斷要不要退出循環(huán)，這是調(diào)優(yōu)的方式之一

主要是如果一個 spin latch 等待的時(shí)間過長了，要采取什么樣的方式去讓其他線程獲得機(jī)會?(直接把當(dāng)前線程 yeild 讓其他線程先執(zhí)行，或者是直接中斷掉當(dāng)前線程)

### 使用 Reader-Writer Latch

簡而言之就是在基礎(chǔ)的 latch 之上構(gòu)建出 spin latch 或者 POSIX mutex 這種東西，然后通過管理不同的隊(duì)列來跟蹤不同類型的 latch，看看有哪些線程在等待獲取它們

讀寫 latch 的工作原理如下

首先無論是 reader latch 還是 writer latch，它們內(nèi)部都會使用到一些計(jì)數(shù)器

1. 一個計(jì)數(shù)器 1 表示持有該模式 latch 的線程數(shù)量(圖中的芯片 icon)

2. 一個計(jì)數(shù)器 2 表示等待該模式 latch 的線程數(shù)量(圖中的沙漏 icon)

如果此時(shí)有一個 read 線程，它想要獲取 read latch

此時(shí)沒有線程持有這個 read latch，也沒有人正在等待獲取它，所以此時(shí)可以把這個 read latch 分發(fā)給這個線程 ，然后更新下計(jì)數(shù)器 1，表示此時(shí)有一個線程持有這個 read latch

如果此時(shí)又來一個線程，這個線程也想去獲取一個 read latch

因?yàn)?read latch 任何線程都可以共享，所以此時(shí)只需要更新計(jì)數(shù)器 1 即可

如果此時(shí)又來一個 write 線程

那么它必須停下來，等待獲取 write latch，因?yàn)?read latch 已經(jīng)被其他線程持有了。這里只需要更新下 write latch 的計(jì)數(shù)器 2，表示有一個線程正在等待獲取這個 write latch

如果此時(shí)又來了一個 read 線程，并且它想獲取 read latch，此時(shí)會發(fā)生什么呢?

這取決于使用的策略。此時(shí)的情況是什么呢?

read latch 已經(jīng)被上面幾個線程拿到了，并且其他線程也在等待獲取它，如果此時(shí)要分發(fā) read latch 給這個新來的 read 線程，那么就會導(dǎo)致 starvation(饑餓)，因?yàn)橛疫叺?write 線程永遠(yuǎn)拿不到這個 write latch 了，所以此時(shí)只能將這個新來的 read 線程停下來，并將它添加到計(jì)數(shù)器的等待隊(duì)列中去

最終，當(dāng)之前的 2 個 read 線程釋放了它們獲取到的 read latch 之后，右邊的 write 線程就會拿到它的 write latch

這里所說的策略是指什么呢?

如果有這么一種數(shù)據(jù)結(jié)構(gòu)，它不會涉及到太多的寫入操作。而由于這些寫入操作非常重要，此時(shí)就會賦予 write 線程一個更高的優(yōu)先級，也就是上面出現(xiàn)的那個情況

## Hash Table Latching

使用 Hash Table Latching 來支持并發(fā)訪問是非常容易的，因?yàn)槎鄠€線程間通過使用 hash table 來進(jìn)行交互的方式是有限的(有限，意味著有規(guī)則，有規(guī)則，意味著不會出現(xiàn)太多的意外情況)

1. 所有線程只會朝 hash table 的一個方向去做訪問，并且在同一時(shí)間只會訪問到一個 hash table 中的 page/slot

2. 不會發(fā)生死鎖

例如，在一個靜態(tài)的 hash table 中(暫且忽略掉動態(tài) hash table，因?yàn)榍闆r更加復(fù)雜)，當(dāng)你要插入某個 key 時(shí)，你需要對他進(jìn)行一次 hash，然后跳到這個 hash table 的某個 slot 處，這個時(shí)候線程可以按照順序往下掃描 hash table，以此來找到它想要找到的東西。對于其他線程來說也是一樣的，他們也會自上而下的對這個 hash table 進(jìn)行掃描，掃描到底部如果找不到，那么他們會從這個 hash table 的起始位置開始繼續(xù)掃描，循環(huán)反復(fù)(可以將這個 hash table 想象成一個環(huán)形的 buffer)

由于線程訪問 hash table 的順序一致，那么對于持有 latch 的線程來說，每個線程都不會碰到并且擁有來自反方向的線程的 latch，那么也就不會發(fā)生死鎖問題

但是如果要重新對 hash table 的 size 進(jìn)行調(diào)整的話，我們通常會在 header page 上加一個全局的 latch，這主要是為了避免在對 hash table 的 size 的調(diào)整結(jié)束之前，有其他線程對當(dāng)前的 hash table 進(jìn)行了讀寫操作(但如果一開始 hash table 的 size 很大，這種情況就會變得少見)

hash table 的 latching 有 2 種粒度

1. Page Latches(粒度較大)

2. Slot Latches(粒度較小)

如果使用 Page Latches，那么用的 latch 就會少些，畢竟一個 latch 對應(yīng)一個 page，缺點(diǎn)是線程訪問的并行性會降低(如果有 2 個線程操作的 slot 是在同一個 page 中，那它們倆也就沒法在同一時(shí)間執(zhí)行任務(wù)了)

如果使用的是 Slot Latches，那么用的 latch 就會多一些，畢竟一個 latch 對應(yīng)一個 slot，并行性雖然提升了，但是在線程進(jìn)行訪問時(shí)，開銷會變大(因?yàn)檫@么多的 latches 占的空間大，占的計(jì)算資源也多)

### Page Latches 原理

假設(shè)現(xiàn)在有 3 個簡單的 page table，每個 page table 里面都有 2 個 slot

第一個線程要尋找 D，通過對 D 進(jìn)行 hash 處理，它落到下圖中 A 的位置

雖然不知道這個位置里面的東西是不是這個線程真的想要的，但是還是要在這個線程訪問到里面的內(nèi)容之前，先拿到這個 page 的 read latch

一旦拿到這個 latch，就開始利用游標(biāo)查找

假設(shè)現(xiàn)在又來了一個線程，這個線程想要插入 E，通過對 E 進(jìn)行 hash 處理，它落到下圖中 C 的位置

此時(shí)這個線程還可以進(jìn)行插入操作嗎? 當(dāng)然不行，在這之前這個線程需要拿到這個 page table 上的 write latch，因?yàn)樗恢?C 這個位置對應(yīng)的內(nèi)容是否是滿的，它也需要去做掃描操作。然而此時(shí)它所拿到的 write latch 跟左邊那個線程拿到的 read latch 并不匹配，所以右邊這個線程需要停下來等待

所以此時(shí)左邊的線程繼續(xù)往下掃描

繼續(xù)看下一個 page table

> 注意: 如果要知道要查看的 page 里面包含了什么，就從 hash table 的 header 中去獲取查看信息，這個 header 會給你要查看的 page 有哪些。從邏輯上來講，page table 是按照順序排列的，比如下圖中的 page 0、page 1、page 2，所以通過 header 就可以知道 hash table 中 page2 對應(yīng)的位置

左邊的線程為了能從 page 1 遍歷到 page 2，就不需要持有 page 1 的 latch 了(假設(shè)此時(shí)的 hash table 是靜態(tài)的，size 不會變，對應(yīng)的 page 1 2 3 的地址都是一樣的)

在跳到 page 2 之前，立即釋放掉 page 1 的 latch，然后獲取 page 2 的 latch

> 注意: 不能去對 latch 的模式進(jìn)行升級，即將 read latch 升級成 write latch，只能是將當(dāng)前持有的 latch 釋放掉，然后去獲取另一個不同模式的 latch

現(xiàn)在，右邊的線程可以去拿 page 1 的 write latch 了

此時(shí) C 的位置并不是右邊線程所期望的，所以它繼續(xù)往下找來到 page 2，并且拿到 write latch(此時(shí)左邊線程的查找工作已經(jīng)做完)

看到 D 的位置已滿，就插入到 D 下面

### Slot Latches 原理

對于線程 T1，它將訪問到 page 1 上的 A 位置，并獲取到了 A 位置上的 read latch

此時(shí)對于線程 T2，它將訪問到 page 1 上的 C 位置，并獲取到了 C 位置上的 write latch

當(dāng) T1 再次執(zhí)行任務(wù)時(shí)，它會試著去看 C 位置這里，此時(shí)它必須停下來，因?yàn)樗鼪]拿到 C 位置上的 latch

所以 T2 可以繼續(xù)往下走，它釋放了 C 位置的 latch，然后拿到了 page 2 上 D 位置的 latch

現(xiàn)在 T1 可以往下走了，它去拿 C 位置的 latch

接著，T1 又得停下來，因?yàn)樗鼪]法拿到 D 位置的 latch

直到 T2 完成插入操作，T1 才可以繼續(xù)處理

### 小結(jié)

這里的特點(diǎn)還是不能有死鎖，因?yàn)樵谏鲜隼又?，所有的線程的執(zhí)行操作的方向都是一致的，即從上往下，因?yàn)闆]有任何一個線程是反過來的，這樣就能保證數(shù)據(jù)一致性

## B+ Tree 并發(fā)控制

如果有 2 條線程同時(shí)對同一個 B+ Tree 的某個節(jié)點(diǎn)進(jìn)行讀寫操作，那么有可能其中一條線程經(jīng)過一系列操作之后，這個節(jié)點(diǎn)被 merge/split 了，然后另一條線程在對當(dāng)前的節(jié)點(diǎn)做操作時(shí)可能就會訪問到一個無效的 地址/值

### B+ Tree 多線程訪問會出現(xiàn)的問題

現(xiàn)在有一個 B+ Tree 的數(shù)據(jù)如下圖

假設(shè)現(xiàn)在要有一個線程 T1 要刪除葉子節(jié)點(diǎn)上的 44?

第一個線程會先從根節(jié)點(diǎn) A 開始深度向下遍歷，直到遍歷到 44 這個節(jié)點(diǎn)

此時(shí)將 44 節(jié)點(diǎn)刪除

現(xiàn)在之前的 44 這個對應(yīng)的節(jié)點(diǎn)是處于半滿(half-full)的情況，所以此時(shí)就需要重新平衡這個 B+ Tree，但在這個例子中不需要做 split 操作，而是從兄弟節(jié)點(diǎn)中復(fù)制一個 key 到這個空的節(jié)點(diǎn)中去。但在執(zhí)行重新平衡操作之前，OS 會將這個要刪除的線程交換出去，所以這個線程就必須停下來等待

如果此時(shí)有另一個線程 T2 要查找 41，此時(shí)線程會遍歷直到到 D 這個節(jié)點(diǎn)

此時(shí)，線程 T2 會在這里停下來，OS 會切換回線程 T1，然后 T1 會將 41 移動到之前的那個空節(jié)點(diǎn)上

然后當(dāng) T2 再次可以執(zhí)行時(shí)，它到了 H 這個節(jié)點(diǎn)上，就會發(fā)現(xiàn) 41 已經(jīng)不在這里了

那么如何解決這種情況呢?

### Latch Crabbing/Coupling

本質(zhì)上還是使用 latches 來做一個數(shù)據(jù)訪問保護(hù)的操作

它的基本工作原理是，我們在對某個節(jié)點(diǎn)做操作時(shí)，這個節(jié)點(diǎn)上必須掛有一個 讀/寫 latch，在訪問這個節(jié)點(diǎn)的 child 節(jié)點(diǎn)之前，需要先拿到這個節(jié)點(diǎn)的 child 節(jié)點(diǎn)的上的 latch，以及下一個需要訪問到的節(jié)點(diǎn)的 latch

而當(dāng)真正訪問到了這個節(jié)點(diǎn)的 child 節(jié)點(diǎn)時(shí)，就需要對它里面的內(nèi)容進(jìn)行判斷: 我訪問到的這個節(jié)點(diǎn)是否安全?如果安全，那么就將這個節(jié)點(diǎn)的上的 latch 釋放掉

> 就像螃蟹走路，一條腿邁過另一條腿

那么如何定義一個節(jié)點(diǎn)是否安全?

就是當(dāng)你需要修改這個節(jié)點(diǎn)時(shí)，這個節(jié)點(diǎn)沒必要做一些 merge/split 操作

并且

1. 如果要做 insert 操作，那么該節(jié)點(diǎn)必須要有足夠的空間去容納要 insert 的 key(這樣就不會發(fā)生 split)

2. 如果要做 delete 操作，那么該節(jié)點(diǎn)中元素的數(shù)量必須要超過該節(jié)點(diǎn)容量的一半(這樣就不會發(fā)生 merge)

總之，基本原理如下圖

> 注意在該例子中，所有的線程都是 從上往下 深度遞歸遍歷的

### find 操作

?

比如要查找 38 這個 key ，每次向下遍歷時(shí)要加一個 read latch，直到遍歷到 B 這個節(jié)點(diǎn)

因?yàn)樗龅亩际侵蛔x操作，所以釋放 A 節(jié)點(diǎn)處的 read latch 是安全的

繼續(xù)往下掃描，到達(dá) D 節(jié)點(diǎn)時(shí)釋放掉 A 節(jié)點(diǎn)的 latch

最終到達(dá) H 節(jié)點(diǎn)，釋放掉 B 節(jié)點(diǎn)上的 latch

然后讀 H 節(jié)點(diǎn)之前，釋放掉 D 節(jié)點(diǎn)上的 latch

### delete 操作

比如要刪除 38 這個 key ，每次向下遍歷時(shí)要加一個 write latch，直到遍歷到 B 這個節(jié)點(diǎn)

此時(shí)釋放 A 節(jié)點(diǎn)的 latch 對于執(zhí)行該刪除操作的線程來說是安全的嗎?

不是

因?yàn)樵?B 節(jié)點(diǎn)處，只有一個 key 即 35，對于這個線程來說，它還不知道 B 節(jié)點(diǎn)下面的子節(jié)點(diǎn)的數(shù)據(jù)是一個什么情況，如果遍歷到 D 節(jié)點(diǎn)執(zhí)行刪除操作，對于 B 節(jié)點(diǎn)它就必須進(jìn)行 merge，那么這個 merge 的遞歸操作就會傳播到 A 節(jié)點(diǎn)，A B 2 個節(jié)點(diǎn)都會有被修改的可能

所以這個時(shí)候得同時(shí)持有 A、B 節(jié)點(diǎn)的 write lacth

接著遍歷到 D 節(jié)點(diǎn)，拿到 D 節(jié)點(diǎn)的 write latch，此時(shí)不管 D 節(jié)點(diǎn)下面的子節(jié)點(diǎn)發(fā)生了什么操作，刪除了 key 38 并不會導(dǎo)致 C 節(jié)點(diǎn)和 D 節(jié)點(diǎn)的 merge。對于此時(shí)的 A B 節(jié)點(diǎn)來說修改可能不會存在

所以此時(shí)可以將 A B 節(jié)點(diǎn)的 write latch 釋放掉

繼續(xù)向下遍歷到 H 節(jié)點(diǎn)，此時(shí)可以釋放掉 D 節(jié)點(diǎn)的 write latch，因?yàn)?H 節(jié)點(diǎn)是全滿(100% full)狀態(tài)

執(zhí)行刪除操作，釋放掉 latch，即完成整個過程

?

### insert 操作

比如要插入 45 這個 key ，每次向下遍歷時(shí)要加一個 write latch，直到遍歷到 B 這個節(jié)點(diǎn)

如果 D 節(jié)點(diǎn)要執(zhí)行 split 操作，對于 B 節(jié)點(diǎn)來說它是有空間容納的下一個 key 的，那么在遞歸 split 時(shí) B 節(jié)點(diǎn)就不會發(fā)生 split，B 節(jié)點(diǎn)不會發(fā)生那么 A 節(jié)點(diǎn)也不會發(fā)生，所以此時(shí)釋放掉 A 節(jié)點(diǎn)的 latch 是安全的

繼續(xù)向下遍歷，直到 D 節(jié)點(diǎn)

因?yàn)榇藭r(shí) D 節(jié)點(diǎn)是一個全滿狀態(tài)，此時(shí)如果在 D 節(jié)點(diǎn)下面做插入會不會導(dǎo)致 D 節(jié)點(diǎn)被 split ? 不清楚。D 節(jié)點(diǎn)如果被 split ，那么 B 節(jié)點(diǎn)也可能會被 split，所以此時(shí)需要持有 B 節(jié)點(diǎn)的 latch

繼續(xù)向下遍歷，直到 I 節(jié)點(diǎn)

因?yàn)?I 節(jié)點(diǎn)有足夠空間支持插入一個 key，所以此時(shí)不需要對 I 節(jié)點(diǎn)進(jìn)行 split 操作。在插入之前，可以釋放掉 B D 節(jié)點(diǎn)處的 write latch，最后執(zhí)行插入操作

### 小結(jié)

基本上就是用一個棧去存儲這些 latch，當(dāng)找到一個安全的節(jié)點(diǎn)時(shí)，用 stack 將它們一一 pop 出來

> 注意這里，不用在意 stack pop latch 的順序。雖然將順序?qū)τ谧罱K的結(jié)果來說都一樣，但從性能的角度，還是盡可能快的釋放更上層節(jié)點(diǎn)的 latch 會比較好，因?yàn)楦蠈拥墓?jié)點(diǎn)的 latch 不再涉及更多的葉子節(jié)點(diǎn)(leaf node)，盡快釋放更上層節(jié)點(diǎn)的 latch 主要是為了讓下一個線程能更快的拿到這個 latch，從而減少阻塞訪問的時(shí)間

### 性能問題

在 B+ Tree 中做插入和刪除時(shí)，都需要做的第一件事就是使用獨(dú)占模式的的 latch 或者是寫模式的 latch 對根節(jié)點(diǎn)加鎖

由于寫模式下的 latch 具備獨(dú)占性，為了訪問這個 B+ Tree，每個線程都需要去獲取這個 latch，但一次只能有一個線程能持有這個 latch，所以這對并行和并發(fā)的性能都會有影響

那么怎么做優(yōu)化呢？那自然是在訪問這個 B+ Tree 時(shí)，讓這些線程都盡量能夠持有這些個 latch

### 更好的 Latching 算法

> 1977 年的算法，由 2 個德國佬所寫

首先，假設(shè)訪問到的葉子節(jié)點(diǎn)是安全的，并且假設(shè)大部分的線程不需要對葉子節(jié)點(diǎn)進(jìn)行 split/merge 操作

那么就有

1. 從根節(jié)點(diǎn)開始，在向下訪問 B+ Tree 時(shí)，獲取 read latch 而不是 write latch

2. 處理葉子節(jié)點(diǎn)時(shí)，獲取 write latch

3. 如果此時(shí)該節(jié)點(diǎn)不需要 split/merge 操作，那么繼續(xù)向下訪問時(shí)只需要拿到 read latch 就行，此時(shí)也可以對該節(jié)點(diǎn)執(zhí)行任意的修改

4. 如果此時(shí)該節(jié)點(diǎn)需要 split/merge 操作，并且此時(shí)如果操作犯錯，那么操作在這里就直接 abort ，然后在根節(jié)點(diǎn)處重啟該操作，在向下訪問時(shí)獲取 write latch

這就是樂觀 latch 和 悲觀 latch 算法

樂觀的意思就是假設(shè)不會去做任何的 split/merge 操作，在這種情況下盡量用 read latch，那么性能就會很高

悲觀的意思就是線程在訪問時(shí)拿的全都是 write latch

在實(shí)際工作中，這種樂觀的假設(shè)是非常安全的，因?yàn)楹艽蟾怕噬希跀?shù)據(jù)庫系統(tǒng)中所作的大部分操作都是樂觀鎖這樣的場景

### delete 操作

比如說要刪除 38 這個 key

在根節(jié)點(diǎn)處不會去獲取一個 write latch，在向下遍歷時(shí)，拿到的始終是 read latch

直到遍歷到 D 節(jié)點(diǎn)，此時(shí)獲取到 H 節(jié)點(diǎn)的處的 write latch

刪除掉 H 節(jié)點(diǎn)處的 38 這個 key，此時(shí)線程樂觀的認(rèn)為在 H 節(jié)點(diǎn)不需要做 split/merge 操作，那么只需要在執(zhí)行刪除這個操作時(shí)，再去獲取 H 節(jié)點(diǎn)的 write latch

最后執(zhí)行刪除，釋放 latch

### insert 操作

比如說要插入 25 這個 key

在根節(jié)點(diǎn)處不會去獲取一個 write latch，在向下遍歷時(shí)，拿到的始終是 read latch

直到遍歷到 C 節(jié)點(diǎn)，此時(shí)獲取到 F 節(jié)點(diǎn)處的 write latch

在 F 節(jié)點(diǎn)插入 25，就必須做一次 split 操作

所以就需要 abort 這次插入操作，回到根節(jié)點(diǎn)開始重新來一遍，當(dāng)向下遍歷時(shí)，拿的都是 write latch

### 小結(jié)

樂觀鎖的機(jī)制并不完美，沒法保證所要做的遍歷以及其他操作總是最小的。因?yàn)樵诖罅坎迦氲膱鼍爸?，split/merge 的操作也是大量的，那么就需要不停的回到根節(jié)點(diǎn)處，向下遍歷時(shí)一直拿 write latch

所以如果線程間的爭搶率很高的話，樂觀鎖的假設(shè)就是錯誤的，那這樣還不如一開始就用悲觀鎖呢

但還是那句話，看場景用哪種鎖機(jī)制

### 如何遍歷葉子節(jié)點(diǎn)

一個線程從 B+ Tree 中從上往下遍歷，另一個線程在葉子節(jié)點(diǎn)中從左往右進(jìn)行遍歷，這 2 個線程還是有可能產(chǎn)生死鎖的

那么如何解決呢?

### 單個線程遍歷讀葉子節(jié)點(diǎn)

比如通過線程 T1 來查找所有小于 4 的 key

首先在根節(jié)點(diǎn)處獲取一個 read latch

然后向下遍歷到 C 節(jié)點(diǎn)，獲取到該節(jié)點(diǎn)處的 read latch，釋放掉 A 節(jié)點(diǎn)處的 latch

然后從 C 節(jié)點(diǎn)開始，從右向左遍歷這個葉子節(jié)點(diǎn)

為了能遍歷到 B 節(jié)點(diǎn)，必須要拿到 B 節(jié)點(diǎn)的 read latch，然后釋放掉 C 節(jié)點(diǎn)的 latch

### 多個線程遍歷讀葉子節(jié)點(diǎn)

此時(shí)有另一個線程 T2，它要查找所有大于 1 的 key

那么它們同時(shí)遍歷，T1 到 C 節(jié)點(diǎn)，T2 到 B 節(jié)點(diǎn)

但到 T1 想要獲取 B 節(jié)點(diǎn)上的 read latch，而 T2 想要獲取 C 節(jié)點(diǎn)上的 read latch 時(shí)

它們都交替獲得了對方的 read latch

最后完成遍歷

最后再釋放掉自己持有的 latch

這里不會產(chǎn)生死鎖，因?yàn)?read latch 是共享的

### 多個線程遍歷寫葉子節(jié)點(diǎn)

如果線程 T1 想要刪除 4 這個 key

在根節(jié)點(diǎn)處，T1 和 T2 拿到的始終是 read latch，只有在葉子節(jié)點(diǎn)時(shí)才會拿 write latch

繼續(xù)遍歷

T2 在葉子節(jié)點(diǎn)上繼續(xù)遍歷，它想要拿到 C 節(jié)點(diǎn)上的 read latch，但這是不可能拿到的，因?yàn)?t1 已經(jīng)拿到了 C 節(jié)點(diǎn)處的 write latch

此時(shí) T2 并不了解 T1 啥情況，為什么，因?yàn)樵跀?shù)據(jù)庫系統(tǒng)的實(shí)現(xiàn)中，并不會使用一個全局的角度來告訴你另一個線程在做什么，線程間無權(quán)訪問各自的信息

這里是可能會產(chǎn)生死鎖的，因?yàn)?T1 也可以去嘗試獲取 B 節(jié)點(diǎn)處的 write latch，但由于 T2 不知道 T1 在干嘛，所以 T1 不可能釋放掉 B 節(jié)點(diǎn)的 read latch，那么 T1 也就永遠(yuǎn)拿不到 B 節(jié)點(diǎn)的 write latch

那么怎么解決這個問題呢? 還是直接 abort 掉線程 T2 吧

然后讓 T2 重新執(zhí)行查詢操作

### 小結(jié)

雖然通過 abort + 不停的重試能解決死鎖問題，但這同樣會導(dǎo)致 starvation 出現(xiàn)，或者浪費(fèi)大量的 CPU 時(shí)鐘周期來遍歷葉子節(jié)點(diǎn)的數(shù)據(jù)

## 如何處理葉子節(jié)點(diǎn)數(shù)據(jù) overflow

通常節(jié)點(diǎn)在發(fā)生 overflow 時(shí)會通過遞歸 split 的方式，將這個 overflow 的 key 插入到一個經(jīng)過 B+ Tree 平衡操作之后的一個新的節(jié)點(diǎn)中去，但提出 B-link Tree 的人提出了一種優(yōu)化方式，即

當(dāng)某個子節(jié)點(diǎn)發(fā)生 overflow 情況時(shí)，延遲對父節(jié)點(diǎn)的更新操作，這樣就不用再從根節(jié)點(diǎn)開始，并且拿著 write latch 一直往下遍歷了，只需要更新這個 Tree 中的全局信息表中的一點(diǎn)點(diǎn)內(nèi)容就可以了

當(dāng)在某個時(shí)刻，有另一個線程在遍歷這個 Tree 時(shí)，再去更新這個父節(jié)點(diǎn)即可

### insert 操作

比如線程 T1 要插入 25 這個 key，用樂觀鎖機(jī)制遍歷

當(dāng)遍歷到 F 節(jié)點(diǎn)時(shí)，如果做插入操作，F(xiàn) 節(jié)點(diǎn) overflow，需要 split

但是此時(shí)不需要再從根節(jié)點(diǎn)開始用獲取 write latch 的方式進(jìn)行遍歷，而是進(jìn)行插入操作

從 F 節(jié)點(diǎn)處弄一個 overflow 的節(jié)點(diǎn)出來放入 31，然后將 25 插入到 F 節(jié)點(diǎn)中

這樣就不用為了更新 C 節(jié)點(diǎn)而再從根節(jié)點(diǎn)開始遍歷了，這里就使用該 Tree 的一個小的全局表來處理這個 overflow 的信息

如果此時(shí)有個線程 T2 要查找 31 這個 key，它會按照遍歷規(guī)則查到 F 指向的這個 overflow 節(jié)點(diǎn)

如果此時(shí)有個 T3 線程要插入 33，那么它會遍歷到 C 節(jié)點(diǎn)處，拿到一個 write latch

然后完成 C 節(jié)點(diǎn)處內(nèi)容的修改

最終拿到 overflow 節(jié)點(diǎn)的 write latch，并插入 33

這樣就不需要重新遍歷來進(jìn)行操作了

## 總結(jié)

要確保所有線程始終沿著一個方向遍歷數(shù)據(jù)結(jié)構(gòu)，這樣就可以避免死鎖