分布式數(shù)據(jù)庫

1、5.1并發(fā)控制的概念和理論 1.并發(fā)控制的概念 在通常情況下數(shù)據(jù)庫中總是有若干個(gè)事務(wù)在運(yùn)行，這些事務(wù)可能并發(fā)地存取相同的數(shù)據(jù)，稱為事務(wù)的并發(fā)操作。 當(dāng)數(shù)據(jù)庫中有多個(gè)事務(wù)并發(fā)執(zhí)行時(shí)，系統(tǒng)必須對(duì)并發(fā)事務(wù)之間的相互作用加以控制，這是通過稱為并發(fā)控制機(jī)制來實(shí)現(xiàn)的。 分布式并發(fā)控主要是解決多個(gè)分布式事務(wù)對(duì)數(shù)據(jù)并發(fā)執(zhí)行的正確性 另外，在分布式數(shù)據(jù)庫中，允許數(shù)據(jù)被復(fù)制在多個(gè)站點(diǎn)上，當(dāng)需要對(duì)數(shù)據(jù)執(zhí)行更新操作時(shí)，也必須同時(shí)正確地更新它的所有副本。 1）.丟失更新問題 對(duì)某個(gè)數(shù)據(jù)項(xiàng)處理上的先后會(huì)造成結(jié)果的不正確。 2）.不一致分析問題 3）.依賴于未提交更新的問題2.事務(wù)可串行化理論的基本概念 若干個(gè)事務(wù)并發(fā)執(zhí)行

2、的結(jié)果與按希望的順序執(zhí)行的結(jié)果相同時(shí)，稱諸事務(wù)是可串行的 1)分布式事務(wù)的一個(gè)調(diào)度 2)串行調(diào)度 3)可串行化調(diào)度3.分布式事務(wù)的可串行化理論 1)事務(wù) 2)沖突操作 3)并發(fā)事務(wù)的一個(gè)調(diào)度 4)串行調(diào)度 5)一致性調(diào)度 6)兩個(gè)調(diào)度等價(jià) 7)可串行化調(diào)度 例5.14.分布式事務(wù)的可串行化調(diào)度 1）使用優(yōu)先圖判別可串行化調(diào)度 算法5.1 2）分布式數(shù)據(jù)庫中可串行化理論的擴(kuò)展 例5.2 3）單副本可串行化 4）讀一個(gè)/寫全部副本控制協(xié)議5.并發(fā)控制機(jī)制的常用方法及其分類 1）使用協(xié)議或規(guī)則保證調(diào)度是可串行化的(如2PL) 2）并發(fā)控制機(jī)制常用的方法及其分類: 封鎖方法 時(shí)標(biāo)排序的方法 混合的方法

3、5.2分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的封鎖技術(shù) 1.基于封鎖的并發(fā)控制方法概述: 基本思想是事務(wù)訪問數(shù)據(jù)項(xiàng)前要對(duì)該數(shù)據(jù)項(xiàng)封鎖,如果已被其他事務(wù)鎖定,就要等等,直到那個(gè)事務(wù)釋放該鎖為止. 1)鎖的粒度,類型和操作 A.鎖的粒度是指鎖定數(shù)據(jù)項(xiàng)的范圍 粒度會(huì)影響并發(fā)控制和恢復(fù)的性能 首先,數(shù)據(jù)項(xiàng)尺寸越大,允許的并發(fā)程度越低 另外,數(shù)據(jù)項(xiàng)尺寸越小,數(shù)據(jù)庫中項(xiàng)的數(shù)理越多 B.鎖的類型 共享鎖S,排他鎖X C.鎖的操作 READ_LOCK讀封鎖 WRITE_LOCK寫封鎖 UNLOCK解鎖2).封鎖準(zhǔn)則和鎖的轉(zhuǎn)換 A.封鎖準(zhǔn)則事務(wù)T在執(zhí)行任何READ_ITEM操作之前,必須先執(zhí)行READ_LOCK操作或WRIT

4、E_LOCK操作事務(wù)T在執(zhí)行任何WRITE_ITEM操作之前,必須先執(zhí)行WRITE_LOCK操作如果事務(wù)在執(zhí)行READ_LOCK操作,數(shù)據(jù)項(xiàng)必須沒有加鎖或者已經(jīng)加了讀鎖,否則事務(wù)的這個(gè)操作不能執(zhí)行如果事務(wù)執(zhí)行WRITE_LOCKRK操作,數(shù)據(jù)項(xiàng)必須沒有加鎖,否則事務(wù)的這個(gè)操作不能執(zhí)行事務(wù)執(zhí)行WRITE_LOCKR操作和WRITE_ITEM操作之后,必須執(zhí)行UNLOCK操作如果事務(wù)已經(jīng)持有數(shù)據(jù)項(xiàng)上的一個(gè)讀鎖或者一個(gè)寫鎖,那么它不能再執(zhí)行READ_LOCK操作.如果事務(wù)已經(jīng)持有數(shù)據(jù)項(xiàng)上的一個(gè)讀鎖或者一個(gè)寫鎖,那么它不能再執(zhí)行WRITE_LOCK操作如果事務(wù)已經(jīng)沒有持有數(shù)據(jù)項(xiàng)上的一個(gè)讀鎖或者一個(gè)寫鎖

5、,那么它不能再執(zhí)行unLOCK操作B.鎖的轉(zhuǎn)換 在特定條件下,一個(gè)已經(jīng)在數(shù)據(jù)項(xiàng)上持有鎖的事務(wù),允許某種封鎖狀態(tài)轉(zhuǎn)換成另外一種封鎖狀態(tài). 如,一個(gè)事務(wù)先執(zhí)行了READ_LOCK操作,然后它可以通過執(zhí)行WRITE_LOCK操作來升級(jí)該鎖.3)基本封鎖算法 分布式比集中式更為復(fù)雜:數(shù)據(jù)的分布導(dǎo)致執(zhí)行的分布,封鎖消息將在整個(gè)網(wǎng)絡(luò)上傳輸,其通信代價(jià)相當(dāng)大;對(duì)多副本的數(shù)據(jù),要實(shí)現(xiàn)同步更新,原則上就要鎖定所有副本. 常用的算法有: 簡單的分布式封鎖方法:類似于集中式,數(shù)據(jù)更新時(shí),要將同一數(shù)據(jù)的全部副本封鎖,然后對(duì)其進(jìn)行更新,更新完成后解除全部上述封鎖. 主站點(diǎn)封鎖法:主站點(diǎn)封鎖法模擬集中式,選定一個(gè)站點(diǎn)定義

6、為“主站點(diǎn)”,負(fù)責(zé)系統(tǒng)全部封鎖管理,所有站點(diǎn)都有向這個(gè)主站點(diǎn)提出封鎖和解鎖請(qǐng)求,所有封鎖和解鎖信息都被傳送到那個(gè)主站點(diǎn)管理和保存,然后由主站點(diǎn)去處理封鎖事宜. 主副本封鎖法:這個(gè)方法不指定主站點(diǎn),而對(duì)每個(gè)數(shù)據(jù)項(xiàng)指定一個(gè)主副本,不同數(shù)據(jù)項(xiàng)的主副本被放在不同的站點(diǎn)上 快照方法:它是類似于視圖一種導(dǎo)出關(guān)系,但又與視圖不同.它是數(shù)據(jù)的暫時(shí)凝聚,是一種存儲(chǔ)方式.2.兩階段封鎖協(xié)議 1)兩階段封鎖協(xié)議保證調(diào)度的可串行化 第一階段是擴(kuò)張或稱成長階段.在這個(gè)階段中,事務(wù)只能獲得新的數(shù)據(jù)項(xiàng)鎖,而不能釋放任何已持有的鎖. 第二階段是收縮或稱衰退階段.在這個(gè)階段中,事務(wù)只能釋放已經(jīng)持有的鎖.遵守兩階段封鎖協(xié)議的兩個(gè)

7、事務(wù) T1 Read_lock(y); Read_item(y); Write_lock(x); Unlock(y); Read_item(x); X:=x+y Write_item(x); Unlock(x); T2 Read_lock(x); Read_item(x); Write_lock(y); Unlock(x); Read_item(y); X:=x+y Write_item(y); Unlock(y);2)基本的,保守的,嚴(yán)格的,嚴(yán)酷的兩階段封鎖協(xié)議 保守2PL和嚴(yán)格2PL:對(duì)于前者,事務(wù)必須在開始之前封鎖它所需要的所有數(shù)據(jù)項(xiàng),因此,一旦事務(wù)開始就處在收縮階段;而對(duì)于后者,直到事

8、務(wù)結(jié)束后才開始解鎖,因此事務(wù)一直處于擴(kuò)張階段,直到結(jié)束. 鎖的使用會(huì)引起:死鎖和饑餓3.兩階段封鎖協(xié)議的實(shí)現(xiàn)方法 1)集中式兩階段鎖協(xié)議的實(shí)現(xiàn)方法 2)主副本兩階段鎖協(xié)議的實(shí)現(xiàn)方法 3)分布式兩階段鎖協(xié)議的實(shí)現(xiàn)方法4.多粒度封鎖與意向鎖 1)多粒度封鎖 2)意向鎖 是如果對(duì)一個(gè)節(jié)點(diǎn)加意向鎖,則說明該節(jié)點(diǎn)的下層節(jié)點(diǎn)正在被封鎖;對(duì)任一節(jié)點(diǎn)封鎖的,必須先對(duì)它的上層節(jié)加意向鎖. 三種類型的意向鎖:意向共享鎖,意向排他鎖,共享意向排他鎖5.3分布式數(shù)據(jù)庫系統(tǒng)中的死鎖處理 1.全局死鎖與等待圖 1)活鎖,死鎖和全局死鎖 例,相互等待引起的全局死鎖 2)等待圖 例,等待圖2.死鎖的預(yù)防方法 非占先權(quán)(排隊(duì)在

9、先者可能失去優(yōu)先)法 占先權(quán)(排隊(duì)在先者絕對(duì)優(yōu)先)法3.死鎖的檢測和解決方法 1)死鎖檢測和解決的一般方法 檢測通過對(duì)全局等待圖中回路的形成進(jìn)行研究來實(shí)現(xiàn)的.如果系統(tǒng)處于死鎖狀態(tài),就必須撤銷一些引起死鎖的事務(wù). 2)分布式死鎖檢測和解決方法 集中式 層次式 分布式:A由于每一站接收從其他站點(diǎn)傳來的可能的死鎖回路,因此向自己的局部WFG增加一些邊. B在站點(diǎn)的LWFG中,被增加的用于表示本地事務(wù)正在等待其他站點(diǎn)事務(wù)的邊,同用于表示遠(yuǎn)程事務(wù)正在等待本站點(diǎn)事務(wù)的邊相連接,該節(jié)點(diǎn)稱為外部節(jié)點(diǎn).5.4分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的時(shí)標(biāo)技術(shù) 1.基于時(shí)標(biāo)的并發(fā)控制方法 1)基本概念 與基于封鎖的算法不同,基于

10、時(shí)標(biāo)的并發(fā)控制算法并不試圖通過互斥來支持串行性,而是選擇一個(gè)事先的串行次序執(zhí)行事務(wù). 時(shí)標(biāo)是用來唯一地識(shí)別每個(gè)事務(wù)并允許排序的標(biāo)識(shí)符. 2)全局唯一時(shí)標(biāo)的形成和調(diào)整 如果全局唯一時(shí)標(biāo)由本地計(jì)數(shù)器值和站點(diǎn)標(biāo)識(shí)符構(gòu)成,有兩個(gè)站點(diǎn),在每一站點(diǎn)設(shè)置一計(jì)數(shù)器,每當(dāng)發(fā)生一個(gè)事務(wù),計(jì)數(shù)器值加1,這解決了同一站點(diǎn)內(nèi)事務(wù)的次序問題.2.基本時(shí)標(biāo)法基本時(shí)標(biāo)法使用下述規(guī)則: 每個(gè)事務(wù)在本站點(diǎn)開始時(shí)賦予一個(gè)全局唯一時(shí)標(biāo); 在事務(wù)結(jié)束之前,不對(duì)數(shù)據(jù)庫進(jìn)行物理更新; 事務(wù)的每個(gè)讀操作或?qū)懖僮鞫季哂性撌聞?wù)的時(shí)標(biāo); 對(duì)于數(shù)據(jù)庫中的每個(gè)數(shù)據(jù)X,記錄對(duì)其進(jìn)行操作和寫操作的最大時(shí)標(biāo),分別記為RTM(X)和WTM(X); 如果事務(wù)被

11、重新啟動(dòng),則被賦予新的時(shí)標(biāo).基本時(shí)標(biāo)法的執(zhí)行過程: 設(shè)READ_TS是對(duì)數(shù)據(jù)X進(jìn)行讀操作的時(shí)標(biāo),如果READ_TSWTM(X),則拒絕該操作,并使發(fā)出該操作的事務(wù)用新時(shí)標(biāo)重新啟動(dòng);否則執(zhí)行該操作,且把RTM(X)置為 max(rtm(x),read_ts) 設(shè)WRITE_TS是對(duì)數(shù)據(jù)進(jìn)行寫操作,如果WRITE_TSRTM(X)或TSTS（S），那么撤銷并回滾T；否則創(chuàng)建X的一個(gè)新版本XJ，并且令READ-TS（XJ）=WRITE-TS（XJ）=TS（T）如果事務(wù)T發(fā)布一個(gè)READ-ITEM(X)操作，并且X的版本I具有所有版本中最高的WRITE-TS（XI），那么，把XI的值返回給事務(wù)T，并且將READ-TS（ XI）的值置為TS（T）和當(dāng)前READ-TS（ XI）中較大的一個(gè)2.采用驗(yàn)證鎖的多版本兩階段封鎖 在這種封鎖模式中,每個(gè)數(shù)據(jù)項(xiàng)都有三種鎖方式:讀、寫和驗(yàn)證 多版本2PL的思想是：當(dāng)只有一個(gè)單獨(dú)的事務(wù)T持有項(xiàng)X上的寫鎖時(shí)，允許其他事務(wù)T讀該項(xiàng)X。這一點(diǎn)是通過給予每個(gè)項(xiàng)X兩個(gè)版本實(shí)現(xiàn)的。5.6分布式數(shù)據(jù)庫系統(tǒng)并發(fā)控制的落樂觀方法 基本思想：對(duì)于沖突操作不像悲觀方法那樣采取掛起或拒絕的方法，而是讓一個(gè)事務(wù)執(zhí)行直到完成。 樂觀方法基于