> 草，這期沒(méi)有 Andy 了

## 上期回顧

## Observation

在一個(gè)真實(shí)的系統(tǒng)中，需要一種方式在運(yùn)行時(shí)能做到，保證所有的 Schedule 的執(zhí)行都是正確的，并且不需要提前知道整個(gè) Schedule 的情況

當(dāng)事務(wù)提交給數(shù)據(jù)庫(kù)執(zhí)行時(shí)，數(shù)據(jù)庫(kù)并不會(huì)得到該事務(wù)的所有的 Schedule

沒(méi)法去查看數(shù)據(jù)庫(kù) client 要做什么，以及預(yù)測(cè)它們的操作是否是 Serializable 的，所以就需要一種協(xié)議，一種能并行執(zhí)行這些事務(wù)的系統(tǒng)，同時(shí)還需要保證隔離性

所以就需要鎖，之前提到過(guò)悲觀鎖和樂(lè)觀鎖，今天要研究的就是兩階段鎖

## 鎖的執(zhí)行

在能執(zhí)行 R(A) 之前，去 Lock 管理器那里拿到 A 的鎖，該 Lock 管理器會(huì)去判斷你是否有權(quán)去訪問(wèn)這個(gè) tuple，它維護(hù)了一些關(guān)于哪個(gè)持有鎖的元數(shù)據(jù)，并在系統(tǒng)中強(qiáng)制使用鎖協(xié)議

接著，T2 開(kāi)始執(zhí)行

假設(shè)目前處于一個(gè)單線程的環(huán)境，同一時(shí)間我們只會(huì)執(zhí)行其中一個(gè)事務(wù)

T2 目前要獲取到這個(gè)鎖，因?yàn)樗罱K要在下面執(zhí)行 R(A) 和 W(A)，但它被 Lock 管理器拒絕，因?yàn)?T1 已經(jīng)拿著這把鎖了

那么 T2 唯一能做的事情就是等待

然后 T1 執(zhí)行 W(A) 和 R(A)，最后把鎖釋放，那么 Lock 管理器就會(huì)告訴 T2 可以拿鎖了，最后做完 T2 要做的事情就把鎖釋放掉

## 課程目標(biāo)

- 鎖類型

- 兩階段鎖

- 死鎖原因

- 層級(jí)鎖(通過(guò)這個(gè)，可以減少在系統(tǒng)中使用鎖的數(shù)量，更高效的使用鎖)

- 隔離級(jí)別不在本節(jié)課討論范圍之內(nèi)

## Locks vs. Lathes

latch 是用來(lái)保護(hù)線程所訪問(wèn)的當(dāng)前數(shù)據(jù)結(jié)構(gòu)所在的內(nèi)存不被瞎亂寫

lock 是用來(lái)保護(hù)數(shù)據(jù)庫(kù)中的邏輯結(jié)構(gòu)，比如數(shù)據(jù)庫(kù)表中那些 tuple，防止事務(wù)彼此間發(fā)生沖突

通過(guò)使用 latch，能避免編程時(shí)遇到的死鎖問(wèn)題，比如 B+ Tree 的訪問(wèn)

## 基本鎖類型

- 共享鎖(讀操作)

- 獨(dú)占鎖(寫操作)

有點(diǎn)類似之前提到過(guò)的 Read Latch 和 Write Latch

在某個(gè)對(duì)象已經(jīng)有了一個(gè) Shared Lock 的情況下，不能再去發(fā)放該對(duì)象的 Exclusive Lock

## 鎖的執(zhí)行

Lock 管理器會(huì)基于它內(nèi)部的元數(shù)據(jù)來(lái)決定是否有權(quán)去擁有這個(gè) Lock

Lock 管理器不一定會(huì)對(duì)持有該 Lock 的時(shí)間長(zhǎng)度有所限制，所以這個(gè)應(yīng)當(dāng)取決于事務(wù)

當(dāng)事務(wù)完成時(shí)，取決于該事務(wù)是否要去釋放這個(gè) Lock

例子

事務(wù)負(fù)責(zé)去獲取和釋放鎖，Lock 管理器負(fù)責(zé)分發(fā)這些 Lock

但是這里會(huì)出現(xiàn)不可重復(fù)讀的情況

## 并發(fā)控制協(xié)議

這里要用的就是兩階段鎖，它允許數(shù)據(jù)庫(kù)系統(tǒng)始終以保證 Confilict Serializable Schedule 的情況下來(lái)分發(fā) Lock，因?yàn)楝F(xiàn)在沒(méi)必要去限制系統(tǒng)中的并行性，可以嘗試在同一時(shí)間執(zhí)行多個(gè)事務(wù)

在不生成那些 Unserializable Schedule 或者違反隔離性要求的情況下，希望能獲取到事務(wù)方面的高吞吐量

### 兩階段鎖

1. Growing 階段

? ? 允許該事務(wù)去獲取它需要的那個(gè) Lock，而這個(gè) Lock 是 Lock 管理器給的

? ? 事務(wù)執(zhí)行完操作后，它會(huì)去釋放這個(gè) Lock，告訴 Lock 管理器，用完這個(gè) Lock 了

2. Shrinking 階段

? ? 上述過(guò)程之后，該事務(wù)就會(huì)處于 Shrinking 階段，然后該事務(wù)就不再允許它獲取更多的 Lock 了

用圖的方式表示就是如下

一個(gè)違反兩階段鎖的例子就是如下

因?yàn)檫@個(gè)事務(wù)釋放了一部分 Lock，然后它又去獲取了一些 Lock

例子

如果遵循兩階段鎖這個(gè)協(xié)議，就會(huì)得到 Conflict Serializable 的 Schedule，保證依賴圖是無(wú)環(huán)的

但是單獨(dú)使用兩階段鎖并不保證不會(huì)遇上 臟讀 的情況，可能會(huì)遇上 Cascading Abort

### Cascading Aborts

T2 讀取了一個(gè)來(lái)自 T1 的值，因?yàn)?T1 這個(gè)事務(wù)被中止了，它并沒(méi)有被提交，所以實(shí)際上它并不在系統(tǒng)中

因?yàn)?T1 被中止了，現(xiàn)在也必須將 T2 中止，因?yàn)?T2 讀取的那個(gè)值并不再生效

因?yàn)橐粋€(gè)事務(wù)的中止會(huì)導(dǎo)致另一個(gè)事務(wù)的中止，所以需要在數(shù)據(jù)庫(kù)寫的回滾邏輯會(huì)越來(lái)越復(fù)雜

而由于 T2 已經(jīng)執(zhí)行了一堆復(fù)雜的邏輯，并對(duì)系統(tǒng)化執(zhí)行了一大堆寫操作，而后要中止這個(gè) T2 事務(wù)，所以也就浪費(fèi)了大量的時(shí)間

### 兩階段鎖 Observations

有些 Schedule 是 Serializable 的，但在兩階段鎖中并不允許

用到了鎖，就會(huì)略微限制系統(tǒng)的并發(fā)性

當(dāng)遇上臟讀的情況時(shí)，可能會(huì)導(dǎo)致 Cascading Aborts

怎么解決這個(gè)問(wèn)題呢?

使用 Strong Strict Two Phase Locking (強(qiáng)嚴(yán)格兩階段鎖)

死鎖的情況也會(huì)遇到，所以需要一種檢測(cè)機(jī)制來(lái)解決這個(gè)問(wèn)題

### 強(qiáng)嚴(yán)格兩階段鎖

當(dāng)事務(wù)執(zhí)行完，要進(jìn)行提交時(shí)，才去釋放鎖

Growing 階段，會(huì)根據(jù)需要不斷地獲取鎖，直到提交時(shí)才去釋放這些鎖，這可以防止遇上跨事務(wù)時(shí)所遇到的臟讀問(wèn)題以及 Cascading Aborts 問(wèn)題

注意上圖中，所有的鎖都會(huì)在事務(wù)結(jié)束時(shí)釋放掉，所以嚴(yán)格意義上來(lái)講這里并沒(méi)有 Shrinking Phase 階段

strict 這個(gè)單詞對(duì)于并發(fā)控制來(lái)說(shuō)擁有特定的意義，直到提交事務(wù)時(shí)，該事務(wù)所做的修改才會(huì)被系統(tǒng)中其他執(zhí)行的事務(wù)看到

這能簡(jiǎn)化中止邏輯，因?yàn)槟切┲兄沟氖聞?wù)必須要將它們所操作的值變回原樣，這樣的話，就無(wú)須擔(dān)心系統(tǒng)中這些事務(wù)會(huì)去讀取那些未提交的值了。否則，它們就得保存它們自己的元數(shù)據(jù)，或者通過(guò)某種方法回滾它們之前所做的修改

例子

不使用兩階段鎖的例子(會(huì)得出一個(gè)錯(cuò)誤的輸出結(jié)果)

在一開(kāi)始時(shí)，A B 兩個(gè)賬戶中分別都有 1000 $

T1 已經(jīng)拿到了 A 的 Exclusive Lock，并執(zhí)行 R(A)，因?yàn)榻酉聛?lái)需要執(zhí)行 A = A - 100

T2 想要獲取 A 的 Shared Lock，因?yàn)?T2 后面要執(zhí)行 A + B，所以它沒(méi)法此時(shí)獲取到這個(gè) Lock，它只能等待

T1 釋放 Lock 之后，T2 拿到了 A 對(duì)應(yīng)的 Shared Lock，并執(zhí)行 R(A)，然后 T2 釋放 Lock

> 注意這里并沒(méi)有使用到兩階段鎖

T2 也會(huì)獲取 B 對(duì)應(yīng)的 Shared Lock，因?yàn)橐獔?zhí)行 R(B)，所以 T1 需要等待

最終，T2 釋放了這個(gè) Lock，T1 拿到了 B 對(duì)應(yīng)的 Exclusive Lock，執(zhí)行了 B = B + 100，釋放 Lock 并提交。但是此時(shí) A + B 計(jì)算為 1900，因?yàn)樗x取到了一個(gè)不一致的狀態(tài)。它讀取到了 T1 已經(jīng)完成的部分工作結(jié)果，這意味著 T1 已經(jīng)將該信息泄漏到系統(tǒng)的其他地方

使用兩階段鎖的例子

在 T1 進(jìn)入 Shrinking 階段之前，它去獲取了 B 對(duì)應(yīng)的 Exclusive Lock，T2 原地等待獲取它需要的那些 Lock。

T1 對(duì) B 的操作執(zhí)行完畢，才會(huì)釋放 A 對(duì)應(yīng)的 Lock

那么這個(gè)就會(huì)出一個(gè)正確的輸出結(jié)果

另一個(gè)使用兩階段鎖的例子

T2 需要等待一整個(gè) T1 執(zhí)行的時(shí)間，嚴(yán)格兩階段鎖有效地控制了事務(wù)的有序執(zhí)行

也就是說(shuō)，事務(wù)會(huì)去獲取你所需要用到的所有鎖并一直持有，直到事務(wù)要到提交的時(shí)候才做釋放

用上圖來(lái)說(shuō)，就是保證 T2 中存在的任何會(huì)引起沖突的操作都會(huì)被強(qiáng)制按照某種順序執(zhí)行

## Schedules 的包含關(guān)系

## 死鎖問(wèn)題

死鎖其實(shí)就是事務(wù)間彼此依賴成環(huán)，它們都在等待對(duì)面釋放它們所需要的鎖

如圖所示，現(xiàn)在這 2 個(gè)事務(wù)都在等待獲取彼此手上的 Lock

那么就需要某種方式來(lái)打破這種僵局

1. 檢測(cè)

2. 預(yù)防

### 檢測(cè)

系統(tǒng)會(huì)使用一個(gè)后臺(tái)線程來(lái)進(jìn)行死鎖檢測(cè)，簡(jiǎn)單來(lái)說(shuō)，就是去查看 Lock 管理器中的元數(shù)據(jù)，構(gòu)建一個(gè) waits-for 圖，圖中每一個(gè)節(jié)點(diǎn)就是一個(gè)事務(wù)，每一條線會(huì)指向另一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)持有著另一端那個(gè)節(jié)點(diǎn)想要獲取的鎖

例子

T3 想獲取 A 的 Exclusive Lock，但是 T1 已經(jīng)拿到了 A 對(duì)應(yīng)的 Shared Lock，于是死鎖了

### 處理死鎖

簡(jiǎn)單來(lái)說(shuō)，就是選擇一個(gè) Victim(犧牲者)，干掉它

選擇一個(gè)事務(wù)，然后將它回滾，回滾多少內(nèi)容取決于具體實(shí)現(xiàn)

可以只回滾部分查詢來(lái)釋放鎖，以此移除掉死鎖

但是在系統(tǒng)中需要權(quán)衡構(gòu)建這些 waits-for 圖的頻率，因?yàn)槭情_(kāi)的后臺(tái)程序去做的檢測(cè)，如果頻率過(guò)高，很可能會(huì)浪費(fèi) CPU 資源來(lái)構(gòu)建這些圖，并且也可能檢測(cè)不出什么死鎖

所以需要考慮的是，在不檢測(cè)死鎖的情況下，陷入死鎖狀態(tài)的可接受時(shí)長(zhǎng)是多少

另一種處理方式就是 Victim Selection

干掉某個(gè) Victim 時(shí)，可以去看下時(shí)間戳最小的那個(gè)事務(wù)，因?yàn)榈阶詈髸?huì)有一個(gè)環(huán)，選一個(gè)干掉就好了

也可以去查下這個(gè) Victim 已經(jīng)完成的工作量，或者它已經(jīng)執(zhí)行的查詢數(shù)量

同樣也可以查下這個(gè) Victim 它拿了多少個(gè) Lock

然后就是如果遇上 Cascading Abort 問(wèn)題，需要看下要回滾的事務(wù)數(shù)量

還有一種處理方式就是 Rollback Length

可以最小程度去中止某個(gè)事務(wù)，即僅回滾該事務(wù)中的個(gè)別查詢所做的修改

或者緩慢地釋放掉部分鎖

在 MySQL 中，可以通過(guò)

```

SET GLOBAL innodb_lock_wait_timeout = 10;

```

來(lái)設(shè)置檢測(cè)死鎖的頻率

當(dāng) MySQL 嘗試去獲取鎖時(shí)，如果發(fā)現(xiàn)其中存在著死鎖的情況，它會(huì)嘗試重啟事務(wù)

在 PostgreSQL 中，可以通過(guò)

```

BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;

```

設(shè)置該事務(wù)的隔離級(jí)別為 Serializable

在數(shù)據(jù)庫(kù)中有一些可調(diào)參數(shù)，可以通過(guò)調(diào)整它們來(lái)改變數(shù)據(jù)庫(kù)系統(tǒng)尋找死鎖的主動(dòng)性

### 預(yù)防

如果能夠阻止死鎖發(fā)生，那么也就不需要去構(gòu)建 waits-for 圖了，也就意味著不需要這個(gè)后臺(tái)任務(wù)了，也就不需要?dú)⑺肋M(jìn)程或者事務(wù)了

一種簡(jiǎn)單的做法是根據(jù)時(shí)間戳來(lái)分配優(yōu)先級(jí)，比如較老的事務(wù)有更高的優(yōu)先級(jí)

另一種做法是較年輕的事務(wù)有更高的優(yōu)先級(jí)

例子

T1 的優(yōu)先級(jí)比 T2 高，但 T2 先拿到鎖，所以 T1 是較老的那個(gè)事務(wù)

- Wait-Die: T1 會(huì)等待獲取這個(gè)鎖

- Wound-Wait: T1 會(huì)干掉 T2，T2 需要進(jìn)行重啟

T1 還是比 T2 先執(zhí)行，T1 擁有的時(shí)間戳較老，T1 的優(yōu)先級(jí)更高， T1 會(huì)先拿到這個(gè)鎖

- Wait-Die: T2 會(huì)被干掉

- Wound-Wait: T2 會(huì)一直等待

如果能以某種順序去獲取 Lock，就會(huì)讓死鎖的解決變得更高效，甚至可以完全避開(kāi)死鎖問(wèn)題

為了避免死鎖問(wèn)題，簡(jiǎn)單來(lái)說(shuō)就發(fā)放一種類型的 Lock

當(dāng)一個(gè)事務(wù)重啟時(shí)，它的優(yōu)先級(jí)(時(shí)間戳)是什么

是和原來(lái)一樣，為啥

為了不能讓事務(wù)陷入 Starvation 的狀態(tài)，所以當(dāng)事務(wù)重啟時(shí)，要確保它依然使用的是和之前相同的時(shí)間戳

## Observation

因?yàn)槊看问聞?wù)都要做這種鎖管理的方式，所以不可能將所有的這些就交給 Lock 管理器，因?yàn)檫@樣做在遇到要管理更新很多個(gè) tuple 的場(chǎng)景時(shí)，開(kāi)銷就很大了

那么怎么做合適呢?

就是往系統(tǒng)里面引入某種 hierarchy(分層)，或者是使用不同粒度的 Lock

## Lock 保證

那么 Lock 的粒度怎么分呢?

可以在 tuple、page、table 上使用 Lock，如果要對(duì)一個(gè) table 上 10 億條 tuple 進(jìn)行更新操作，那么有沒(méi)有可能，只需要對(duì)整個(gè) table 用一個(gè) Exclusive Lock 就行了

本質(zhì)上就是通過(guò)這種分層的模型來(lái)減少，在 Lock 管理器中的需要操作的 Lock 的總數(shù)量的訪問(wèn)

### Lock 分層

如圖所示，可以系統(tǒng)的不同層面使用這些 Lock

數(shù)據(jù)庫(kù)系統(tǒng)以這種層次結(jié)構(gòu)來(lái)表示往它里面插入的那些表和 tuple

例子

上圖中，因?yàn)殂y行賬戶余額正在進(jìn)行修改，所以需要 Exclusive Lock 和 Shared Lock

Intention Lock 是在數(shù)據(jù)庫(kù)分層這個(gè)樹(shù)上的較高層處使用的，以此來(lái)提示其他事務(wù)在該系統(tǒng)的分層的較低層面做什么事情，它會(huì)試著增加系統(tǒng)的并行性

### Intention Locks

對(duì)于其他事務(wù)來(lái)說(shuō)，Intention Lock 是一種提示

如果在這個(gè)樹(shù)上有一個(gè) Intention Shared Lock，那么子樹(shù)的根節(jié)點(diǎn)就是在這個(gè)節(jié)點(diǎn)上，而該節(jié)點(diǎn)的下方某處會(huì)有一個(gè)顯式的 Shared Lock，對(duì)于 Intention Exclusive Lock 也是如此，在子樹(shù)根節(jié)點(diǎn)下方某處，會(huì)有一個(gè)顯式的 Exclusive Lock

另外一種 Lock 類型就是 Shared + Intention-Exclusive 模型

在這個(gè)節(jié)點(diǎn)上有一個(gè)顯式的 Shared Lock，在子樹(shù)下方的所有東西上，都會(huì)有一個(gè)與之對(duì)應(yīng)的 Shared Lock。而在子樹(shù)下方的某處地方，也有一個(gè)顯式的 Exclusive Lock

基本上就是在某個(gè) tuple 上使用 Exclusive Lock，然后在整個(gè) table 上使用一個(gè) Shared Lock，這樣就可以做到，可以讀取表中的所有的值，但只會(huì)去更新其中某個(gè)值

### 兼容性

### Lock 協(xié)議

為了獲取一個(gè) Shared Lock，至少要在父節(jié)點(diǎn)處加一個(gè) Intention-Shared Lock

對(duì)于 Exclusive Lock/ Intention-Exclusive / Shared + Intention-Exclusive Lock 也是類似的，至少要在父節(jié)點(diǎn)處加一個(gè) Intention-Exclusive Lock

例子(這是一個(gè)兩層結(jié)構(gòu)的系統(tǒng))

T1 開(kāi)始執(zhí)行，在 Tuple1 上加一個(gè) Shared Lock，以此來(lái)讀取 Tuple1 的內(nèi)容，但是在這之前會(huì)先在父節(jié)點(diǎn)上加一個(gè) Intention-Shared Lock

這里會(huì)作為一個(gè)提示，在該節(jié)點(diǎn)下面，會(huì)有一個(gè)顯式的 Shared Lock

接著 T2 開(kāi)始執(zhí)行，它想要更新 Tuple n 的內(nèi)容，并且要在這個(gè)上面加上一個(gè)顯式的 Exclusive Lock

然后就是在父節(jié)點(diǎn)上加上 Intention Exclusive Lock，然后再在 Tuple n 上加上 Exclusive Lock

另一個(gè)例子

T1 要去讀取所有的 tuple，并對(duì)其中一個(gè) tuple 進(jìn)行更新，所以它會(huì)去獲取一個(gè) Shared + Intention-Exclusive Lock，意味著它給整個(gè) table 加了一個(gè) Shared Lock，那么就可以讀取該 table 中所有 tuple 的所有屬性，而 Shared + Intention-Exclusive Lock 的意思是，它至少會(huì)去更新下方其中某一個(gè) tuple(在這個(gè)例子中是 tuple n)

T2 想要讀取 table 中某個(gè) tuple

那么 tuple1 就需要用到 Shared Lock，那么在 table 這一層就需要用到 Intention-Shared Lock

T3 想要對(duì) table 中所有數(shù)據(jù)進(jìn)行讀取

它想對(duì)這個(gè) table 使用 Shared Lock，但是不能這么做，因?yàn)樗鼰o(wú)法和 Shared + Intention-Exclusive Lock 相兼容，這個(gè) table 有執(zhí)行寫操作的事務(wù)，所以 T3 只能等待

### 多個(gè) Lock 的保證

### Lock 升級(jí)

這是為了減少 Lock 管理器的工作量以及不違反兩階段鎖

可以在不釋放鎖的情況下，對(duì)鎖進(jìn)行升級(jí)(Shared Lock -> Exclusive Lock)

### 真實(shí)系統(tǒng)中的 Lock

如果要對(duì)一個(gè) table 進(jìn)行一系列操作，在執(zhí)行的過(guò)程中，要一直拿著鎖，就不能顯式地鎖住這個(gè) table

### SELECT...FOR UPDATE

這個(gè)概念是指，如果讀取了某個(gè) tuple，然后要對(duì)這個(gè) tuple 進(jìn)行更新，可以給數(shù)據(jù)庫(kù)系統(tǒng)一個(gè) hint，這個(gè)表示數(shù)據(jù)庫(kù)系統(tǒng)在執(zhí)行一個(gè)讀操作，然后會(huì)去請(qǐng)求一個(gè) Shared Lock

然后會(huì)去執(zhí)行一次寫操作，這個(gè)時(shí)候就可以去請(qǐng)求一個(gè) Exclusive Lock

具體方式就是可以在 SELECT 語(yǔ)句后面加一個(gè) FOR UPDATE

## 結(jié)論