MVCC介紹
MVCC， 即multi-version concurrency control，多版本并發控制。 它的核心思想是為每一個寫操作建立一個新版本，不同的事務根據它的時間戳讀取對應的版本。
與鎖機制相比，MVCC不阻塞讀操作，也不阻塞寫操作。很大程度上提高了事務的并發數，然後，可串行化的MVCC卻可能會付出很大的復原開銷。
可串行化MVCC
- 假設并行事務的所有操作都是非沖突操作，如果某個事務的操作導緻了沖突，則該事務需復原；
- 事務時間戳順序(從低到高)即是事務沖突可串行化的順序，如果事務的并行操作産生了沖突，則至少一個事務需要復原重新開機；
- 每個記錄都有多個已送出版本和多個零時版本，每個版本都包含讀時間戳RT，寫時間戳WT，和一個送出位C，送出位表示最近一次修改是否修改被送出。
如下圖所示；每次合法的寫操作都将産生該記錄的一個臨時版本，讀時間戳為建立該版本的事務的時間戳
時間戳産生的方式主要有以下兩種
- 采用系統時間作為時間戳，隻要確定排程器不會在一個時鐘周期内排程兩個以上的事務的；
- 采用計數器，單調遞增，作為事務的邏輯時間戳
導緻沖突的兩種操作
在基于時間戳的排程中，同樣也需要確定，事務最後的執行順序必須是事務串行化的順序。然而基于時間戳還是存在沖突。
-
過晚的讀
兩個并行事務T，U，T比U先開始
T：RT(X)
U：WU(X)
如果在U在T讀之前寫，則T的讀就導緻了一個沖突，使T，U無法通過非沖突交換等價于一個串行排程(T,U)。
什麼是可串行化MVCC -
過晚的寫
兩個并行事務T，U，T比U先開始
T：WT(X)
U：RU(X)
T，U的串行排程為：WT(X)，RU(X)
如圖所示，實際排程是：RU(X)，WT(X)，這個排程不能通過非沖突交換等價與串行排程(T，U)，是以T的寫操作導緻了一個沖突，T該被復原并重新開機。
什麼是可串行化MVCC
可串行化多版本時間戳排程規則
對于事務T的讀寫請求，按照如下規則進行排程
假設收到事務T的讀請求RT(X)
該讀請求會試圖讀取寫時間戳小于或等于TS(T)的最大寫時間戳的版本V，即寫時間戳小于或等于T的版本中，離TS(T)最近的版本，找到這樣的版本後V，直接讀取；當成功讀取一個版本的時候，如果TS(T)大于該版本的讀時間戳，則設定其讀時間戳為TS(T)，否則不改變該版本讀時間戳。這種不阻塞讀的政策，會導緻級聯復原，即一個事務復原，會導緻語氣相關的事務跟着復原。并且,同一個事務的double-write可能會導緻該事務復原。這裡也可以采取讀阻塞，直到該版本C位變為真。
假設收到事務T的寫請求WT（X）
排程器首先找到寫時間戳小于或等于TS(T)的所有版本中寫時間戳最大的版本V(該版本可能未送出)，如果V的讀時間戳滿足：RT(X) ＜ TS(T)，則建立一個新版本，置該版本寫時間戳為TS(T)(此時還沒有其他事務來讀取該版本，可将該版本的讀時間戳設定為T時間戳，因為不會有時間戳比T小的事務來讀取該版本，這樣做是合理的)；如果V的寫時間戳等于T的時間戳，即版本V是由T建立的，則直在版本V上修改即可；如果V的讀時間戳不滿足要求，則回中止T，并重新開機。
假設收到事務的送出請求
要求必須按照事務時間戳的順序建立每個對象的送出版本，是以，如果一個事務送出時，在時間戳排序上，還有在它之前的事務未送出，該事務需要等待。
假設收到事務的中止請求
當一個事務被中止時，它建立的所有版本都需要被删除，因為讀阻塞在這些版本上的事務需要重新開始讀操作。如果有其他事務讀取了該事務建立的版本,那麼這些事務也需要重新開機。
Read Committed隔離級别
該隔離級别下，事務的讀請求，每次讀取的資料都是在該讀請求發起時，是已送出的最新版本。
對于事務T的讀寫請求，按照如下規則進行排程
- 該請求會讀取在該請求發起的時刻，最近送出的事務建立的版本，即符合條件的版本是在該請求發起時，最新的已送出版本；
-
假設收到事務T的寫請求WT(X)
排程器首先找到寫時間戳小于或等于TS(T)的所有版本中寫時間戳最大的版本V(該版本可能未送出)，如果V的讀時間戳滿足：RT(X) ＜ TS(T)，則建立一個新版本，置該版本寫時間戳為TS(T)(此時還沒有其他事務來讀取該版本，可将該版本的讀時間戳設定為T時間戳，因為不會有時間戳比T小的事務來讀取該版本，這樣做是合理的)；如果V的寫時間戳等于T的時間戳，即版本V是由T建立的，則直在版本V上修改即可；如果V的讀時間戳不滿足要求，則回中止T，并重新開機。
- 因為事務建立的版本在未送出之前是不會被其他事務讀取的，并且事務隻會讀取已經送出的資料，是以，事務發出送出請求時，就一定可以送出。
- 當一個事務被中止時，它建立的所有版本都需要被删除，因為讀阻塞在這些版本上的事務需要重新開始讀操作。
Repeatable Read 隔離級别
該隔離級别下，事務的讀請求，每次讀取的資料都是在該事務開始之前，最近送出的資料。
對于事務T的讀寫請求，按照如下規則進行排程
- 該請求會讀取在該事務開始時，最近送出的事務建立的版本。記事務T的時間戳A(事務T開始的時刻)，則版本清單中寫時間戳(建立該版本的時間戳)小于等于A的所有已送出版本中寫時間戳最大者即為符合條件的版本，即所讀取的版本首先必須是已經送出了的，其次，它是離A最近的事務建立的版本；
- 因為事務建立的版本在未送出之前是不會被其他事務讀取的，并且，事務讀取的資料都是在事務開始時已經送出的資料，是以，事務發出送出請求時，就一定可以送出。
按照上述規則可能出現一種不是幻讀的錯誤，是以，它不是嚴格的RR隔離級别，可以參考postgreSQL的RR隔離級别，舉例說明如下。
事務T1，T2，表Table1，Table1中有一個整形字段Val。
假設Table1中已經有2條記錄，值分别為10,20，如下表所示：
| int id | int val |
| 1 | 10 |
| 2 | 20 |
T1，T2的操作如下：
T1讀取第2行資料，設該行資料為X，則修改第一行資料為X；
T2讀取第1行資料，設該行資料為Y，修改第2行資料為Y；
T1，T2的操作序列是為了将兩行資料設定成相等的值，如果按照串行的執行順序，最終2行将會是一樣的值，但在Repeatable Read隔離級别下，由于讀取限制，最後修改完成後，不能得到預期的效果。
T1，T2的操作序列如下：
按照上述操作序列，在RR隔離級别下，最後第1行記錄值為20，第2行記錄值為10，這與串行執行的效果是不一緻的。
上述錯誤是postgreSQL在第三種隔離級别下的一個Bug，postgreSQL使用predicate lock修複了這個Bug，并将具有predicate lock的Reapeatable Read隔離級别作為第四種隔離級别。
可串行化排程規則舉例
- 使用多版本時間戳的排程規則，讀操作永遠不會被拒絕，因為過晚的讀操作可以讀更早的版本。
- 寫操作被拒絕舉例
什麼是可串行化MVCC 上圖有兩個寫時間戳為T1和T2的送出版本。
操作序列為:
T3 read; T3 write; T5 read; T4 write;
a) T3請求一個讀操作，它在T2版本上設定讀時間戳T3。
b) T3請求一個寫操作，生成一個寫時間戳為T3的臨時版本。
c) T5請求一個讀操作，它通路寫時間戳為T3的版本(小于T5的具有最高寫時間戳的版本)，同時設定該臨時版本的讀時間戳為T5。
d) T4請求一個寫操作，由于寫時間戳為T3的版本的讀時間戳T5大于T4，該寫操作被拒絕。(如果該寫操作不被拒絕，那麼新版本的寫時間戳将是T4。如果允許建立這個版本，那麼這回合T5的讀操作沖突，此時，T5的讀操作應該使用時間戳為T4的版本。)
-
某個事務double-write導緻復原
事務Ta，Tb，Tia< Tb(即Ta比Tb早開始)
操作序列為：Ta write；Tb read；Ta write；
什麼是可串行化MVCC a) Ta請求一個寫操作，生成一個寫時間戳為Ta的臨時版本；
b) Tb請求一個讀操作，它通路寫時間戳為Ta的版本，該臨時版本是寫時間戳比Tb小的所有版本中寫時間戳最大者，同時設定該版本讀時間戳為Tb；
c) Ta再次請求一個寫操作，它會通路自己先前建立的版本，但是，該版本的讀時間戳Tb > Ta，該寫被拒絕，Ta復原，并以一個更大的時間戳重新開機。