<input id="0qass"><u id="0qass"></u></input>
  • <input id="0qass"><u id="0qass"></u></input>
  • <menu id="0qass"><u id="0qass"></u></menu>

    什么是可串行化MVCC

    MVCC介紹

    ?MVCC, 即multi-version concurrency control,多版本并發控制。 它的核心思想是為每一個寫操作創建一個新版本,不同的事務根據它的時間戳讀取對應的版本。
    ?與鎖機制相比,MVCC不阻塞讀操作,也不阻塞寫操作。很大程度上提高了事務的并發數,然后,可串行化的MVCC卻可能會付出很大的回滾開銷。

    可串行化MVCC

    1. 假設并行事務的所有操作都是非沖突操作,如果某個事務的操作導致了沖突,則該事務需回滾;
    2. 事務時間戳順序(從低到高)即是事務沖突可串行化的順序,如果事務的并行操作產生了沖突,則至少一個事務需要回滾重啟;
    3. 每個記錄都有多個已提交版本和多個零時版本,每個版本都包含讀時間戳RT,寫時間戳WT,和一個提交位C,提交位表示最近一次修改是否修改被提交。

    ?如下圖所示;每次合法的寫操作都將產生該記錄的一個臨時版本,讀時間戳為創建該版本的事務的時間戳
    在這里插入圖片描述
    ?時間戳產生的方式主要有以下兩種

    1. 采用系統時間作為時間戳,只要確保調度器不會在一個時鐘周期內調度兩個以上的事務的;
    2. 采用計數器,單調遞增,作為事務的邏輯時間戳

    導致沖突的兩種操作

    ?在基于時間戳的調度中,同樣也需要確保,事務最后的執行順序必須是事務串行化的順序。然而基于時間戳還是存在沖突。

    1. 過晚的讀
      兩個并行事務T,U,T比U先開始
      T:RT(X)
      U:WU(X)
      如果在U在T讀之前寫,則T的讀就導致了一個沖突,使T,U無法通過非沖突交換等價于一個串行調度(T,U)。
      在這里插入圖片描述
    2. 過晚的寫
      ?兩個并行事務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的讀寫請求,按照如下規則進行調度

    假設收到事務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的讀寫請求,按照如下規則進行調度

    1. 假設收到事務T的讀請求RT(X)
      該請求會讀取在該請求發起的時刻,最近提交的事務創建的版本,即符合條件的版本是在該請求發起時,最新的已提交版本;
    2. 假設收到事務T的寫請求WT(X)
      調度器首先找到寫時間戳小于或等于TS(T)的所有版本中寫時間戳最大的版本V(該版本可能未提交),如果V的讀時間戳滿足:RT(X) < TS(T),則創建一個新版本,置該版本寫時間戳為TS(T)(此時還沒有其他事務來讀取該版本,可將該版本的讀時間戳設置為T時間戳,因為不會有時間戳比T小的事務來讀取該版本,這樣做是合理的);如果V的寫時間戳等于T的時間戳,即版本V是由T創建的,則直在版本V上修改即可;如果V的讀時間戳不滿足要求,則回中止T,并重啟。
    3. 假設收到事務的提交請求
      因為事務創建的版本在未提交之前是不會被其他事務讀取的,并且事務只會讀取已經提交的數據,因此,事務發出提交請求時,就一定可以提交。
    4. 假設收到事務的中止請求
      當一個事務被中止時,它創建的所有版本都需要被刪除,因為讀阻塞在這些版本上的事務需要重新開始讀操作。

    Repeatable Read 隔離級別

    ?該隔離級別下,事務的讀請求,每次讀取的數據都是在該事務開始之前,最近提交的數據。
    ?對于事務T的讀寫請求,按照如下規則進行調度

    1. 假設收到事務T的讀請求RT(X)
      該請求會讀取在該事務開始時,最近提交的事務創建的版本。記事務T的時間戳A(事務T開始的時刻),則版本列表中寫時間戳(創建該版本的時間戳)小于等于A的所有已提交版本中寫時間戳最大者即為符合條件的版本,即所讀取的版本首先必須是已經提交了的,其次,它是離A最近的事務創建的版本;
    2. 假設收到事務T的寫請求WT(X)
      調度器首先找到寫時間戳小于或等于TS(T)的所有版本中寫時間戳最大的版本V(該版本可能未提交),如果V的讀時間戳滿足:RT(X) < TS(T),則創建一個新版本,置該版本寫時間戳為TS(T)(此時還沒有其他事務來讀取該版本,可將該版本的讀時間戳設置為T時間戳,因為不會有時間戳比T小的事務來讀取該版本,這樣做是合理的);如果V的寫時間戳等于T的時間戳,即版本V是由T創建的,則直在版本V上修改即可;如果V的讀時間戳不滿足要求,則回中止T,并重啟。
    3. 假設收到事務的提交請求
      因為事務創建的版本在未提交之前是不會被其他事務讀取的,并且,事務讀取的數據都是在事務開始時已經提交的數據,因此,事務發出提交請求時,就一定可以提交。
    4. 假設收到事務的中止請求
      當一個事務被中止時,它創建的所有版本都需要被刪除,因為讀阻塞在這些版本上的事務需要重新開始讀操作。

    ?按照上述規則可能出現一種不是幻讀的錯誤,因此,它不是嚴格的RR隔離級別,可以參考postgreSQL的RR隔離級別,舉例說明如下。
    事務T1,T2,表Table1,Table1中有一個整形字段Val。
    假設Table1中已經有2條記錄,值分別為10,20,如下表所示:

    int idint val
    110
    220

    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隔離級別作為第四種隔離級別。

    可串行化調度規則舉例

    1. 使用多版本時間戳的調度規則,讀操作永遠不會被拒絕,因為過晚的讀操作可以讀更早的版本。
    2. 寫操作被拒絕舉例
      在這里插入圖片描述
      ?上圖有兩個寫時間戳為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的版本。)
    1. 某個事務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回滾,并以一個更大的時間戳重啟。
    已標記關鍵詞 清除標記
    ??2020 CSDN 皮膚主題: Age of Ai 設計師:meimeiellie 返回首頁
    多乐彩