作者：旺德，阿裡雲資料庫進階開發工程師
1.資料庫并發控制的作用
1.1 事務的概念
在介紹并發控制前，首先需要了解事務。資料庫提供了增删改查等幾種基礎操作，使用者可以靈活地組合這幾種操作，實作複雜的語義。在很多場景下，使用者希望一組操作可以做為一個整體一起生效，這就是事務。事務是資料庫狀态變更的基本單元，包含一個或多個操作（例如多條SQL語句）。經典的轉賬事務，就包括三個操作：（1）檢查A賬戶餘額是否足夠。（2）如果足夠，從A扣減100塊。（3）B賬戶增加100塊。
事務有個基本特性：這一組操作要麼一起生效，要麼都不生效，事務執行過程中如遇錯誤，已經執行的操作要全部撤回，這就是事務的原子性。如果失敗發生後，部分生效的事務無法撤回，那資料庫就進入了不一緻狀态，與真實世界的事實相左。例如轉賬事務從A賬戶扣款100塊後失敗了，B賬戶還未增加款項，如果A賬戶扣款操作未撤回，這個世界就莫名奇妙丢失了100塊。原子性可以通過記日志（更改前的值）來實作，還有一些資料庫将事務操作緩存在本地，如遇失敗，直接丢棄緩存裡的操作。
事務隻要送出了，它的結果就不能改變了，即使遇到系統當機，重新開機後資料庫的狀态與當機前一緻，這就是事務的持久性。資料隻要存儲非易失存儲媒體，當機就不會導緻資料丢失。是以資料庫可以采用以下方法來保證持久性：（1）事務完成前，所有的更改都保證存儲到磁盤上了。或（2）送出完成前，事務的更改資訊，以日志的形式存儲在磁盤，重新開機過程根據日志恢複出資料庫系統的記憶體狀态。一般而言，資料庫會選擇方法（2），原因留給讀者思考。
資料庫為了提高資源使用率和事務執行效率、降低響應時間，允許事務并發執行。但是多個事務同時操作同一對象，必然存在沖突，事務的中間狀态可能暴露給其它事務，導緻一些事務依據其它事務中間狀态，把錯誤的值寫到資料庫裡。需要提供一種機制，保證事務執行不受并發事務的影響，讓使用者感覺，目前仿佛隻有自己發起的事務在執行，這就是隔離性。隔離性讓使用者可以專注于單個事務的邏輯，不用考慮并發執行的影響。資料庫通過并發控制機制保證隔離性。由于隔離性對事務的執行順序要求較高，很多資料庫提供了不同選項，使用者可以犧牲一部分隔離性，提升系統性能。這些不同的選項就是事務隔離級别。
資料庫反映的是真實世界，真實世界有很多限制，例如：賬戶之間無論怎麼轉賬，總額不會變等現實限制；年齡不能為負值，性别最多隻能有男、女、跨性别者三種選項等完整性限制。事務執行，不能打破這些限制，保證事務從一個正确的狀态轉移到另一個正确的狀态，這就是一緻性。不同與前三種性質完全由資料庫實作保證，一緻性既依賴于資料庫實作（原子性、持久性、隔離性也是為了保證一緻性），也依賴于應用端編寫的事務邏輯。
1.2 事務并發控制如何保證隔離性
為了保證隔離性，一種方式是所有事務串行執行，讓事務之間不互相幹擾。但是串行執行效率非常低，為了增大吞吐，減小響應時間，資料庫通常允許多個事務同時執行。是以并發控制子產品需要保證：事務并發執行的效果，與事務串行執行的效果完全相同（serializability），以達到隔離性的要求。
為了友善描述并發控制如何保證隔離性，我們簡化事務模型。事務是由一個或多個操作組成，所有的操作最終都可以拆分為一系列讀和寫。一批同時發生的事務，所有讀、寫的一種執行順序，被定義為一個schedule，例如：
T1、T2同時執行，一個可能的schedule: T1.read(A),T2.read(B),T1.write(A),T1.read(B),T2.write(A)
如果并發事務執行的schedule效果與串行執行的schedule（serial schedule）等價，就可以滿足serializability。一個schedule不斷調換讀寫操作的順序，總會變成一個serializable schedule，但是有的調換可能導緻事務執行的結果不一樣。一個schedule中，相鄰的兩個操作調換位置導緻事務結果變化，那麼這兩個操作就是沖突的。沖突需要同時滿足以下條件：
1.這兩個操作來自不同僚務
2.至少有一個是寫操作
3.操作對象相同
是以常見的沖突包括：
• 讀寫沖突。事務先A讀取某行資料、事務B後修改該行資料，和事務B先修改某行事務、事務A後讀該行記錄兩種schedule。事務A讀到的結果不同。這種沖突可能會導緻不可重複讀異象和髒讀異象。
• 寫讀沖突。與讀寫沖突産生的原因相同。這種沖突可能會導緻髒讀異象。
• 寫寫沖突。兩個操作先後寫一個對象，後一個操作的結果決定了寫入的最終結果。這種沖突可能會導緻更新丢失異象。
資料庫隻要保證，并發事務的schedule，保持沖突操作的執行順序不變，隻調換不沖突的操作，可以成為serial schedule，就可以認為它們等價。這種等價判斷方式叫做conflict equivalent：兩個schedule的沖突操作順序相同。
例如下圖的例子，T1 write(A)與T3 read(A)沖突，且T1先于T3發生。T1 read(B)和 T2 write(B)沖突，且T2先于T1，是以左圖事務執行的schedule，與T2,T1,T3串行執行的serial schedule（右圖） 等價。左圖的執行順序滿足conflict serializablity。
再分析一個反例：T1 read(A)與T2 write(A)沖突且T1先于T2，T2 write(A)與T2 write(A)沖突且T2先于T1。下圖這個個schedule無法與任何一個serial schedule等價，是一個不滿足conflict serializablity的執行順序，會造成更新丢失的異象。
總體來說，serializability是比較嚴格的要求，為了提高資料庫系統的并發性能，很多使用者願意去降低隔離性的要求以尋求更好的性能。資料庫系統往往會實作多種隔離級别，供使用者靈活選擇，關于事務隔離級别，可以參看這篇文章。
并發控制的要求清楚了，如何實作呢？後文将依據沖突檢測的樂觀程度，一一介紹并發控制常見的實作方法。
2.基于兩階段鎖的并發控制
2.1 2PL
既然要保證操作按正确的順序執行，最容易想到的方法就是加鎖保護通路對象。資料庫系統的鎖管理器子產品，專門負責給通路對象加鎖和釋放鎖，保證隻有持有鎖的事務，才能操作相應的對象。鎖可以分為兩類：S-Lock和X-Lock，S-Lock是讀請求使用的共享鎖，X-Lock是寫請求使用的排他鎖。它們的相容性如下：操作同一個對象，隻有兩個讀請求互相相容，可以同時執行，讀寫和寫寫操作都會因為鎖沖突而串行執行。
2PL（Two-phase locking）是資料庫最常見的基于鎖的并發控制協定，顧名思義，它包含兩個階段：
• 階段一：Growing，事務向鎖管理器請求它需要的所有鎖（存在加鎖失敗的可能）。
• 階段二：Shrinking，事務釋放Growing階段擷取的鎖，不允許再請求新鎖。
為什麼加鎖和放鎖要泾渭分明地分為兩個階段呢？
2PL并發控制目的是為了達到serializable，如果并發控制不事先将所有需要的鎖申請好，而是釋放鎖後，還允許再次申請鎖，可能出現事務内兩次操作同一對象之間，其它事務修改這一對象（如下圖所示），進而無法達到conflict serializable，出現不一緻的現象（下面的例子是lost update）。
2PL可以保證conflict serializability，因為事務必須拿到所有需要的鎖才能執行。例如正在執行的事務A與事務B沖突，事務B要麼已經執行完，要麼還在等待。是以那些沖突操作的執行順序，與BA或AB串行執行時沖突操作執行順序一緻。
是以，資料庫隻要采用2PL就能保證一緻性和隔離性了嗎？來看一下這個例子：
以上執行順序是符合2PL的，但T2讀到了未送出的資料。如果此時T1復原，則會引發級聯復原（T1的更改，不能被任何事務看到）。是以，資料庫往往使用的是加強版的S(trong)S(trict)2PL，它相較于2PL有一點不同：shrinking階段，隻能在事務結束後再釋放鎖，完全杜絕了事務未送出的資料被讀到。
2.2 死鎖處理
并發事務加鎖放鎖必然繞不開一個問題--死鎖：事務1持有A鎖等B鎖，事務2持有B鎖等A鎖。目前解決死鎖問題有兩種方案：
• Deadlock Detection：
資料庫系統根據waits-for圖記錄事務的等待關系，其中點代表事務，有向邊代表事務在等待另一個事務放鎖。當waits-for圖出現環時，代表死鎖出現了。系統背景會定時檢測waits-for圖，如果發現環，則需要選擇一個合适的事務abort。
• Deadlock Prevention：
當事務去請求一個已經被持有的鎖時，資料庫系統為防止死鎖，殺死其中一個事務（一般持續越久的事務，保留的優先級越高）。這種防患于未然的方法不需要waits-for圖，但提高了事務被殺死的比率。
2.3 意向鎖
如果隻有行鎖，那麼事務要更新一億條記錄，需要擷取一億個行鎖，将占用大量的記憶體資源。我們知道鎖是用來保護資料庫内部通路對象的，這些對象根據大小可能是：屬性（Attribute）、記錄（Tuple）、頁面（Page）、表（Table），相應的鎖可分為行鎖、頁面鎖、表鎖（沒人實作屬性鎖，對于OLTP資料庫，最小的操作單元是行）。對于事務來講，獲得最少量的鎖當然是最好的，比如更新一億條記錄，或許加一個表鎖就足夠了。
層次越高的鎖（如表鎖），可以有效減少對資源的占用，顯著減少鎖檢查的次數，但會嚴重限制并發。層次越低的鎖（如行鎖），有利于并發執行，但在事務請求對象多的情況下，需要大量的鎖檢查。資料庫系統為了解決高層次鎖限制并發的問題，引入了意向（Intention）鎖的概念：
• Intention-Shared (IS)：表明其内部一個或多個對象被S-Lock保護，例如某表加IS，表中至少一行被S-Lock保護。
• Intention-Exclusive (IX)：表明其内部一個或多個對象被X-Lock保護。例如某表加IX，表中至少一行被X-Lock保護。
• Shared+Intention-Exclusive (SIX)：表明内部至少一個對象被X-Lock保護，并且自身被S-Lock保護。例如某個操作要全表掃描，并更改表中幾行，可以給表加SIX。讀者可以思考一下，為啥沒有XIX或XIS
意向鎖和普通鎖的相容關系如下所示：
意向鎖的好處在于：當表加了IX，意味着表中有行正在修改。
（1）這時對表發起DDL操作，需要請求表的X鎖，那麼看到表持有IX就直接等待了，而不用逐個檢查表内的行是否持有行鎖，有效減少了檢查開銷。
（2）這時有别的讀寫事務過來，由于表加的是IX而非X，并不會阻止對行的讀寫請求（先在表上加IX，再去記錄上加S/X），事務如果沒有涉及已經加了X鎖的行，則可以正常執行，增大了系統的并發度。
3.基于Timing Order（T/O）的并發控制
為每個事務配置設定timestamp，并以此決定事務執行順序。當事務1的timestamp小于事務2時，資料庫系統要保證事務1先于事務2執行。timestamp配置設定的方式包括：
（1）實體時鐘；
（2）邏輯時鐘；
（2）混合時鐘。
3.1 Basic T/O
基于T/O的并發控制，讀寫不需加鎖， 每行記錄都标記了最後修改和讀取它的事務的timestamp。當事務的timestamp小于記錄的timestamp時（不能讀到”未來的”資料），需要abort後重新執行。假設記錄X上标記了讀寫兩個timestamp：WTS(X)和RTS(X)，事務的timestamp為TTS，可見性判斷如下：
讀：
• TTS < WTS(X)：該對象對該事務不可見，abort事務，取一個新timestamp重新開始。
• TTS > WTS(X)：該對象對事務可見，更新RTS(X) = max(TTS,RTS(X))。為了滿足repeatable read，事務複制X的值。
• 為了防止讀到髒資料，可以在記錄上做特殊标記，讀請求需等待事務送出後再去讀。
寫：
• TTS < WTS(X) || TTS < RTS(X)：abort事務，重新開始。
• TTS > WTS(X) && TTS > RTS(X)： 事務更新X，WTS(X) = TTS。
這裡之是以要求TTS > RTS(X)，是為了防止如下情況：讀請求的時間戳為rts，已經讀過X，時間戳設為RTS(X)=rts，如果新事務的TTS < RTS(X)，并且更新成功，則rts讀請求再來讀一次就看到新的更改了，違反了repeatable read，是以這是為了避免讀寫沖突。記錄上存儲了最後的讀寫時間，可以保證conflict serializable
這種方式也能避免write skew，例如：初始狀态，X和Y兩條記錄，X=-3，Y=5，X+Y >0，RTS(X)=RTS(Y)=WTS(X)=WTS(Y)=0。事務T1的時間戳為TTS1=1，事務T2的時間戳TTS2=2。
它缺陷包括：
• 長事務容易餓死，因為長事務的timestamp偏小，大機率會在執行一段時間後讀到更新的資料，導緻abort。
• 讀操作也會産生寫（寫RTS）。
4.基于Validation（OCC）的并發控制
執行過程中，每個事務維護自己的寫操作（Basic T/O在事務執行過程中寫就将資料寫入DB）和相應的RTS/WTS，送出時判斷自己的更改是否和資料庫中已存在的資料沖突，如果不沖突才寫入DB。OCC分為三個階段：
• Read & Write Phase：即讀寫階段，事務維護讀的結果和即将送出的更改，以及寫入記錄的RTS和WTS。
• Validation Phase：檢查事務是否與資料庫中的資料沖突。
• Write Phase：不沖突就寫入，沖突就abort,restart。
Read & Write Phase結束，進入Validation Phase相當于事務準備完成，進入送出階段了，進入Validation Phase的時間被選做記錄行的時間戳，來定序。不用事務開始時間是因為：事務執行時間可能較長，導緻後開始的事務可能先送出，這會加大事務沖突的機率，較小時間戳的事務後寫入資料庫，肯定會abort。
Validation過程
假設目前隻有兩個事務T1和T2，并修改了相同資料行，T1的時間戳 < T2的時間戳（即validation順序：T1 < T2，對使用者而言，T1先發生于T2），則有如下情況：
（1）T1在validate階段，T2還在Read & Write Phase。此時隻要T1和T2已經發生的讀寫沒有沖突，就可以送出。
• 如果WS(T1) ∩ (RS(T2) ∪ WS(T2)) = ∅，說明T2和T1寫的記錄無沖突，validation通過，可以寫入。
• 否則，T2與T1之間存在讀寫沖突或寫寫沖突，T1需要復原。讀寫沖突：T2讀到了T1寫之前的版本，T1送出後，它可能讀到T1寫的版本，不可重複讀。寫寫沖突：T2有可能在舊版本基礎上更新，再次寫入，造成T1的更新丢失。
（2）T1完成validate階段，進入write階段直到送出完成，這已經是不可逆的了。T2在T1進入write phase之前的讀寫，肯定和T1的操作不沖突（因為T1 validation通過了）。T2之後繼續的讀寫操作，有可能沖突與T1要送出的操作，是以T2進入validate階段：
• 如果WS(T1) ∩ RS(T2)= ∅，說明T2沒讀到T1寫的記錄，validation通過，T2可以寫入。（為什麼不驗證WS(T2)了呢？WS(T1)已經送出了，且它的時間戳小于WS(T2)，WS(T2)裡之前的一部分肯定沒有沖突，之後的一部分，因為沒有讀過T1的寫入的對象，寫進去也沒問題，不會覆寫WS（T1）的寫）
• 否則，T2與T1之間存在讀寫沖突和寫寫沖突，T2需要復原。讀寫沖突：T2讀到了T1寫之前的版本，T1送出後，它可能讀到T1寫的版本，不可重複讀。寫寫沖突：T2有可能在舊版本基礎上更新，再次寫入，造成T1的更新丢失。
5.基于MVCC的并發控制
資料庫維護了一條記錄的多個實體版本。事務寫入時，建立寫入資料的新版本，讀請求依據事務/語句開始時的快照資訊，擷取當時已經存在的最新版本資料。它帶來的最直接的好處是：寫不阻塞讀，讀也不阻塞寫，讀請求永遠不會是以沖突失敗（例如單版本T/O）或者等待（例如單版本2PL）。對資料庫請求來說，讀請求往往多于寫請求。主流的資料庫幾乎都采用了這項優化技術。
MVCC是讀和寫請求的優化技術，沒有完全解決資料庫并發問題，它需要與前述的幾種并發控制技術組合，才能提供完整的并發控制能力。常見的并發控制技術種類包括：MV-2PL，MV-T/O和MV-OCC，它們的特點如下表：
MVCC還有兩個關鍵點需要考慮：多版本資料的存儲和多餘多版本資料的回收。
多版本資料存儲方式，大緻可以分為兩類：
（1）Append only的方式，新舊版本存儲在同一個表空間，例如基于LSM-Tree的存儲引擎。
（2）主表空間記錄最新版本資料，前鏡像記錄在其它表空間或資料段，例如InnoDB的多版本資訊記錄在undo log。多版本資料回收又稱為垃圾回收（GC），那些沒有機會再被任何讀請求擷取的舊版本記錄，應該被及時删除。
6.總結
本文依據沖突處理的時機（樂觀程度），依次介紹了基于鎖（在事務開始前預防沖突）、基于T/O（在事務執行中判斷沖突）和基于Validation（在事務送出時驗證沖突）的事務并發控制機制。不同的實作适用于不同的workload，并發沖突小的workload，當然适合更樂觀的并發控制方式。而MVCC可以解決隻讀事務和讀寫事務之間互相阻塞的問題，提高了事務的并發讀，被大多數主流資料庫系統采用。