[[323145]]

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