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

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

　　關(guān)于串行化與一致性的關(guān)系：數(shù)據(jù)庫并發(fā)控制的基本目標(biāo)是確保事務(wù)的并發(fā)執(zhí)行不會(huì)導(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章)

　　確保串行化的方法之一就是要求對(duì)數(shù)據(jù)項(xiàng)的訪問以互斥的方式進(jìn)行。也就是說當(dāng)一個(gè)事務(wù)訪問某個(gè)數(shù)據(jù)項(xiàng)時(shí)，其他任何=事務(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)在行級(jí)鎖定時(shí)所使用的)

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

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

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

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

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

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

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

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

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

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

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

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

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

　　例如事務(wù)T3和T4是兩階段的，T1和T2不是兩階段的。兩階段鎖協(xié)議可以保證沖突可串行化，但無法避免死鎖的出現(xiàn)。在兩階段對(duì)的事務(wù)中最后加鎖的位置稱為鎖點(diǎn)(lock point)。
　　兩階段鎖協(xié)議有兩個(gè)加強(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ù)是為每個(gè)事務(wù)分配一個(gè)時(shí)間戳，這個(gè)時(shí)間戳通常就是事務(wù)的開始的時(shí)間。對(duì)于每個(gè)數(shù)據(jù)項(xiàng)，系統(tǒng)維護(hù)兩個(gè)時(shí)間戳，一個(gè)讀時(shí)間戳和一個(gè)寫時(shí)間戳。數(shù)據(jù)項(xiàng)的讀時(shí)間戳記錄讀該數(shù)據(jù)項(xiàng)的的事務(wù)的最大(即最近的)時(shí)間戳，數(shù)據(jù)項(xiàng)的寫時(shí)間戳記錄寫入該數(shù)據(jù)項(xiàng)當(dāng)前值的事務(wù)的時(shí)間戳。時(shí)間戳用來確保在訪問沖突情況下，事務(wù)按照時(shí)間戳的順序來訪問數(shù)據(jù)項(xiàng)。當(dāng)按照時(shí)間戳的順序，一事務(wù)不能訪問時(shí)，該事務(wù)會(huì)被中止，并且分配一個(gè)新的時(shí)間戳重新開始。

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

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

???????

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

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

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

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

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

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

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

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

???????一次封鎖法就是要求每個(gè)事務(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)可能封鎖很長(zhǎng)時(shí)間卻用不到。
　　順序封鎖法是對(duì)所有的數(shù)據(jù)項(xiàng)強(qiáng)加一個(gè)次序，同時(shí)要求按次序規(guī)定的順序?qū)?shù)據(jù)項(xiàng)進(jìn)行加鎖。
　　順序封鎖法存在的問題：維護(hù)成本高。數(shù)據(jù)庫系統(tǒng)中可封鎖的數(shù)據(jù)對(duì)象極其眾多，并且隨數(shù)據(jù)的插入、刪除等操作而不斷地變化，要維護(hù)這樣極多而且變化的資源的封鎖順序非常困難，成本很高。

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

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

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

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

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