> 這期依然沒有 Andy，悲

## 并發(fā)控制方案

兩階段鎖是一種機制，數(shù)據(jù)庫可以通過它在運行時生成 Serializable Schedule，它依靠鎖才能做到這些

但是今天要討論的是一些不依靠鎖的協(xié)議(就靠時間戳來實現(xiàn))

兩階段鎖其實就是個悲觀鎖方案，它假設(shè)數(shù)據(jù)庫中執(zhí)行的事務(wù)里面存在著大量的爭搶情況

而基于時間戳順序的方案則是個樂觀鎖方案，因為它可以允許數(shù)據(jù)庫在不獲取鎖的情況下對數(shù)據(jù)進行讀和寫。然后正確地調(diào)整出正確的 Serializable Schedule

## T/O 并發(fā)控制

數(shù)據(jù)庫可以基于時間戳這種機制來對時間戳進行分配，以此來預(yù)定義這些事務(wù)的提交順序

數(shù)據(jù)庫要保證的是，如果事務(wù) Ti 小于事務(wù) Tj 的時間戳，那么在 Serializable Schedule 中，Ti 會在 Tj 之前執(zhí)行

那么如何做到呢

## 時間戳分配

這些時間戳其實就是唯一并且有固定長度的數(shù)字

時間戳有幾個特征

1. 必須單調(diào)增加(時間戳的值必須隨著時間的流逝而增加)

2. 值是唯一的(永遠不能擁有兩個具備相同時間戳的事務(wù))

事務(wù)執(zhí)行時，數(shù)據(jù)庫會將這些時間戳分配給事務(wù)

需要注意的是，時間戳不一定要和 clock time (CPU 的掛鐘時間)有所對應(yīng)，因為可以在事務(wù)執(zhí)行時的任意時間點給事務(wù)分配時間戳

如果是分布式數(shù)據(jù)庫，如果使用掛鐘時間，那么很難保證時間同步(因為有很多機器)

在同步時間時，時間軸可能會回調(diào)(tiao)

使用系統(tǒng)時鐘(System Clock)，就會遇到夏令時和冬令時導(dǎo)致的時間調(diào)整。比如到了夏令時，時間會往回調(diào)整一個小時，那么現(xiàn)在這個所謂的時間就不是單調(diào)增加的了，因為它往回調(diào)了

邏輯計數(shù)器是這樣的概念，假設(shè)在 CPU 中有一個專門用來保存時間的寄存器，它里面的值是單調(diào)增加的，而這些值的長度是 32 Bit 或者 64 Bit

邏輯計數(shù)器依然不適合分布式，而且假如你的長度是 32 Bit，如果計數(shù)超過 32 Bit，那么到那個時候，計數(shù)器也會往回走

最后一種就是 Hybrid 方案，它回讓時間戳和物理計數(shù)器以及邏輯計數(shù)器進行匹配，以此確定所有東西都是正常工作的

## 課程目標

## 基礎(chǔ) T/O

基于時間戳順序方案的基本思想是，在不獲取鎖的情況下，要讓系統(tǒng)中的事務(wù)能夠?qū)?shù)據(jù)中的對象進行讀寫操作

怎么做呢，這個就需要往數(shù)據(jù)庫對象中添加一些額外的元數(shù)據(jù)，特別是，要往數(shù)據(jù)庫系統(tǒng)中每個 tuple 上都要添加兩個時間戳

- read timestamp

? ? 表示最近讀取該對象的事務(wù)的時間戳

- write timestamp

? ? 表示是該系統(tǒng)中最近對該 tuple 進行寫入操作的那個事務(wù)的時間戳

當事務(wù)執(zhí)行時，它要確保它可以利用與該 tuple 相關(guān)的時間戳來讀取這個 tuple

### 基礎(chǔ) T/O Reads

在從數(shù)據(jù)庫系統(tǒng)中讀取一個值之前，要確保它是一個不變量

要確保這個事務(wù) Ti 中這個時間戳不小于該系統(tǒng)中這個 tuple 所對應(yīng)的 write timestamp

也就是說，要確保該系統(tǒng)中沒用其他事務(wù)對該 tuple 進行寫入操作

也就確保了，這個事務(wù)不會讀取到未來另一個事務(wù)在這個數(shù)據(jù)庫中覆寫的值

如果這個不變量失效了，就要把這個對應(yīng)事務(wù)中止掉

要更新時間戳，就必須在 read timestamp 和自己的時間戳中選出那個最新的時間戳來進行更新

一旦時間戳得到更新，就必須將該 tuple 的副本保存到一個本地私有工作空間中去(只對你可見)，這樣才可以確保做到可重復(fù)讀

> TODO: 這里沒怎么懂，后面再看一遍

當另一個事務(wù)進來并對系統(tǒng)中的數(shù)據(jù)進行更新操作時，這種情況下必須能讀取到你最初讀取的值，但如果你允許另一個事務(wù)去更新這里的值，那么就要無效化之前提到的那個不變量，就不能讀取到這個值，但實際上應(yīng)該能夠讀取到這個值，因為在這個事務(wù)中讀取到的是一個不一致狀態(tài)

### 基礎(chǔ) T/O Writes??

如果事務(wù)的時間戳小于寫入的那個對象所攜帶的 read timestamp，這意味著這是一個新的事務(wù)，并且會讀取到一個過時的值，這個值就不應(yīng)該存在，這就違反了時間戳順序協(xié)議

如果事務(wù)的時間戳小于另一個對象所攜帶的 write timestamp，那么一個新事務(wù)會覆蓋掉這個值，這種情況也違反了協(xié)議

如果不是上述兩種情況，那么就是一個有效的寫操作，就需要去更新該 tuple 的 write timestamp，所以這里也必須要制作一個本地副本，用來支持可重復(fù)讀(這樣就可以從副本讀而沒必要去數(shù)據(jù)庫讀了)

### 例子 1

R-TS(Read TimeStamp)

W-TS(Write TimeStamp)

T1 事務(wù)執(zhí)行 R(B)，此時得到的時間戳 1 > 0，于是將 B 的 read timestamp 值更新為 1

現(xiàn)在切換到 T2，執(zhí)行 R(B)，然后可以對它的 read timestamp 進行更新，取當前 read timestamp 和新時間戳這兩者間的最大值作為它的新 read timestamp，就是 2

然后執(zhí)行 W(B)，通過查看 B 的 write timestamp，發(fā)現(xiàn)真實的時間戳要大于它，所以要將 B 的 write timestamp 更新為 2

然后切回 T1，T1 執(zhí)行 R(A)，它去查看 A 的 write timestamp(這里為啥是 write 不是 read?)，發(fā)現(xiàn) 1 > 0，所以就更新對應(yīng)的 A 的 read timestamp 為 1

然后切回到 T2，執(zhí)行 R(A)，此時看 A 的 write timestamp，2 > 0，將 A 的 read timestamp 更新為 2

最后，T2 執(zhí)行 W(A)，它去查看 A 的 read 和 write timestamp，此時的時間戳要比這兩個時間戳都要來的大，即 2

所以此時就不存在違反協(xié)議的情況

### 例子 2

T1 執(zhí)行 R(A)，那么 T1 會去更新 read timestamp

接著切換到 T2，執(zhí)行 W(A)，它會檢查 A 的 read timestamp 和 write timestamp，此時有效，然后它會將 A 的 write timestamp 更新為 2

然后再切換回 T1，此時執(zhí)行 W(A)，它會檢查 A 的 read timestamp 和 write timestamp，此時無效，因為 A 的 read timestamp 是 1，而這個 1 小于 A 的 write timestamp 的 2，這就造成了一個協(xié)議違反，所以 T1 不能進行提交，需要對它進行中止

那么這里可不可以優(yōu)化呢

可以的，因為每個事務(wù)會為它所操作的 tuple 制作一份本地副本，本質(zhì)上來講，這個 T1 的 W(A) 就可以被系統(tǒng)所忽略了。盡管在事務(wù)內(nèi)部，T1 依然需要這個寫操作，因為需要能夠讀取到這個寫操作所做的修改

## 托馬斯寫入規(guī)則

基本思路是，如果試著對對象 X 進行寫入操作，如果當前時間戳小于該對象的 read timestamp，則依然需要中止該事務(wù)，并開啟一個攜帶新時間戳的事務(wù)

但如果該時間戳小于該對象的 write timestamp，這意味著有一個比較新的事務(wù)已經(jīng)修改過該對象了，實際上就可以忽略掉這個寫操作

此時可以讀取這個對象的本地存儲副本

從外界來看，將這個寫操作忽略掉是 OK 的

在特定場景下，這種優(yōu)化是有用的，這會允許數(shù)據(jù)庫去提交這種 Schedule

例子

T1 執(zhí)行 R(A)，并更新它的時間戳

T2 執(zhí)行 W(A)

切回到 T1，執(zhí)行 W(A)，此時 T1 執(zhí)行的這個寫操作應(yīng)該是無效的

此時就不用去更新 A 的 write timestamp 或者對應(yīng)的值，但會維護一份本地副本，忽略掉這個問題，并讓 T1 繼續(xù)執(zhí)行

對于 T1 中所有對于 A 接下來的進行讀操作時讀取到的值，都是本地副本中的這個值

## 基礎(chǔ) T/O

和兩階段鎖類似，只要不使用托馬斯寫入規(guī)則，數(shù)據(jù)庫可以通過這種機制生成 Conflict Serializable Schedule

通過使用這種方法可以防止死鎖問題

對于在數(shù)據(jù)庫中執(zhí)行的每個操作來說，要確保這是一個有效的操作，就要逐步生成這種 Serialization Graph，一旦檢測到有環(huán)存在，就在兩階段鎖中讓這個事務(wù)無效，并中止該事務(wù)

而基于這些時間戳，那么就要逐步檢查每個操作是否有效，然后盡早中止它們

對于 Starvation 的情況，假設(shè)有一個已經(jīng)運行了很長一段時間的事務(wù)，然后還有一些執(zhí)行時間很短的事務(wù)，這些短事務(wù)只是對一些 tuple 進行更新，然后提交事務(wù)，就結(jié)束了。本質(zhì)上來講，它們會讓那些引起沖突和連環(huán)中止的老事務(wù)無效化

時間戳順序協(xié)議規(guī)定了 Schedule 是不可恢復(fù)的

那么什么是可恢復(fù)的 Schedule?

## 可恢復(fù)的 Schedule

一個事務(wù)只有當它所依賴數(shù)據(jù)的對應(yīng)的事務(wù)都已經(jīng)提交的情況下，它再進行提交，這樣的 Schedule 是可恢復(fù)的

例子

T1 執(zhí)行 W(A)，T2 執(zhí)行 R(A)，接著執(zhí)行了 W(B)

在這種 Serial Order 情況下，T1 先執(zhí)行，然后 T2 再執(zhí)行，那么 T2 中的這個讀操作是可以讀取到 T1 中的這個寫操作修改過的值

然后 T2 又執(zhí)行了 W(B)，進行提交

假設(shè)過了一段時間后， T1 被中止了。然而此時對于外界來說，T2 已經(jīng)被提交了，但它讀取到了一個來自已經(jīng)被中止的事務(wù)(T1)中的值，實際上這是無效的，這不是一個可恢復(fù)的 Schedule

那么也就不應(yīng)該將 T2 中的寫操作落地

雖然這個 Schedule 不可恢復(fù)，但對于 basic timestamp ordering 并發(fā)協(xié)議來說，這種情況是允許發(fā)生的

## Basic T/O 的性能問題

basic timestamp ordering 協(xié)議的開銷很大，因為每當要執(zhí)行讀寫操作時，都需要將數(shù)據(jù)復(fù)制到本地工作空間中

在執(zhí)行長時間運行的事務(wù)時，會遇上 starvation 的情況，那些執(zhí)行時間不長的事務(wù)會快速更新 1 個或者 2 個 tuple，而這會讓那些執(zhí)行時間很長的事務(wù)被中止并重啟

## 一個觀察

在兩階段鎖中，只要對數(shù)據(jù)庫中的值進行讀寫，那么就必須獲取某個 Lock，以防止數(shù)據(jù)庫系統(tǒng)中其他事務(wù)跑過來影響

而 timestamp ordering 協(xié)議也是這樣，每當要對某個 tuple 進行讀寫時，必須確保時間戳與要執(zhí)行的那個操作對齊

而這兩種方案都假設(shè)系統(tǒng)中存在大量爭搶鎖的場景，并試著阻止那些錯誤的事情發(fā)生

那么假設(shè)系統(tǒng)中沒有這么多爭搶鎖的場景會怎么樣呢?

假設(shè)這些事務(wù)的存活周期很短，并且彼此之間沒有沖突，該怎么優(yōu)化?

## 樂觀并發(fā)控制

即以樂觀的角度來看待系統(tǒng)中事務(wù)執(zhí)行的方式

(由 CMU 的 HT Kung 發(fā)明)

思路是，在基本的 timestamp ordering 協(xié)議中，每次要執(zhí)行一個操作時，首先要將要操作的那個數(shù)據(jù)的副本放入一個線程私有的工作空間中。每當要從數(shù)據(jù)庫讀取某個元素時，先去制作該元素所在的數(shù)據(jù)的副本，然后再對它進行操作

要更新的話，將它的副本放入本地工作空間中，然后對這個本地副本進行更新(這個更新不是在數(shù)據(jù)庫中的)

一旦所有工作完成，準備提交事務(wù)時，要去驗證所有修改與數(shù)據(jù)庫系統(tǒng)中并發(fā)執(zhí)行的其他事務(wù)是相一致的

驗證完成，將在私有工作空間中所做的所有修改，都落地到全局數(shù)據(jù)庫空間中

## OCC 階段

OCC 的作用是用來驗證該事務(wù)是否依然有效，并且不與其他的產(chǎn)生沖突

當 validation 階段結(jié)束時，就必須要將在私有工作空間所做的修改落地到主數(shù)據(jù)庫中

write 階段，以原子的方式將所有修改落地到主數(shù)據(jù)庫中

例子

開始執(zhí)行 T1，此時它構(gòu)建了一個私有工作空間

然后將 A 的副本放入它的私有工作空間中，該副本攜帶著它從數(shù)據(jù)庫系統(tǒng)中所讀取到的 write timestamp

接著執(zhí)行 T2，此時它也構(gòu)建了一個私有工作空間

T2 會在它的私有工作空間中執(zhí)行 R(A)，A 會攜帶著它的 write timestamp

然后 T2 進入 validation 階段，此時它所拿到的時間戳是 1

目前來說因為 T2 是一個只讀事務(wù)，它不需要做任何驗證方面的事情

然后 T2 進入 write 階段，由于沒什么東西可寫，直接提交

現(xiàn)在切換回 T1，T1 要執(zhí)行 W(A)，那么此時 T1 要對它的本地副本進行修改，它的 write timestamp 就被設(shè)置成 ∞

(只有當個事務(wù)進行 validation 階段時，才會被分配一個時間戳，而這里 T1 此時沒有 validation 階段，所以就沒有時間戳)

T1 進入 validation 階段，此時它拿到的時間戳是 2，若此時系統(tǒng)中沒有其他并發(fā)執(zhí)行的事務(wù)，那么 T1 的 validation 階段就算完成了

T1 的 write 階段，需要將其操作的 tuple 的 write timestamp 更新為它開始進行驗證時所分配的 timestamp(也就是 2)

### OCC-驗證階段

數(shù)據(jù)庫要確保它所生成的 Schedule 是 Serializable/Conflict Serializable 的，對于每個事務(wù)來說，需要去確保這些被修改的東西不存在任何沖突，并且不會與系統(tǒng)中所有其他并發(fā)執(zhí)行的事務(wù)產(chǎn)生讀寫/寫寫沖突

拿到一個時間戳后，用這個時間戳去查看系統(tǒng)中所有其他并發(fā)之心的事務(wù)，確保 read set 和 write set 不會相交，確保有一個正確的 Serial Order

當準備驗證時，調(diào)用 commit，那么數(shù)據(jù)庫就會執(zhí)行 validation 階段，因為它能看到數(shù)據(jù)庫系統(tǒng)中所有的事務(wù)，所以它要確保這個要提交的事務(wù)和其他事務(wù)有沒有沖突

有 2 種驗證技術(shù): backward 和 forward

backward validation

指的是，當某個事務(wù)準備提交時，數(shù)據(jù)庫系統(tǒng)就會去查看該系統(tǒng)中所有較老的事務(wù)

以 T2 為基準，找到所有比 T2 的時間戳還要小的的事務(wù)，并對它們進行驗證操作

畫紅圈的是 T2 的 backward scope，T1 比 T2 老

有可能會遇到這種情況，數(shù)據(jù)庫系統(tǒng)從主數(shù)據(jù)庫中讀取到了某個新數(shù)據(jù)，但這個數(shù)據(jù)在執(zhí)行 T1 的時候就已經(jīng)讀過了，因為 T1 修改的是它自己空間中的那個副本，如果發(fā)生了這種情況，就需要中止 T1

forward validation

找到所有并發(fā)執(zhí)行但還沒有提交的那些事務(wù)，對它們進行驗證操作

假如 T2 對它本地私有空間中的數(shù)據(jù)進行了更新，在 Serial Order 中，它在 T3 之前執(zhí)行，但它已經(jīng)從數(shù)據(jù)庫中讀到了一個過時的值，如果發(fā)生這種情況，就必須中止該事務(wù)

所有事務(wù)在執(zhí)行驗證的時候都是沿著同一方向進行的(要么向前，要么向后)

### OCC-驗證步驟-1

例子

在 T2 執(zhí)行任何操作之前，T1 就完成了它的所有步驟

### OCC-驗證步驟-2

如果 Tj 在開始執(zhí)行它的寫階段前，Ti 就完成了它的工作，那就需要確保，在這種情況下，事務(wù)中寫操作要處理的東西不會與其他事務(wù)的讀操作要涉及的東西相沖突

即其他事務(wù)不會去讀取這個事務(wù)要寫入的東西

例子

如上圖所示

T1 在執(zhí)行驗證操作時，需要中止 T1，因為它是 read set，它的時間戳要比 T2 小，因為 T1 先開始執(zhí)行驗證操作，T1 的 write set 與 T2 的 read set 沖突了。所以這就違反了之前擁有的不變量，就需要中止 T1

那假如 T2 在 T1 之前先執(zhí)行驗證操作呢?

T2 執(zhí)行 R(A)，接著開始驗證，這里它并沒有 write set，也就沒有任何和 T1 這個事務(wù)沖突的部分

T1 也做了相同的事情

T1 的 write set 不與其他并發(fā)事務(wù)中的操作沖突

### OCC-驗證步驟-3

要確保 Tj 開始它的讀階段之前，Ti 完成了它的讀階段

要確保該事務(wù)中的 write set 不與其他事務(wù)的 read set 和 write set 沖突，或者不與其讀階段重疊

例子

T1 執(zhí)行 R(A) 和 W(A)，T2 執(zhí)行 R(B)

然后 T1 執(zhí)行它的驗證階段，它拿到的時間戳是 1

此時 T1 可以進行提交，因為 T1 中的 write set 此時并沒有與 T2 中的 read set 沖突

更新 A 的 Value 為 456，并將它的 write timestamp 設(shè)置為 1

切換回 T2，T2 執(zhí)行 R(A)，現(xiàn)在它去主數(shù)據(jù)庫那邊，讀取到由 T1 更新過的 A 的值，并將它寫入本地副本

驗證后數(shù)據(jù)可以成功寫入，因為這里沒有任何其他的并發(fā)事務(wù)

### OCC-序列驗證

數(shù)據(jù)庫保證事務(wù)是真正 Serializable 的方式是，用一種全局視野，能夠看到系統(tǒng)中所有正在運行的活躍事務(wù)，那么也就能看到每個事務(wù)在系統(tǒng)中所做的所有修改，那么也就可以通過用這種機制來決定系統(tǒng)中事務(wù)的執(zhí)行順序

在整個系統(tǒng)中，在 validation 階段會有一個很大的 latch，它用來確保一次只有一個事務(wù)在執(zhí)行驗證操作

### OCC-讀階段

當試著要對某個值進行讀寫時，要去制作對應(yīng)的副本，并且只對本地副本進行更新，確保支持可重復(fù)讀

### OCC 觀察

當沒有什么沖突的情況下，樂觀并發(fā)協(xié)議中這些基于時間戳的協(xié)議的效果非常好，因為這允許在不獲取 Lock 以及不做那些代價很高的操作的情況下，去處理事務(wù)

然后做一些(半)輕量級的驗證來確保事務(wù)有效

### OCC 性能問題

開銷就是，要維護進行讀寫操作的那些對象的本地副本

驗證階段和寫階段會按照順序執(zhí)行，一次只會有一個事務(wù)進行驗證，所以這個就成為了一個巨大的瓶頸

當一個事務(wù)要提交時，從邏輯上來將，即便這些事務(wù)彼此不會重疊，依然必須要維護要訪問的對應(yīng)數(shù)據(jù)結(jié)構(gòu)的物理正確性

加 latch 的情況下，盡管沖突率低，但只要并發(fā)一大，這個依然會慢

因為即便在邏輯上 read set 和 write set 不相交，但它們依然存在爭搶問題，比如并發(fā)驗證，可能同時會有多個線程查看同一事務(wù)中的本地副本中的數(shù)據(jù)，這個就需要 latch

那么假如，對整個數(shù)據(jù)庫進行分區(qū)會怎么樣呢?

一個事務(wù)所有的工作都只在一個分區(qū)上，那么就可以移除掉這個事務(wù)上所有的 lock/latch，這種做法可行嗎?

可行

## 基于分區(qū)的 T/O

事實上，它就叫做，Partition-Based Timestamp Ordering

將數(shù)據(jù)庫拆分為水平分區(qū)，然后通過時間戳來對該分區(qū)所涉及的事務(wù)進行排序，讓它們以 Serial Order 的順序執(zhí)行

如果事務(wù)都是按照順序執(zhí)行，那么在一個數(shù)據(jù)庫中，也不需要用 lock/latch 了，因為此時不存在并發(fā)

例子

上圖中的 Schema，有 3 個表，Customer 表、Orders 表、Oitems(某個 order 涉及的 item) 表

通過使用這種外鍵引用結(jié)構(gòu)，可以將一些客戶信息、這些客戶對應(yīng)的訂單信息、訂單中涉及的商品信息都保存在一個分區(qū)中

想象一下，將 c_id 1 ~ 1000 的客戶信息放入一個數(shù)據(jù)庫中，將 c_id 10001 到 2000 的客戶信息放入另一個數(shù)據(jù)庫中

假設(shè)此時要去更新某個客戶的信息、訂單信息之類的

某個客戶落在這個分區(qū)，那么這個事務(wù)就會在這個分區(qū)上進行操作，它能安全的做到這些，因為所有的事務(wù)都會放在一個隊列中，這個隊列是用一個單線程去執(zhí)行的

想象一下，如果能將數(shù)據(jù)庫分區(qū)的粒度分的更細，那么在執(zhí)行事務(wù)時，所能獲得的并行性就越高，這樣每個事務(wù)執(zhí)行的速度就會變得更快，因為此時不用去獲取 lock/latch 了

當更多事務(wù)以這種并發(fā)的方式去訪問那些不相交的數(shù)據(jù)集時，并行性就越高

這個協(xié)議很流行

當然這里依然需要給這些事務(wù)分配 id，然后要根據(jù)這些 id 對這些事務(wù)進行排序

### 讀操作

如果讀取存在于多個數(shù)據(jù)庫分區(qū)中的幾行數(shù)據(jù)時，情況就會變得復(fù)雜，比如通過一個事務(wù)來對 2 個不同分區(qū)內(nèi)的 Customer 信息進行修改，那么情況就會變得復(fù)雜

在執(zhí)行這個操作之前，必須要獲取這 2 個不同分區(qū)的 lock 才行

當然這種方式就會損耗性能了，所以用基于分區(qū)的 T/O 時就要注意這些問題

### 寫操作

因為在基于分區(qū)的 T/O 的方式看來，會保證同一時間只有一個事務(wù)在執(zhí)行，那么就可以在數(shù)據(jù)庫中直接更新數(shù)據(jù)，回滾也是，但是可以在不需要制作本地副本的情況下做到這點，這樣就能減少通常存在于 OCC 系統(tǒng)中那些數(shù)據(jù)復(fù)制所帶來的開銷

### 例子

假設(shè)這里 2 個服務(wù)器都要試著去訪問第一個分區(qū)中的某個客戶的數(shù)據(jù)

它們發(fā)起的 BEGIN 請求，就會進入一個事務(wù)隊列進行排隊，然后被分配時間戳(100 和 101)

然后執(zhí)行時間戳較小的那個事務(wù)，即 server1，它會去獲取這個數(shù)據(jù)庫分區(qū)對應(yīng)的 lock

操作完成后，server1 提交了該事務(wù)，這樣做是安全的，因為同一時間沒有其他事務(wù)在執(zhí)行

那么 server2 就可以排在隊列前面，獲取 lock 并執(zhí)行

### 性能問題

如果數(shù)據(jù)庫在開始執(zhí)行事務(wù)之前就知道這些事務(wù)需要用到哪些分區(qū)，那么這些系統(tǒng)的速度就會很快，但是在這種事務(wù)協(xié)議中，這樣的做法并不現(xiàn)實

如果事務(wù)要接觸多個分區(qū)，就必須先執(zhí)行一下該事務(wù)，接著中止該事務(wù)，獲取更多的 lock 并重新執(zhí)行該事務(wù)，這樣系統(tǒng)就會變得很慢

這種多分區(qū)設(shè)置，可能會使得有些分區(qū)處于閑置狀態(tài)

## 動態(tài)數(shù)據(jù)庫

如果在執(zhí)行事務(wù)的過程中，數(shù)據(jù)可以被插入，被更新，被刪除，那么就違反了協(xié)議中制定的那些假設(shè)

## 幻讀問題

這里有一個 People 表，里面有 name、age、status 字段

執(zhí)行第一個 SQL，得到 72

T2 執(zhí)行插入，然后切回 T1，T1 試著執(zhí)行和剛才相同的查詢，那么得到的結(jié)果和第一次不同

T2 要往數(shù)據(jù)庫中插入一個新 tuple，它們的操作中沒有用到 lock，那么這個就是一個問題

如果遇上這種幻讀問題，就要確保這里可以進行可重復(fù)讀

沒必要獲取 tuple 中的 lock，但是可以獲取抽象對象對應(yīng)的 lock

比如獲取上述表達式中的 (status = 'lit') 的 lock，可行嗎?

可行

實際上就是這么做的

## 條件鎖

上述的解決方案的術(shù)語就叫做 Predicate Locking，但是實現(xiàn)這個方案的成本非常高，大部分數(shù)據(jù)庫系統(tǒng)都不會去實現(xiàn)它

## 索引鎖

假設(shè)在 status 這個字段上建立了索引，那么就對索引中 status = 'lit' 的 slot 加鎖，然后任何新的插入操作都需要去遍歷索引，并對索引進行更新

如果 status = 'lit' 不在索引中，就要去獲取一個叫 Gap Lock(間隙鎖) 的東西

> 在索引中有一個間隙，獲取了該間隙對應(yīng)的 lock 之后，如果另一個插入操作試圖將符合 (status = 'lit') 條件的 tuple 插入索引中的這個間隙，就不允許它這么做

## 不使用索引加鎖

對 page、table 加鎖，或者使用層級鎖(hierarchical lock)

## 重復(fù)掃描

在事務(wù)提交前，進行反復(fù)掃描

讀的數(shù)據(jù)在提交的這一刻就是最新的，如果不是，就重啟事務(wù)

## 結(jié)論

暫無