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可以解決只讀事務和讀寫事務之間相互阻塞的問題，提高了事務的併發讀，被大多數主流數據庫系統採用。
