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

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

2、行時(shí)，系統(tǒng)必須對(duì)并發(fā)事務(wù)之間的相互作用加以控制，這是通過(guò)并發(fā)控制機(jī)制來(lái)實(shí)現(xiàn)的。 并發(fā)控制就是負(fù)責(zé)正確協(xié)調(diào)并發(fā)事務(wù)的執(zhí)行，保證這種并發(fā)的存取操作不至于破壞數(shù)據(jù)庫(kù)的完整性和一致性，確保并發(fā)執(zhí)行的多個(gè)事務(wù)能夠正確地運(yùn)行并獲得正確的結(jié)果。 分布式數(shù)據(jù)庫(kù)中的并發(fā)控制解決多個(gè)分布式事務(wù)對(duì)數(shù)據(jù)并發(fā)執(zhí)行的正確性，保證數(shù)據(jù)庫(kù)的完整性和一致性。比集中式并發(fā)控制更復(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更新事務(wù)T2數(shù)據(jù)庫(kù)中X的值更新事務(wù)T1時(shí)間注：其中FIND表示從數(shù)據(jù)庫(kù)中讀值，UPDATE表

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

5、LBACKt5FIND x90t4UPDATE xt3FIND xt1100t0更新事務(wù)T2數(shù)據(jù)庫(kù)中A的值更新事務(wù)T1時(shí)間注： 事務(wù)T2依賴(lài)于事務(wù)T1的未完成更新1.1 并發(fā)控制的概念并發(fā)控制的概念1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論并發(fā)控制問(wèn)題之三：依賴(lài)于未提交更新（讀臟數(shù)據(jù)）并發(fā)控制問(wèn)題之三：依賴(lài)于未提交更新（讀臟數(shù)據(jù)）事務(wù)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 事務(wù)可串行

6、化理論事務(wù)可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論 操作符集 讀Ri(x)和寫(xiě)Wi(x)動(dòng)作序列 沖突動(dòng)作 R1(A) W2(A) W1(A) W2(A) R1(A) W2(A) 一個(gè)調(diào)度事務(wù)的一個(gè)操作序列稱(chēng)為一個(gè)調(diào)度，一般用S表示比如，S: R1(x),R2(y),W2(y),R2(x),W1(x),W2(x)1.2 事務(wù)可串行化理論事務(wù)可串行化理論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先序關(guān)系例子例子已知：站點(diǎn)1有數(shù)據(jù)X，站點(diǎn)2有數(shù)據(jù)Y約束：X=Y1.2 事務(wù)可串行化理論事務(wù)可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論(X站點(diǎn))(Y站點(diǎn))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 , 結(jié)果: X=Y=200 調(diào)度S1事務(wù)內(nèi)事務(wù)間令T= T1,T2,Tn 是一組事務(wù). T上的調(diào)度 S 是具有如下順序關(guān)系T的偏序，即S=T ,T :(1) T= Ti(2) T i(3) 對(duì)于任意一

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

9、2等價(jià), 也就是說(shuō), 對(duì)于沖突操作, , Oi Oj在S1中成立, 同時(shí) Oi Oj 在S2中也成立 可串行化調(diào)度 如果一個(gè)調(diào)度等價(jià)于某個(gè)串行調(diào)度，則該調(diào)度稱(chēng)為可串行化調(diào)度。 也就是說(shuō)，該調(diào)度可以通過(guò)一系列非沖突動(dòng)作的交換操作使其成為串行調(diào)度1.2 事務(wù)可串行化理論事務(wù)可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論例子兩個(gè)事務(wù)，定義如下：T1:1.Read(x）2.x=x+103.Write(x)4.Read(y)5.y=y-156.Write(y)mit1.2 事務(wù)可串行化理論事務(wù)可串行化理論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 事務(wù)可串行化理論事務(wù)可串行化理論1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論如果將事務(wù)提交延遲到兩個(gè)事務(wù)操作完成之后執(zhí)行，有：調(diào)度S1和S4是串行調(diào)度調(diào)度S2和S1的沖突操作具有相同的順序，因此是等價(jià)調(diào)度；S2是可串行化調(diào)

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

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

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

15、優(yōu)先圖中這條邊的旁邊 如果調(diào)度S中不存在環(huán)路，那么就可能存在若干個(gè)與S等價(jià)的串行調(diào)度1.3 分布式事務(wù)的可串行化調(diào)度測(cè)試分布式事務(wù)的可串行化調(diào)度測(cè)試1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論1.3 分布式事務(wù)的可串行化調(diào)度測(cè)試分布式事務(wù)的可串行化調(diào)度測(cè)試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個(gè)事務(wù)： 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個(gè)事務(wù)的一個(gè)調(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無(wú)環(huán)， S是串行調(diào)度。1.3 分布式事務(wù)的可串行化調(diào)度測(cè)試分布式事務(wù)的可串行化調(diào)度測(cè)試1 1 并發(fā)控制的概念和理論并發(fā)控制的概念和理論另外一個(gè)調(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無(wú)環(huán)，是可串調(diào)度。1.3 分布式事務(wù)的

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

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

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

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

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

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

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

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

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

26、的并發(fā)控制方法概述2 2 分布式數(shù)據(jù)庫(kù)系統(tǒng)并發(fā)控制機(jī)制的封鎖技術(shù)分布式數(shù)據(jù)庫(kù)系統(tǒng)并發(fā)控制機(jī)制的封鎖技術(shù) 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）兩個(gè)事務(wù)T1和T2初始值：X=20，Y=30串行調(diào)度T1，T2的結(jié)果： X=50，Y=80串行

27、調(diào)度T2，T1的結(jié)果： X=70，Y=50（b）T1和T2可能的串行調(diào)度的結(jié)果 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);這個(gè)調(diào)度S的結(jié)果：X=50，Y=50(不可串行化)（c）使用鎖的一個(gè)不可串行化調(diào)度的結(jié)果滿足封鎖規(guī)則不滿足封鎖規(guī)則不能保證產(chǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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