mvcc介紹
可串行化mvcc
導緻沖突的兩種操作
可串行化多版本時間戳排程規則
假設收到事務t的讀請求rt(x)
假設收到事務t的寫請求wt（x）
假設收到事務的送出請求
假設收到事務的中止請求
read committed隔離級别
repeatable read 隔離級别
可串行化排程規則舉例
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)。
過晚的寫
兩個并行事務t，u，t比u先開始
t：wt(x)
u：ru(x)
t，u的串行排程為：wt(x)，ru(x)
如圖所示，實際排程是：ru(x)，wt(x)，這個排程不能通過非沖突交換等價與串行排程(t，u)，是以t的寫操作導緻了一個沖突，t該被復原并重新開機。
可串行化多版本時間戳排程規則
對于事務t的讀寫請求，按照如下規則進行排程
該讀請求會試圖讀取寫時間戳小于或等于ts(t)的最大寫時間戳的版本v，即寫時間戳小于或等于t的版本中，離ts(t)最近的版本，找到這樣的版本後v，直接讀取；當成功讀取一個版本的時候，如果ts(t)大于該版本的讀時間戳，則設定其讀時間戳為ts(t)，否則不改變該版本讀時間戳。這種不阻塞讀的政策，會導緻級聯復原，即一個事務復原，會導緻語氣相關的事務跟着復原。并且,同一個事務的double-write可能會導緻該事務復原。這裡也可以采取讀阻塞，直到該版本c位變為真。
排程器首先找到寫時間戳小于或等于ts(t)的所有版本中寫時間戳最大的版本v(該版本可能未送出)，如果v的讀時間戳滿足：rt(x) ＜ ts(t)，則建立一個新版本，置該版本寫時間戳為ts(t)(此時還沒有其他事務來讀取該版本，可将該版本的讀時間戳設定為t時間戳，因為不會有時間戳比t小的事務來讀取該版本，這樣做是合理的)；如果v的寫時間戳等于t的時間戳，即版本v是由t建立的，則直在版本v上修改即可；如果v的讀時間戳不滿足要求，則回中止t，并重新開機。
要求必須按照事務時間戳的順序建立每個對象的送出版本，是以，如果一個事務送出時，在時間戳排序上，還有在它之前的事務未送出，該事務需要等待。
當一個事務被中止時，它建立的所有版本都需要被删除，因為讀阻塞在這些版本上的事務需要重新開始讀操作。如果有其他事務讀取了該事務建立的版本,那麼這些事務也需要重新開機。
read committed隔離級别
該隔離級别下，事務的讀請求，每次讀取的資料都是在該讀請求發起時，是已送出的最新版本。
對于事務t的讀寫請求，按照如下規則進行排程
假設收到事務t的讀請求rt(x)
該請求會讀取在該請求發起的時刻，最近送出的事務建立的版本，即符合條件的版本是在該請求發起時，最新的已送出版本；
假設收到事務t的寫請求wt(x)
假設收到事務的送出請求
因為事務建立的版本在未送出之前是不會被其他事務讀取的，并且事務隻會讀取已經送出的資料，是以，事務發出送出請求時，就一定可以送出。
假設收到事務的中止請求
當一個事務被中止時，它建立的所有版本都需要被删除，因為讀阻塞在這些版本上的事務需要重新開始讀操作。
repeatable read 隔離級别
該隔離級别下，事務的讀請求，每次讀取的資料都是在該事務開始之前，最近送出的資料。
該請求會讀取在該事務開始時，最近送出的事務建立的版本。記事務t的時間戳a(事務t開始的時刻)，則版本清單中寫時間戳(建立該版本的時間戳)小于等于a的所有已送出版本中寫時間戳最大者即為符合條件的版本，即所讀取的版本首先必須是已經送出了的，其次，它是離a最近的事務建立的版本；
因為事務建立的版本在未送出之前是不會被其他事務讀取的，并且，事務讀取的資料都是在事務開始時已經送出的資料，是以，事務發出送出請求時，就一定可以送出。
按照上述規則可能出現一種不是幻讀的錯誤，是以，它不是嚴格的rr隔離級别，可以參考postgresql的rr隔離級别，舉例說明如下。
事務t1，t2，表table1，table1中有一個整形字段val。
假設table1中已經有2條記錄，值分别為10,20，如下表所示：
<col>
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隔離級别作為第四種隔離級别。
可串行化排程規則舉例
使用多版本時間戳的排程規則，讀操作永遠不會被拒絕，因為過晚的讀操作可以讀更早的版本。
寫操作被拒絕舉例
上圖有兩個寫時間戳為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；
a) ta請求一個寫操作，生成一個寫時間戳為ta的臨時版本；
b) tb請求一個讀操作，它通路寫時間戳為ta的版本，該臨時版本是寫時間戳比tb小的所有版本中寫時間戳最大者，同時設定該版本讀時間戳為tb；
c) ta再次請求一個寫操作，它會通路自己先前建立的版本，但是，該版本的讀時間戳tb > ta，該寫被拒絕，ta復原，并以一個更大的時間戳重新開機。