多版本并發(fā)控制(數(shù)據(jù)庫(kù))

時(shí)間：2022-12-18 08:30:01 | 來(lái)源：信息時(shí)代

時(shí)間：2022-12-18 08:30:01 來(lái)源：信息時(shí)代

    多版本并發(fā)控制 : 系統(tǒng)對(duì)于每個(gè)數(shù)據(jù)項(xiàng)維護(hù)其多個(gè)版本(值)的并發(fā)控制。當(dāng)事務(wù)訪問(wèn)請(qǐng)求某個(gè)數(shù)據(jù)項(xiàng)的時(shí)候,選擇一個(gè)合適的版本執(zhí)行,并維護(hù)執(zhí)行調(diào)度的可串行性。
版本(version)是指數(shù)據(jù)對(duì)象的一個(gè)快照,記錄了數(shù)據(jù)對(duì)象某個(gè)時(shí)刻的狀態(tài)。多版本并發(fā)控制是指在數(shù)據(jù)庫(kù)中通過(guò)維護(hù)數(shù)據(jù)對(duì)象的多個(gè)版本信息,來(lái)實(shí)現(xiàn)高效并發(fā)控制的一種策略。隨著計(jì)算機(jī)系統(tǒng)存儲(chǔ)設(shè)備價(jià)格的不斷降低,可以考慮為數(shù)據(jù)庫(kù)系統(tǒng)的數(shù)據(jù)對(duì)象保留歷史的狀態(tài)。這和現(xiàn)實(shí)世界的實(shí)際情況是符合的,并不會(huì)因?yàn)闀r(shí)間的變遷而讓歷史消失。這給我們提高系統(tǒng)的并發(fā)操作程度提供了可能。看下面這個(gè)例子: 有一個(gè)數(shù)據(jù)對(duì)象A,有兩個(gè)事務(wù)T₁和T₂,其中T₁是讀事務(wù),T₂是寫事務(wù)。假定先啟動(dòng)T₁事務(wù),后啟動(dòng)T₂事務(wù)。按照傳統(tǒng)的封鎖協(xié)議,T₂事務(wù)必須等待事務(wù)T₁執(zhí)行結(jié)束釋放A上的封鎖后才能獲得對(duì)A的封鎖。也就是說(shuō),T₁和T₂實(shí)際上是串行執(zhí)行的。但是,如果我們?cè)赥₂準(zhǔn)備寫A的時(shí)候,不是等待而是為A生成一個(gè)新的版本(表示為A′),那么T₂就可以繼續(xù)在A′上執(zhí)行。只是在T₂準(zhǔn)備提交的時(shí)候要看一下,事務(wù)T₁是否已經(jīng)完成。如果T₁已經(jīng)完成了,T₂就可以放心地提交。如果T₁還沒有完成,那么T₂必須等待直到T₁完成。這樣既能保持事務(wù)執(zhí)行的可串行性,又提高了事務(wù)執(zhí)行的并行度。
在多版本機(jī)制中,每個(gè)write(Q)操作都創(chuàng)建Q的一個(gè)新的版本,這樣一個(gè)數(shù)據(jù)項(xiàng)就有一個(gè)版本序列Q₁,Q₂,…,Q_m與之相關(guān)聯(lián)。每一個(gè)版本Q_k都像一個(gè)獨(dú)立的數(shù)據(jù)項(xiàng)一樣對(duì)待,也就是擁有版本的值、創(chuàng)建Q_k的事務(wù)的時(shí)間戳W-timestamp(Q_k)、成功讀取Q_k的事務(wù)的最大時(shí)間戳R-timestamp(Q_k)。其中,W-timestamp(Q)表示在數(shù)據(jù)項(xiàng)Q上成功執(zhí)行write(Q)操作的所有事務(wù)中的最大時(shí)間戳,R-timestamp(Q)表示在數(shù)據(jù)項(xiàng)Q上成功執(zhí)行read(Q)操作的所有事務(wù)中的最大時(shí)間戳。
用TS(T)表示事務(wù)T的時(shí)間戳,TS(T_i)〈TS(T_j):表示事務(wù)T_i在事務(wù)T_j之前開始執(zhí)行。多版本協(xié)議描述如下:
(1)假設(shè)版本Q_k具有小于或等于TS(T)的最大時(shí)間戳。
(2)若事務(wù)T發(fā)出read(Q),則返回版本Q_k的內(nèi)容。
(3)若事務(wù)T發(fā)出write(Q),則: 當(dāng)TS(T)〈Rtimestamp(Q_k)時(shí),回滾T;當(dāng)TS(T)=W-timestamp(Q_k)時(shí),覆蓋Q_k的內(nèi)容; 否則,創(chuàng)建Q的新版本。
(4) 一個(gè)數(shù)據(jù)項(xiàng)的2個(gè)版本Q_k和Q₁,其W-timestamp都小于系統(tǒng)中最老的事務(wù)的時(shí)間戳,那么這兩個(gè)版本中較舊的那個(gè)版本將不再被用到,因而可以從系統(tǒng)中刪除。
可以進(jìn)一步改進(jìn)多版本協(xié)議。區(qū)分事務(wù)的類型為只讀事務(wù)和更新事務(wù)。對(duì)于只讀事務(wù),發(fā)生沖突的可能性很小,可以采用多版本時(shí)間戳。對(duì)于更新事務(wù),采用較保守的2PL協(xié)議。這樣的混合協(xié)議稱為MV2PL。具體做法如下:
除了傳統(tǒng)的讀鎖(共享鎖)和寫鎖(排他鎖)外,引進(jìn)一個(gè)新的封鎖類型,稱為驗(yàn)證鎖(certify-lock,或C鎖)。封鎖的相容矩陣如下:

	R-Lock	W-Lock	C-Lock
R-Lock	Y	Y	N
W-Lock	Y	N	N
C-Lock	N	N	N

在這個(gè)相容矩陣中,讀鎖和寫鎖變得是相容的了。這樣,當(dāng)某個(gè)事務(wù)寫數(shù)據(jù)項(xiàng)的時(shí)候,允許其他事務(wù)讀數(shù)據(jù)(當(dāng)然,寫操作將生成一個(gè)新的版本,而讀操作就是在舊的版本上讀)。一旦寫事務(wù)要提交的時(shí)候,必須首先獲得在那些加了寫鎖的數(shù)據(jù)項(xiàng)上的驗(yàn)證鎖。由于驗(yàn)證鎖和讀鎖是不相容的,所以,為了得到驗(yàn)證鎖,寫事務(wù)不得不延遲它的提交,直到所有被它加上寫鎖的數(shù)據(jù)項(xiàng),都被所有那些正在讀他們的事務(wù)釋放。一旦寫事務(wù)獲得驗(yàn)證鎖,系統(tǒng)就可以丟棄數(shù)據(jù)項(xiàng)的舊值,代之于新版本,然后釋放驗(yàn)證鎖,提交事務(wù)。
在這里,系統(tǒng)最多只要維護(hù)數(shù)據(jù)項(xiàng)的兩個(gè)版本就可以了。多個(gè)讀操作可以和一個(gè)寫操作并發(fā)地執(zhí)行。這種情況是傳統(tǒng)的2PL所不允許的,提高了讀寫事務(wù)之間的并發(fā)度。
目前的很多商用數(shù)據(jù)庫(kù)系統(tǒng),例如Oracle數(shù)據(jù)庫(kù)、國(guó)產(chǎn)Kingbase ES數(shù)據(jù)庫(kù)都是采用MV2PL協(xié)議的。