1、寫在前面
1.1 為什么要并發(fā)控制
如果事務(wù)在并發(fā)執(zhí)行時(shí)，來自各個(gè)并發(fā)事務(wù)的所有指令的執(zhí)行控制都是由操作系統(tǒng)負(fù)責(zé)，那么許多調(diào)度都是可能的。這樣，很可能會(huì)導(dǎo)致數(shù)據(jù)庫處于不一致的狀態(tài)。所以，必須保證數(shù)據(jù)庫執(zhí)行的任何調(diào)度都能是數(shù)據(jù)庫保持一致狀態(tài)，這是數(shù)據(jù)庫中并發(fā)控制(concurrency-control)模塊的功能。
具體地說，數(shù)據(jù)庫的并發(fā)控制模塊就是為用戶提交的多個(gè)事務(wù)產(chǎn)生滿足需求的調(diào)度。
1.2 并發(fā)控制的相關(guān)內(nèi)容
1.2.1 內(nèi)容列表
為了理解這一過程，我們需要了解：
- 并發(fā)中有關(guān)調(diào)度的相關(guān)基本概念
- 串行化及其判定
- 可恢復(fù)調(diào)度與無級(jí)聯(lián)調(diào)度
- 事務(wù)的隔離級(jí)別等相關(guān)信息。
1.2.2 內(nèi)容概要
基本概念部分，略過不表。
串行化及其判定部分大致介紹了如何判定事務(wù)在并發(fā)執(zhí)行時(shí)是否和先后順序執(zhí)行時(shí)效果一致。明確了這部分，DBMS在為事務(wù)選擇并發(fā)調(diào)度時(shí)，才知道最優(yōu)解是什么(也就是，執(zhí)行效果和先后執(zhí)行相同)。
可恢復(fù)調(diào)度和無級(jí)聯(lián)調(diào)度部分是在從故障恢復(fù)的角度講述，如果一個(gè)并行執(zhí)行的調(diào)度中間發(fā)生故障，為了保證事務(wù)的原子性，必須進(jìn)行回滾恢復(fù)，然而，有時(shí)恢復(fù)的代價(jià)很大，有時(shí)甚至無法恢復(fù)。這部分對(duì)這些情況分別介紹。
事務(wù)的隔離級(jí)別部分講述，在事務(wù)并發(fā)的過程中，如果要保證任何時(shí)刻絕對(duì)的數(shù)據(jù)正確，代價(jià)是很高的。比如，好多時(shí)候就無法實(shí)現(xiàn)并發(fā)，只能是串行執(zhí)行。在一些聯(lián)機(jī)的場景中，這是不能接受的。隔離級(jí)別就是為了兼顧效率的產(chǎn)物，通過允許不同程度地允許，并發(fā)過程中數(shù)據(jù)的暫時(shí)不一致，來換取更好的執(zhí)行效率。
2、幾個(gè)基本概念
- 調(diào)度(schedule)
事務(wù)在并發(fā)執(zhí)行時(shí)，各個(gè)事務(wù)中的不同指令的先后執(zhí)行順序稱為調(diào)度。比如事務(wù)T1由兩條指令a和b組成，事務(wù)T2由c和d組成。那么，這兩個(gè)事務(wù)在并發(fā)執(zhí)行時(shí)abcd、acbd等的這些執(zhí)行順序都稱之為調(diào)度。 - 串行的(serial)
如果在一個(gè)調(diào)度中，屬于同一個(gè)事務(wù)的指令緊挨在一起，我們就稱這個(gè)調(diào)度是串行的。上面的例子中，T1和T2的串行調(diào)度有兩種，分別是abcd和cdab。對(duì)于n個(gè)事務(wù)組成的事務(wù)組，共有n!個(gè)不同的串行調(diào)度。 - 可串行化的(serializable)
如果一個(gè)調(diào)度等價(jià)于一個(gè)串行調(diào)度，那么就稱該調(diào)度是可串行化的。顯然，串行調(diào)度是可串行化的。
3、調(diào)度的可串行化
3.1 串行化與沖突可串行化
串行調(diào)度是可串行化的，但是，如果許多事務(wù)的指令交錯(cuò)執(zhí)行，則很難確定一個(gè)調(diào)度是否是可串行化的。事務(wù)就是程序，要確定一個(gè)事務(wù)有哪些操作，多個(gè)事務(wù)的不同操作如何相互作用，是非常困難的。
因此，這里我們不會(huì)考慮一個(gè)事務(wù)可以對(duì)一個(gè)數(shù)據(jù)項(xiàng)執(zhí)行的所有不同類型的操作，而只考慮兩種操作：read和write。我們假設(shè)，在數(shù)據(jù)Q上的read(Q)和write(Q)之間，事務(wù)可以對(duì)駐留在事務(wù)局部緩沖區(qū)中Q的拷貝執(zhí)行任意操作序列。按這種模式，從調(diào)度的角度來說，事務(wù)唯一重要的操作就是read和write。
假設(shè)I和J是不同事務(wù)在相同數(shù)據(jù)項(xiàng)上的操作，那么當(dāng)它們?nèi)莚ead時(shí)，它們的次序無關(guān)緊要。但是，當(dāng)其中至少有一個(gè)書write時(shí)，它們的順序?qū)⒅苯佑绊懽罱K事務(wù)的執(zhí)行結(jié)果，這時(shí)我們說I和J是沖突(conflict)的。
如果調(diào)度S經(jīng)過一系列非沖突指令次序交換轉(zhuǎn)換成S'，我們稱S和S'是沖突等價(jià)(conflict equivalent)的。
可以理解，不是所有的串行調(diào)度之間都是沖突等價(jià)的。
如果一個(gè)調(diào)度與串行調(diào)度沖突等價(jià)，則稱該調(diào)度是沖突可串行化(conflict serializable)的。
3.2 沖突可串行化的判定
這里給出一個(gè)簡單有效的方法，來確定一個(gè)調(diào)度是否沖突可串行化。假設(shè)S是一個(gè)調(diào)度，我們由S構(gòu)造一個(gè)有向圖，稱為優(yōu)先圖(precedence graph)。該圖由定義為G=(V,E)，其中V是頂點(diǎn)集，E是邊集，頂點(diǎn)集由所有參與調(diào)度的事務(wù)組成。如果事務(wù)Ti和Tj滿足下列三個(gè)條件之一，優(yōu)先圖中就存在邊Ti->Tj：
- 在Tj執(zhí)行read(Q)之前，Ti執(zhí)行write(Q)。
- 在Tj執(zhí)行write(Q)之前，Ti執(zhí)行read(Q)。
- 在Tj執(zhí)行write(Q)之前，Ti執(zhí)行write(Q)。
這里的意思是，事務(wù)中沖突的操作決定了事務(wù)的執(zhí)行順序。所以，如果優(yōu)先圖中存在邊Ti->Tj，則在任何等價(jià)于S的串行調(diào)度S’中，Ti必出現(xiàn)在Tj之前。
這樣，如果調(diào)度S的優(yōu)先圖中有環(huán)，則調(diào)度S是非沖突可串行化的，如果優(yōu)先圖中無環(huán)，則調(diào)度S是沖突可串行化的。
串行化順序(serializability order)可通過拓?fù)渑判?topological sorting，用于計(jì)算與優(yōu)先圖的偏序相一致的線形順序)得到。一般而言，通過拓?fù)渑判蚩梢垣@得多個(gè)線形順序。
因此，要判斷沖突可串行化，需要構(gòu)造優(yōu)先圖并調(diào)用一個(gè)環(huán)檢測算法?；谏疃葍?yōu)先的環(huán)檢測算法需要n^2數(shù)量級(jí)的運(yùn)算，其中n是優(yōu)先圖中的定點(diǎn)數(shù)(即事務(wù)數(shù))。
3.3 沖突等價(jià)的局限性
有可能存在兩個(gè)調(diào)度，它們產(chǎn)生的結(jié)果相同，但它們不是沖突等價(jià)的。比如下面的例子：
利用前面提到的優(yōu)先圖判定方法，上圖的調(diào)度S并不與串行調(diào)度<T1, T2>等價(jià)。然而，它們的執(zhí)行結(jié)果卻相同。
這個(gè)例子可以看出，調(diào)度等價(jià)的定義實(shí)際上是比沖突等價(jià)更為寬松，也就是說存在不是沖突等價(jià)的兩個(gè)等價(jià)調(diào)度。
對(duì)于計(jì)算機(jī)來說，要判定調(diào)度S與串行調(diào)度<T1, T2>產(chǎn)生的結(jié)果相同，必須分析T1和T2所進(jìn)行的計(jì)算，而不只是分析read和write操作。上面的例子比較簡單，由于從數(shù)學(xué)的角度，遞增和遞減是可以交換的，導(dǎo)致兩個(gè)調(diào)度等價(jià)。實(shí)際中，一個(gè)事務(wù)可能會(huì)表示為一條復(fù)雜的SQL語句，或一個(gè)有JDBC調(diào)用的Java程序等，這種判定的計(jì)算代價(jià)很大。
除此之外，也存在一些別的純粹基于read和write操作的調(diào)度等價(jià)定義，比如視圖等價(jià)，其中有視圖可串行化的概念。這里暫且不做介紹。
4、事務(wù)的隔離性和原子性
不管是什么原因，如果事務(wù)Ti失敗了，我們必須撤銷該事務(wù)的影響以確保其原子性。在允許并發(fā)執(zhí)行的系統(tǒng)中，原子性要求依賴于Ti的任何事務(wù)Tj（即Tj讀取了Ti寫的數(shù)據(jù)）也中止。為了確保這一點(diǎn)我們需要對(duì)系統(tǒng)所允許的調(diào)度類型做一些限制。
4.1 可恢復(fù)調(diào)度
如下所示的調(diào)度，事物T2只執(zhí)行一條指令：read(A)。我們稱之為部分調(diào)度(partial schedule)。因?yàn)門1中沒有包括commit或abort操作。注意T2執(zhí)行read(A)指令后立即提交。因此T2提交時(shí)T1仍處于活躍狀態(tài)?，F(xiàn)假定T1在提交前發(fā)生了故障。T2已經(jīng)讀取了T1寫入的數(shù)據(jù)A的值（我們說T2依賴于T1）。因此，我們必須終止T2以保證事務(wù)的原子性。但T2已經(jīng)提交，不能再中止。這樣就出現(xiàn)了T1發(fā)生故障之后不能正確恢復(fù)的情形。
上面例子中的調(diào)度是一個(gè)不可恢復(fù)調(diào)度的例子。一個(gè)可恢復(fù)調(diào)度（recoverable schedule）應(yīng)滿足：對(duì)于每對(duì)事務(wù)Ti和Tj，如果Tj讀取了之前由Ti所寫的數(shù)據(jù)項(xiàng)，則Ti應(yīng)該先于Tj提交。上面的例子如果是可恢復(fù)的，那么T2應(yīng)該推遲至T1提交之后再提交。
4.2 無級(jí)聯(lián)調(diào)度
即使一個(gè)調(diào)度是可恢復(fù)的，要從事務(wù)Ti的故障中正確恢復(fù)，可能需要回滾若干事務(wù)。當(dāng)其它事務(wù)讀取了Ti寫入的數(shù)據(jù)項(xiàng)時(shí)就會(huì)發(fā)生這種情況。下面調(diào)度中，如果T1發(fā)生故障，回滾。由于T2讀取了T1寫入的數(shù)據(jù)A，T2必須回滾。同理，T3也必須回滾。這種因單個(gè)事務(wù)故障導(dǎo)致一系列事務(wù)回滾的現(xiàn)象稱為級(jí)聯(lián)回滾(cascading rollback)。
級(jí)聯(lián)回滾導(dǎo)致大量的撤銷工作，這是我們不希望的。所以要對(duì)調(diào)度進(jìn)行限制，避免級(jí)聯(lián)回滾發(fā)生，這樣的調(diào)度稱為無級(jí)聯(lián)調(diào)度。規(guī)范地說，無級(jí)聯(lián)調(diào)度(cascadeless schedule)必須滿足：對(duì)于事務(wù)Ti和Tj，如果Tj讀取了先前由Ti所寫的數(shù)據(jù)項(xiàng)，則Ti必須在Tj這一讀操作之前提交。
容易理解，一個(gè)無級(jí)聯(lián)調(diào)度也是可恢復(fù)調(diào)度。
5、事務(wù)的隔離級(jí)別
5.1 隔離級(jí)別定義和解釋
- 讀未提交(read uncommitted)
這是最低的隔離級(jí)別。意思是，事務(wù)在并發(fā)時(shí)，允許一個(gè)事務(wù)讀取另一個(gè)事務(wù)已經(jīng)修改但還未提交的數(shù)據(jù)。這種情況下，會(huì)導(dǎo)致臟讀。臟讀針對(duì)的是更新操作。比如，事務(wù)T1更新了數(shù)據(jù)庫中記錄A的值，沒有提交，T2讀取了記錄A，然后，T1回滾。這樣，T2讀取到的就是一個(gè)錯(cuò)誤的數(shù)據(jù)。這種現(xiàn)象就叫臟讀。 - 讀提交(read committed)
事務(wù)在并發(fā)執(zhí)行時(shí)，只允許讀取其它事務(wù)已經(jīng)提交的數(shù)據(jù)。
這樣，可以解決數(shù)據(jù)的臟讀問題，但是并不能保證可重復(fù)讀。比如，事務(wù)T1中有兩次對(duì)記錄A的讀取操作，在這兩次讀取操作之間，事務(wù)T2修改了記錄A的值并提交。這樣，T1兩次讀取到的值就會(huì)不同，這種現(xiàn)象成為不可重復(fù)讀。 - 可重復(fù)讀(repeatable read)
事務(wù)在并發(fā)執(zhí)行時(shí)，只允許讀取已經(jīng)提交的數(shù)據(jù)，而且一個(gè)事務(wù)在兩次讀取一個(gè)數(shù)據(jù)項(xiàng)期間，其他事務(wù)不得更新該數(shù)據(jù)。這樣，就保證了數(shù)據(jù)的可重復(fù)讀。但是，也存在幻讀的問題。
幻讀，幻讀針對(duì)的是插入操作。比如事務(wù)T1中選出數(shù)據(jù)庫中符合條件的記錄，然后，事務(wù)T2又向數(shù)據(jù)庫中插入了一條數(shù)據(jù)，也符合T1的篩選條件，然后提交，這時(shí)，T1第二次查找符合條件的數(shù)據(jù)，就會(huì)發(fā)現(xiàn)結(jié)果集中多了一條記錄。就好像出現(xiàn)了幻覺，所以稱為幻讀。 - 可串行化(serializable)
通常保證可串行化調(diào)度。但是，一些數(shù)據(jù)庫對(duì)該隔離級(jí)別的實(shí)現(xiàn)，在某些情況下允許非串行化執(zhí)行。
5.2 上述事務(wù)隔離級(jí)別的說明
從上到下，隔離級(jí)別依次提高。每個(gè)隔離級(jí)別的定義和解釋中，說的都是該級(jí)別的最低要求。
所有的隔離級(jí)別都不允許臟寫(dirty write)，即如果一個(gè)數(shù)據(jù)項(xiàng)已經(jīng)被另外一個(gè)未提交或者終止的事務(wù)寫入，則不允許其它事務(wù)對(duì)該數(shù)據(jù)項(xiàng)進(jìn)行寫操作。
實(shí)現(xiàn)上，大多數(shù)數(shù)據(jù)庫默認(rèn)的事務(wù)隔離級(jí)別是Read committed，比如Sql Server , Oracle。Mysql的默認(rèn)隔離級(jí)別是Repeatable read。
SQL中，可以顯示設(shè)定事務(wù)的隔離級(jí)別。如可以通過語句set transaction isolation level serializable;來顯示將隔離級(jí)別設(shè)置為可串行化。另外，修改事務(wù)隔離級(jí)別必須作為事務(wù)的第一條語句執(zhí)行。
