上海交通大學(xué)高級數(shù)據(jù)庫課件ed6ch

1、16.1 n基于鎖的協(xié)議 n死鎖處理 n多粒度 n基于時間戳的協(xié)議 n基于有效性檢查的協(xié)議 n多版本方案 n快照隔離 n插入,刪除操作與謂詞讀 n實(shí)踐中的弱一致性級別 16.2 n確保隔離性的一種方法: 以互斥的方式訪問數(shù)據(jù)項(xiàng), 即當(dāng)一個事務(wù)正在訪問數(shù)據(jù) 項(xiàng)Q時, 其他事務(wù)不能修改Q. n鎖是最常用的實(shí)現(xiàn)互斥訪問的方法: 事務(wù)只能訪問它持有鎖的數(shù)據(jù)項(xiàng). n兩種鎖方式(mode): l共享(S)方式: 只能讀數(shù)據(jù)項(xiàng); l排它(X)方式: 數(shù)據(jù)項(xiàng)可讀可寫. n事務(wù)必須向并發(fā)控制管理器請求鎖. 僅當(dāng)事務(wù)被授予鎖之后才能執(zhí)行相應(yīng)讀寫 操作. l數(shù)據(jù)項(xiàng)Q上的S-鎖用 lock-S(Q)指令請求. l數(shù)據(jù)

2、項(xiàng)Q上的X-鎖用 lock-X(Q)指令請求. 16.3 n鎖相容性矩陣 n如果事務(wù)對Q的鎖請求與其他事務(wù)在Q上已有的鎖相容, 則可授予鎖 l任意數(shù)目的事務(wù)可對同一數(shù)據(jù)持有S-鎖 l若一事務(wù)對Q持有X-鎖, 則其他事務(wù)不得持有Q上的任何鎖. l不相容鎖對應(yīng)于沖突指令(ch.14) n若不能授予鎖, 則發(fā)出請求的事務(wù)只能等待, 直至其他事務(wù)持有的所有不相容 鎖被釋放. l釋放數(shù)據(jù)項(xiàng)Q上的鎖用unlock(Q)指令 16.4 T1 T2 并發(fā)控制管理器 lock-X(B) grant-X(B, T1) read(B) B:=B-50 write(B) unlock(B) lock-S(A) gra

3、nt-S(A, T2) read (A) unlock(A) lock-S(B) grant-S(B, T2) read (B) unlock(B) display(A+B) lock-X(A) grant-X(A, T1) read(A) A:=A+50 write(A) unlock(A) T2顯示不一致的總額! 16.5 T3 T4 lock-X(B) lock-S(A) read(B) read (A) B:=B-50 lock-S(B) write(B) read (B) lock-X(A) display(A+B) read(A) unlock(A) A:=A+50 unlock(

4、B) write(A) unlock(B) unlock(A) T4不會顯示不一致的總額! 16.6 n考慮調(diào)度 nT3 和T4 都不能繼續(xù) 執(zhí)行l(wèi)ock-S(B) 使T4 等待T3 釋放它持有的B上的鎖, 而執(zhí) 行 lock-X(A) 使T3 等待T4 釋放它持有的A上的鎖. n這種情形稱為死鎖死鎖. l為處理死鎖, T3 或T4 必須回滾并釋放它持有的鎖. 16.7 n如果并發(fā)控制管理器設(shè)計的不好還可能出現(xiàn)餓死餓死. 例如: l一個事務(wù)可能在等待給數(shù)據(jù)項(xiàng)加X-鎖, 同時一系列其他事務(wù)在請 求并被授予同一數(shù)據(jù)項(xiàng)上的S-鎖. l同一事務(wù)因死鎖而被重復(fù)回滾. n并發(fā)控制管理器可設(shè)計成能夠防止餓死

5、: 當(dāng)事務(wù)T請求lock-M(Q), 僅 當(dāng)滿足下列條件才授予 l沒有事務(wù)在Q上持有與M不相容的鎖; l沒有比T先提出請求且正在等待Q上鎖的事務(wù) 16.8 n要求每個事務(wù)分兩個階段來發(fā)出封鎖與釋放請求: l階段1: 增長階段 4事務(wù)可獲得鎖 4但不能釋放鎖 l階段2: 收縮階段 4事務(wù)可釋放鎖 4但不能獲得新鎖 n2PL協(xié)議確保沖突可串行化. l試證明: 各事務(wù)可按它們的lock point(即調(diào)度中各事務(wù)獲得其最后 一個鎖的地方)的次序串行化. 16.9 n兩階段鎖不能確保避免死鎖. n兩階段鎖不能避免級聯(lián)回滾. l嚴(yán)格嚴(yán)格(strict)兩階段封鎖協(xié)議兩階段封鎖協(xié)議可避免級聯(lián)回滾: 事務(wù)必

6、須保持它的所 有排他鎖直至提交/中止. 4所有未提交數(shù)據(jù)都不會被其他事務(wù)讀取 n強(qiáng)強(qiáng)(rigorous)兩階段封鎖協(xié)議兩階段封鎖協(xié)議更加嚴(yán)格: 所有鎖都必須保持 到事務(wù)提交/中止. l事務(wù)可按它們提交的次序串行化. 16.10 n存在用兩階段封鎖不能產(chǎn)生的沖突可串行化調(diào)度. n然而, 在沒有關(guān)于事務(wù)的額外信息或?qū)?shù)據(jù)施加某種結(jié)構(gòu) 或序的情況下, 兩階段封鎖對沖突可串行化按如下意義是 必要的: 給定不遵守兩階段封鎖的事務(wù)Ti, 總可以找到遵守兩階段封 鎖的事務(wù)Tj 使得存在Ti 與Tj 的非沖突可串行化調(diào)度. n在缺乏有關(guān)數(shù)據(jù)項(xiàng)被存取的方式的信息的情況下, 兩階段 封鎖協(xié)議對確保沖突可串行化是充

7、分必要的. 16.11 n允許鎖轉(zhuǎn)換的兩階段封鎖協(xié)議: 增長階段: l可獲得 lock-S l可獲得 lock-X l可將 lock-S 轉(zhuǎn)換為 lock-X (升級) 收縮階段: l可釋放 lock-S l可釋放 lock-X l可將 lock-X 轉(zhuǎn)換為 lock-S (降級) n本協(xié)議確保沖突可串行化. 16.12 16.13 n事務(wù)Ti 發(fā)出標(biāo)準(zhǔn)的讀/寫操作, 無需使用顯式的封鎖調(diào)用. n對read(D) 的處理如下: if Ti 在D上持有鎖 then read(D) else begin lock-S(D); read(D) end 16.14 n對write(D)的處理如下: i

8、f Ti 在D上有 lock-X then write(D) else if Ti 在D上有l(wèi)ock-S then upgrade(D); write(D) else lock-X(D); write(D) end; n所有鎖在事務(wù)提交/中止之后釋放 16.15 n存在事務(wù)存取數(shù)據(jù)的額外信息時, 可以構(gòu)造非兩階段封鎖協(xié)議, 仍保持 沖突可串行化. n例如基于圖的協(xié)議: 預(yù)先知道對數(shù)據(jù)的處理次序 n在所有數(shù)據(jù)項(xiàng)的集合D = d1, d2 ,., dh 上施加一個偏序. l如果di dj 則同時存取di 和dj 的事務(wù)必須先存取di 后存取dj. l集合D可視為有向無圈圖, 稱為數(shù)據(jù)庫圖. n樹協(xié)

9、議是圖協(xié)議的一種簡單形式. 16.16 n只允許排他鎖. nTi 的第一個鎖可以加在任何數(shù)據(jù)項(xiàng)上. 其后, Ti 可對數(shù)據(jù)Q 加鎖僅當(dāng)Q的 父節(jié)點(diǎn)當(dāng)前已被Ti 加鎖. n數(shù)據(jù)項(xiàng)可在任意時刻釋放鎖. n已被Ti 封鎖及釋放過的數(shù)據(jù)項(xiàng)此后不能被Ti 再次封鎖 16.17 n樹協(xié)議確保沖突可串行化且可避免死鎖. n樹協(xié)議中釋放鎖可比兩階段鎖協(xié)議中更早發(fā)生. l較短等待時間, 增加并發(fā)度 l協(xié)議無死鎖, 不需回滾 n缺點(diǎn) l協(xié)議不能保證可恢復(fù)性或無級聯(lián)回滾. 4保持排他鎖到事務(wù)提交/中止. 4并發(fā)性更好的方法: 引入提交依賴. 僅確?？苫謴?fù)性. l事務(wù)可能不得不對它不存取的數(shù)據(jù)項(xiàng)加鎖. 4增加鎖開銷以

10、及額外的等待時間 4潛在的并發(fā)度降低 4如果沒有預(yù)先的使用數(shù)據(jù)的知識, 事務(wù)只好對根加鎖 n樹協(xié)議可產(chǎn)生兩階段鎖協(xié)議不能產(chǎn)生的調(diào)度, 反之亦然. 16.18 n考慮下列兩個事務(wù): T1: write (X) T2: write(Y) write(Y) write(X) n帶來死鎖的調(diào)度 T1T2 lock-X on X write (X) lock-X on Y write (X) 等待 lock-X on X 等待lock-X on Y 16.19 n如果有一個事務(wù)集合使得集合中的每個事務(wù)都在等待集合中的另一個 事務(wù), 則系統(tǒng)死鎖. n死鎖處理的兩類方法: 死鎖預(yù)防vs死鎖檢測與恢復(fù). l死

11、鎖預(yù)防死鎖預(yù)防協(xié)議確保系統(tǒng)永遠(yuǎn)不會進(jìn)入死鎖狀態(tài). l死鎖檢測與恢復(fù)死鎖檢測與恢復(fù)協(xié)議允許死鎖發(fā)生, 但能檢測到并能從死鎖恢復(fù). n若系統(tǒng)死鎖概率很高, 適合用死鎖預(yù)防; 否則適合用死鎖檢測與恢復(fù). 16.20 n兩類預(yù)防方法: l確保不會發(fā)生循環(huán)等待的方法 4要求每個事務(wù)在開始執(zhí)行之前為其所有數(shù)據(jù)項(xiàng)加鎖. 缺點(diǎn): 難以預(yù)測要用的數(shù)據(jù); 數(shù)據(jù)使用率低. 4在所有數(shù)據(jù)項(xiàng)上施加序, 并要求事務(wù)只能按序封鎖數(shù)據(jù)項(xiàng)(如樹協(xié)議). l利用搶占與回滾的方法: 使用事務(wù)時間戳來控制搶占與否. 4等待等待-死亡死亡方案 非搶占式 老事務(wù)等待年輕事務(wù)釋放數(shù)據(jù)項(xiàng). 年輕事務(wù)永遠(yuǎn)不會等待老事務(wù), 而是回滾( 死亡).

12、 越老越可能等待;年輕事務(wù)可能在獲得所需數(shù)據(jù)項(xiàng)之前死亡多次. 4傷害傷害-等待等待方案 搶占式 老事務(wù)傷害 (強(qiáng)制回滾)年輕事務(wù)而不是等待它. 年輕事務(wù)等待老事務(wù). 年輕事務(wù)可能比等待-死亡方案有較少的回滾. 4在上面兩方案中, 回滾的事務(wù)重啟動時帶有原來的時間戳. 老事務(wù)因此 具有對新事務(wù)的優(yōu)先級, 故避免了餓死. 16.21 n基于封鎖超時 l事務(wù)對一個鎖只等待一個指定的時間量. 此后, 等待超時, 事務(wù)回滾. l因此即使發(fā)生死鎖, 也會很快解開. l特點(diǎn): 4實(shí)現(xiàn)簡單; 適合短事務(wù). 4可能有餓死. 4難以確定合適的超時間隔. 16.22 n死鎖可用等待圖描述, 即G = (V,E ),

13、 lV 是頂點(diǎn)集合 (即系統(tǒng)中的所有事務(wù)) lE 是邊的集合; 其中每個元素是一有序?qū)i Tj. n若Ti Tj 屬于E, 則存在從Ti 到Tj 的有向邊, 意味著Ti 等待Tj 釋放數(shù)據(jù) 項(xiàng). n當(dāng)Ti 請求一個正被Tj 持有的數(shù)據(jù)項(xiàng)時, 邊Ti Tj 被插入到等待圖中. n當(dāng)Tj 不再持有Ti 所需的數(shù)據(jù)項(xiàng)時, 這條邊被刪除. n系統(tǒng)處于死鎖狀態(tài)當(dāng)且僅當(dāng)?shù)却龍D包含圈. n死鎖檢測: 系統(tǒng)維護(hù)等待圖信息, 并周期性地調(diào)用死鎖檢測算法來查找 等待圖中的圈. l若死鎖頻繁, 則需更經(jīng)常調(diào)用死鎖檢測算法; 16.23 無圈的等待圖 有圈的等待圖 16.24 n當(dāng)檢測到死鎖時: 某些事務(wù)必須回滾(

14、作為犧牲品)來打破死鎖. l選擇導(dǎo)致最小代價的事務(wù)作為犧牲品. 4事務(wù)已計算多久, 還需計算多久; 4事務(wù)已使用多少數(shù)據(jù), 還需使用多少; 4回滾將涉及多少事務(wù). l回滾 決定事務(wù)回滾多遠(yuǎn) 4完全回滾: 中止事務(wù)并重啟動. 4部分回滾: 只做為打破死鎖所必需的回滾. l基于代價因子的系統(tǒng)中, 若同一事務(wù)總是被選為犧牲品則發(fā)生了餓 死. 4在代價因子中包括回滾次數(shù)以避免餓死 16.25 n同步單位: 單個數(shù)據(jù)項(xiàng) vs 一組數(shù)據(jù)項(xiàng) n允許數(shù)據(jù)項(xiàng)具有不同大小, 從而定義一個數(shù)據(jù)粒度層次, 其中細(xì)粒度嵌 在粗粒度中 n可圖示為一棵樹 (勿與樹封鎖協(xié)議混淆) n樹中每個節(jié)點(diǎn)都可獨(dú)立加鎖. n當(dāng)一事務(wù)對樹

15、中節(jié)點(diǎn)顯式地加鎖, 它也對該節(jié)點(diǎn)的所有后裔隱式地加了 同樣方式的鎖. n鎖粒度 (封鎖所在的樹層次): l細(xì)粒度 (樹中較低層): 高并發(fā)度, 高封鎖開銷 l粗粒度 (樹中較高層): 低封鎖開銷, 低并發(fā)度 16.26 從頂層開始的各個層次是: ldatabase larea lfile lrecord 16.27 n多粒度情況下, 如何發(fā)現(xiàn)不同粒度數(shù)據(jù)上的鎖沖突? n引入意向鎖方式 l意向共享意向共享(IS): 表示在樹的較低層有顯式共享鎖. l意向排他意向排他(IX): 表示在樹的較低層有顯式排他或共享鎖 l共享及意向排他共享及意向排他(SIX): 以該節(jié)點(diǎn)為根的子樹加顯式共享鎖, 并且在

16、 子樹的某較低層加顯式排他鎖. n意向鎖使得可對較高層節(jié)點(diǎn)按S或X方式加鎖而無需檢查其所有后裔節(jié) 點(diǎn). 16.28 n包括所有封鎖方式的兼容性矩陣 IS IXSS IXX IS IX S S IX X 16.29 n事務(wù)Ti 根據(jù)下列規(guī)則來封鎖一個節(jié)點(diǎn)Q: l必須遵守鎖相容性矩陣. l必須首先對樹根加鎖, 并且可以任何方式加鎖. l僅當(dāng)節(jié)點(diǎn)Q 的父節(jié)點(diǎn)當(dāng)前被Ti 以IX或IS方式封鎖時, Q 才可被Ti 以S或IS方 式加鎖. l僅當(dāng)節(jié)點(diǎn)Q 的父節(jié)點(diǎn)當(dāng)前被Ti 以IX或SIX方式封鎖時, Q 才可以被Ti 以X, SIX, 或IX方式加鎖. l僅當(dāng)Ti 先前沒有對任何節(jié)點(diǎn)開鎖時才可以對一個節(jié)點(diǎn)

17、加鎖(即, Ti 是兩階段 的). l僅當(dāng)Q 的子女當(dāng)前沒有被Ti 封鎖時, Ti 才可以對節(jié)點(diǎn)Q 開鎖. n鎖是按從根到葉次序獲得的, 但是按從葉到根次序釋放的. n此協(xié)議確保可串行化. n此協(xié)議增強(qiáng)了并發(fā)度, 減少了鎖開銷. 1.不能避免死鎖. 16.30 n預(yù)先為每個事務(wù)定序(可串行化序): 例如使用時間戳. n每個事務(wù)進(jìn)入系統(tǒng)時被賦予唯一且固定的時間戳. l若一個老事務(wù)Ti 具有時間戳TS(Ti), 則一個新事務(wù)Tj 被賦予時間戳 TS(Tj) 使得 TS(Ti) TS(Tj). n事務(wù)的時間戳決定了可串行化次序: 若TS(Ti) TS(Tj), 則系統(tǒng)必須確保 所產(chǎn)生的調(diào)度等價于串行

18、調(diào)度: Ti Tj n為實(shí)現(xiàn)這種方案, 為每個數(shù)據(jù)Q 維護(hù)兩個時間戳值: lW-timestamp(Q)是成功執(zhí)行了write(Q)的所有事務(wù)中的最大時間戳 . lR-timestamp(Q)是成功執(zhí)行了read(Q)的所有事務(wù)中的最大時間戳. 16.31 n時間戳序協(xié)議時間戳序協(xié)議確保任何沖突的read 和write操作按時間戳序執(zhí)行. n假設(shè)事務(wù)Ti 發(fā)出read(Q) l若TS(Ti) W-timestamp(Q), 則Ti 需要讀的Q的值已經(jīng)被寫覆蓋. n因此, read 操作被拒絕, Ti 回滾. l若TS(Ti) W-timestamp(Q), 則執(zhí)行read操作, 并將R-tim

19、estamp(Q) 置為 max(R-timestamp(Q), TS(Ti ). n假設(shè)事務(wù)Ti 發(fā)出write(Q) l若TS(Ti) R-timestamp(Q), 則Ti 要產(chǎn)生的Q 值是過去需要的, 而系統(tǒng)假設(shè) 該值永遠(yuǎn)不會產(chǎn)生了. n于是, write 操作被拒絕, Ti 回滾. l若TS(Ti) W-timestamp(Q), 則Ti 試圖寫一個過時的Q 值. n因此, 這個write 操作被拒絕, Ti 回滾. l否則, 執(zhí)行write操作, 且將W-timestamp(Q) 置為TS(Ti). 1.事務(wù)回滾后被賦予新的時間戳, 并重新啟動. 16.32 以下是具有時間戳1,

20、2, 3, 4, 5 的五個事務(wù)的一個部分調(diào)度 T1T2T3T4T5 read(Y) read(X) read(Y) write(Y) write(Z) read(Z) read(Z) abort read(X) write(Z) abort write(Y) write(Z) 16.33 n時間戳排序協(xié)議確保了沖突可串行化, 因?yàn)閮?yōu)先圖中的所有邊都形如: 因此, 優(yōu)先圖中沒有圈. l存在2PL協(xié)議能產(chǎn)生而時間戳序協(xié)議不能產(chǎn)生的調(diào)度, 反之亦然. n時間戳協(xié)議確保不會死鎖, 因?yàn)闆]有事務(wù)會等待. n長事務(wù)可能餓死: 一系列沖突的短事務(wù)導(dǎo)致該長事務(wù)反復(fù)回滾. n可能導(dǎo)致不可恢復(fù)調(diào)度(見下slid

21、e). 較小時間戳 事務(wù) 較大時間戳 事務(wù) 16.34 n時間戳序協(xié)議的問題: l假如Ti 中止, 但Tj 已經(jīng)讀了Ti 所寫的一個數(shù)據(jù)項(xiàng), 則Tj 必須中止; l進(jìn)一步, 任何讀了Tj 所寫的數(shù)據(jù)項(xiàng)的事務(wù)必須中止. 這導(dǎo)致級聯(lián)回滾. l若Tj 已被允許較早提交, 則該調(diào)度不可恢復(fù). n解決方法1: 確?？苫謴?fù)性與無級聯(lián)回滾性. l在事務(wù)結(jié)束時一起執(zhí)行所有寫操作. l事務(wù)的所有寫操作構(gòu)成一個原子動作: 執(zhí)行寫時, 其他事務(wù)不能訪問被寫數(shù) 據(jù). n解決方法2: 確?？苫謴?fù)性與無級聯(lián)回滾性. l使用一種受限形式的封鎖: 對未提交數(shù)據(jù)的讀操作被推遲到更新該數(shù)據(jù)的 事務(wù)提交之后. n解決方法3: 確保

22、可恢復(fù)性. l跟蹤未提交寫操作 l若Tj 讀了Ti 所寫數(shù)據(jù), 則Tj 必須等Ti 提交之后才能提交. 4利用提交依賴 16.35 n是時間戳序協(xié)議的修改版: 某些過時write操作可忽略. n針對read操作的規(guī)則與時間戳序協(xié)議相同. nThomas write規(guī)則: 當(dāng)Ti 發(fā)出write(Q), l若TS(Ti) R-timestamp(Q), 則Ti 要產(chǎn)生的Q 值是過去需要的, 而系統(tǒng)假設(shè) 該值永遠(yuǎn)不會產(chǎn)生了. 4于是, write 操作被拒絕, Ti 回滾. l若TS(Ti) W-timestamp(Q), 則Ti 正試圖寫一個過時的Q值. 4這時不是按時間戳序協(xié)議要求的那樣回滾T

23、i, 而是忽略這個write操作. l否則, 執(zhí)行write操作, 且將W-timestamp(Q) 置為TS(Ti) nThomas write規(guī)則允許更多的潛在并發(fā)性. l允許產(chǎn)生某些非沖突可串行化但觀察可串行化的調(diào)度. 16.36 n當(dāng)沖突很少發(fā)生時, 并發(fā)控制的監(jiān)控開銷就顯得過大. l例如當(dāng)大多數(shù)事務(wù)都是只讀事務(wù). n假設(shè)事務(wù)Ti 的執(zhí)行分成順序的三個階段(只讀事務(wù)只有兩個階段). l讀與執(zhí)行階段讀與執(zhí)行階段: 事務(wù)Ti 的write操作只寫到Ti 的臨時局部變量. l有效性檢查階段有效性檢查階段: 事務(wù)Ti 執(zhí)行“有效性檢查”來決定局部變量的值是否可以 寫到數(shù)據(jù)庫而不破壞可串行化.

24、l寫階段寫階段: 若Ti 通過有效性檢查, 則更新數(shù)據(jù)庫; 否則Ti 回滾. n并發(fā)執(zhí)行的各事務(wù)的三個階段可以交叉, 但是每個事務(wù)必須按順序通過三個階 段. n也稱為樂觀并發(fā)控制樂觀并發(fā)控制，因?yàn)槭聞?wù)執(zhí)行時完全寄希望于在有效性檢查時一切都正 常. 1.封鎖與時間戳序都是悲觀的: 發(fā)現(xiàn)沖突時要么等待, 要么中止. 16.37 n每個事務(wù)Ti 有三個時間戳 lStart(Ti ) : Ti 開始執(zhí)行的時間 lValidation(Ti ): Ti 進(jìn)入有效性檢查階段的時間 lFinish(Ti ) : Ti 完成寫階段的時間 n可串行化次序由有效性檢查時間戳次序決定. l即: TS(Ti )被賦予

25、Validation(Ti ) 的值. l若TS(Ti) TS(Tj), 則系統(tǒng)必須確保所產(chǎn)生的調(diào)度等價于串行調(diào)度: Ti Tj l采用Validation(Ti )而非Start(Ti )可以提高并發(fā)度, 如果沖突發(fā)生率確 實(shí)很低的話. n如果沖突的概率較小, 本協(xié)議很有用, 能帶來更大程度的并發(fā)性. l因?yàn)榭纱谢涡虿皇穷A(yù)先決定的, 且 1.相對較少的事務(wù)會被回滾. 16.38 n若對所有滿足TS(Ti ) TS(Tj )的Ti 都有下列任一條件成立: lFinish(Ti ) Start(Tj ) lStart(Tj ) Finish(Ti ) Validation(Tj ), 并且T

26、i 所寫的數(shù)據(jù)項(xiàng)集合與 Tj 所讀的數(shù)據(jù)項(xiàng)集合不相交. 則通過有效性檢查, Tj 可以提交; 否則有效性檢查失敗, Tj 中止. n正確性說明: 要么滿足第一個條件, 沒有交叉的執(zhí)行; 要么滿足第二個 條件, 使得 nTj 的寫不影響Ti 的讀, 因?yàn)樗鼈儼l(fā)生在Ti 完成讀操作之后. nTi 的寫不影響Tj 的讀, 因?yàn)門j 不讀Ti 所寫的任何數(shù)據(jù)項(xiàng). n有效性檢查協(xié)議自動防止了級聯(lián)回滾: 實(shí)際寫發(fā)生在事務(wù)提交后. n長事務(wù)可能餓死: 一系列短事務(wù)導(dǎo)致長事務(wù)反復(fù)重啟. 16.39 n利用有效性檢查產(chǎn)生的可串行化調(diào)度例: 假設(shè)TS(T14 )TS(T15 ) T14T15 read(B) re

27、ad(B) B:= B-50 read(A) A:= A+50 read(A) (validate) display (A+B) (validate) write (B) write (A) 16.40 n多版本并發(fā)控制方案保存數(shù)據(jù)項(xiàng)的老版本以增加并發(fā)性. l多版本時間戳序 l多版本兩階段鎖 n每個成功的write(Q)創(chuàng)建Q的一個新版本. l用時間戳標(biāo)記不同版本. n當(dāng)發(fā)出read(Q) 操作時, 基于事務(wù)的時間戳來選擇Q 的合適版本, 并返回 所選版本的值. 合適是指能確?？纱谢? lread 永遠(yuǎn)不必等待, 可以立即返回一個合適的版本. 16.41 n每個數(shù)據(jù)項(xiàng)Q 具有一系列版本. 每

28、個版本Qk 包含三個數(shù) 據(jù)字段: l內(nèi)容內(nèi)容 版本Qk 的值. lW-timestamp(Qk) 創(chuàng)建(寫)版本Qk 的事務(wù)的時間戳 lR-timestamp(Qk) 成功讀取版本Qk 的事務(wù)的最大時間戳 n當(dāng)事務(wù)Ti 創(chuàng)建Q 的一個新版本Qk 時, Qk的W-timestamp 與R-timestamp 初始化為TS(Ti). n每當(dāng)事務(wù)Tj 讀Qk, 并且TS(Tj) R-timestamp(Qk)時, Qk 的R-timestamp被 更新. 16.42 n假設(shè)事務(wù)Ti 發(fā)出read(Q) 或write(Q) 操作. 令Qk 表示Q 的具有小于或等于TS(Ti)的最大寫 時間戳的版本.

29、l若事務(wù)Ti 發(fā)出read(Q), 則所返回的值是版本Qk 的內(nèi)容. l若事務(wù)Ti 發(fā)出write(Q) 4若TS(Ti) R-timestamp(Qk), 則事務(wù)Ti 回滾. 4若TS(Ti) = W-timestamp(Qk), 則Qk 的內(nèi)容被覆蓋 4否則創(chuàng)建Q 的一個新版本. n可看出 l讀操作總能成功, 且無需等待; l如果有事務(wù)本該讀取Ti 所寫的值卻去讀取了比Ti 老的另一事務(wù)所創(chuàng)建的版本, 則Ti 的寫操作被拒絕. l讀操作也導(dǎo)致一次寫R-timestamp. l沖突是通過回滾而非等待來化解的. n此協(xié)議確保可串行化; 但不確?？苫謴?fù)性與無級聯(lián)回滾性. 1.刪除不再需要的版本:

30、 設(shè)W-timestamp(Qj )W-timestamp(Qk )TS(Toldest ), 則Qj 可被刪除. 16.43 n區(qū)分只讀事務(wù)和更新事務(wù) n更新事務(wù)獲得讀鎖和寫鎖,遵循強(qiáng)(rigorous)兩階段封鎖協(xié)議, 即將所有 鎖保持到事務(wù)結(jié)束. l每個成功的write創(chuàng)建所寫數(shù)據(jù)項(xiàng)的一個新版本. l數(shù)據(jù)項(xiàng)的每個版本都有單一時間戳, 其值得自于計數(shù)器ts-counter, 此計數(shù)器的值在每個事務(wù)提交處遞增. 4因?yàn)樗惺聞?wù)可按其提交順序串行化. n只讀事務(wù)開始執(zhí)行之前, 系統(tǒng)通過讀取ts-counter的當(dāng)前值賦予事務(wù)一 個時間戳; 執(zhí)行讀操作時遵循多版本時間戳序協(xié)議. 16.44 n當(dāng)

31、更新事務(wù)要讀取一個數(shù)據(jù)項(xiàng)時 l需獲得其上的共享鎖, 并讀取最近的版本. n當(dāng)更新事務(wù)要寫一個數(shù)據(jù)項(xiàng)時 l需獲得其上的X鎖, 然后創(chuàng)建該數(shù)據(jù)項(xiàng)的一個新版本并設(shè)置新版本的時間戳 為. n當(dāng)更新事務(wù)Ti 完成后, 進(jìn)行提交處理: lTi 將它創(chuàng)建的版本上的時間戳設(shè)置為ts-counter + 1 lTi 將ts-counter 加1 n在Ti 遞增ts-counter之后開始的只讀事務(wù)將看到被Ti 更新的值. n在Ti 遞增ts-counter之前開始的只讀事務(wù)將看到Ti 更新之前的值. n只產(chǎn)生可串行化調(diào)度. 確?？苫謴?fù)性與無級聯(lián)回滾性. n刪除無用版本: 同多版本時間戳序協(xié)議. 16.45 n事

32、務(wù)開始執(zhí)行時獲得一個數(shù)據(jù)庫快照,然后對該快 照進(jìn)行操作,與其他事務(wù)完全隔離. l快照中只包括已提交事務(wù)所寫的數(shù)據(jù)值. l只讀事務(wù)無需等待,也不會被中止. l更新事務(wù)的更新操作發(fā)生在事務(wù)的私有工作空間,知道 提交才寫入DB 4寫入DB之前需要處理與其他事務(wù)的沖突 4所有寫操作必須作為一個原子操作執(zhí)行,以確保其他事務(wù)的快照 要么包括該事務(wù)的所有更新,要么不包括該事務(wù)的任何更新. 16.46 n丟失更新問題:兩個事務(wù)都提交并將自己的更新寫 入DB,可能導(dǎo)致前一個事務(wù)的更新被覆蓋. n先提交者獲勝(first committer wins) l事務(wù)T進(jìn)入部分提交狀態(tài)時,以原子操作的方式執(zhí)行以下 操作

33、4檢查是否有與T并發(fā)執(zhí)行的事務(wù)T,T已經(jīng)將T想寫入的Q寫入DB 4如果有這樣的T,則T中止 4否則T提交,并將所有更新寫入DB 16.47 n先更新者獲勝(first updater wins) l事務(wù)T更新Q時需要獲得Q上的寫鎖 l如果沒有并發(fā)事務(wù)持有Q上的寫鎖,則T獲得鎖,并檢驗(yàn)更 新的有效性: 4如果Q已經(jīng)被T的并發(fā)事務(wù)T更新,則T中止; 4否則T可以更新Q l如果有并發(fā)事務(wù)T持有Q的寫鎖,則T不能執(zhí)行,并按以下 規(guī)則執(zhí)行: 4T等待T中止或提交 如果T中止,則鎖被釋放,T可獲得鎖; 如果T提交,則T中止. 16.48 n寫偏斜(write skew) T T read(A) read(A) read(B) read(B) write(B) write(A) lT和T都可以提交 l但是優(yōu)先圖中有TT和TT:T在T寫A之前讀A,T在T 寫B(tài)之前讀B 16.49 n考慮如下事務(wù) T T T read(B) read(A) read(A) write(B) read(B) read(B) write(A) l優(yōu)先圖中有TT:T在T寫B(tài)之前讀B. l假設(shè)T提交后T仍活動,這時新的只讀事務(wù)T進(jìn)入系統(tǒng). lT的快照包括T的更新,不包括T的更新. l優(yōu)先圖中有TT和TT:T在T讀B之前寫B(tài),T