摘要：關(guān)于串行化與一致性的關(guān)系數(shù)據(jù)庫并發(fā)控制的基本目標(biāo)是確保事務(wù)的并發(fā)執(zhí)行不會導(dǎo)致數(shù)據(jù)庫一致性的丟失。該請求發(fā)送給并發(fā)控制管理器，只有并發(fā)控制管理器授予所需鎖后，事務(wù)才能繼續(xù)其操作。

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

　　關(guān)于串行化與一致性的關(guān)系：數(shù)據(jù)庫并發(fā)控制的基本目標(biāo)是確保事務(wù)的并發(fā)執(zhí)行不會導(dǎo)致數(shù)據(jù)庫一致性的丟失?？梢岳每纱行愿拍顏磉_(dá)到這一目標(biāo)，因?yàn)?strong>所有可串行化的調(diào)度都能保持?jǐn)?shù)據(jù)庫的一致性。然而，并非所有保證數(shù)據(jù)庫一致性的調(diào)度都是可串行化的。(也存在著允許非可串行化調(diào)度的并發(fā)控制機(jī)制，詳見數(shù)據(jù)庫系統(tǒng)概念25章)

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

　　給數(shù)據(jù)項(xiàng)加鎖的方式有多種，這一節(jié)只考慮兩種(這兩種也正是MySQL默認(rèn)引擎(InnoDB)在行級鎖定時所使用的)

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

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

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

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

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

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

　　避免餓死的方法：合適的并發(fā)控制器授權(quán)加鎖的條件可以規(guī)避餓死情況的發(fā)生。如，當(dāng)事務(wù)Ti申請對數(shù)據(jù)項(xiàng)Q加M型鎖時，并發(fā)控制管理器授權(quán)加鎖的條件是

不存在 已在數(shù)據(jù)項(xiàng)Q上持有與M型鎖沖突的鎖 的其他事務(wù)

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

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

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

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

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

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

嚴(yán)格兩階段鎖協(xié)議：在兩階段鎖協(xié)議的基礎(chǔ)上，還要求事務(wù)持有的所有排他鎖必須在事務(wù)提交之后方可釋放。

強(qiáng)兩階段鎖協(xié)議：在兩階段協(xié)議的基礎(chǔ)上，要求所有鎖都必須在事務(wù)提交之后方可釋放。

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

使用系統(tǒng)時鐘的值作為時間戳，即事務(wù)的時間戳等于該事務(wù)進(jìn)入系統(tǒng)這里包括后面的系統(tǒng)一詞指的都是數(shù)據(jù)庫系統(tǒng)時的時鐘值。

使用邏輯計(jì)數(shù)器，每賦予一個時間戳，計(jì)數(shù)器增加計(jì)數(shù)，即事務(wù)的時間戳等于該事務(wù)進(jìn)入系統(tǒng)時的計(jì)數(shù)器值。

???????

對于一個進(jìn)行讀取數(shù)據(jù)項(xiàng)的事務(wù)，只有在當(dāng)前事務(wù)的時間戳大于等于數(shù)據(jù)項(xiàng)上的寫時間戳時，才能進(jìn)行讀取，并將數(shù)據(jù)項(xiàng)的讀時間戳更新為當(dāng)前時間戳。

對于一個進(jìn)行寫入數(shù)據(jù)項(xiàng)的事務(wù)，只有在當(dāng)前事務(wù)的時間戳大于等于數(shù)據(jù)項(xiàng)上的讀時間戳以及寫時間戳，才能進(jìn)行寫入操作，并將數(shù)據(jù)項(xiàng)的寫時間戳更新為當(dāng)前時間戳。

當(dāng)事務(wù)不能滿足時間戳順序要求進(jìn)行訪問操作時，則事務(wù)會被回滾，由系統(tǒng)賦予它新的時間戳并重新啟動。

　　時間戳協(xié)議和兩段鎖協(xié)議相似，都是保證了沖突可串行化，但兩者都是保證的沖突可串行化的兩個不同的真子集，存在滿足兩階段鎖協(xié)議卻不能滿足時間戳協(xié)議的調(diào)度，反之亦然。時間戳協(xié)議保證沖突可串行化的原因在于：沖突操作是按時間戳順序進(jìn)行處理的。
　　死鎖：時間戳協(xié)議保證了無死鎖，因?yàn)椴淮嬖诘却氖聞?wù)。
　　餓死：當(dāng)一系列的短事務(wù)引起長事務(wù)反復(fù)重啟時，可能導(dǎo)致長事務(wù)餓死的現(xiàn)象。解決方式：如果發(fā)現(xiàn)一個事務(wù)反復(fù)重啟，與之沖突的事務(wù)應(yīng)當(dāng)暫時阻塞，以使該事務(wù)能夠完成。

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

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

　　預(yù)防死鎖主要有兩種思路：

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

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

　　2.?第二種思路比較接近死鎖恢復(fù)，每當(dāng)?shù)却锌赡軐?dǎo)致死鎖時，進(jìn)行事務(wù)回滾而不是等待加鎖。
???????這種思路的實(shí)現(xiàn)方式是使用搶占和事務(wù)回滾。在搶占機(jī)制中，若事務(wù)Tj所申請的鎖已經(jīng)被事務(wù)Ti所持有，則授予Ti的鎖可能通過回滾事務(wù)Ti被搶占，并將鎖授予Tj。為控制搶占，我們給每個事務(wù)賦予一個唯一的時間戳，系統(tǒng)僅用時間戳來決定事務(wù)應(yīng)當(dāng)?shù)却€是回滾。并發(fā)協(xié)議仍使用封鎖協(xié)議，若一個事務(wù)回滾，則該事務(wù)重啟時保持原有的時間戳。
　　根據(jù)此思路提出的兩種相反的預(yù)防機(jī)制：

wait-die機(jī)制：當(dāng)事務(wù)Ti申請的數(shù)據(jù)項(xiàng)被Tj持有，僅當(dāng)Ti的時間戳小于Tj的時間戳?xí)r，允許Ti等待。否則Ti回滾。即如老可等

wound-wait機(jī)制：當(dāng)事務(wù)Ti申請的數(shù)據(jù)項(xiàng)被Tj持有，僅當(dāng)Ti的時間戳大于Tj的時間戳?xí)r，允許Ti等待。否則Tj回滾。(Tj被Ti傷害)即如少可等，如老傷少

???????兩種機(jī)制的缺點(diǎn)都是：可能會發(fā)生不必要的回滾。

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