概述 本lab將實現一個鎖管理器，事務通過鎖管理器獲取鎖，事務管理器根據情況決定是否授予鎖，或是阻塞等待其它事務釋放該鎖。 背景 事務屬性 眾所周知，事務具有如下屬性： 1. 原子性：事務要麼執行完成，要麼就沒有執行。 2. 一致性：事務執行完畢後，不會出現不一致的情況。 3. 隔離性：多個事務併發 ...
概述
本lab將實現一個鎖管理器，事務通過鎖管理器獲取鎖，事務管理器根據情況決定是否授予鎖，或是阻塞等待其它事務釋放該鎖。
背景
事務屬性
眾所周知，事務具有如下屬性：
- 原子性：事務要麼執行完成，要麼就沒有執行。
- 一致性：事務執行完畢後，不會出現不一致的情況。
- 隔離性：多個事務併發執行不會相互影響。
- 持久性：事務執行成功後，所以狀態將被持久化。
一些定義
將對數據對象Q的操作進行抽象，read(Q)：取數據對象Q，write(Q)寫數據對象Q。
schedule
考慮事務T1，T1從賬戶A向賬戶B轉移50。
T1:
read(A);
A := A - 50;
write(A);
read(B);
B := B + 50;
write(B).事務T2將賬戶A的10%轉移到賬戶B。
T2:
read(A);
temp := A * 0.1;
A := A - temp;
write(A);
read(B);
B := B + temp;
write(B).假設賬戶A、B初始值分別為1000和2000。
我們將事務執行的序列稱為schedule。如下麵這個schedule，T1先執行完，然後執行T2，最終的結果是具有一致性的。我們稱這種schedule為serializable schedule。
T1 T2
read(A);
A := A - 50;
write(A);
read(B);
B := B + 50;
write(B).
read(A);
temp := A * 0.1;
A := A - temp;
write(A);
read(B);
B := B + temp;
write(B).但是看下麵這個shedule：
T1 T2
read(A);
A := A - 50;
read(A);
temp := A * 0.1;
A := A - temp;
write(A);
read(B);
write(A);
read(B);
B := B + 50;
write(B).
read(B);
B := B + temp;
write(B).執行完賬戶A和B分別為950和2100。顯然這個shecule不是serializable schedule。
考慮連續的兩條指令I和J，如果I和J操作不同的數據項那麼，這兩個指令可以交換順序，不會影響schedule的執行結果。如果I和J操作相同的數據項，那麼只有當I和J都是read(Q)時才不會影響schedule的結果。如果兩條連續的指令，操作相同的數據項，其中至少一個指令是write，那麼I和J是conflict的。
如果schedule S連續的條指令I和J不conflict，我們可以交換它們執行的順序，從而產生一個新的schedlue S'，我們稱S和S'conflict equivalent。如果S經過一系列conflict equivalent變換，和某個serializable schedule等價，那麼我們稱S是conflict serializable。
比如下麵這個schedule S：
T1 T2
read(A);
write(A);
read(A);
write(A);
read(B);
write(B);
read(B);
write(B);經過多次conflict equivalent變換，生成新的schedule S'，S'是serializable schedule。
T1 T2
read(A);
write(A);
read(B);
write(B);
read(A);
write(A);
read(B);
write(B);所以S是conflict serializable的。
two-phase locking
不對加解鎖進行限制
前面提到多個事務併發執行的時候，可能出現數據不一致得情況。一個很顯然的想法是加鎖來進行併發控制。
可以使用共用鎖(lock-S)，排他鎖（lock-X）。
問題來了。
在什麼時候加鎖？什麼時候釋放鎖？
考慮下麵這種加解鎖順序：
事務一從賬戶B向賬戶A轉移50。
T1:
lock-X(B);
read(B);
B := B - 50;
write(B);
unlock(B);
lock-X(A);
read(A);
A := A + 50;
write(A);
unlock(A).事務二展示賬戶A和B的總和。
T2:
lock-S(A);
read(A);
unlock(A);
lock-S(B);
read(B);
unlock(B);
display(A+B).可能出現這樣一種schedule：
T1 T2
lock-X(B);
read(B);
B := B - 50;
write(B);
unlock(B);
lock-S(A);
read(A);
unlock(A);
lock-S(B);
read(B);
unlock(B);
display(A+B).
lock-X(A);
read(A);
A := A + 50;
write(A);
unlock(A).假設初始時A和B分別是100和200，執行後事務二顯示A+B為250，顯然出現了數據不一致。
我們已經加了鎖，為什麼還會出現數據不一致？
問題出在T1過早unlock(B)。
two-phase locking
這時引入了two-phase locking協議，該協議限制了加解鎖的順序。
該協議將事務分成兩個階段，
Growing phase：事務可以獲取鎖，但是不能釋放任何鎖。
Shringking phase：事務可以釋放鎖，但是不能獲取鎖。
最開始事務處於Growing phase，可以隨意獲取鎖，一旦事務釋放了鎖，該事務進入Shringking phase，之後就不能再獲取鎖。
按照two-phase locking協議重寫之前的轉賬事務：
事務一從賬戶B向賬戶A轉移50。
T1:
lock-X(B);
read(B);
B := B - 50;
write(B);
lock-X(A);
read(A);
A := A + 50;
write(A);
unlock(B);
unlock(A).事務二展示賬戶A和B的總和。
T2:
lock-S(A);
read(A);
lock-S(B);
read(B);
display(A+B).
unlock(A);
unlock(B);現在無論如何都不會出現數據不一致的情況了。
two-phase locking正確性證明
課本的課後題15.1也要求我們證明two-phase locking（以下稱2PL rule）的正確性。我看了下解答，用的是反正法。我還看到一個用歸納法證的，比較有趣。
前提：
- 假設T1, T2, ... Tn，n個事務遵循two-phase locking協議。
- Sn是T1, T2, ... Tn併發執行的一個schdule。
目標：
證明Sn是conflict serializable的schedule。
證明開始：
起始步驟，n = 1的情況：
T1遵守2PL rule。
S1這個schedule只包含T1。
顯然S1是conflict serializable的schedule。
迭代步驟：
迭代假設：假設Sn-1是T1, T2, ... Tn−1形成的一個schedule，並且Sn-1是conflict serializable的schedule。我們需要證明Sn-1是conflict serializable的schedule，Sn也是conflict serializable的schedule。
假設Ui(•)是事務i的解鎖操作，並且是schedule Sn中第一個解鎖的操作：
可以證明，我們可以將事務i所有ri(•) and wi(•)操作移到Sn的最前面，而不會引起conflict。
證明如下：
令Wi(Y)是事務i的任意操作，Wj(Y)是事務j的一個操作，並且和Wi(Y)conflict。等價於證明不會出現如下這種情況：
假設出現了這種情況，那麼必然有如下加解鎖順序：
又因為所有事務都遵守2PL rule，所以必然有如下加解鎖順序：
衝突出現了，Ui(•)應該是Sn中第一個解鎖操作，但是現在卻是Uj(Y)。所以假設不成立，所以結論："我們可以將事務i所有ri(•) and wi(•)操作移到Sn的最前面，而不會引起conflict"成立。
我們將事務i的所有操作移到schedule最前面，
又因為Sn-1是conflict serializable的所以Sn是conflict serializable的。
證明完畢
two-phase locking不能保證不會死鎖
two-phase locking可以保證conflict serializable，但可能會出現死鎖的情況。
考慮這個schedule片段：
T1 T2
lock-X(B);
read(B);
B := B - 50;
write(B);
lock-S(A);
read(A);
lock-S(B);
lock-X(A);T1和T2都遵循2PL rule，但是T2等待T1釋放B上的鎖，T1等待T2釋放A上的鎖，造成死鎖。
死鎖處理
有兩類基本思路：
- 死鎖預防，這類方法在死鎖出現前就能發現可能導致死鎖的操作。
- 死鎖檢測，這類方法定期執行死鎖檢測演算法，看是否發生死鎖，如果發生了，執行死鎖恢復演算法。
這裡介紹wait-die這種死鎖預防機制，該機制描述如下：
事務Ti請求某個數據項，該數據項已經被事務Tj獲取了鎖，Ti允許等待當且僅當Ti的時間戳小於Tj，否則Ti將被roll back。
wait-die正確性證明
為什麼該機制能保證，不會出現死鎖的情況呢？
如果Ti等待Tj釋放鎖，我們記Ti->Tj。那麼系統中所有的事務將組成一個稱作wait-for graph的有向圖。容易證明：wait-for graph出現環和系統將出現死鎖等價。
wait-die這種機制就能防止出現wait-for graph出現環。為什麼？因為wait-die機制只允許時間戳小的等待時間戳大的事務，也就是說在wait-for graph中任意一條邊Ti->Tj，Ti的時間戳都小於Tj，顯然不可能出現環。所以不會出現環，也就不可能出現死鎖。
事務管理器實現
事務管理器LockManager對外提供四個介面函數：
- LockShared(Transaction *txn, const RID &rid)：事務txn希望獲取數據對象rid的讀鎖，對應上述lock-S()。
- LockExclusive(Transaction *txn, const RID &rid)：事務txn希望獲取數據對象rid的寫鎖，對應上述的lock-X()。
- LockUpgrade(Transaction *txn, const RID &rid)：將寫鎖升級為讀鎖。
- Unlock(Transaction *txn, const RID &rid)：對應上述unloxk()。
可以用如下數據結構來實現：
每個數據項對應一個鏈表，該鏈表記錄請求隊列。
當一個請求到來時，如果請求的數據項當前沒有任何事務訪問，那麼創建一個空隊列，將當前請求直接放入其中，授權通過。如果不是第一個請求，那麼將當前事務加入隊列，只有當前請求之前的請求和當前請求相容，才授權，否則等待。
在哪裡調用LockManager呢？
page/table_page.cpp中的TablePage類用於插入，刪除，更新，查找表記錄。在執行插入，刪除，查找前都會獲取相應的鎖，確保多個事務同時操作相同數據項是安全的。
LockManager的具體代碼可以參考我的手實現：https://github.com/gatsbyd/cmu_15445_2018
參考資料：
- http://www.mathcs.emory.edu/~cheung/Courses/554/Syllabus/7-serializability/2PL.html
- 《Database System concepts》 chapter 14, 15
