本文我們將繼續討論實現事務的不同方法。
與教科書直接列出實現方法不同，本文將會由淺入深地介紹加鎖實現機制和時間戳機制這兩種不同實現方法的形成過程。
加鎖實現機制 (Lock-based protocols)
實現事務隔離的最簡單方法就是在對任何數據進行讀寫時，都保證互斥性，即當一個事務在讀寫數據時，保證其他事務不能對數據進行修改。最常見的實現就是對數據進行加鎖 (lock)。
假設，我們對數據庫設置了一把唯一的全局鎖：任何事務需要執行時，都需要獲取這把鎖。那麼，全局鎖就保證了事務之間的有序性，從而保證了 ACID 屬性。因此，從正確性角度考慮， 全局鎖是可行的方法。但全局鎖的缺點也顯而易見，事務之間，即使讀寫的數據完全無關，也沒有任何並行，這對性能的影響不言而喻。
有什麼辦法可以改進嗎？一個方法是把鎖的粒度變細，即僅對要讀寫的數據加鎖而非全局鎖。通過加鎖來確保在同一時間，只有獲得鎖的事務可以對數據進行處理。
另一個方法是定義不同類型的鎖。因為並不是所有的事務對數據都是寫操作，如果兩個事務同時對某一數據進行讀操作，它們之間並不需要互斥。因此，我們可以通過定義不同類型的鎖，以及它們之間的兼容程度來獲得更細粒度的控制。
通常，我們定義兩種類型的鎖：1）共享鎖 (share-mode lock; S-lock)，即當事務獲得了某個數據的共享鎖，它僅能對該數據進行讀操作，但不能寫，共享鎖有時候也被稱為讀鎖。2）獨佔鎖 (exclusive-mode lock; X-lock)，即當事務獲得了某個數據的獨佔鎖，它可以對數據進行讀和寫操作，獨佔鎖也常被叫做寫鎖。共享鎖和獨佔鎖的兼容模式如下：
S-lockX-lockS-lock兼容不兼容X-lock不兼容不兼容
僅 S-lock 之間互相兼容，只有當多個事務同時持有共享鎖時才能同時對數據進行讀操作。
定義了鎖之後，在事務中對數據的操作必須持有相應的鎖。但是問題又來了，什麼時候該加鎖，什麼時候又該釋放鎖呢？是否應該在事務的開始就對所有的數據都加鎖？(這顯然不是一個高效的辦法，甚至在事務開始的時候，我們可能並不知道要操作哪些數據)。
我們可以先從簡單的情況來嘗試，比如只在讀取和修改數據的時候申請相對應的鎖。如下圖所示：
(圖 1：T1)
(圖 2: T2)
圖 1 和圖 2 分別顯示了兩個事務對賬號 A 和 B 進行操作 (假設 A 初始值是 100；B 是 200)，事務 T1 用了 X-lock，因為需要對數據進行修改， 而 T2 僅需要使用 S-lock，因為只是讀取數據。乍看之下，好像沒有問題。無論是 T1 先執行，還是 T2 先執行，T2 中 display(A+B) 都會是 300。但是，如果 T1 和 T2 的執行順序如下：
(圖 3：T1 + T2）
這時候，T2 中的 display(A+B) 的值就是 250，這是錯誤的數據。問題出在哪呢？T1 中釋放對 B 的 X-lock 過早，使得 T2 獲得了一個不正確的數值。既然原因是釋放過早，那能不能通過延遲釋放鎖來解決這個問題。我們把 T1 和 T2 分別改寫為 T3 和 T4(唯一的區別就是延緩了鎖的釋放到最後)，如下圖所示
(圖 4: T3 + T4)
經過驗證，這種情況下，無論 T3 和 T4 如何交互，都不再會出現 display(A+B) 等於 250 的錯誤了。把釋放鎖放在事務的最後是否就解決了所有問題呢？答案是否定的。它確實解決了數據讀取不正確的問題，但也同時引入了新問題。
(圖 5: T3 + T4)
T3 和 T4 分別獲取了對 B 和對 A 的鎖並且相互請求對 A 和對 B 的鎖。相信大家都看出來了，這導致了死鎖 (dead lock)。這裡就不具體介紹死鎖的檢查和破壞機制了 (詳情參見操作系統課)，你只需要知道，數據庫系統是可以發現死鎖的。解決方法也簡單，選擇其中一個參與的事務，回滾並放棄執行 (如果一個不行，就兩個)。相對於錯誤的數據，死鎖顯然是我們更願意接受的，所謂兩害取其輕。
我們引入了第一個加鎖實現：兩階段加鎖機制 (Two-phase locking protocol)。它要求事務在加鎖的過程中遵循下面兩步：
1）獲取鎖階段 (growing phase)：在這個過程中，事務只能不斷地獲取新的鎖，但不能釋放鎖。
2）釋放鎖階段 (shrinking phase)：在這個過程中，事務只能逐漸釋放鎖，並且無權再獲取新的鎖。
重要的事情說三遍：千萬不要和兩階段提交 (Two-phase commit (2PC)) 搞混；千萬不要和兩階段提交搞混；千萬不要和兩階段提交搞混。兩階段提交是針對分佈式事務的概念，我會在以後的文章中詳細講。
上述的 T3 和 T4 就是遵循兩階段加鎖機制，因此數據的正確性是可以保證的。但就像上述所說，兩階段加鎖不能避免死鎖，依然需要數據系統來檢測並破壞死鎖。並且，基本款的兩階段提交還會遇到連鎖回滾 (cascading rollback)。
(圖 6: T5 + T6 + T7)
當 T5 執行到 bad thing happen 時，導致出錯，那 T6 和 T7 都會需要被回滾。為了避免連鎖回滾，我們可以引入兩階段提交的升級版：嚴格的兩階段加鎖 (strict two-phase locking protocol) 。** 除了需要遵循加鎖和釋放鎖的兩階段外，它還規定，對於獨佔鎖 (X-lock) 必須等到事務結束時才釋放。這個規定避免了其他事務對未提交的數據進行讀寫操作，因此也避免了連鎖回滾。另一個更嚴格的升級本叫做更嚴格的兩階段加鎖 (rigorous two-phase locking protocol)，** 規定了所有獲得的鎖都得等到事務結束時才釋放。
以上就是關於加鎖的實現，如果我們總結一下，主要是介紹了這些內容：
1）引入共享鎖 (S-lock) 和獨佔鎖 (X-lock) 來獲得對數據細粒度的控制；
2）引入兩階段加鎖 (Two-phase locking protocol) 來保證數據的正確性；
3）兩階段加鎖不能避免死鎖，依然需要數據庫系統來檢查並破壞死鎖，破壞死鎖可以通過回滾相關的事務來進行；
4）兩階段加鎖的兩個升級版本：(更) 嚴格的兩階段加鎖 (rigorous/strict two-phase locking) 通過規定把釋放鎖等到事務結束來避免連鎖回滾 (cascading rollback)。
時間戳機制 (Timestamp-based protocols)
加鎖實現是通過比較哪個事務先獲得鎖來決定事務執行的順序，以此來保證事務之間的有序性。那除了鎖之外，有沒有其他方式來衡量先後呢？大家可能都已經想到了，時間戳 (Timestamp)。如果每個事務開啟的時候，系統可以記錄這個事務開啟的時間 TS(Ti)，記為事務 Ti 的時間，通過比較不同事務的時間戳，我們就能給事務排序了。
如果兩個事務的時間戳一模一樣呢？其實，有個方法來避免這種情況，通過一個統一的事務管理機制來分發時間戳：每一個事務，不能自行根據執行時間來得到時間戳，而是必須調用一個方法 (這個方法可以是由單個線程或者進程管理的) 來獲得。這個線程就能夠保證事務之間的時間戳總有先後關係。
如果你還要考慮極限情況，例如某個方法性能特別高，可以在一個納秒裡面連續發送兩個時間戳。面對這種極限情況，我們的解決方法是不必用真實的時間來表示時間戳，可以用數字計數 (logical counter) 來表示相對時間。管理線程只需維護一個計數，在分發計數的同時不斷自增即可。
我們可以通過比較事務的時間戳來保證事務之間的有序性。假定 Ti 和 Tj 的時間戳分別為 TS(Ti) 及 TS(Tj)。如果 TS(Ti)
如何實現呢？首先，我們引入兩個概念：
1）W-timestamp(A): 記錄對於數據 A，最近一次被某個事務修改的時間戳。
2）R-timestamp(A): 記錄對於數據 A，最近一次被某個事務讀取的時間戳。
一旦有一個更新的事務成功地對數據進行讀取，相對應的讀寫時間戳就會被更新。
下面，我們給出用時間戳機制實現事務的定義：
對於事務 Ti 要讀取數據 A read(A):
- 如果 TS(Ti) < W-timestamp(A)，說明 A 被一個 TS 比 Ti 更大的事務改寫過，但 Ti 只能讀取比自身 TS 小的數據。因此 Ti 的讀取請求會被拒絕，Ti 會被回滾。
- 如果 TS(Ti) > W-timestamp(A)，說明 A 最近一次被修改小於 TS(Ti)，因此讀取成功，並且，R-timestamp(A) 被改寫為 TS(Ti)。
對於事務 Ti 要修改數據 A write(A):
- 如果 TS(Ti) < R-timestamp(A)，說明 A 已經被一個更大 TS 的事務讀取了，Ti 對 A 的修改就沒有意義了，因此 Ti 的修改請求會被拒絕，Ti 會被回滾。
- 如果 TS(Ti) < W-timestamp(A)，說明 A 已經被一個更大 TS 的事務修改了，Ti 對 A 的修改也沒有意義了，因此 Ti 的修改請求會被拒絕，Ti 會被回滾。
- 其他情況下，Ti 的修改會被接受，同時 W-timestamp(A) 會被改寫為 TS(Ti)。
一旦一個事務因為任何原因被回滾，再次重新執行時，會被系統分配一個新的 TS。
通過上述規則，系統就可以保證對於任意 Ti 和 Tj，如果 TS(Ti)
假定下面兩個事務 T1 和 T2，並且 TS(T1) < TS(T2)。
(圖 7: T1 + T2)
那麼如下的調度根據時間戳機制就是合理的調度
(圖 8: T1 + T2 調度)
兩邊的 display(A+B) 都會返回正確的數據。時間戳機制保證了有序性，因為讀寫都會根據事務的時間戳進行比較再回滾。這種機制同時也避免了死鎖，雖然有可能導致飢餓 (starvation)：某些運氣不好的長事務因為不停地失敗被回滾然後重試。
有什麼方法能夠讓時間戳機制進一步提高併發性？
(圖 9: T3 + T4)
我們假定 TS(T3) < TS(T4)。首先，T3 的 read(A) 會成功。其次，T4 的 write(A) 也會成功，因為 T4 的時間戳大於 T3。最後，當 T3 試圖 write(A) 時會失敗，因為 TS(T3) < W-timestamp(A) = TS(4)。因此根據時間戳機制，T3 的 write(A) 會失敗並被回滾。但事實上，即使不回滾 T3 也不會有問題。因為 T4 已經修改了 A 的值，那麼 T3 的修改從時間戳角度來看，已經沒有意義，因為不會被其他事務讀取：任何 TS 小於 T4 對 A 的讀取都會被拒絕然後回滾 (因為 TS(Ti) < W-timestamp(A) = TS(T4))；而任何 TS 大於 T4 對 A 的讀取都會讀取 T4 修改後的 A 值。利用這個發現，我們可以改進時間戳機制來使得無意義的修改操作可以直接被忽略。
這個改進策略被稱為托馬斯的修改規則 (Thomas’ write rule): 假設 Ti 要 write(A):
- 如果 TS(Ti) < R-timestamp(A)，說明 A 已經被一個更大 TS 的事務讀取了，Ti 對 A 的修改就沒有意義了，因此 Ti 的修改請求會被拒絕，Ti 會被回滾。
- 如果 TS(Ti) < W-timestamp(A)，說明 Ti 的修改沒有意義，因此這個修改操作會被忽略。
- 其他情況下，Ti 的修改會被接受，同時 W-timestamp(A) 會被改寫為 TS(Ti)。
可見，僅第二條規則被改進了。
總結
這篇文章主要介紹了兩類對事務隔離的實現，分別是加鎖實現機制和時間戳機制。
在加鎖實現機制中，介紹了兩階段加鎖 (Two-phase locking protocol)，通過將事務劃分成獲取鎖階段和釋放鎖階段來保證數據的正確性。同時引入了改進機制，嚴格的兩階段加鎖 (rigorous/strict two-phase locking protocol) 來避免連鎖回滾。兩階段加鎖雖然能夠保證正確性，卻無法避免死鎖。因此，需要數據庫系統能夠檢查並破壞死鎖。
時間戳機制是通過對每個事務定義時間戳，以及對讀寫數據記錄時間戳來保證正確性。時間戳機制本身也避免了死鎖，托馬斯的修改規則可以進一步優化時間戳機制。但這兩種機制並不是目前常見的實現，下一篇文章，我們會介紹更主流的多版本併發控制 (MVCC)。
