摘要：關于串行化與一致性的關系數據庫并發控制的基本目標是確保事務的并發執行不會導致數據庫一致性的丟失。該請求發送給并發控制管理器，只有并發控制管理器授予所需鎖后，事務才能繼續其操作。

全文主要參考數據庫系統概念一書以及mooc上戰德臣老師的數據庫課程
　　事務最基本的特性之一是隔離性，當數據庫中有多個事務并發執行的時候，隔離性不一定能保持。為了保持事務的隔離性，系統必須對并發事務之間的相互作用加以控制，這是被稱為并發控制機制來實現的。本文講述的機制都是保證調度是可串行化的。最常用機制有兩階段封鎖和快照隔離。

　　關于串行化與一致性的關系：數據庫并發控制的基本目標是確保事務的并發執行不會導致數據庫一致性的丟失。可以利用可串行性概念來達到這一目標，因為所有可串行化的調度都能保持數據庫的一致性。然而，并非所有保證數據庫一致性的調度都是可串行化的。(也存在著允許非可串行化調度的并發控制機制，詳見數據庫系統概念25章)

　　確保串行化的方法之一就是要求對數據項的訪問以互斥的方式進行。也就是說當一個事務訪問某個數據項時，其他任何=事務都不能修改該數據項。實現該需求最常用的方法是只允許事務訪問當前該事務持有該數據項的鎖的數據項。

　　給數據項加鎖的方式有多種，這一節只考慮兩種(這兩種也正是MySQL默認引擎(InnoDB)在行級鎖定時所使用的)

共享鎖：如果事務Ti獲得了數據項Q的共享型鎖(記為S)，則Ti可讀但不能寫Q。

排他鎖：如果事務Ti獲得了數據項Q的排他型鎖(記為X)，則Ti既可讀又可寫Q。

???????每個事務都要根據將對數據項Q進行的操作類型申請適當的鎖。該請求發送給并發控制管理器，只有并發控制管理器授予所需鎖后，事務才能繼續其操作。
　　相容：假設事務Ti請求對數據項Q加A類型的鎖，而事務Tj(i不等于j)已在Q上擁有B類型的鎖。如果事務Ti仍能立即獲得在數據項Q上A類型的鎖，則說A類型的鎖和B類型的鎖相容。相容矩陣如下所示：
?

　　即共享型鎖與共享型鎖相容，而與排他型鎖不相容。在任何時候，一個具體的數據項上可能同時有(被不同的事務持有的)多個共享鎖。如事務在訪問一數據項時而在數據項上已經存在可不相容類型的鎖，那么只能等待該數據上所有不相容的鎖被釋放才能獲得鎖從而對數據項進行訪問。
　　注意：一個事務只要還在訪問一個數據項，那么它就必須擁有該數據項上的鎖。另外，讓事務對一個數據項作最后一次訪問后立即釋放該數據項上的鎖也未必是可取的，因為這可能破壞串行化。如下圖例子所示，事務T2看到了不一致的狀態(A+B的值)，而串行化就是為了事務開始和結束之間的中間狀態不會被其他事務看到。所以我們下面的討論都是建立在不會在結束訪問一個數據項后立即釋放鎖的情況下的(如兩階段鎖協議下的)。這也就會導致了死鎖發生的可能性的存在，但死鎖可以通過回滾事務來解決，出現死鎖比出現不一致狀態好得多。

　　加鎖可能會出現兩個事務都在等待對方解除它所占用數據項上的鎖(也可能是多個事務之間的循環等待)，這種現象稱為死鎖。當死鎖發生時，系統必須回滾兩個事務中的一個。一旦某個事務回滾，該事務鎖住的數據項就被解鎖，其他事務就可以訪問這些數據項，繼續自己的執行例如下圖所示就必須回滾：

　　饑餓(餓死)：當一個事務想要對一個數據項上加排他鎖，因為該數據項上已經有其他事務所加的共享鎖了，因此必須等待。而在等待期間又有其他事務對該數據項加上了共享鎖，之前的那個事務對一段時間后解除了共享鎖，但當前事務還是要繼續等待，就這樣不斷地出現對該數據項加共享鎖的其他事務，那么該事務則會一直處于等待狀態，永遠不可能取得進展，這稱為饑餓或者餓死。

　　避免餓死的方法：合適的并發控制器授權加鎖的條件可以規避餓死情況的發生。如，當事務Ti申請對數據項Q加M型鎖時，并發控制管理器授權加鎖的條件是

不存在 已在數據項Q上持有與M型鎖沖突的鎖 的其他事務

不存在 等待對數據項Q加鎖并且先于Ti申請加鎖 的其他事務(即按照順序來)

???????在這樣的授權加鎖條件下，一個加鎖請求就不會被氣候的加鎖申請阻塞。

　　保證可串行性的一個協議是兩階段鎖協議。該協議要求每個事務分兩個階段提出加鎖和解鎖申請：

增長階段：事務可以獲得鎖，但不能釋放鎖

縮減階段：事務可以釋放鎖，但不能獲得鎖

　　例如事務T3和T4是兩階段的，T1和T2不是兩階段的。兩階段鎖協議可以保證沖突可串行化，但無法避免死鎖的出現。在兩階段對的事務中最后加鎖的位置稱為鎖點(lock point)。
　　兩階段鎖協議有兩個加強版：嚴格兩階段鎖協議和強兩階段鎖協議

嚴格兩階段鎖協議：在兩階段鎖協議的基礎上，還要求事務持有的所有排他鎖必須在事務提交之后方可釋放。

強兩階段鎖協議：在兩階段協議的基礎上，要求所有鎖都必須在事務提交之后方可釋放。

　　另一類實現可串行化的技術是為每個事務分配一個時間戳，這個時間戳通常就是事務的開始的時間。對于每個數據項，系統維護兩個時間戳，一個讀時間戳和一個寫時間戳。數據項的讀時間戳記錄讀該數據項的的事務的最大(即最近的)時間戳，數據項的寫時間戳記錄寫入該數據項當前值的事務的時間戳。時間戳用來確保在訪問沖突情況下，事務按照時間戳的順序來訪問數據項。當按照時間戳的順序，一事務不能訪問時，該事務會被中止，并且分配一個新的時間戳重新開始。

使用系統時鐘的值作為時間戳，即事務的時間戳等于該事務進入系統這里包括后面的系統一詞指的都是數據庫系統時的時鐘值。

使用邏輯計數器，每賦予一個時間戳，計數器增加計數，即事務的時間戳等于該事務進入系統時的計數器值。

???????

對于一個進行讀取數據項的事務，只有在當前事務的時間戳大于等于數據項上的寫時間戳時，才能進行讀取，并將數據項的讀時間戳更新為當前時間戳。

對于一個進行寫入數據項的事務，只有在當前事務的時間戳大于等于數據項上的讀時間戳以及寫時間戳，才能進行寫入操作，并將數據項的寫時間戳更新為當前時間戳。

當事務不能滿足時間戳順序要求進行訪問操作時，則事務會被回滾，由系統賦予它新的時間戳并重新啟動。

　　時間戳協議和兩段鎖協議相似，都是保證了沖突可串行化，但兩者都是保證的沖突可串行化的兩個不同的真子集，存在滿足兩階段鎖協議卻不能滿足時間戳協議的調度，反之亦然。時間戳協議保證沖突可串行化的原因在于：沖突操作是按時間戳順序進行處理的。
　　死鎖：時間戳協議保證了無死鎖，因為不存在等待的事務。
　　餓死：當一系列的短事務引起長事務反復重啟時，可能導致長事務餓死的現象。解決方式：如果發現一個事務反復重啟，與之沖突的事務應當暫時阻塞，以使該事務能夠完成。

　　通過維護數據項的多個版本，一個事務允許讀取一個舊版本的數據項，而不是被另一個未提交或者在串行化序列中應該排在后面的事務寫入的新版本的數據項。有許多多版本并發控制技術，其中一個是實際中廣泛應用的稱為快照隔離的技術。
　　在快照隔離中，我們可以視為每個事務開始時都有其自身的數據庫版本或者快照(實際實現中不會復制整個數據庫，只有被改變的數據項才會保留多個版本)。事務從這個私有版本中讀取數據，因此和其他事務所做的更新隔離開，如果事務更新數據庫，更新只出現在其私有版本中，而不是實際的數據庫本身中。當事務提交時，和更新有關的信息將保存，使得更新被寫入真正的數據庫。
　　當一個事務T進入提交狀態后，只有在 沒有其他并發事務已經修改該事務想要更新的數據項 的情況下，事務進入提交狀態。而不能提交的事務則終止。
　　快照隔離可以保證讀數據的嘗試永遠無需等待(不像鎖協議那樣要讀的數據項上面被加了排他鎖就只能等待)。只讀事務不會終止。只有修改數據的事務才有微小的終止風險。由于每個事務讀取它自己的數據庫版本或快照，因此讀數據不會導致此后其他事務的更新嘗試被迫等待(不像鎖協議要寫的數據項中被加了共享鎖后就只能等待甚至有餓死的情況)。因為大部分事務是只讀的，并且大多數其他事務讀數據的情況多于更新，所以這是與鎖相比往往能帶來性能改善的主要原因。
　　矛盾在于，快照隔離帶來的問題是它提供了太多的隔離。考慮兩個事務T和T",在一個串行化調度中，要么T看到T"所做的所有更新，要么T"看到T所做的所有更新，因為在串行化順序中一個必須在另一個之后。在快照隔離下，任何事務都不能看到對方的更新，這是在串行化調度中不會出現的。在許多(事實上，大多數)情況下，兩個事務的數據訪問不會沖突，因此沒有什么問題。DNA一旦T讀取的是T"要更新的數據項，T"讀取的是T"要更新的數據項，則可能兩個事務都無法讀取到對方的更新。結果可能導致數據庫的不一致狀態。
　　詳情參看數據庫系統概念第六版中的15.5基于有效性檢查的協議、15.6多版本機制、15.7快照隔離。
　　注意：根據論文，快照隔離能排除掉嚴格版本的幻讀A3，但對于寬泛版本的P3(實際上使得隔離性更嚴格了)是不能排出的，此外還存在寫偏斜(write skew)的異常。

　　如果存在一個事務集，該集合中的每個事務都在等待該集合中的另一個事務，那么我們說系統處于死鎖狀態。更確切地說，存在一個等待事務集{T0,T1,...,Tn}，使得T0正等待被T1鎖住的數據項，T1正等待被T2鎖住的數據項，....，Tn-1正等待被Tn鎖住的數據項，且Tn正等待被T0鎖住的數據項。在這種情況下，沒有一個事務能夠取得進展。
　　此時系統的唯一補救措施就是采取激烈的動作，如回滾某些陷于死鎖的事務。事務有可能只部分回滾，即事務回滾到 它得到鎖的點 之前，這樣就釋放了鎖從而解決死鎖。
　　處理死鎖有兩種主要的方法：我們可以使用死鎖預防協議來保證系統永不進入死鎖狀態。另一種方法是，我們允許系統進入死鎖狀態，然后試著用死鎖檢測與死鎖恢復機制進行恢復。兩種方法均有可能引起事務回滾。如果事務進入死鎖狀態概率相對比較高，則通常使用死鎖預防機制，否則使用檢測與恢復機制。
　　注意：檢測與恢復機制所帶來的各種開銷，不僅包括在運行時維護必要信息及執行檢測算法的代價，還要包括從死鎖中恢復所固有的潛在損失。

　　預防死鎖主要有兩種思路：

第一種思路是：通過對加鎖請求進行排序(順序封鎖法) 或 要求同時獲得所有的鎖從而來保證不會發生循環等待(一次封鎖法)(就不會發生占著一個數據項的鎖還在等著另一個數據項的鎖的情況，要么就一起占著要么就都不占)。

???????一次封鎖法就是要求每個事務在開始之前封鎖它的所有的數據項，此外，要么一次全部封鎖，要么全不封鎖。
　　一次封鎖協議主要的缺點是：(1)在事務開始前通常很難預知哪些數據項需要封鎖。(2)數據項的使用率可能很低，因為很多數據項可能封鎖很長時間卻用不到。
　　順序封鎖法是對所有的數據項強加一個次序，同時要求按次序規定的順序對數據項進行加鎖。
　　順序封鎖法存在的問題：維護成本高。數據庫系統中可封鎖的數據對象極其眾多，并且隨數據的插入、刪除等操作而不斷地變化，要維護這樣極多而且變化的資源的封鎖順序非常困難，成本很高。

　　2.?第二種思路比較接近死鎖恢復，每當等待有可能導致死鎖時，進行事務回滾而不是等待加鎖。
???????這種思路的實現方式是使用搶占和事務回滾。在搶占機制中，若事務Tj所申請的鎖已經被事務Ti所持有，則授予Ti的鎖可能通過回滾事務Ti被搶占，并將鎖授予Tj。為控制搶占，我們給每個事務賦予一個唯一的時間戳，系統僅用時間戳來決定事務應當等待還是回滾。并發協議仍使用封鎖協議，若一個事務回滾，則該事務重啟時保持原有的時間戳。
　　根據此思路提出的兩種相反的預防機制：

wait-die機制：當事務Ti申請的數據項被Tj持有，僅當Ti的時間戳小于Tj的時間戳時，允許Ti等待。否則Ti回滾。即如老可等

wound-wait機制：當事務Ti申請的數據項被Tj持有，僅當Ti的時間戳大于Tj的時間戳時，允許Ti等待。否則Tj回滾。(Tj被Ti傷害)即如少可等，如老傷少

???????兩種機制的缺點都是：可能會發生不必要的回滾。

　　3.?還有一種額外的思路是鎖超時機制，申請鎖的事務至多等待一段給定的時間。若此時間內為授予該事務鎖，則稱該事務超時，則該事務會進行回滾并重啟。該機制介于死鎖預防(不會發生死鎖)和死鎖檢與恢復之間。
　　鎖超時機制實現起來及其容易，但其缺點在于很難確定一個事務超時之前應等待多長時間，過長則會在死鎖時造成延遲，過短則會造成不必要的回滾。所以僅應用于事務主要是短事務并且長時間的等待極可能是死鎖造成的情況下。