01數據庫并發控制的作用

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中，相鄰的兩個操作調換位置導致事務結果變化，那么這兩個操作就是沖突的。沖突需要同時滿足以下條件：

• 這兩個操作來自不同事務
• 至少有一個是寫操作
• 操作對象相同

因此常見的沖突包括：

• 讀寫沖突。事務先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是比較嚴格的要求，為了提高數據庫系統的并發性能，很多用戶愿意去降低隔離性的要求以尋求更好的性能。數據庫系統往往會實現多種隔離級別，供用戶靈活選擇，關于事務隔離級別，可以參看這篇文章。

并發控制的要求清楚了，如何實現呢？后文將依據沖突檢測的樂觀程度，一一介紹并發控制常見的實現方法。

02基于兩階段鎖的并發控制

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鎖的行，則可以正常執行，增大了系統的并發度。

3303基于Timing Order（T/O）的并發控制

為每個事務分配timestamp，并以此決定事務執行順序。當事務1的timestamp小于事務2時，數據庫系統要保證事務1先于事務2執行。timestamp分配的方式包括：（1）物理時鐘；（2）邏輯時鐘；（3）混合時鐘。

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）。

04基于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的更新丟失。

05基于MVCC的并發控制

數據庫維護了一條記錄的多個物理版本。事務寫入時，創建寫入數據的新版本，讀請求依據事務/語句開始時的快照信息，獲取當時已經存在的最新版本數據。它帶來的最直接的好處是：寫不阻塞讀，讀也不阻塞寫，讀請求永遠不會因此沖突失敗（例如單版本T/O）或者等待（例如單版本2PL）。對數據庫請求來說，讀請求往往多于寫請求。主流的數據庫幾乎都采用了這項優化技術。

MVCC是讀和寫請求的優化技術，沒有完全解決數據庫并發問題，它需要與前述的幾種并發控制技術組合，才能提供完整的并發控制能力。常見的并發控制技術種類包括：MV-2PL，MV-T/O和MV-OCC，它們的特點如下表：

MVCC還有兩個關鍵點需要考慮：多版本數據的存儲和多余多版本數據的回收。

多版本數據存儲方式，大致可以分為兩類：

（1）Append only的方式，新舊版本存儲在同一個表空間，例如基于LSM-Tree的存儲引擎。

（2）主表空間記錄最新版本數據，前鏡像記錄在其它表空間或數據段，例如InnoDB的多版本信息記錄在undo log。多版本數據回收又稱為垃圾回收（GC），那些沒有機會再被任何讀請求獲取的舊版本記錄，應該被及時刪除。

06總結

本文依據沖突處理的時機（樂觀程度），依次介紹了基于鎖（在事務開始前預防沖突）、基于T/O（在事務執行中判斷沖突）和基于Validation（在事務提交時驗證沖突）的事務并發控制機制。

不同的實現適用于不同的workload，并發沖突小的workload，當然適合更樂觀的并發控制方式。而MVCC可以解決只讀事務和讀寫事務之間相互阻塞的問題，提高了事務的并發讀，被大多數主流數據庫系統采用。

原文鏈接
本文為云棲社區原創內容，未經允許不得轉載。

總結

以上是生活随笔為你收集整理的一篇讲透如何理解数据库并发控制的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。