> 本文圖片中出現(xiàn)的 txns 指代 transactions

## 已經(jīng)討論過的數(shù)據(jù)庫技術(shù)

現(xiàn)在要考慮 2 個重要的部分，即 并發(fā)控制 和 故障恢復(fù)

并發(fā)控制和故障恢復(fù)并不是獨(dú)立于 Buffer Pool 管理器、索引之外的東西

## 并發(fā)控制和故障恢復(fù)的的動機(jī)

2 個線程爭搶同一個資源時，如何避免競爭條件?

如何保證故障的數(shù)據(jù)的恢復(fù)?

## 并發(fā)控制與故障恢復(fù)

為了確保系統(tǒng)中一切東西都正確地執(zhí)行，或者所有修改都做持久化處理，就需要利用到事務(wù)，而事務(wù)會和 ACID 這種特性一起使用

## 事務(wù)

什么是事務(wù)呢?

事務(wù)就是，在數(shù)據(jù)庫系統(tǒng)中，通過執(zhí)行一系列操作(SQL 查詢或者讀寫操作)，來執(zhí)行某種更高級的功能(比如銀行轉(zhuǎn)賬)

對于執(zhí)行事務(wù)來講，不允許的事情是，只執(zhí)行該事務(wù)中的部分操作

例子

一旦執(zhí)行了上述例子中的事務(wù)的 3 個操作，要么這個事務(wù)中的操作被全部執(zhí)行，要么就都不執(zhí)行

## Strawman System

(假設(shè)數(shù)據(jù)庫只支持單線程的情況，即一次只能執(zhí)行一個事務(wù)，如果要執(zhí)行多個事務(wù)那只能放在隊(duì)列中)那么，在開始執(zhí)行事務(wù)之前，要做的事情是，復(fù)制整個數(shù)據(jù)庫文件或者一組文件，將其制作成該數(shù)據(jù)庫的第二個副本，并將其所有的修改應(yīng)用到該副本上，如果修改成功，并且要保存這些修改，那么只需要重新 set 下指針，指向剛剛創(chuàng)建的那個副本就好了

這能保證原子性的傳播

副本的作用在于，如果一些寫操作失敗，或者數(shù)據(jù)庫發(fā)生崩潰，如果還有原始數(shù)據(jù)，那么數(shù)據(jù)恢復(fù)就不是問題(前提是磁盤也不會掛掉)

但是由于數(shù)據(jù)庫文件的復(fù)制，這個總要走磁盤 I/O，所以成本很高

單線程運(yùn)行，由于需要訪問的數(shù)據(jù)在磁盤中，所以就會產(chǎn)生線程阻塞，這也會成為一個性能瓶頸

## Problem Statement

那么更好的方案是什么呢，如果能在同一時間同時執(zhí)行多個事務(wù)就好了

為什么需要這種方式?

1. 更高的吞吐量，在相同的時間內(nèi)，可以做更多的工作

2. 更快的系統(tǒng)響應(yīng)速度

但同時也需要

在交錯執(zhí)行事務(wù)操作時，也需要保證系統(tǒng)的正確性，并且不能讓任何一個事務(wù)執(zhí)行時占據(jù)了全部資源

硬件不能保證原子性，因?yàn)樾枰鄺l指令或者多個操作才能做到(比如在轉(zhuǎn)賬時，要轉(zhuǎn)賬的錢在一段時間內(nèi)不在任何地方，也就是 數(shù)據(jù)的 臨時不一致)，這個雖然不可避免但是是 ok 的，通過允許這個臨時數(shù)據(jù)，使所有的一切都工作正常

那么如何避免 永久不一致 呢(比如轉(zhuǎn)賬時數(shù)據(jù)庫崩了)，這個時候就需要通過一種方式來解釋要做的事情是否正確

## 事務(wù)的麻煩點(diǎn)

很難保證執(zhí)行事務(wù)時的正確性，事務(wù)在執(zhí)行時也很難運(yùn)行的快

## 定義

一個事務(wù)中可能包含了一個或者多個操作，如果這個事務(wù)涉及到了一些額外的步驟、過程或者操作，并且這些并不是對數(shù)據(jù)庫進(jìn)行讀/寫的操作，這就超出了數(shù)據(jù)庫的控制范圍

因?yàn)橹荒軐?shù)據(jù)庫中那些底層的讀/寫操作進(jìn)行解釋、回滾和持久化

## 公式定義

假設(shè)數(shù)據(jù)庫中數(shù)據(jù)量的大小是恒定的(這樣處理起來會比較簡單)，這意味著數(shù)據(jù)庫唯一要做的事情就是讀和寫，即對現(xiàn)有的數(shù)據(jù)進(jìn)行讀取或者更新

## Transactions in SQL

如何在應(yīng)用程序和數(shù)據(jù)庫系統(tǒng)中實(shí)現(xiàn)或者使用事務(wù)呢?

用 BEGIN 關(guān)鍵字來顯式聲明開始一個新事務(wù)，然后寫出要做的查詢，這個會作為一個事務(wù)的一部分來執(zhí)行

然后通過 COMMIT/ABORT 來決定是否要提交/中止這個事務(wù)

應(yīng)用程序調(diào)用 COMMIT 并不意味著就會提交這個事務(wù)

如果事務(wù)被 ABORT，那么任何來自 BEGIN 所做的修改都會被回滾

需要注意的是，事務(wù)的中止可能是自發(fā)的，也就是說可能就是數(shù)據(jù)庫自己自發(fā)的主動的去中止這個事務(wù)(比如異常捕獲的處理，事務(wù)執(zhí)行失敗就做中止處理)

## 正確性標(biāo)準(zhǔn) ACID

1. 原子性

? ? 對于一個事務(wù)中的所有操作來說，要么全都執(zhí)行，要么全不執(zhí)行，不存在這個事務(wù)只執(zhí)行部分的情況

? ??

2. 一致性

? ? 當(dāng)事務(wù)執(zhí)行時，數(shù)據(jù)庫的狀態(tài)是一致的，跟正確性相關(guān)

? ??

3. 隔離性

? ? 如果在同一時間有幾個事務(wù)在同時運(yùn)行，那么事務(wù)間是彼此隔離開的

4. 持久性

? ? 如果事務(wù)都提交了，并且所有的修改都被保存了，那么不管數(shù)據(jù)庫是崩潰了還是其他事情掛了，那么這些修改都應(yīng)該是持久化的。當(dāng)系統(tǒng)恢復(fù)正常后，它應(yīng)該能看到我們所做的修改

ACID 簡寫

## 課程目標(biāo)

ACID 純享版

對于那些不使用事務(wù)的 NoSQL 數(shù)據(jù)庫來說，他們有些就直接不用 ACID 了

## Atomicity

數(shù)據(jù)庫系統(tǒng)要保證所有的事務(wù)的執(zhí)行都是原子的，這意味著某個事務(wù)要么執(zhí)行，要么不執(zhí)行

不管怎么說，只要事務(wù)提交了，那么所有的修改就會都落地執(zhí)行

如何處理上面 2 種被中止和斷電的情況呢

### 保障 Atomicity 的機(jī)制

常見方案就是做 Logging (日志)，這里面的日志指的是 Write Ahead Logging(預(yù)寫式日志)，這些日志文件是存在磁盤上的

對要覆寫掉的舊值弄一份副本，如果遇上數(shù)據(jù)庫崩潰或者事務(wù)中止，因?yàn)檫€保留舊值的副本，那么就可以回頭將它恢復(fù)原狀

需要做的事情就是，在內(nèi)存和磁盤種，去維護(hù)這些 Undo Record，銅鼓耦這種 Logging 的方式將數(shù)據(jù)持久化到磁盤

通過 Logging，可以將隨機(jī)寫入變成循序?qū)懭耄@會使得系統(tǒng)跑的更快

還有一種方案叫做 Shadow Paging

對于每個事務(wù)來說，數(shù)據(jù)庫系統(tǒng)會在磁盤上制作一份該數(shù)據(jù)庫文件的副本，所有的修改都在這個副本上進(jìn)行。當(dāng)事務(wù)提交時，讓指針指向這個副本就好了，那么現(xiàn)在這個副本就是該數(shù)據(jù)的主版本

但沒必要每次都去復(fù)制一份文件，當(dāng)事務(wù)運(yùn)行時，只要復(fù)制該事務(wù)要修改的那些 page 就行。page 修改，指針指向做修改，指向這些 shadow page，那么這些個 shadow page 就是主副本 page

問題是速度很慢，而且在管理磁盤數(shù)據(jù)方面有很大的問題(畢竟是 1970 年代的產(chǎn)物了)，比如磁盤碎片和無序數(shù)據(jù)集

而使用這種過時的方案的數(shù)據(jù)庫就是倆: CouchDB 和 LMDB

## Consistency

一致性是描述數(shù)據(jù)庫正確性的一個模糊術(shù)語

這里主要需要關(guān)心的是 Database Consistency(數(shù)據(jù)庫一致性)

Transaction Consistency(事務(wù)一致性)很難做到

### Database Consistency

數(shù)據(jù)庫反映的是現(xiàn)實(shí)世界的樣子，那么如何做到這種反映呢

為數(shù)據(jù)庫系統(tǒng)提供 Intergrity Constraint(完整性約束)，通過這個約束，可以保證擁有正確的數(shù)據(jù)

比如一個表里面，所有人的年齡都不能小于 0，這就是一個完整性約束

任何未來執(zhí)行的事務(wù)都應(yīng)該能看到以前的某個事務(wù)所做出的正確修改，對于單節(jié)點(diǎn)數(shù)據(jù)庫系統(tǒng)來說，這并沒有什么問題

但對于分布式數(shù)據(jù)庫系統(tǒng)來說，它會更關(guān)注這個，因?yàn)檫@個涉及到并發(fā)，同一時刻 DBMS 的狀態(tài)可能都不是完全相同的

### Transaction Consistency

事務(wù)一致性，簡單來說，如果數(shù)據(jù)庫在執(zhí)行事務(wù)前，它是一致的，并且事務(wù)也是一致的，當(dāng)執(zhí)行完事務(wù)后，數(shù)據(jù)庫的最終狀態(tài)也應(yīng)該是一致的

這個怎么做到呢，可以強(qiáng)制使用一些完整性約束和引用完整性約束，防止事務(wù)去做某些修改

## Isolation of Transactions

隔離性指的是，用戶提交了很多事務(wù)，但是每個事務(wù)都在自己做自己的事情

有隔離性這種保障，那么事務(wù)中的邏輯就容易編寫(只用寫單線程代碼就好了)

可以通過最開始提到的 Strawman 方案來做到這點(diǎn)，通過單線程來逐個執(zhí)行這些事務(wù)

為了獲得更好的并行性，可以在并發(fā)時交錯執(zhí)行這些事務(wù)

但是既要保證隔離性又要保證并發(fā)，這個就很難了

### 保證 Isolation 的機(jī)制

就是通過并發(fā)控制協(xié)議來做到這點(diǎn)

使用 latch 來強(qiáng)制保證多個線程要訪問的數(shù)據(jù)結(jié)構(gòu)的正確性，所以要對數(shù)據(jù)庫對象做相同的處理

latch 用來保護(hù)數(shù)據(jù)結(jié)構(gòu)中的內(nèi)部信息

lock 則用來保護(hù)這些數(shù)據(jù)庫對象

有 2 種協(xié)議

1. 悲觀協(xié)議

? ? 不要讓問題在最開始發(fā)生。在允許事務(wù)執(zhí)行操作之前，先讓它們?nèi)カ@取 lock。通過使用 lock，確保事務(wù)以正確的順序執(zhí)行

2. 樂觀協(xié)議

? ? 假設(shè)數(shù)據(jù)訪問沖突的問題出現(xiàn)的次數(shù)很少，那么就讓這些事務(wù)直接去執(zhí)行操作。在它們提交時，在回過頭去看看它們所做的事情是否正確，執(zhí)行期間是否存在沖突

為什么并發(fā)控制協(xié)議復(fù)雜?

例子

假設(shè) A 和 B 都有 1000 刀，這個時候去執(zhí)行 T1 和 T2 這兩個事務(wù)，會發(fā)生什么

可能會得到很多個結(jié)果，如下圖

但不管 T1 和 T2 執(zhí)行的順序如何，最終 A+B 都應(yīng)該是 2120 刀

即便 T1 先比 T2 交付給數(shù)據(jù)庫系統(tǒng)，數(shù)據(jù)庫系統(tǒng)也不能保證它會先執(zhí)行 T1

但最終，還是希望該數(shù)據(jù)庫的最終狀態(tài)和在單線程中按照順序執(zhí)行這些事務(wù)所得到的結(jié)果相同

在不同的執(zhí)行順序下，A 和 B 的狀態(tài)可能是不同的

但是交錯執(zhí)行后，A + B 的結(jié)果是相同的

## Interleaving Transactions

交錯執(zhí)行這些事務(wù)，才能提升并發(fā)性能

例子

上圖中，左邊和右邊按照順序執(zhí)行事務(wù)的效果相同，數(shù)據(jù)庫數(shù)據(jù)最終狀態(tài)相等，盡管 T2 對同一個對象執(zhí)行操作前，T1 會先對該對象進(jìn)行操作

但對于上圖中的交錯執(zhí)行來說就不行，因?yàn)閿?shù)據(jù)庫最終的狀態(tài)跟之前的不一致了

那么站在數(shù)據(jù)庫系統(tǒng)的角度，它看到了啥呢

它看到的就是一系列讀和寫操作?？傊瑪?shù)據(jù)庫系統(tǒng)始終會通過正確的執(zhí)行順序來判讀調(diào)度是否正確

## Correctness

如果某個 schedule 的執(zhí)行結(jié)果等同于按順序的執(zhí)行的結(jié)果，那么這種執(zhí)行順序的 schedule 就是正確的

## Formal Properties of Schedules

Serial Schedule 的意思是逐個執(zhí)行事務(wù)，而不是交錯執(zhí)行它們

Equivalent Schedules 的意思是如果數(shù)據(jù)庫這些對象的最終狀態(tài)是相等的，那么它們的執(zhí)行效果就是相同的

如果一個 schedule 的執(zhí)行結(jié)果等同于某種按順序執(zhí)行的結(jié)果，不管它是按照哪種順序執(zhí)行，如果該 schedule 的執(zhí)行結(jié)果等于按順序執(zhí)行的結(jié)果，那么不管這個 schedule 是什么，它都是 Serializable 的

如果用一種正式的方式來確定，當(dāng)某個沖突違反來事務(wù)的有序性時，會發(fā)生什么

## Conflicting Operations

如果 2 個不同的事務(wù)在同一時刻同時執(zhí)行，并且它們要對同一個對象進(jìn)行操作，并且至少其中一個操作是一個寫操作，那么就會有 3 種沖突類型

### Interleaved Execution Anomalies

1. 讀寫沖突

? ? 也叫 Unrepeatable Read(不可重復(fù)讀)

? ??

2. 寫讀沖突

? ? 也叫 Dirty Reads(臟讀)

? ??

3. 寫寫沖突

? ? 覆寫未能提交的數(shù)據(jù)

### Conflict Serializable Schedules

如果 2 個 schedule 被認(rèn)為是 confilct equivalent(沖突等價)，僅僅只當(dāng)它們涉及到同時運(yùn)行的是同一組操作和事務(wù)時，每對 conflicting transaction 會按照相同的方式進(jìn)行編排

當(dāng) 1 個 confilcting transaction 對某個對象進(jìn)行更新，就會發(fā)生對某個對象進(jìn)行讀取或者寫入操作

假設(shè) Schedule S 是 conflict serializable 的

那么如何判斷一個 schedule 是 conflict serializable 的呢

通過交換那些不沖突操作的順序來弄清楚該 Schedule 是否是 conflict serializable 的

比如將事務(wù) 1 的一些操作放在事務(wù) 2 的一些操作之前執(zhí)行，直到它們的執(zhí)行結(jié)果和按照順序所得到的結(jié)果一致為止

例子

比如上圖中這里要交換的操作是 R(B) 和 W(A)，注意此時這倆操作涉及的并不是同一個對象

此時可以讓 R(B) 在 W(A) 之前執(zhí)行

同樣的 R(B) 也可以在 R(A) 之前執(zhí)行

那么中間經(jīng)過兩兩交換之后，它就會出現(xiàn)下圖

它等同于右邊這個 Schedule

但是上圖中的例子就不能這么干了，因?yàn)?左邊交換之后 !== 右邊

### Serializability

但是交換操作成本太高，那么有沒有一種方式是不通過交換就能確定這個 Schedule 是 Serializable 的呢

有，使用 Dependency Graph(依賴圖)

### Dependency Graphs

也叫優(yōu)先圖

在 Schedule 中，每個事務(wù)都是一個節(jié)點(diǎn)，如果一個事務(wù)中的某個操作會與其他事務(wù)中的另一個操作產(chǎn)生沖突，那么這兩個事務(wù)間就會有一條線

在這個 Schedule 中第一個操作執(zhí)行的要比其他事務(wù)更早，如果去查看整個 Schedule，并生成了相關(guān)的依賴圖，如果這個圖里面存在一個環(huán)，那么它就不是 Serializable 的，因?yàn)榇藭r不能交換它們的執(zhí)行順序

如果這個圖里面不存在環(huán)，那么它就是 Conflict Serializable

例子

很明顯，上圖中 W(A) 會和 R(A) 發(fā)生沖突，那么在其依賴圖中就會有一條線

對于 B 也是一樣的

此時，就有了一個環(huán)，那么這個執(zhí)行順序就是 Conflict Serializable 的

例子 2

經(jīng)過上圖中的交換之后，這是否等同于按順序執(zhí)行的效果呢

答案是肯定的，因?yàn)樗罱K產(chǎn)生的結(jié)果跟按照順序執(zhí)行所得到的結(jié)果是一致的

例子 3

對 B 所做的任何修改都不會被寫入數(shù)據(jù)庫，只有 W(B) 這個操作會被寫入數(shù)據(jù)庫

在依賴圖中，有 1 條關(guān)于 A 的從 T1 指向 T2 的線

在下面有 1 條關(guān)于 B 的線，它的方向和上面那條線是相反的

此時有一個環(huán)，所以這個就不是 Conflict Serializable 的，盡管如此，此時依然能得到與按順序執(zhí)行事務(wù)時相同的結(jié)果和相同的數(shù)據(jù)庫狀態(tài)

而這就是 View Serializability

## View Serializability

屏幕打印看到的結(jié)果和實(shí)際最終的結(jié)果不一樣，所以要追求看到的和實(shí)際的一致

但實(shí)際上，沒人這么做，因?yàn)檫@需要解釋該應(yīng)用程序或者該事務(wù)要嘗試做的是什么，以此來知道是否能交錯執(zhí)行它們

當(dāng)下這個并不存在，還處于理論階段

例子

生成的依賴圖中，這里面存在一個環(huán)，因此它也不是 Conflict Serializable 的

實(shí)際執(zhí)行效果等同于下圖

在應(yīng)用程序中，如果 T3 所執(zhí)行的這個寫操作是最后一個寫操作，那么這是 OK 的

因?yàn)楫?dāng)執(zhí)行完全這些事務(wù)后，唯一要關(guān)注的，就是 A 的值是什么，沒人會去在意 T1 和 T2 對 A 所做的寫入操作，因?yàn)?T3 會將它覆蓋掉，最后就只需要關(guān)心 T3 所做的這個寫操作，而不用去在意其他線程所做的寫操作

## Transaction Durability

事務(wù)持久化，與日志相關(guān)

## Universe of Schedules

## 結(jié)論

要確保當(dāng)對任意對象進(jìn)行讀或者寫操作時，如果另一個事務(wù)也在做相同的操作，那么需要通過正確的執(zhí)行順序來判斷調(diào)度是否正確

Serial Schedule 是包含在具有正確結(jié)果的 Ordering Schedule 之中的，它們最終都會有一個相同的狀態(tài)