資料庫管理系統(一): 並發控制簡介

在多用戶使用的資料庫情境中，為了確保每個用戶在讀取或者修改數據時一致，且儘可能提高處理並發請求的能力，資料庫通常需要一種機制，叫做並發控制 (Concurrency Control).

事務 (Transaction)，是連續的對資料庫操作的集合，對於一個事務中的所有資料庫操作：要不全部成功，不要全部失敗。也就是說，如果事務A中寫操作a成功了，但是寫操作b失敗了，資料庫會拒絕a操作的提交。並發控制是和事務緊密相關的概念，並發控制通常指的是對事務的並發控制。事務能保證用戶操作意圖的完整性。例如典型的一個情景：從小王賬戶轉20塊錢去小劉的賬戶。這裡牽扯兩個對資料庫數據的修改，小王賬戶 - 20， 小劉賬戶 + 20。如果這兩個修改沒有在一個事務中，也就是沒有一個事務約束兩個操作同時成功，那麼很可能出現諸如小王賬戶扣了錢，但是小劉沒有收到錢 (更新失敗)的問題。

並發控制的有兩種實現方法：

1. 基於鎖

2. 基於時間戳

基於鎖的原理如下：

一個事務擁有兩個階段，增長階段 (growing phrase) 和收縮階段 (Shrinking).

在增長階段，事務可以嘗試獲取所有涉及記錄的鎖，這樣就能保證暫時的排他的擁有並修改數據。如果另一事務需要讀或者寫已經被鎖住的記錄，那麼該事務就會被阻塞。這樣持有鎖的事務就保證了當前自己對記錄的讀取和修改，在事務的整個周期內都是一致的，也就是讀到的記錄不會被其它事務篡改，而寫過的記錄不會被其它事務重新覆蓋。

在收縮階段，事務不再獲取鎖，而是釋放持有的所有鎖。

這一版本的並發控制有死鎖的問題。

例如：

txn #1 (growing) lock A lock B read A write B (shrinking) unlock A unlock B commit

txn #2 (growing) lock B lock A write A read B (shrinking) unlock B unlock A commit

基於時間戳的原理如下：

資料庫和事務通過時間戳來監測不一致的讀寫，並相應的中止受到干擾的事務。

每個事務剛開始都會獲得一個時間戳，資料庫對於存儲的每一個記錄，都有一個上一次事務讀寫的時間戳的標記。例如：

讀時間戳 寫時間戳

記錄 A 10000 10000

記錄 B 10000 10000

事務1時間戳10001，事務2時間戳10005。

剛開始，記錄A, B的時間戳記錄都是10000. 事務1開始後，假定讀了A，寫了B，則此時:

讀時間戳 寫時間戳

記錄 A 10001 10000

記錄 B 10000 10001

如果這時事務1暫時在處理拿到的數據，沒有進一步資料庫操作，而事務2寫了記錄A，則:

讀時間戳 寫時間戳

記錄 A 10001 10005

記錄 B 10000 10001

記錄A的寫時間戳被改變了。假定事務1之後嘗試寫記錄A，會發現記錄A具有「未來」的時間戳，說明記錄A被新的事務修改過了。此時事務1知道自己的操作收到了影響，因此事務1可以終止。

在理想情況下，資料庫應該實現事務的串列化(Serializability)。 串列化是事務隔離的一種程度，是一種最高的程度，在這種程度下事務之間沒有影響。所謂事務隔離，指的是事務之間在執行的過程中相互影響的程度。這裡有兩個概念，一個是事務隔離程度 (Isolation level)，一種是幫助定義隔離程度的異常 (Anomaly)

首先總結一下四種事務之間影響的異常：

1. 臟讀 (Dirty Read). 事務1讀了事務2沒有提交的寫。這個異常不好之處在於事務1將自己依賴於事務2之上。因為事務1讀了事務2的寫，所以事務1的成功也依賴於事務2的成功。如果事務1失敗了，那麼事務2所看到的修改其實是不存在的，那麼如果事務2成功了，那麼問題就發生了。

2. 不可重複的讀 (Unrepeatable Read). 事務1在time 1讀了數據A，然後事務2在time 2修改或者刪除了數據A， 然後提交成功，事務1回來在time 3讀到A是一個不同的版本，也就是事務1讀了不是自己修改的數據。這一個現象在並發中非常常見，例如兩個線程共享一個沒有鎖保護的變數。顯然這種異常會影響程序的正常運作。

3. 幻象讀 (Phantom Read). 幻想讀是不可重複讀的一種特殊例子，也就是事務1讀到事務2新加入的數據。在不可重複讀中，事務1對數據A的讀受到了影響。在幻想讀中，事務1對某一些數據的讀會受到影響。比如說，如果要消除不可重複讀，那麼可以讓事務1在讀數據的時候先拿到鎖，然後在提交時釋放鎖。但是，如果事務1在做一個範圍查詢，那麼所以事務1能拿到已有的數據的所有鎖，但是事務2如果新插入一個數據，事務1是不知道的。那麼事務1第二次做同樣的範圍查詢時，還是能看到上一次沒見過的數據。解決這個異常的方法之一就是支持範圍鎖。

4. 更新丟失 (Lost Update). 基於時間戳的實現版本帶來的問題，略過....

然後是隔離程度:

1. 串列化。確定異常1，2，3, 4 都不會出現。也就是很安全。

2. 可重複讀 (Repeatable Read)。幻想讀可能出現。

3. 提交的讀 (Read Committed)。幻想讀和不可重複讀可能出現。

4. 未提交的讀 (Read Uncommited)。所有異常都可以出現。這裡等於完全沒有並發控制。

上面提到的四種隔離程度的定義來自於基於鎖的並發控制。後來出現的基於時間戳的實現方法增加了新的可能的異常，所以學界又定義了多兩種隔離程度：一個是Cursor Stability，一個是Snapshot Isolation，在此暫時不展開了。總結一下，就是串列化的隔離程度最高，但是資料庫一般默認使用的隔離程度比較低，除非單獨設定。

在業界常見的資料庫里，沒有會使用上面提到過的簡單的並發控制的演算法。為了提高並發處理能力，同時保證良好的隔離程度，學界提出了多個複雜的演算法，例如多版本並發控制 (Multiversion Concurrency Control)。

多版本並發控制及其它高級演算法留在以後的文章解釋。

參考資料：

1. Isolation Level in Database Engine.

2. Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth ONeil, Patrick ONeil, A Critique of ANSI SQL Isolation Level, ACM SIGMOD Record 24 (2), 1-10, May 1995.