淺析資料庫併發控制機制

摘要： 資料庫事務隔離發展標準 一文中，從標準制定的角度介紹了資料庫的隔離級別，介紹了Read Uncommitted、Read Committed、Repeatable Read、Serializable等隔離級別的定義。本文就來看看究竟有哪些常見的實現事務隔離的機制，稱之為併發控制（Concur...

ofollow,noindex" target="_blank">資料庫事務隔離發展標準 一文中，從標準制定的角度介紹了資料庫的隔離級別，介紹了Read Uncommitted、Read Committed、Repeatable Read、Serializable等隔離級別的定義。本文就來看看究竟有哪些常見的實現事務隔離的機制，稱之為併發控制（Concurrency Control）。

原理

所謂 併發控制，就是保證併發執行的事務在某一隔離級別上的正確執行的機制 。需要指出的是併發控制由資料庫的排程器負責，事務本身並不感知，如下圖所示，Scheduler將多個事務的讀寫請求，排列為合法的序列，使之依次執行：

這個過程中，對可能破壞資料正確性的衝突事務，排程器可能選擇下面兩種處理方式：

• Delay：延遲某個事務的執行到合法的時刻
• Abort：直接放棄事務的提交，並回滾該事務可能造成的影響

可以看出Abort比Delay帶來更高的成本，接下來我們就介紹不同的併發控制機制在不同情況下的處理方式。

分類

這裡從兩個維度，對常見的併發控制機制進行分類：

1. 樂觀程度

不同的實現機制，基於不同的對發生衝突概率的假設，悲觀方式認為只要兩個事務訪問相同的資料庫物件，就一定會發生衝突，因而應該儘早阻止；而樂觀的方式認為，衝突發生的概率不大，因此會延後處理衝突的時機。如上圖橫座標所示，樂觀程度從左向右增高：

• 基於Lock：最悲觀的實現，需要在操作開始前，甚至是事務開始前，對要訪問的資料庫物件加鎖，對衝突操作Delay；
• 基於Timestamp：樂觀的實現，每個事務在開始時獲得全域性遞增的時間戳，期望按照開始時的時間戳依次執行，在操作資料庫物件時檢查衝突並選擇Delay或者Abort；
• 基於Validation：更樂觀的實現，僅在Commit前進行Validate，對衝突的事務Abort

可以看出，不同樂觀程度的機制 本質的區別在於，檢查或預判衝突的時機，Lock在事務開始時，Timestamp在操作進行時，而Validation在最終Commit前 。相對於悲觀的方式，樂觀機制可以獲得更高的併發度，而一旦衝突發生，Abort事務也會比Delay帶來更大的開銷。

2. 單版本 VS 多版本

如上圖縱座標所示，相同的樂觀程度下，還存在多版本的實現。所謂多版本，就是在每次需要對資料庫物件修改時，生成新的資料版本，每個物件的多個版本共存。讀請求可以直接訪問對應版本的資料，從而避免讀寫事務和只讀事務的相互阻塞。當然多版本也會帶來對不同版本的維護成本，如需要垃圾回收機制來釋放不被任何事物可見的版本。

需要指出的是這些併發控制機制並不與具體的隔離級別繫結，通過沖突判斷的不同規則，可以實現不同強度的隔離級別，下面基於Serializable具體介紹每種機制的實現方式。

基於Lock

基於Lock實現的Scheduler需要在事務訪問資料前加上必要的鎖保護，為了提高併發，會根據實際訪問情況分配不同模式的鎖，常見的有讀寫鎖，更新鎖等。最簡單地，需要長期持有鎖到事務結束，為了儘可能的在保證正確性的基礎上提高並行度，資料庫中常用的加鎖方式稱為 兩階段鎖（2PL） ，Growing階段可以申請加鎖，Shrinking階段只能釋放，即在第一次釋放鎖之後不能再有任何加鎖請求。需要注意的是2PL並不能解決死鎖的問題，因此還需要有死鎖檢測及處理的機制，通常是選擇死鎖的事務進行Abort。

Scheduler對衝突的判斷還需要配合 Lock Table ，如下圖所示是一個可能得Lock Table資訊示意，每一個被訪問的資料庫物件都會在Lock Table中有對應的表項，其中記錄了當前最高的持有鎖的模式、是否有事務在Delay、以及持有或等待對應鎖的事務連結串列；同時對連結串列中的每個事務記錄其事務ID，請求鎖的模式以及是否已經持有該鎖。Scheduler會在加鎖請求到來時，通過查詢Lock Table判斷能否加鎖或是Delay，如果Delay需要插入到連結串列中。對應的當事務Commit或Abort後需要對其持有的鎖進行釋放，並按照不同的策略喚醒等待佇列中Delay的事務。

基於Timestamp

基於Timestamp的Scheduler會在事務開始時候分配一個全域性自增的Timestamp，這個Timestamp通常由物理時間戳或系統維護的自增id產生，用於區分事務開始的先後。同時，每個資料庫物件需要增加一些額外的資訊，這些資訊會由對應的事務在訪問後更新，包括:

• RT(X): 最大的讀事務的Timestamp
• WT(X): 最大的寫事務的Timestamp
• C(X): 最新修改的事務是否已經提交

基於Timestamp假設開始時Timestamp的順序就是事務執行的順序，當事務訪問資料庫物件時，通過對比事務自己的Timestamp和該物件的資訊，可以發現與這種與開始順序不一致的情況，並作出應對：

• Read Late：比自己Timestamp晚的事務在自己想要Read之前對該資料進行了寫入，並修改了WT(X)，此時會Read不一致的資料。
• Write Late: 比自己Timestamp晚的事務在自己想要Write之前讀取了該資料，並修改了RT(X)，如果繼續寫入會導致對方讀到不一致資料。

這兩種情況都是由於實際訪問資料的順序與開始順序不同導致的，Scheduler需要對衝突的事務進行Abort。

• Read Dirty：通過對比C(X)，可以發現是否看到的是已經Commit的資料，如果需要保證Read Commit，則需要Delay事務到對方Commit之後再進行提交。

基於Validation（OCC）

基於Validation的方式，有時也稱為Optimistic Concurrency Control(OCC)，大概是因為它比基於Timestamp的方式要更加的樂觀，將衝突檢測推遲到Commit前才進行。不同於Timestamp方式記錄每個物件的讀寫時間，Validation的方式記錄的是每個事物的讀寫操作集合。並將事物劃分為三個階段：

• Read階段：從資料庫中讀取資料並在私有空間完成寫操作，這個時候其實並沒有實際寫入資料庫。維護當前事務的讀寫集合，RS、WS；
• Validate階段：對比當前事務與其他有時間重疊的事務的讀寫集合，判斷能否提交；
• Write階段：若Validate成功，進入Write階段，這裡才真正寫入資料庫。

同時，Scheduler會記錄每個事務的開始時間START(T)，驗證時間VAL(T)，完成寫入時間FIN(T)

基於Validataion的方式假設事務Validation的順序就是事務執行的順序，因此驗證的時候需要檢查訪問資料順序可能得不一致：

• RS(T)和WS(U) 是否有交集，對任何事務U，FIN(U) > START(T)，如果有交集，則T的讀可能與U的寫亂序；
• WS(T)和WS({U) 是否有交集，對任何事務U， Fin(U) > VAL(T)，如果有交集，則T的寫可能與U的寫亂序。

Multiversion（MVCC）

對應上述每種樂觀程度，都可以有多版本的實現方式，多版本的優勢在於，可以讓 讀寫事務與只讀事務互不干擾，因而獲得更好的並行度 ，也正是由於這一點成為幾乎所有主流資料庫的選擇。為了實現多版本的併發控制，需要給每個事務在開始時分配一個唯一標識TID，並對資料庫物件增加以下資訊：

• txd-id，建立該版本的事務TID
• begin-ts及end-ts分別記錄該版本建立和過期時的事務TID
• pointer: 指向該物件其他版本的連結串列

其基本的實現思路是，每次對資料庫物件的寫操作都生成一個新的版本，用自己的TID標記新版本begin-ts及上一個版本的end-ts，並將自己加入連結串列。讀操作對比自己的TID與資料版本的begin-ts，end-ts，找到其可見最新的版本進行訪問。根據樂觀程度多版本的機制也分為三類：

1. Two-phase Locking (MV2PL)

與單版本的2PL方式類似，同樣需要Lock Table跟蹤當前的加鎖及等待資訊，另外給資料庫物件增加了多版本需要的begin-ts和end-ts資訊。寫操作需要對最新的版本加寫鎖，並生成新的資料版本。讀操作對找到的最新的可見版本加讀鎖訪問。

2. Timestamp Ordering (MVTO)

對比單版本的Timestamp方式對每個資料庫物件記錄的Read TimeStamp(RT)，Write TimeStamp(WT)，Commited flag(C)資訊外增加了標識版本的begin-ts和end-ts，同樣在事務開始前獲得唯一遞增的Start TimeStamp（TS），寫事務需要對比自己的TS和可見最新版本的RT來驗證順序，寫入是建立新版本，並用自己的TS標記新版本的WT，不同於單版本，這個WT資訊永不改變。讀請求讀取自己可見的最新版本，並在訪問後修改對應版本的RT，同樣通過判斷C flag資訊避免Read Uncommitted。

3. Optimistic Concurrency Control (MVOCC)

對比單版本的Validataion（OCC）方式，同樣分為三個階段，Read階段根據begin-ts，end-ts找到可見最新版本，不同的是在多版本下Read階段的寫操作不在私有空間完成，而是直接生成新的版本，並在其之上進行操作，由於其commit前begin-ts為INF，所以不被其他事務課件；Validation階段分配新的Commit TID，並以之判斷是否可以提交；通過Validation的事務進入Write階段將begin-ts修改為Commit TID。

總結

相對於悲觀的鎖實現，樂觀的機制可以在衝突發生較少的情況下獲得更好的併發效果，然而一旦衝突，需要事務回滾帶來的開銷要遠大於悲觀實現的阻塞，因此他們各自適應於不同的場景。而多版本由於避免讀寫事務與只讀事務的互相阻塞， 在大多數資料庫場景下都可以取得很好的併發效果，因此被大多數主流資料庫採用。可以看出無論是樂觀悲觀的選擇，多版本的實現，讀寫鎖，兩階段鎖等各種併發控制的機制，歸根接地都是 在確定的隔離級別上儘可能的提高系統吞吐，可以說隔離級別選擇決定上限，而併發控制實現決定下限。

本文從樂觀悲觀的程度以及單版本多版本選擇上對可用的併發控制機制選擇進行了劃分，並介紹了各種機制大體的設計思路，而距離真正的實現還有比較大的距離，包括實現細節和配套機制。比如常用的各種型別的MVCC中，由於多版本的存在而帶來的一些列如垃圾回收、索引管理、版本儲存等相關問題。我們之後將以MyRocks為例看看併發控制在工程上的具體實現。

參考

資料庫事務隔離發展標準

An Empirical Evaluation of In-Memory Multi-Version Concurrency Control

Database System Implementation

CMU SCS 15-721 (Spring 2018) :: Optimistic Concurrency Control