> 這期依然沒(méi)有 Andy，我好懷念他

## 前言

### 多版本并發(fā)控制

多版本并發(fā)控制，是構(gòu)建系統(tǒng)的一種方式，即通過(guò)維護(hù)多版本數(shù)據(jù)來(lái)做到并發(fā)執(zhí)行事務(wù)

多版本并發(fā)控制的思路和樂(lè)觀并發(fā)控制的思路很類似，它維護(hù)的是這些對(duì)象的不同物理版本，而不是為每個(gè)事務(wù)創(chuàng)建一個(gè)私有空間

對(duì)于全局?jǐn)?shù)據(jù)庫(kù)里面的部分?jǐn)?shù)據(jù)，會(huì)有若干個(gè)版本，那么需要明確的是，是否需要將某個(gè)版本的數(shù)據(jù)對(duì)某一個(gè)特定的事務(wù)可見?

### MVCC 歷史?

在 MVCC 中，writer 不會(huì)阻塞 reader，reader 不會(huì)阻塞 writer

當(dāng)有 2 個(gè)事務(wù)同時(shí)要對(duì)同一個(gè)對(duì)象嘗試做寫入操作時(shí)，就得退一步，使用某種并發(fā)控制協(xié)議，比如 兩階段鎖或者使用時(shí)間戳

對(duì)于只讀事務(wù)來(lái)說(shuō)，MVCC 很有用，因?yàn)?SQL dialect 允許聲明該事務(wù)是否是只讀事務(wù)，那么數(shù)據(jù)庫(kù)系統(tǒng)就不會(huì)去獲取任何 Lock 或者維護(hù) read set/write set。而因?yàn)樗幸粋€(gè)一致的 snapshot，就只會(huì)看到該事務(wù)開始時(shí)就存在的那些修改，這就使得只讀事務(wù)變得非常高效，而且執(zhí)行速度也很快

本質(zhì)上來(lái)講，它就是在維護(hù)一個(gè)版本信息表之類的東西

MVCC 也支持 Time-Travel Query，通過(guò)這種查詢，可以知道數(shù)據(jù)庫(kù)之前的狀態(tài)是什么

但是支持這種 feature，就永遠(yuǎn)不能將老版本的數(shù)據(jù)扔掉，永遠(yuǎn)不做垃圾回收，而隨著時(shí)間的流逝，事務(wù)提交的數(shù)量會(huì)越來(lái)越多，磁盤空間很快就會(huì)滿了

### MVCC 例子

MVCC 不依賴并發(fā)控制協(xié)議

在上圖中的 Version 字段中，有一個(gè)值是 A0，說(shuō)明對(duì)象 A 的版本號(hào)是 0

Begin 和 End 字段里面放的都是時(shí)間戳，它們的值始終增加

當(dāng)一個(gè)新事務(wù)到達(dá)時(shí)，要去查看 T1 和 T2，當(dāng) T1 到達(dá)時(shí)，分配時(shí)間戳 1 給它

T1 執(zhí)行 R(A)，這個(gè)時(shí)候要去查看表，通過(guò)弄清楚當(dāng)前時(shí)間戳處于開始時(shí)間和結(jié)束時(shí)間中的哪個(gè)位置，來(lái)決定哪個(gè) tuple 對(duì)它是可見的

此時(shí) T1 的時(shí)間戳是 1，開始時(shí)間是 0，時(shí)間戳 1 是在 0 和無(wú)窮大之間，那么將 A 的版本號(hào)設(shè)置為 A0

T2 執(zhí)行 W(A)，這里給 T2 分配的時(shí)間戳是 2，但是此時(shí)要?jiǎng)?chuàng)建 A 的一個(gè)全新版本，即 A1，這里要做的只是去增加版本號(hào)計(jì)數(shù)器

然后在 T2 中，要將 A0 的 end timestamp 設(shè)置為 2

整個(gè)過(guò)程中需要用到的就是事務(wù)狀態(tài)表

但是如果這些事務(wù)被中止，那么就需要回過(guò)頭去，將這些時(shí)間戳恢復(fù)原樣

此時(shí) T1 再執(zhí)行 R(A)，那么此時(shí) T1 要讀取到的 A 版本是什么呢

是 A0，因?yàn)樗臅r(shí)間戳依然是在 begin timestamp 和 end timestamp 之間

例子 2

首先 T1 執(zhí)行 R(A)，此時(shí)很明顯，要讀取的版本是 A0

然后 T1 執(zhí)行 W(A)，更新 database

然后需要到 A0 這里，將它的 end timestamp 設(shè)置為 T1 的當(dāng)前時(shí)間戳，即 1

然后開始執(zhí)行 T2，那么此時(shí) T2 執(zhí)行 R(A)，要讀取的是 A 的哪個(gè)版本呢?

是 A0，為什么?

其實(shí)這里取決于選擇的隔離級(jí)別，它選擇的可能是 A0 或者 A1，但假設(shè)它的隔離級(jí)別是 Serializable，此時(shí)它需要讀取 A0，因?yàn)?A1 還沒(méi)有被提交

然后 T2 執(zhí)行 W(A)，這里遇上了 寫寫沖突，假設(shè)這里用的是兩階段鎖，T2 必須等到 T1 提交后才能繼續(xù)執(zhí)行

切換回 T1，執(zhí)行 R(A)

T1 會(huì)讀取它上次剛修改過(guò)的版本，即 A1，然后做提交

此時(shí)再回到 T2，這個(gè)時(shí)候就要去創(chuàng)建 A 的新版本，即 A2，它的值是 789，然后將 A2 的 begin timestamp 設(shè)置為 2，end timestamp 設(shè)置為無(wú)窮大。然后將 A1 的 end timestamp 設(shè)置為 2

有非常多的數(shù)據(jù)庫(kù)用到了 MVCC 這個(gè)技術(shù)?

## MVCC 設(shè)計(jì)決策

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

這些都是前面學(xué)過(guò)的，就不筆記了

### 版本存儲(chǔ)

需要弄清楚某個(gè) tuple 的哪個(gè)版本是可見的

假設(shè)要對(duì)整個(gè) table 進(jìn)行循序掃描，那就要知道應(yīng)該在哪里找，才能找到想要的哪個(gè)版本的 tuple

如何實(shí)現(xiàn)這個(gè)功能?

去維護(hù)一個(gè) internal pointer 的字段，那么就可以通過(guò)這個(gè)字段，找到該 tuple 的前一個(gè)版本或者下一個(gè)版本

可以把這個(gè)看作是一個(gè)鏈表，索引指向的始終是該鏈表的頭節(jié)點(diǎn)

而版本存儲(chǔ)主要有 3 個(gè)方案

#### Append-Only Storage

每當(dāng)創(chuàng)建某個(gè)數(shù)據(jù)的新版本時(shí)，只需要復(fù)制該 tuple 的老版本，并將該副本作為 table 空間中的一個(gè)新的物理 tuple，并對(duì)其進(jìn)行更新

例子

每個(gè)物理版本其實(shí)就是 Main table 中的一個(gè)新 tuple

假設(shè)現(xiàn)在有一個(gè)新事務(wù)，它要去更新對(duì)象 A，首先要做的是在這個(gè) table 空間中找到一個(gè)空的 slot，然后它會(huì)去復(fù)制 A 的當(dāng)前值，即 A1，并將這個(gè)值放入 table 這個(gè)空的 slot 中

然后 A2 也是，它會(huì)將這個(gè)修改后的值放入表中這個(gè) slot 中

更新指針，讓它指向當(dāng)前插入的最新版本數(shù)據(jù)

這個(gè)由指針串聯(lián)起來(lái)的鏈表，就有 2 種排序方式，從新到舊或者從舊到新

#### Time-Travel Storage

在這種方案中，有一個(gè) master version table，這個(gè)里面保存的始終是對(duì)象或者 tuple 的最新版本

然后，將這些老版本數(shù)據(jù)復(fù)制到一個(gè)單獨(dú)的 table 上，這個(gè) table 就是 Time-Travel table，此時(shí)需要維護(hù)的就是 master version table 中指向 Time-Travel table 的指針

當(dāng)數(shù)據(jù)庫(kù)中的 tuple 被修改時(shí)，要將舊版本數(shù)據(jù)復(fù)制到這個(gè)表上，并維護(hù)這些舊版本的數(shù)據(jù)

更新過(guò)程就是如上圖，假如現(xiàn)在要更新 A3，Time-Travel table 中有 A1 和 A2，A2 是新的，它用一個(gè)指針指向那個(gè)舊的 A 的值即 A1

最后需要更新指針，將指向 A3 的指針指向剛在 Time-Travel 表中插入的 A2

#### Delta Storage

最佳方案，可以類比成 git 里面的 diff，這樣就不用每次都去復(fù)制這些老版本的數(shù)據(jù)，然后在它們的副本上進(jìn)行更新了，只需要維護(hù)那些對(duì)前一個(gè)版本所做的修改就好了

每次要更新時(shí)，只需要將那些修改過(guò)的值復(fù)制到這個(gè)單獨(dú)的 Delta Storage Segment 中即可

為了更新 A，要將這個(gè)值復(fù)制到右邊的表上，表中的 delta 值存放的時(shí)該 tuple 中實(shí)際被修改過(guò)的屬性值

然后在 Main table 中更新實(shí)際的值

類似的，插入新的值

這里只對(duì)該 tuple 的一小部分屬性進(jìn)行修改，也就沒(méi)必要復(fù)制整個(gè) tuple

Delta Storage 的缺點(diǎn)在于，必須要重新演算這些 Delta 值，以此來(lái)將 tuple 變回原來(lái)正確的值

## 垃圾回收

當(dāng)事務(wù)在執(zhí)行和結(jié)束時(shí)，所有老版本的數(shù)據(jù)都會(huì)積累在一起

在某個(gè)時(shí)候，某個(gè)特定版本的數(shù)據(jù)不會(huì)對(duì)其他任何活躍的事務(wù)可見，也就是說(shuō)，在這些老版本數(shù)據(jù)的 begin timestamp 和 end timestamp 范圍之內(nèi)，沒(méi)有活躍事務(wù)的時(shí)間戳

所以這個(gè)時(shí)候，這些數(shù)據(jù)都是占空間的，需要回收，以此來(lái)釋放空間

那么該如何查找那些過(guò)期的版本數(shù)據(jù)呢?

如何及時(shí)回收這些數(shù)據(jù)才是安全的呢?

(15-721 會(huì)講)

垃圾回收級(jí)別有 2 種，tuple 級(jí)別和事務(wù)級(jí)別

tuple 級(jí)別: 對(duì) table 進(jìn)行循序掃描，通過(guò)使用版本時(shí)間戳和那些活躍的事務(wù)來(lái)確定這些版本是否過(guò)期，如果過(guò)期，就清楚掉(需要查看內(nèi)存中的 page 里的那些數(shù)據(jù)，還需要查看那些交換到磁盤上的那些 page)

事務(wù)級(jí)別: 當(dāng)這些事務(wù)提交時(shí)，事務(wù)會(huì)去維護(hù)它們的 read set 和 write set

### tuple 級(jí)別 GC

通過(guò)使用 background vacuuming , 在后臺(tái)運(yùn)行一些線程，它們會(huì)執(zhí)行這種清理，定期對(duì) table 進(jìn)行全 table 掃描，看哪些版本時(shí)可以被清理的，主要還是通過(guò)查看當(dāng)前事務(wù)的時(shí)間戳

在上圖的例子中，從這 2 個(gè)事務(wù)中拿到了 2 個(gè)時(shí)間戳，即 12 和 25，然后去查看數(shù)據(jù)版本的 begin timestamp 和 end timestamp

A100 和 B100 的時(shí)間戳范圍時(shí) 1 到 9，而 12 和 25 不屬于這個(gè)范圍，所以它們不可見，那么就可以安全回收 A100 和 B100

### tuple 級(jí)別 GC 優(yōu)化

為 dirty page 維護(hù)一個(gè) bitmap，當(dāng)更新數(shù)據(jù)時(shí)，可以翻轉(zhuǎn)修改的那個(gè) page 對(duì)應(yīng)的 bit，以此來(lái)表示這個(gè) page 變 dirty 了

所以在數(shù)據(jù)庫(kù)中，會(huì)為其所有的 page 維護(hù)一個(gè) bitmap

那么當(dāng) Vacuum 開始工作時(shí)，它立刻就能知道哪些 page 需要被清理，并將該 page 對(duì)應(yīng) bit 重置為 0

Cooperative Cleaning 這種方案是這樣的，當(dāng)線程在執(zhí)行查詢時(shí)，當(dāng)它們遇到舊版本數(shù)據(jù)時(shí)，因?yàn)檫@些數(shù)據(jù)時(shí)不會(huì)再用的，所以它們會(huì)把這些數(shù)據(jù)清理掉

Cooperative Cleaning 這種方案，是否適用于從新到舊這種順序呢

答案是 No

如果是按照從新到舊的順序，就沒(méi)辦法查看那些舊事務(wù)了，因?yàn)檫@樣就直接找到目標(biāo)了，也就沒(méi)有必要遍歷其他數(shù)據(jù)了，那么其他舊數(shù)據(jù)的空間也沒(méi)有辦法做回收了

所以它的順序只能是從舊到新

例子

假設(shè) T1 要通過(guò)索引來(lái)找對(duì)象 A

它會(huì)落在 version chain 的頭節(jié)點(diǎn)處，即 A 的最舊的那個(gè)值的地方

然后它會(huì)沿著這個(gè)對(duì)象的 version chain 進(jìn)行掃描，來(lái)確定該數(shù)據(jù)的哪個(gè)版本是對(duì)其可見的

如果 T1 知道它正在遍歷的某個(gè)版本對(duì)于其他事務(wù)來(lái)說(shuō)是不可見的，那么這些版本就會(huì)被標(biāo)記為 deleted ，并最終被回收

最后索引得到更新，讓它指向這個(gè) version chain 的新的頭節(jié)點(diǎn)

在物理刪除這些數(shù)據(jù)或者回收這些空間之前，可以先更新索引，讓它指向 A2

### 事務(wù)級(jí)別 GC

只需要維護(hù)事務(wù)的 read/write set，通過(guò)它們來(lái)弄清楚哪些版本數(shù)據(jù)不再可用，然后再去回收這些空間

## 索引管理

要對(duì)索引進(jìn)行更新，讓它指向該 version chain 的新頭節(jié)點(diǎn)

但在更新主鍵時(shí)，這會(huì)有點(diǎn)麻煩(主鍵索引指向的永遠(yuǎn)是 version chain 的頭節(jié)點(diǎn))

因?yàn)閷?duì)于同一個(gè)邏輯 tuple 來(lái)說(shuō)，是有可能會(huì)出現(xiàn) 2 個(gè) version，即新的和之前舊的

比如，當(dāng)要更新主鍵時(shí)，先執(zhí)行 delete，緊接著再插入一個(gè)新的邏輯 tuple

### 非主鍵索引

1. 通過(guò)維護(hù)一個(gè)邏輯指針來(lái)確保索引反映了 version chain 中的正確值，而每個(gè) tuple 都有一個(gè)唯一標(biāo)識(shí)符，這個(gè)不會(huì)改變。同時(shí)也有一個(gè)間接層，就是將 tuple 的邏輯 id 映射到數(shù)據(jù)庫(kù)中的物理位置，每當(dāng)要更新 version chain 時(shí)，只需要更新這個(gè)間接層即可，無(wú)需更新每個(gè)索引

2. 使用物理指針

例子

使用主鍵查找 A，對(duì)于主鍵來(lái)說(shuō)，它就是一個(gè)物理地址，它由 page id 和 offset 組成。通過(guò) page id，可以知道這個(gè)對(duì)象在哪個(gè) page 上，通過(guò) offset，可以知道它在該 page 的哪個(gè)位置上

也可以使用物理地址來(lái)作為非主鍵索引使用，但是每當(dāng)更新某個(gè) tuple 時(shí)，也必須對(duì)非主鍵索引進(jìn)行更新，讓它也指向這條鏈的頭節(jié)點(diǎn)

對(duì)于 OLTP 數(shù)據(jù)庫(kù)來(lái)說(shuō)，一個(gè) table 上有多個(gè)非主鍵索引，所以每當(dāng)要更新 version chain 時(shí)，就需要更新所有的非主鍵索引，所以這樣成本就很高

所以與其在非主鍵索引中存物理地址，不如存邏輯指針

這里通過(guò)非主鍵索引來(lái)指向主鍵索引，所以如果現(xiàn)在要查一個(gè)數(shù)據(jù)，首先需要通過(guò)主鍵索引查找，而不是非主鍵索引

這樣更新 tuple 和它對(duì)應(yīng)的 version chain 的頭節(jié)點(diǎn)時(shí)，可以只更新主鍵索引，也就自動(dòng)更新了所有的非主鍵索引

另外一種方案是，有像 tuple id 那樣的合成值，這個(gè)值通常是由一個(gè)計(jì)數(shù)器來(lái)弄出來(lái)的，然后有個(gè) hash table，通過(guò)這個(gè)將 tuple id 映射到對(duì)應(yīng)的物理地址上

現(xiàn)在，通過(guò)非主鍵索引來(lái)獲取 tuple id，然后通過(guò) tuple id 拿到對(duì)應(yīng)的地址，就能夠?qū)?shù)據(jù)進(jìn)行訪問(wèn)了

這樣也能做到，每次要更新 version chain 時(shí)，也能避免更新所有的非主鍵索引，唯一要去更新的就是那個(gè)映射地址的 hash table 和指針

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

## 結(jié)論