布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)中的

1、1. 1.并發(fā)控制的概念和理論并發(fā)控制的概念和理論2.2.分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的封鎖技術3.3.分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理4.4.分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術5.5.分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的多版本技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的多版本技術6.6.分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的樂觀方法分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的樂觀方法分布式數(shù)據(jù)庫中的并發(fā)控制分布式數(shù)據(jù)庫中的并發(fā)控制 第第5章章 通常，數(shù)據(jù)庫總有若干個事務在運行，這些事務可能并發(fā)地存取相同的數(shù)據(jù)，稱為事務的并發(fā)操作。 當數(shù)據(jù)庫中有多個事務并發(fā)執(zhí)

2、行時，系統(tǒng)必須對并發(fā)事務之間的相互作用加以控制，這是通過并發(fā)控制機制來實現(xiàn)的。 并發(fā)控制就是負責正確協(xié)調(diào)并發(fā)事務的執(zhí)行，保證這種并發(fā)的存取操作不至于破壞數(shù)據(jù)庫的完整性和一致性，確保并發(fā)執(zhí)行的多個事務能夠正確地運行并獲得正確的結果。 分布式數(shù)據(jù)庫中的并發(fā)控制解決多個分布式事務對數(shù)據(jù)并發(fā)執(zhí)行的正確性，保證數(shù)據(jù)庫的完整性和一致性。比集中式并發(fā)控制更復雜。1.1 并發(fā)控制的概念并發(fā)控制的概念1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論集中式DB環(huán)境 T1T2TnDB(一致性約束)1.1 并發(fā)控制的概念并發(fā)控制的概念1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論分布式DB環(huán)境XYZT1T21.1

3、并發(fā)控制的概念并發(fā)控制的概念1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論 多處理器CPU1CPU2T1T2Time1.1 并發(fā)控制的概念并發(fā)控制的概念1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論并發(fā)執(zhí)行并發(fā)執(zhí)行 單處理器T1t1T2t2T1t3T2t4TimeCPU1.1 并發(fā)控制的概念并發(fā)控制的概念1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論非并發(fā)執(zhí)行非并發(fā)執(zhí)行UPDATE x70t6FIND xt2200t7UPDATE xt5x:=x*2t4x:=x-30t3FIND xt1100t0更新事務T2數(shù)據(jù)庫中X的值更新事務T1時間注：其中FIND表示從數(shù)據(jù)庫中讀值，UPDATE表

4、示把值寫回到數(shù)據(jù)庫T1T2，結果140，T2T1,結果170，得到結果是200，顯然是不對的，T1在t7丟失更新操作。1.1 并發(fā)控制的概念并發(fā)控制的概念1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論并發(fā)控制問題之一：丟失更新并發(fā)控制問題之一：丟失更新FIND xt270t5UPDATE xt4x:=x-30t3FIND xt1100t0更新事務T2數(shù)據(jù)庫中A的值更新事務T1時間注：在時間t5事務T2仍認為x的值是1001.1 并發(fā)控制的概念并發(fā)控制的概念1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論并發(fā)控制問題之二：不一致分并發(fā)控制問題之二：不一致分析析100t6x:=x-10t2ROL

5、LBACKt5FIND x90t4UPDATE xt3FIND xt1100t0更新事務T2數(shù)據(jù)庫中A的值更新事務T1時間注： 事務T2依賴于事務T1的未完成更新1.1 并發(fā)控制的概念并發(fā)控制的概念1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論并發(fā)控制問題之三：依賴于未提交更新（讀臟數(shù)據(jù)）并發(fā)控制問題之三：依賴于未提交更新（讀臟數(shù)據(jù)）事務Ti Ti= i, i 其中：1. i : 操作符集合：Ri(x), Wi(x) U Ai, Ci 2. Ai, Ci 是最后的操作符，只能是其一3. i : (沖突)操作有序執(zhí)行，Ri(x) i Wi(x) 或 Wi(x) i Ri(x)1.2 事務可串行

6、化理論事務可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論 操作符集 讀Ri(x)和寫Wi(x)動作序列 沖突動作 R1(A) W2(A) W1(A) W2(A) R1(A) W2(A) 一個調(diào)度事務的一個操作序列稱為一個調(diào)度，一般用S表示比如，S: R1(x),R2(y),W2(y),R2(x),W1(x),W2(x)1.2 事務可串行化理論事務可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論 T1 T21(T1) a X 5 (T2) c X2(T1) X a+100 6 (T2) X 2c3(T1) b Y 7 (T2) d Y4(T1) Y b+100 8 (T

7、2) Y 2d先序關系例子例子已知：站點1有數(shù)據(jù)X，站點2有數(shù)據(jù)Y約束：X=Y1.2 事務可串行化理論事務可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論(X站點)(Y站點)1 (T1) a X 2 (T1) X a+100 5 (T2) c X 3 (T1) b Y6 (T2) X 2c 4 (T1) Y b+100 7 (T2) d Y 8 (T2) Y 2d 初值: X=Y=0 , 結果: X=Y=200 調(diào)度S1事務內(nèi)事務間令T= T1,T2,Tn 是一組事務. T上的調(diào)度 S 是具有如下順序關系T的偏序，即S=T ,T :(1) T= Ti(2) T i(3) 對于任意一

8、組沖突操作 p,q S, 存在 p q 或 q p關系并發(fā)調(diào)度定義i=1NNi=11.2 事務可串行化理論事務可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論 調(diào)度 一組事務的調(diào)度必須包含這些事務的所有操作 調(diào)度中某個事務的操作順序必須保持與該事務原有的順序相同 串行調(diào)度 一個事務的第一個動作是在另一個事務的最后一個動作完成后開始. 即調(diào)度中事務的各個操作不會交叉, 每個事務相繼執(zhí)行. 一致性調(diào)度 調(diào)度可以使得數(shù)據(jù)庫從一個一致性狀態(tài)轉變?yōu)榱硪粋€一致性狀態(tài)，則稱調(diào)度為一致性調(diào)度1.2 事務可串行化理論事務可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論 調(diào)度等價 S1與S

9、2等價, 也就是說, 對于沖突操作, , Oi Oj在S1中成立, 同時 Oi Oj 在S2中也成立 可串行化調(diào)度 如果一個調(diào)度等價于某個串行調(diào)度，則該調(diào)度稱為可串行化調(diào)度。 也就是說，該調(diào)度可以通過一系列非沖突動作的交換操作使其成為串行調(diào)度1.2 事務可串行化理論事務可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論例子兩個事務，定義如下：T1:1.Read(x）2.x=x+103.Write(x)4.Read(y)5.y=y-156.Write(y)mit1.2 事務可串行化理論事務可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論T2:1. Read(x）2. x=x

10、-203. Write(x)4. Read(y)5. y=y*26. Write(y)7. commit五種調(diào)度：S1=R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1, R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2S2=R1(x),x=x+10,W1(x), R2(x),x=x-20,W2(x), R1(y),y=y-15,W1(y),C1, R2(y),y=y*2,W2(y),C2S3=R1(x),x=x+10,W1(x), R2(x), x=x-20,W2(x),R2(y),y=y*2,W2(y),C2 ,R1(y),y=

11、y-15,W1(y),C1S4=R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2 ,R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1S5=R2(x),x=x-20,W2(x), R1(x),x=x+10,W1(x), R2(y),y=y*2,W2(y),C2 ,R1(y),y=y-15,W1(y),C11.2 事務可串行化理論事務可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論如果將事務提交延遲到兩個事務操作完成之后執(zhí)行，有：調(diào)度S1和S4是串行調(diào)度調(diào)度S2和S1的沖突操作具有相同的順序，因此是等價調(diào)度；S2是可串行化調(diào)

12、度，也是一致性調(diào)度調(diào)度S3雖是一致調(diào)度，但是它不與S1或S4等價，所以S3不是可串行化調(diào)度調(diào)度S5和S4等價，所以S5是一致調(diào)度，也是可串行化調(diào)度1.2 事務可串行化理論事務可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論有以下推論：一個可串行化調(diào)度必定與某個串行調(diào)度等價，且是一致性調(diào)度一致性調(diào)度不一定是可串行化調(diào)度同一事務集幾個可串行化調(diào)度，他們的結果未必相同1.2 事務可串行化理論事務可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論優(yōu)先圖 P(S) 調(diào)度 S 的優(yōu)先圖是一個有向圖G(N,E) ，其中 N: 一組節(jié)點N=T1T2,Tn, S中的事務 E: 一組有向邊E

13、=e1,e2,en, Ti Tj 是圖中的一條邊，當且僅當 p Ti, q Tj 使得p, q 沖突，并且 p S q1.3 分布式事務的可串行化調(diào)度測試分布式事務的可串行化調(diào)度測試1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論測試調(diào)度S的可串行化 對于調(diào)度 S中的事務Ti，在圖中創(chuàng)建一個節(jié)點Ti 對于每一種這樣的情形：如果S中的在Ti執(zhí)行了W(X)操作后執(zhí)行Tj的R(X)操作，那么在優(yōu)先圖中創(chuàng)建一條邊（TiTj ） 對于每一種這樣的情形：如果S中的在Ti執(zhí)行了R(X)操作后執(zhí)行Tj的W(X)操作，那么在優(yōu)先圖中創(chuàng)建一條邊（TiTj ） 對于每一種這樣的情形：如果S中的在Ti執(zhí)行了W(X)操

14、作后執(zhí)行Tj的W(X)操作，那么在優(yōu)先圖中創(chuàng)建一條邊（TiTj ） 當且僅當優(yōu)先圖中沒有閉環(huán)時，調(diào)度S是可串行化的1.3 分布式事務的可串行化調(diào)度測試分布式事務的可串行化調(diào)度測試1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論測試調(diào)度S的可串行化 優(yōu)先圖中存在環(huán)路，說明調(diào)度是不可串行化的，否則是可串行化的。 環(huán)路是指有向圖中每條邊的起始節(jié)點（第一條邊除外），都與前一條邊的終止節(jié)點連接，而第一條邊的起始節(jié)點于最后一條邊的終止節(jié)點連接，即事務序列是以同一個節(jié)點作為開始和結束的 調(diào)度S中事務Ti在事務Tj之前，與S等價的調(diào)度中Ti也必須在Tj之前 某項數(shù)據(jù)導致了調(diào)度中的一條邊的生成，就把數(shù)據(jù)項標注到

15、優(yōu)先圖中這條邊的旁邊 如果調(diào)度S中不存在環(huán)路，那么就可能存在若干個與S等價的串行調(diào)度1.3 分布式事務的可串行化調(diào)度測試分布式事務的可串行化調(diào)度測試1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論1.3 分布式事務的可串行化調(diào)度測試分布式事務的可串行化調(diào)度測試1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論T1T2T1T2T1T2T1T2T1T2S1的優(yōu)先圖S2的優(yōu)先圖S3的優(yōu)先圖S4的優(yōu)先圖S5的優(yōu)先圖XYXYXYXYXY存在環(huán)路存在環(huán)路舉例 考慮如下3個事務： T1: Read(x); Write(x); Commit; T2: Write(x); Write(y); Read(z); C

16、ommit; T3: Read(x); Read(y); Read(z); Commit; 這3個事務的一個調(diào)度：S=W2(x),W2(y),R2(z),C2,R1(x),W1(x),C1,R3(x),R3(y),R3(z),C3 優(yōu)先圖： T2 T1 T3無環(huán)， S是串行調(diào)度。1.3 分布式事務的可串行化調(diào)度測試分布式事務的可串行化調(diào)度測試1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論另外一個調(diào)度S:S=W2(x), R1(x),W1(x),C1,R3(x), W2(y), R3(y), R2(z), C2,R3(z),C3 先序圖： T2 T1 T3無環(huán)，是可串調(diào)度。1.3 分布式事務的

17、可串行化調(diào)度測試分布式事務的可串行化調(diào)度測試1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論可串性理論擴展 可串性理論可以直接擴展到無重復副本的分布式數(shù)據(jù)庫中。 事務在每個站點上的執(zhí)行調(diào)度稱作局部調(diào)度 如果數(shù)據(jù)庫無重復副本的分布式數(shù)據(jù)庫，并且每個局部調(diào)度都是可串調(diào)度，只要這些局部調(diào)度的順序一致，則它們的并（全局調(diào)度）也是可串調(diào)度 但是有副本的情況下，就比較復雜?？赡芫植空{(diào)度是可串行化的，而全局調(diào)度不是可串行化的。1.3 分布式事務的可串行化調(diào)度測試分布式事務的可串行化調(diào)度測試1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論 保證只產(chǎn)生可串行化調(diào)度的機制 并發(fā)控制機制分類 按分配模式(數(shù)據(jù)方式)

18、 完全復制的DB 部分復制DB或分片的DB 按網(wǎng)絡類型(通信方式) 廣播能力的 星型網(wǎng), 環(huán)形網(wǎng) 同步化原則 建立在相互排斥地訪問共享數(shù)據(jù)基礎上的算法 通過一些準則(協(xié)議)對事務進行排序的算法 悲觀并發(fā)控制法（事務是相互沖突的），樂觀并發(fā)控制法（沒有太多的事務相互沖突） 1.4 并發(fā)控制機制的常用方法及其分類并發(fā)控制機制的常用方法及其分類1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論并發(fā)控制算法悲觀法樂觀法加鎖法集中式加鎖分布式加鎖時標排序法混合法加鎖法時序排序法主副本加鎖基本時標排序保守時標排序多版本時標排序并發(fā)控制算法的分類 封鎖法 事務的同步化是通過對數(shù)據(jù)庫的片斷或者數(shù)據(jù)項進行物理或邏

19、輯封鎖來實現(xiàn)的 封鎖對象的大小通常稱為封鎖粒度 封鎖方法的類型可以根據(jù)在哪里進行封鎖來進一步細分 封鎖法分類 集中式封鎖方法 一個站點被指定為主站點，存放對整個數(shù)據(jù)庫的封鎖表，并且負責對全系統(tǒng)事務進行封鎖 主副本封鎖法：主副本所在站點封鎖 分布式封鎖法：網(wǎng)絡中的站點共享鎖的管理1.4 并發(fā)控制機制的常用方法及其分類并發(fā)控制機制的常用方法及其分類1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論基本思想和概念 基本思想 事務訪問數(shù)據(jù)項之前要對該數(shù)據(jù)項封鎖，如果已經(jīng)被其他事務鎖定，就要等待，直到那個事務釋放該鎖為止 鎖的粒度 鎖定數(shù)據(jù)項的范圍 數(shù)據(jù)項層次 數(shù)據(jù)庫記錄中的一個字段值 一條數(shù)據(jù)庫記錄 一

20、個磁盤塊（頁面） 一個完整的文件 整個數(shù)據(jù)庫2.1 基于封鎖的并發(fā)控制方法概述基于封鎖的并發(fā)控制方法概述2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術基本思想和概念 粒度對并發(fā)控制的影響 大多數(shù)DBMS缺省設置為記錄鎖或頁面鎖 粒度小，并發(fā)度高，鎖開銷大 數(shù)據(jù)項比較多，鎖也多，解鎖和封鎖操作多，鎖表存儲空間大（如存儲讀寫時間戳） 粒度大，并發(fā)度低，鎖開銷小 如果是磁盤塊，封鎖磁盤塊中的一條記錄B的事務T必須封鎖整個磁盤塊 而另外一個事務S如果要封鎖記錄C,而C也在磁盤塊中，由于磁盤塊正在封鎖中，S只能等待 如果是封鎖粒度是一條記錄的話，就不用等待了2.1

21、基于封鎖的并發(fā)控制方法概述基于封鎖的并發(fā)控制方法概述2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術基本思想和概念 如何來確定粒度 取決于參與事務的類型 如果參與事務都訪問少量的記錄，那么選擇一個記錄作為粒度較好 如果參與事務都訪問同一文件中大量的記錄，則最好采用塊或者文件作為粒度2.1 基于封鎖的并發(fā)控制方法概述基于封鎖的并發(fā)控制方法概述2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術 鎖的類型： 共享鎖：Share鎖，S鎖或者讀鎖 排它鎖：eXclusive鎖，X鎖，拒絕鎖或?qū)戞i。 更新鎖：Update鎖，U鎖 鎖的選

22、擇： 數(shù)據(jù)項既可以讀也可以寫.則要用X鎖 如果數(shù)據(jù)項只可以讀.則要用 S鎖.2.1 基于封鎖的并發(fā)控制方法概述基于封鎖的并發(fā)控制方法概述2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術基本思想和概念 鎖的操作 Read_lock(x):讀鎖 Write_lock(x)：寫鎖 unlock(x)：解鎖 數(shù)據(jù)項的狀態(tài) read_locked: 讀鎖 Write_locked:寫鎖 具體操作方法 在系統(tǒng)鎖表中記錄關于鎖的信息 鎖表中每條記錄有四個字段： 鎖狀態(tài)是上面兩種，沒有被封鎖的數(shù)據(jù)項，在系統(tǒng)表中沒有記錄2.1 基于封鎖的并發(fā)控制方法概述基于封鎖的并發(fā)控制方法

23、概述2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術基本思想和概念 封鎖準則： 事務T在執(zhí)行任何read_item（x）操作之前，必須先執(zhí)行read_lock(x)或者write_lock(x)操作 事務T在執(zhí)行任何write_item（x）操作之前，必須先執(zhí)行write_lock(x)操作 如果事務T執(zhí)行read_lock(x)操作,數(shù)據(jù)項x必須沒有加鎖或者已經(jīng)加了讀鎖，否則事務T的這個操作不能進行 如果事務T執(zhí)行write_lock(x)操作,數(shù)據(jù)項x必須沒有加鎖，否則事務T的這個操作不能進行2.1 基于封鎖的并發(fā)控制方法概述基于封鎖的并發(fā)控制方法概述2

24、 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術封鎖準則和鎖的轉換封鎖準則：事務T在完成所有read_item（x）和write_item（x）操作之后，必須執(zhí)行unlock(x)操作如果事務T已經(jīng)持有數(shù)據(jù)項x上的一個讀鎖或者一個寫鎖，那么它不能再執(zhí)行read_lock(x)操作如果事務T已經(jīng)持有數(shù)據(jù)項x上的一個讀鎖或者一個寫鎖，那么它不能再執(zhí)行write_lock(x)操作如果事務T沒有持有數(shù)據(jù)項x上的一個讀鎖或者一個寫鎖，那么它不能執(zhí)行unlock(x)操作2.1 基于封鎖的并發(fā)控制方法概述基于封鎖的并發(fā)控制方法概述2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封

25、鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術封鎖準則和鎖的轉換鎖的轉換1.特定條件下，一個已經(jīng)在數(shù)據(jù)項x上持有鎖的事務T ，允許將某種封鎖狀態(tài)轉換為另外一種封鎖狀態(tài)2.比如，一個事務先執(zhí)行了read_lock（x）操作，然后他可以通過執(zhí)行write_lock(x)操作來升級該鎖3.同樣，一個事務先執(zhí)行了write_lock(x) 操作，然后他可以通過執(zhí)行read_lock（x） 操作來降級該鎖2.1 基于封鎖的并發(fā)控制方法概述基于封鎖的并發(fā)控制方法概述2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術封鎖準則和鎖的轉換2.1 基于封鎖的并發(fā)控制方法概述基于封鎖

26、的并發(fā)控制方法概述2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術 T1 T2read_lock(Y);read_item(Y);unlock(Y);write_lock(X);read_item(X);X:= X+Y;write_item(X);unlock(X);read_lock(X);read_item(X);unlock(X);write_lock(Y);read_item(Y);Y := Y + X;write_item(Y);unlock(Y);（a）兩個事務T1和T2初始值：X=20，Y=30串行調(diào)度T1，T2的結果： X=50，Y=80串行

27、調(diào)度T2，T1的結果： X=70，Y=50（b）T1和T2可能的串行調(diào)度的結果 T1 T2read_lock(Y);read_item(Y);unlock(Y);write_lock(X);read_item(X);X:= X+Y;write_item(X);unlock(X);read_lock(X);read_item(X);unlock(X);write_lock(Y);read_item(Y);Y := Y + X;write_item(Y);unlock(Y);這個調(diào)度S的結果：X=50，Y=50(不可串行化)（c）使用鎖的一個不可串行化調(diào)度的結果滿足封鎖規(guī)則不滿足封鎖規(guī)則不能保證產(chǎn)

28、生串行能保證產(chǎn)生串行化調(diào)度化調(diào)度簡單的分布式封鎖方法類似集中式，將同一數(shù)據(jù)的全部副本封鎖，然后更新，之后解除全部封鎖缺點是各站點間進行相當大的數(shù)據(jù)傳輸，如果有N個站點，就有：N個請求封鎖的消息N個封鎖授權的消息N個更新數(shù)據(jù)的消息N個更新執(zhí)行了的消息N個解除封鎖的消息2.1 基于封鎖的并發(fā)控制方法概述基于封鎖的并發(fā)控制方法概述2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫基本封鎖算法主站點封鎖法定義一個站點為主站點，負責系統(tǒng)全部封鎖管理所有站點都向主站點提出封鎖和解鎖請求，由它去處理缺點有：所有封鎖請求都送往單個站點，容易由于超負荷造成“瓶頸”主

29、站點故障會使系統(tǒng)癱瘓，封鎖消息都在這里，制約了系統(tǒng)可用性和可靠性2.1 基于封鎖的并發(fā)控制方法概述基于封鎖的并發(fā)控制方法概述2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫基本封鎖算法主副本封鎖法不指定主站點，指定數(shù)據(jù)項的主副本事務對某個數(shù)據(jù)項進行操作時，先對其主副本進行封鎖，再進行操作主副本封鎖，意味著所有的副本都被封鎖主副本按使用情況，盡量就近分布可減少站點的負荷,使得各站點比較均衡可減少傳輸量快照方法和上一章講的類似2.1 基于封鎖的并發(fā)控制方法概述基于封鎖的并發(fā)控制方法概述2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)

30、控制機制的封鎖技術分布式數(shù)據(jù)庫基本封鎖算法基本基本2PL協(xié)議協(xié)議如果一個事務所有的封鎖操作（讀寫）都在第一個解鎖操作之前，那么它就遵守2PL協(xié)議事務的執(zhí)行中Lock的管理分成兩個階段 上升階段(成長階段)：獲取Lock階段（只能獲取鎖） 收縮階段(衰退階段）：釋放Lock階段（只能解鎖）封鎖點是指事務獲得了它所要求的所有鎖，并且還沒有開始釋放任何鎖的時刻如果允許鎖的轉換，鎖的升級必須在成長階段進行，鎖的降級必須在鎖的衰退階段進行。 2PL可以保證事務執(zhí)行的可串行性.2.2 2PL 2PL協(xié)議（兩階段封鎖協(xié)議）協(xié)議（兩階段封鎖協(xié)議）2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并

31、發(fā)控制機制的封鎖技術開始加鎖點結束事務執(zhí)行過程獲得鎖釋放鎖兩階段封鎖協(xié)議2.2 基本基本2PL2PL協(xié)議協(xié)議2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術 基本2PL協(xié)議實現(xiàn)的難點 鎖管理器必須要知道事務的鎖點位置 級聯(lián)撤銷(cascading aborts) 如果事務在開始釋放Lock后又Abort時, 將引起級聯(lián)撤銷(cascading aborts)（其他訪問這個數(shù)據(jù)項的事務也被撤銷） 保守2PL 要求事務在開始執(zhí)行之前就持有所有它要訪問的數(shù)據(jù)項上的鎖 事務要預先聲明它的讀集和寫集 大多數(shù)2PL調(diào)度器實現(xiàn)的是嚴格2PL(S2PL) 事務在提交或者撤銷

32、之前，絕對不釋放任何一個寫鎖 事務結束時（提交或者撤銷），同時釋放所有的鎖2.2 2PL 2PL協(xié)議協(xié)議2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術 嚴酷2PL 事務T在提交或撤銷之前，不能釋放任何一個鎖（寫鎖或者讀鎖），因此它比嚴格2PL更容易實現(xiàn) 保守2PL與嚴酷2PL之間的區(qū)別 前者，事務必須在開始之前封鎖它所需要的所有數(shù)據(jù)項，因此，一旦事務開始就處在收縮階段 后者,直到事務結束（提交或者撤銷）后才開始解鎖，因此，事務一直處于擴張階段，直到結束2.2 2PL 2PL協(xié)議協(xié)議2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的

33、封鎖技術開始結束事務執(zhí)行階段獲得鎖釋放鎖 嚴格2PL(Strict Two-phase Locking)協(xié)議數(shù)據(jù)項使用2.2 2PL 2PL協(xié)議協(xié)議2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術并發(fā)控制子系統(tǒng) 可以負責產(chǎn)生讀鎖和寫鎖操作（以嚴格2PL協(xié)議為例） 當事務T發(fā)出read_item(x)操作請求時，系統(tǒng)會代表T調(diào)用read_lock(x)操作 如果Lock(x)的狀態(tài)是被另外一個事務T持有寫鎖，那么系統(tǒng)會把T放到數(shù)據(jù)項X的等待隊列中；否則，系統(tǒng)同意read_lock(x)的請求，從而允許事務T執(zhí)行read_item(x)操作 另外一個方面，如果事

34、務T發(fā)出write_item（x）操作請求時，系統(tǒng)會代表T調(diào)用write_lock(x)操作 如果Lock(x)的狀態(tài)是被另外一個事務T持有讀鎖或?qū)戞i，那么系統(tǒng)會把T放到數(shù)據(jù)項X的等待隊列中； 如果Lock(x)的狀態(tài)是讀鎖，并且事務T本身就是持有x上的讀鎖的唯一事務，那么系統(tǒng)將該鎖升級為寫鎖，并且允許T執(zhí)行write_item(x)操作 如果Lock(x)的狀態(tài)是沒有鎖，那么系統(tǒng)同意write_lock(x)的請求，進而允許事務T執(zhí)行write_item(x)操作2.2 2PL 2PL協(xié)議協(xié)議2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術集中式集中式2P

35、L的實現(xiàn)方法的實現(xiàn)方法 2PL很容易擴展到分布式DBMS(無論復制或無復制DDB), 其最簡單的方法是選擇一個站點(主站點)做Lock管理器, 其他站點上的事務管理器都需要與該選出的站點Lock管理器通信, 而不是與本站點Lock管理器通信. 這就是集中式2PL方法2.3 2PL 2PL協(xié)議的實現(xiàn)方法協(xié)議的實現(xiàn)方法2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術 術語 協(xié)調(diào)事務管理器(coordinating TM) ： 事務原發(fā)站點 數(shù)據(jù)處理器(data processor，DP) ：其他參與站點 中心站點LM：主站點鎖管理器2.3 2PL 2PL協(xié)議的實

36、現(xiàn)方法協(xié)議的實現(xiàn)方法2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術參與站點的數(shù)據(jù)處理器協(xié)調(diào) TM中心站點 LM加鎖請求允許加鎖操作操作結束釋放封鎖集中式2PL的通信結構中心站點LM不需要向DP發(fā)送操作2.3 2PL 2PL協(xié)議的實現(xiàn)方法協(xié)議的實現(xiàn)方法2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術集中式集中式2PL的實現(xiàn)方法的實現(xiàn)方法主副本主副本2PL的實現(xiàn)方法的實現(xiàn)方法 是主站點2PL的直接擴展 選擇一組站點做Lock管理器 每個Lock管理器管理一組數(shù)據(jù)(即每個數(shù)據(jù)選擇一個站點作自己的Lock管理器) 事務管理器根據(jù)

37、Lock申請的數(shù)據(jù)對象分別向這些數(shù)據(jù)的LM發(fā)出鎖申請 必須先為每一個數(shù)據(jù)項確定一個主副本站點，然后再向那個站點上的封鎖管理程序發(fā)送封鎖或釋放鎖的請求，目錄的思想 為分布式INGRES版本提出的，每個站點上要有一個復雜的目錄2.3 2PL 2PL協(xié)議的實現(xiàn)方法協(xié)議的實現(xiàn)方法2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術 特點 每個站點都有LM 無副本DDB上如同主副本2PL 有冗余副本DDB上則使用ROWA控制協(xié)議 與集中式相似，但有不同 集中式中向中心站點封鎖管理程序發(fā)送的信息，在分布式中發(fā)送給所有參與站點的封鎖管理程序 另外不同之處在于操作并不通過協(xié)調(diào)者

38、事務管理程序傳到數(shù)據(jù)處理器，而是通過參與者的封鎖管理程序 參與者的數(shù)據(jù)處理器向協(xié)調(diào)者的事務管理程序發(fā)送“操作結束”信息 另外一種方法，每個數(shù)據(jù)處理器執(zhí)行自身解鎖，并通知協(xié)調(diào)者事務管理程序的封鎖管理程序2.3 2PL 2PL協(xié)議的實現(xiàn)方法協(xié)議的實現(xiàn)方法2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式分布式2PL的實現(xiàn)方法的實現(xiàn)方法參與者 DPs加鎖請求操作分布式2PL的通信結構協(xié)調(diào)者 TM參與者 LMs操作結束釋放鎖2.3 2PL 2PL協(xié)議的實現(xiàn)方法協(xié)議的實現(xiàn)方法2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式

39、分布式2PL的實現(xiàn)方法的實現(xiàn)方法 多粒度封鎖 封鎖的粒度不是單一的一種粒度，而是有多種粒度 可以定義多粒度樹，根節(jié)點是整個數(shù)據(jù)庫，葉節(jié)點表示最小的封鎖粒度 直接封鎖 事務對要進行讀/寫的數(shù)據(jù)對象直接申請加鎖 分層封鎖 DB中各數(shù)據(jù)對象從大到小存在一種層次關系, 例如劃分為DB, 段, 關系, 元組, 字段等 當封鎖了外層數(shù)據(jù)對象時, 蘊含著也同時封鎖了它的所有內(nèi)層數(shù)據(jù)對象 數(shù)據(jù)項的顯式封鎖和隱式封鎖2.4 多粒度封鎖與意向鎖多粒度封鎖與意向鎖2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術數(shù)據(jù)庫段1段n元組元組元組元組.多級粒度樹關系nn關系11.2.4 多

40、粒度封鎖與意向鎖多粒度封鎖與意向鎖2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術2.4 多粒度封鎖與意向鎖多粒度封鎖與意向鎖2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術dbf1f2p11P12.p1nr111r11j r121r12j r1n1r1njp21P22.p2nr211r21j r221r22j r2n1r2nj用來說明多粒度級別封鎖的粒度層次結構用來說明多粒度級別封鎖的粒度層次結構 例子 假定事務T1要更新文件f1中的所有記錄，T1請求并獲得了f1上的一個寫鎖 那么f1下面的頁面和記錄就獲得了隱式寫鎖 如

41、果這時候，事務T2想從f1中的某個頁面中讀某個記錄，那么T2就要申請該記錄上的讀鎖 但是要確認這個讀鎖和已經(jīng)存在鎖的相容性，確認的方法就是要遍歷該樹：從記錄到頁，到文件最后到數(shù)據(jù)庫，如果在任意時刻，在這些項中的任意一個上存在沖突鎖，那么對記錄的封鎖請求就被拒絕，T2被阻止，要等待。2.4 多粒度封鎖與意向鎖多粒度封鎖與意向鎖2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術 意向鎖 如果對一個節(jié)點加意向鎖，則說明該節(jié)點的下層節(jié)點正在被封鎖 對任一節(jié)點封鎖時，必須先對它的上層節(jié)點加意向鎖 意向鎖的類型 意向共享鎖(IS)：指示在其后代節(jié)點上將會請求共享鎖，即如果

42、對某個對象加IS鎖，表示它的后代節(jié)點擬加共享鎖 意向排它鎖(IX)：指示在其后代節(jié)點上將會請求排他鎖，即如果對某個對象加IX鎖，表示它的后代節(jié)點擬加排他鎖 共享意向排它鎖(SIX)：指示當前節(jié)點處在共享方式的封鎖中，但是在它的某些后代節(jié)點中將會請求排他鎖。即如果對一個數(shù)據(jù)對象加SIX鎖,表示對它加共享鎖，再加IX鎖（SIX=S+IX）。例如：對某個表加SIX鎖，則表示該事務要讀整個表（加S鎖），同時會更新個別元組（加IX鎖） 2.4 多粒度封鎖與意向鎖多粒度封鎖與意向鎖2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術T2T1YYYYYY-YNNYNNSIXY

43、NYYNNIXYYYYNYISYNNNNNXYNNYNYS-SIXIXISXSXSIXSIXISY=yes，表示相容的請求 N=no，表示不相容的請求(a)數(shù)據(jù)鎖的相容矩陣(b)鎖的強度的偏序關系 鎖的相容矩陣鎖的相容矩陣2.4 多粒度封鎖與意向鎖多粒度封鎖與意向鎖2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術鎖的強度：對其鎖的強度：對其它鎖的排斥程度它鎖的排斥程度 多粒度封鎖協(xié)議的規(guī)則 必須遵守鎖的相容性規(guī)則 必須首先封鎖樹的根節(jié)點，可以用任何一種方式的鎖 只有當節(jié)點N的父節(jié)點已經(jīng)被事務T以IS或IX方式封鎖后，節(jié)點N才可以被T以S或者IS方式封鎖 只有

44、當節(jié)點N的父節(jié)點已經(jīng)被事務T以IX或SIX方式封鎖后，節(jié)點N才可以被T以X,IX或者SIX方式封鎖 只有當事務T還沒有釋放任何節(jié)點時，T才可以封鎖一個節(jié)點 只有當事務T當前沒有封鎖節(jié)點N的任何子節(jié)點時，T才可以為節(jié)點N解鎖。2.4 多粒度封鎖與意向鎖多粒度封鎖與意向鎖2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術 總結 具有意向鎖的多粒度加鎖方法中，任意事務T要對一個數(shù)據(jù)對象加鎖，必須先對它的上層節(jié)點加意向鎖 申請封鎖時應該按自上而下的次序進行 釋放鎖時則應該按自下而上的次序進行 具有意向鎖的多粒度加鎖方法提高了系統(tǒng)的并發(fā)度, 減少了加鎖和釋放鎖的開銷 它

45、已經(jīng)在實際的DBMS系統(tǒng)中廣泛應用，例如Oracle中2.4 多粒度封鎖與意向鎖多粒度封鎖與意向鎖2 2 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制的封鎖技術 死鎖發(fā)生的條件 互斥條件：事務請求對資源的獨占控制 等待條件：事務已持有分配給它的資源, 又去申請并等待別的資源 非搶占條件：直到資源被持有它的事務釋放前, 不可能將資源強制從持有它的事務奪去 循環(huán)等待條件：存在事務互相等待的等待圈 死鎖分類 局部死鎖：僅在一個站點上發(fā)生的死鎖 全局死鎖：涉及多個站點的死鎖(即等待圈由多個站點組成)3.1 全局死鎖與等待圖全局死鎖與等待圖3 3 分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理分布式

46、數(shù)據(jù)庫系統(tǒng)中的死鎖處理事務T1持有對x的鎖事務T2請求對x的鎖事務T2持有對y的鎖事務T1請求對y的鎖站點A站點BT2等待T1完成釋放對x的鎖T1等待T2完成釋放對y的鎖相互等待引起的全局死鎖3.1 全局死鎖與等待圖全局死鎖與等待圖3 3 分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理T1T2T3站點A：x1,y1站點C：z3站點B：y2,z2等待釋放對y 的鎖等待釋放對x 的鎖等待釋放對z 的鎖站點A：存儲x和y的副本， 發(fā)出事務T1：read(x),write(y)站點B：存儲y和z的副本， 發(fā)出事務T2：read(y),write(z)站點C：存儲z的副本， 發(fā)出事務T3：re

47、ad(z),write(x)多副本引起的三個站點間的死鎖3.1 全局死鎖與等待圖全局死鎖與等待圖3 3 分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理 等待圖 一種用來表示事務之間相互等待關系的有向圖, 是分析死鎖的有用工具 節(jié)點表示事務 帶有箭頭的有向邊表示“等待”關系 如果等待圖有回路，就說明有死鎖 等待圖分類 局部等待圖(LWFG) 全局等待圖(GWFG)3.1 全局死鎖與等待圖全局死鎖與等待圖3 3 分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理T1T3T2yxzT1等待T2釋放對y的共享鎖(s)T2等待T3釋放對z的共享鎖(s)T3等待T1釋放對x的共享鎖(s)上

48、例的GWFG等待圖3.1 全局死鎖與等待圖全局死鎖與等待圖3 3 分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理(a)(b)T2T1T1T2T4T3T4T3站點1站點2LWFG和GWFG之間的不同3.1 全局死鎖與等待圖全局死鎖與等待圖3 3 分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理事務間的等待關系事務間的等待關系T1T2T3T4 解決死鎖的方法 死鎖預防，使引起死鎖的必要條件不成立 所有資源排序, 按資源序列申請 將所有并發(fā)事務排序, 按標識符或開始時間 有死鎖危險時，事務退出已占有的資源，有兩種方法 等待-死亡(Wait-Die)：總是重啟較年輕的事務(非占先權)

49、 受傷-等待(Wound-Wait) ：年輕的等待年老的, 較年輕的重啟,而重啟事務并不一定是目前正申請的事務 (占先權) 死鎖檢測 即檢測死鎖時循環(huán)等待的圈3.2 死鎖的預防方法死鎖的預防方法3 3 分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理 等待-死亡模式 如果Ti對已被Tj封鎖的一數(shù)據(jù)項請求封鎖的話，則只有在Ti比Tj年老時（TiTj），則Ti被終止并帶有同一時間戳重新啟動 最好總是重新啟動較年輕的事務 允許較年老的事務去等待已持有資源的較年輕的事務 但不允許較年輕的事務去等待較年老的事務 受傷-等待模式 如果Ti對已被Tj封鎖的一數(shù)據(jù)項請求封鎖的話，則只有在Ti比Tj年輕

50、時（TiTj），才允許Ti等待 否則，Ti比Tj年老（Ti 等待EX的事務號 分布式死鎖檢測算法 使用局部信息建造LWFG, 該LWFG包含EX節(jié)點 對每次接收到的信息, 執(zhí)行如下對LWFG的修改 對報文中的每個事務, 若LWFG中不存在, 則將其加入 從EX節(jié)點開始, 按照報文所給的信息, 建立一個到下一個事務的邊 在新的LWFG中尋找不含EX的Loop, 若存在, 則檢測到死鎖 在新的LWFG中找到含有EX的Loop, 于是有潛在的死鎖, 再按規(guī)定向外傳送信息3.3 死鎖的檢測和解決方法死鎖的檢測和解決方法3 3 分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理 基本概念 不通過互

51、斥來支持串行性，而是通過在事務啟動時賦給時標（時間戳）來實現(xiàn) 時標是用來唯一識別每個事務并允許排序的標識 如果 ts(T1) ts(T2) ts(Tn), 則調(diào)度器產(chǎn)生的序是: T1,T2, . Tn 規(guī)則 如果T1的操作O1(x)和T2的操作O2(x)是沖突操作, 那么, O1在O2之前執(zhí)行, 當且僅當ts(T1)ts(T2)4.1 基于時標的并發(fā)控制方法基于時標的并發(fā)控制方法4 4 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術 時標分配方法 全局時標 使用全局的單調(diào)遞增的計數(shù)器 全局的計數(shù)器維護是個難題 局部時標 每個站點基于其本地計數(shù)器自治地指定一個時標 標識符由

52、兩部分組成：本地計數(shù)器值，站點標識符 站點標識符是次要的，主要是本地計數(shù)器值 可以使用站點系統(tǒng)時鐘來代替計數(shù)器值4.1 基于時標的并發(fā)控制方法基于時標的并發(fā)控制方法4 4 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術 時標法思想 每個事務賦一個唯一的時標，事務的執(zhí)行等效于按時標次序串行執(zhí)行 如果發(fā)生沖突，是通過撤銷并重新啟動一個事務來解決的 事務重新啟動時，則賦予新的時標 優(yōu)點是沒有死鎖，不必設置鎖 封鎖和死鎖檢測引起的通信開銷也避免了 但要求時標在全系統(tǒng)中是唯一的4.1 基于時標的并發(fā)控制方法基于時標的并發(fā)控制方法4 4 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術分布式數(shù)據(jù)庫

53、系統(tǒng)并發(fā)控制的時標技術 時標性質(zhì) 唯一性 單調(diào)性 全局唯一時間的形成與調(diào)整 每個站點設置一個計數(shù)器, 每發(fā)生一個事務, 計數(shù)器加一 發(fā)送報文時包含本地計數(shù)器值, 近似同步各站點計數(shù)器4.1 基于時標的并發(fā)控制方法基于時標的并發(fā)控制方法4 4 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術4.1 基于時標的并發(fā)控制方法基于時標的并發(fā)控制方法4 4 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術 計數(shù)器X 初值X=0 計數(shù)器Y 初值Y=10 站點1 站點2 時標 A D 時標 TS(A)= TS(D)= 因為XY E TS(E)= 改X=Y+1=11 B

54、 TS(B)= F 因為YX TS(C)= C TS(F)= 本地計數(shù)器 本地計數(shù)器 (或時鐘) (或時鐘)報文1報文2計數(shù)器計數(shù)器站點站點基本時標法基本時標法 規(guī)則 每個事務在本站點開始時賦予一個全局唯一時標 在事務結束前，不對數(shù)據(jù)庫進行物理更新 事務的每個讀操作或?qū)懖僮鞫季哂性撌聞盏臅r標 對每個數(shù)據(jù)項x, 記下寫和讀操作的最大時標，記為WTM(x)和RTM(x) 如果事務被重新啟動，則被賦予新的時標4.2 基本時標法基本時標法4 4 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術 基本時標法執(zhí)行過程 令read_TS是事務對x進行讀操作時的時標 若read_TSWTM

55、(x)，則拒絕該操作, 事務重新啟動 否則, 執(zhí)行, 令RTM(x)=maxRTM(x), read_TS 令write_TS是事務對x進行寫操作時的時標 若write_TS RTM(x) 或 write_TS WTM(x) ,則拒絕該操作, 事務重新啟動 否則, 執(zhí)行, 令WTM(x) = maxWTM(x), write_TS 缺點是重啟動多4.2 基本時標法基本時標法4 4 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術 基本思想 一種消除重啟動的方法 通過緩沖年輕的操作，直至年長的操作執(zhí)行完成，因此操作不會被拒絕，事務也絕不被重啟動 規(guī)則 每個事務只在一個站點執(zhí)行

56、, 它不能激活遠程的程序, 但是可以向遠程站點發(fā)讀/寫請求 站點i接收到來自不同站點j的讀/寫請求必須按時標順序，即每個站點必須按時標順序發(fā)送讀/寫數(shù)據(jù)請求，在傳輸中也不會改變這個順序 每個站點都為其它站點發(fā)來的讀/寫操作開辟一個緩沖區(qū), 分別保存接收到的讀/寫申請4.3 保守時標法保守時標法4 4 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術 假定某個站點k上,各個緩沖區(qū)隊列都已不為空，即每個站點都已向它至少發(fā)送了一個讀和一個寫操作，就停止接收，處理在緩沖區(qū)中的操作 假定站點i至少有一個緩沖的讀和緩沖的寫來自網(wǎng)中其它站點, 根據(jù)規(guī)則2, Site i 知道沒有年老的請

57、求來自其它Site(因為按序接收, 所以不可能有比此更年老的請求到來, 年老的比年輕的先到)4.3 保守時標法保守時標法4 4 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術例子 已知站點i的緩沖區(qū)隊列中有來自所有站點的讀/寫請求如下所示: 站點1 站點2 站點3 站點n R11 R21 R31 Rn1 R12 R22 R32 R13 R23 R24 W11 W21 W31 Wn1 W22 W32 Wn2 W234.3 保守時標法保守時標法4 4 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術執(zhí)行步驟: (1) 設RT=min(Rij), WT= m

58、in(Wij) (2) 按下法處理緩沖區(qū)中的Rij和Wij a. 若隊列中有 (Rij) WT的Rij , 則順序執(zhí)行這些Rij，執(zhí)行完刪掉 b. 若隊列中有 (Wij) RT的Wij, 則順序執(zhí)行這些Wij，執(zhí)行完刪掉 (3) 修改 RT=min(Rij), WT=min(Wij) ，此時的Rij和Wij是隊列中剩余的 (4) 重復上述(2)和(3), 直到?jīng)]有滿足條件的操作, 或者: a. 若某個或某些R隊列為空時, RT=0; b. 若某個或某些W隊列為空時, WT=04.3 保守時標法保守時標法4 4 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術存在問題和解決方

59、法 如果一個站點從來不向某個站點發(fā)送操作的話，那么執(zhí)行過程中的假定就不符合，操作就無法進行。解決辦法是，周期性的發(fā)送帶有時標的空操作 此方法要求網(wǎng)絡上所有站點都連通，這在大系統(tǒng)中很難辦到。為避免不必要的通信，可對無讀寫操作請求的站點，發(fā)送一個時標很大的空操作 此方法過分保守，一律按照時序來進行，其中包括了不沖突的操作4.3 保守時標法保守時標法4 4 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時標技術 基本思想 保存了已更新數(shù)據(jù)項的舊值 維護一個數(shù)據(jù)項的多個版本 通過讀取數(shù)據(jù)項的較老版本來維護可串行性，使得系統(tǒng)可以接受在其他技術中被拒絕的一些讀操作 寫數(shù)據(jù)項時，寫入一個新版本

60、，老版本依然保存 缺點 需要更多的存儲來維持數(shù)據(jù)庫數(shù)據(jù)項的多個版本 模式分類 基于時標排序 基于兩階段封鎖5.1 多版本概念和思想多版本概念和思想5 5 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的多版本技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的多版本技術 數(shù)據(jù)項X的多版本 X1, X2, X3, Xk 系統(tǒng)保存的值 Xi的值 兩種時標 Read_TS(Xi): 讀時標，成功讀取版本Xi的事務的時標，最大的一個 Write_TS(Xi): 寫時標，寫入版本Xi的值的事務的時標5.2 基于時標的多版本技術基于時標的多版本技術5 5 分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的多版本技術分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的多版本技術 多版本規(guī)則 如果事務