Lecture #19 : Multi-Version Concurrency Control

CMU15445課程筆記

多版本并發控制

多版本并發控制講的是Mvcc。即維護單個邏輯對象的多個物理版本，這樣當一個事務讀取某個對象的時候不會阻塞其他事務寫入該對象；反之亦然。但是Mvcc不保護寫寫沖突，對于這種情況，可能需要其兩階段鎖之類的其他控制協議。

Mvcc可以實現：只讀事務并發時，無需使用鎖，即可達成讀層次的一致性快照；并且在Mvcc中，時間戳是用來確定某個對象的某個版本對于事務的可見性；不帶垃圾回收機制的Mvcc允許DBMS支持時間旅行查詢（基于某個時間點的狀態進行的查詢)

時間旅行查詢的一個例子：比如對方想要查詢這個表三星期前的某個數據，現在我們只需要找到三星期前的時間戳，然后讀取即可。——這是在不做垃圾回收機制的情況下。 Postgres有一開始推崇時間旅行查詢到砍掉這一機制的原因就是因為要支持垃圾回收機制，因為如果不支持垃圾回收機制，那么存儲空間很快就會耗盡。

快照隔離

實現的基本思路是：對于事務TS(1)和事務TS(2)。然后對于對象A，兩個事務要對A做一系列操作如下：

      TS(1)             TS(2)
|     Begin      |                |       
|                |                |
|     R(A)       |                |
|     W(A)       |     Begin      |
|                |     R(A)       |
|                |     W(A)       |
|     R(A)       |                |
|                |                |
|     COMMIT     |                |

首先， TS(1)事務和TS(2)事務開始時，要建立一個一致性視圖，視圖有一個時間戳， TS(1)先Begin，建立時間戳為1的視圖。
Database(Buffer Pool）中要維護一個對于A的版本鏈，一開始版本A0，開始時間戳begin-ts 為0，結束時間戳end-ts為∞；
- ```
    A0 | 0 | ∞ |
```
然后， TS(1)進來了，他一開始讀取R(A), 對于A的版本鏈沒有任何影響。
- ```
    A0 | 0 | ∞ |
```
TS(1) 執行W(A), A被修改出新版本A1, A1的開始時間戳就是TS(1)的時間戳1，并且因為A被修改了，所以上一個版本，也就是A0被限制了，它的結束時間戳不再是無窮大了，變成了版本A1出現的時間戳。
- ```
    A0 | 0 | 1 |A1 | 1 | ∞ |
```
- begin-ts和end-ts就可以理解為某個版本所持續的時間。這就可以理解為如果沒有人修改A，那么最新的版本就是版本鏈的最后一個版本，并且這個版本的有效性可以持續到無窮時間以后，但是有人修改A了，這個版本的持續時間就只存在于這一段時間了。
然后對于TS(2)，他Begin了，創建一致性視圖， TS(2)的時間戳為2。然后TS(2)此時想要讀取A，能否讀取一個對象要看三個規則：
- 自身攜帶的時間戳是否大于版本的end-ts，如果大于，則看不到。
- 如果自身攜帶的時間戳處于begin-ts ~ end-ts之間，那么觀察一下active table（這也是一張表，包含了當前正在活躍的事務）中這個版本的begin-ts所在事務是否在活躍，即沒有提交。如果提交了，可以看到，沒提交，看不到。
- 如果自身攜帶的時間戳等于begin-ts, 即是這個版本的創建者，可以看到。
所以這里TS(2)讀取A得到了A0版本。然后W(A)，但是TS(1)此時正在持有鎖， TS(2)要阻塞，直到TS(1)提交。當然，中間TS（1）還有一次R(A), 但是因為TS(1)是A1的創建者，則可以看到A1。然后提交。
TS(2)獲取寫鎖，W(A), 此時最新的版本變成了A2， begin-ts為2, end-ts為∞；A1則修改end-ts變成2，因為A1只存在于A1 ~ A2這段時間就被TS(2)寫入A2邏輯上覆蓋了。
- ```
    A0 | 0 | 1 |A1 | 1 | 2 |A2 | 2 | ∞ |
```

版本存儲

對于版本控制有不同的版本控制方案。版本控制總是一個類似鏈表的數據結構。鏈表內存放了保存的邏輯元組，以及連接到這個邏輯元組的下一個邏輯元組，可以是單鏈表，也可以是雙鏈表。

不同點是這個鏈表的頭指針是新是舊，遍歷方式是從新到舊還是從舊到新，亦或者這個邏輯元組里面存儲的具體內容。

僅追加存儲

僅追加存儲就是每當更新新的版本，就將舊的版本作為新元組追加到版本鏈中。

具體細節就是當來了一個新的元組，然后就把他插入這張表中，因為對于數據庫中的每一張表，都會被分配一個表空間存儲這些元組。然后每次更新元組，比如更新A，那么就要跟新A的版本鏈，讓A的版本鏈中最新的節點指向新更新的節點。這里的問題就是每次鏈接版本鏈，都要從表中查找該數據的頭節點。

并且版本鏈的排序也很重要，因為如果是從新到舊，那么插入新元組的時候直接找到版本鏈的頭節點就可以了；但是如果是從舊到新，那么插入新元組的時候就不僅僅需要找到版本鏈的頭節點，還要遍歷整個版本鏈。

另外對于從舊到新，我們這里查找表頭可能索引，比如我利用索引查找到對應的記錄ID，然后找到版本鏈的鏈頭，然后遍歷整個鏈表，根據節點的begin-ts和end-ts查找當前版本是否符合要求或者追加新節點。

對于從新到舊，雖然讓你我們查找到鏈頭，可以很快的查找到最新的節點，但是這只是聽起來很棒。這只是查詢，如果我們要追加新節點，那么我們因為維護大量了的索引。就要更新所有指向這個頭結點的索引，確保他們都指向新的鏈頭。

這里面有很多細節問題，目前不知道，比如：這些跟蹤索引利用索引鍵跟蹤，如果索引鍵也修改了怎么辦？為什么要有索引？如果沒有索引， SeqScan不就更慢了嗎？（TODO）

在這里插入圖片描述

時間旅行存儲

本質上和僅追加存儲一樣。只不過對于時間旅行存儲將表劃分為了主表和時間旅行表，新元組不再是只追加到一張表中，而是插入到指定的時間旅行表。

在這里插入圖片描述

時間旅行存儲并不比追加存儲好，只是它出現在了并沒有那么多Mvcc設計的年代，并且如果采用從舊到新的方式，進行垃圾回收的時候，要進行數據壓縮，版本新的Time-TravelTable稱為新的Main Table。

增量存儲（類似Git的版本控制）

增量存儲要比前兩種策略要好，如果一個元組一共有1000列，更新了其中的10列，那么對于增量存儲就只是存儲這10列的信息，而前兩種方法要全部存儲。

它的策略是：假如一開始是111，然后插入了新的數據222，那么增量表中就要保存原始的A的被修改的列信息，然后主表中的新元組指向它。也就是新的修改總是在主表中的，而歷史的值是在增量表中的。這類似于LSMTree（TODO，日志結構合并樹）
在這里插入圖片描述

垃圾回收

如果在快照隔離級別下一個版本沒有事務可以看到它并且這個版本是因為事務終止創建的，那么這個就可以移除它。這里有兩個問題：

如何查找過期的版本？
如何確定何時可以安全的回收這些記錄所占用的空間或存儲呢？

元組級GC

遍歷所有版本，并嘗試找到可以回收的版本。 —— 這個可以使用后臺的worker線程進行；也可以在掃描數據的同時清理，即協同清理。

對于使用后臺的worker線程：

在這里插入圖片描述

上圖就是比如現在有兩個事務，事務12和事務25。那么我們遍歷整個表，返現A100和B100不可見，因為這里的A100和B100的生效時間段是1 ~ 9，所以對兩個事務都不可見。 B101對事務1可見，對事務2不可見。

在這里插入圖片描述

對于協同清理：

這里不太理解，大概的意思可能就是對于worker線程來說，他知道哪些元組是對所有事務都不可見，那么掃描到這個元組的時候，就把他刪除。 (TODO)。

事務級別GC

事務級別GC就是需要跟蹤所有事務以及他們修改的內容。比如這里事務1，修改了A， B。然后記錄下AB的舊版本。然后再COMMIT的時候獲得一個新的事務ID。然后將這些OldVersions的信息傳給vacuum進程。由vacuum進程判斷一個最小時間戳，任何小于這個最小時間戳的事務都可以刪除了。

這里同樣不太理解，因為如果vacuum只處理單個事務的最小時間戳那么就不正確，所以這里vacuum應該處理的是所有事物的最小時間戳。但是這樣要一邊修改一遍記錄，然后交給后臺進程處理，相當于元組GC的后臺worker了。 (TODO)

在這里插入圖片描述

索引管理

如果有二級索引，他們指向的是什么，即值指向的是什么。

邏輯指針

一種是邏輯指針，工作是幫助我們找到鏈頭的實際物理地址。這種方法最簡單的是使用主鍵，因為主鍵是現成的，先使用二級索引找到主鍵，然后利用主鍵索引去找到對應的物理地址。另一種方法是合成ID，但是這還需要重新維護一個合成ID到邏輯指針的索引，并不劃算。

物理指針

另一種就是直接存物理地址。二級索引精確的指向了要訪問的物理地址。

在數據庫中可能有大量的二級索引，這些二級索引都指向了版本鏈的頭部。此時就可以根據二級索引來找到具體的物理地址。但是如果更新元組，即便不更新這個元素中二級索引所依賴的屬性，那么這個依舊要更新所有二級索引指向新鏈頭。

Postgres這里采用了其他優化，就是他們在索引中添加了一個新的條目，如果新的版本和之前的版本在同一個頁中，他們不會選擇更新鏈頭，而是直接在條目中顯示：這個元組不是最新的版本，最新的版本應該是那邊的那個。

在這里插入圖片描述

MySQL的處理方法就是二級索引提供主鍵，然后利用主鍵找到對應物理地址，和上面的邏輯指針一樣。

關于不同快照的重復鍵問題

這個問題是有一個場景：

在這里插入圖片描述

就是假如一開始T1讀取到了A， T2讀取A，然后刪除了A。并且T1讀取的是A1， T2讀取的是A2，刪除的也是自己可見的A2。那么T3插入一個A, 他插入的應該是從時間戳30開始生效。所以，這里就要保證兩個東西：

對于T1來說，如果正在運行，在T2刪除的時候，他應該仍能夠看到A1。
對于時間戳30以后的事務，他應該能看到A3。（圖中的是筆誤）

在這種情況下，如果索引的版本鏈還是A1這一條。要確保30以后的事務能夠看到A3，他在遍歷版本鏈的時候，可能直接就發現版本鏈運行結束后，也沒有看到A3。所以就需要其他的信息來維護一種跳轉功能，能夠在索引中存在相同值的時候（此時A的版本鏈有兩條，說明有相同值），能夠正確跳轉。

刪除

刪除就是利用墓碑。

刪除標志

刪除標志就是在元組的頭部設置刪除標記

墓碑元組

墓碑元組就是將元組設置成默認的“空“元組。