分布式系統(tǒng)與WEB服務(wù)

《分布式系統(tǒng)與WEB服務(wù)》由會員分享，可在線閱讀，更多相關(guān)《分布式系統(tǒng)與WEB服務(wù)（65頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,2021/3/13,,,南京理工大學(xué)計(jì)算機(jī)學(xué)院,,,,,,,,分布式系統(tǒng)與,WEB,服務(wù),,,,,,,單擊此處編輯母版標(biāo)題樣式,*,,*,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,,*,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,,*,,,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,,*,分布式系統(tǒng)與WEB服務(wù),5.1 共

2、享文件的語義,兩個(gè)以上的用戶共享同一個(gè)文件時(shí)，會產(chǎn)生多種情況，從而產(chǎn)生不同的語義．故文件效勞時(shí)必須準(zhǔn)確定義效勞的讀寫語義。,一.UNIX語義(時(shí)間順序),對于單處理機(jī)而言，在UNIX系統(tǒng)中，其讀操作的語義是，讀取的結(jié)果是它前面最近一次寫操作形成的結(jié)果。寫操作的語義是，假設(shè)先后連續(xù)有兩個(gè)寫操作，那么文件結(jié)果斷定于后面的寫操作。因此，最后形成的語義是嚴(yán)格意義下的時(shí)間序操作。,在對分布式文件系統(tǒng)中的文件進(jìn)展讀操作時(shí)，能看到以前所有對該文件執(zhí)行寫操作的效果。特別是，客戶對于已翻開文件的寫操作可立即為其它翻開此文件的客戶所見?？蛻艨晒蚕砦募?dāng)前位置的指針。這樣，一個(gè)客戶將指針向前推進(jìn)時(shí)將影響所有共享客戶

3、的視圖。,此種語義的特點(diǎn)是易于理解和實(shí)現(xiàn)。,二.? 會話語義,對于翻開文件的寫操作可以立即為本地客戶所見，遠(yuǎn)程的客戶也同時(shí)翻開該文件，但卻不可見。一旦文件關(guān)閉，對此文件所作的修改僅為后面進(jìn)展的操作所見，該文件已經(jīng)翻開的各副本不表現(xiàn)這些修改.,三.? 不可改變文件語義,一但文件為共享文件，那么所有用戶均不能再修改它。這里的不可改變有兩個(gè)含義：一是其名字不可再變；二是其內(nèi)容不可改變。這樣，不可改變的文件的名字代表該文件的固定內(nèi)容，而不再是信息存儲機(jī)制。這一語義非常簡單，易于實(shí)現(xiàn)，但應(yīng)用起來，很不靈活．,四.?? 事務(wù)語義,用戶假設(shè)要訪問一個(gè)文件或了組文件，首先要執(zhí)行一個(gè)啟動事務(wù)的操作,表示下面的操

4、作必須獨(dú)立執(zhí)行，然后對文件進(jìn)展讀寫操作，當(dāng)工作完成后，再執(zhí)行一個(gè)完畢事務(wù)的操作。,其關(guān)鍵特性是,保證事務(wù)期間的所有文件操作按序執(zhí)行，而不受其它用戶的干擾，也就是說，在事務(wù)內(nèi)部嚴(yán)格具有UNIX語義、顯然，事務(wù)語義是一種比較實(shí)用的文件語義。事務(wù)的完成要求一個(gè)客戶機(jī)與一個(gè)或幾個(gè)效勞器進(jìn)展協(xié)作。,5,．,2,原子事務(wù),在分布式系統(tǒng)中，原子事物又簡稱事物，事務(wù)實(shí)際上就是一組邏輯上連續(xù)執(zhí)行的操作，其具有動態(tài)性，有三種狀態(tài)：,①提交 事務(wù)中的文件數(shù)據(jù)項(xiàng)的修改永久保存,②中止 由于同其他事務(wù)沖突或硬件故障導(dǎo)致事務(wù)中止,③臨時(shí) 事務(wù)執(zhí)行中的存在的臨時(shí)狀態(tài),5.2.1 事務(wù)的特性,事務(wù)具有以下四個(gè)特性,簡稱AC

5、ID特性,①原子性(Atomic):即事務(wù)的作用要么完整，要么沒有。,②一致性(Consistent)：事務(wù)處理不影響系統(tǒng)中的不變性：意思是，當(dāng)系統(tǒng)具有某種不變特性需要保持時(shí)，在事務(wù)執(zhí)行前后該不變性一定要保持。例如，銀行業(yè)務(wù)系統(tǒng)中有一個(gè)關(guān)鍵的不變特性是“金錢不滅〞，經(jīng)過內(nèi)部任何轉(zhuǎn)帳之后，銀行的總錢數(shù)是不變的。,③孤立性(Isolated)：并發(fā)的事務(wù)不會相互影響，多個(gè)事務(wù)處理可并發(fā)執(zhí)行，其結(jié)果和各事務(wù)處理串行執(zhí)行結(jié)果一樣，也叫串行等價(jià)性。,三個(gè)事務(wù)A、B、C被三個(gè)獨(dú)立的進(jìn)程同時(shí)執(zhí)行,假設(shè)順序執(zhí)行其結(jié)果為1、2或3,BEGIN_TRANSACTION A BEGIN_TRANSACTION

6、B BEGIN_TRANSACTION C,X=0; X=0; X=0;,X=X+1; X=X+2; X=X+3;,END_TRANSACTION END_TRANSACTION END_TRANSACTION,時(shí)間,調(diào)度,1,x=0;x=x+1;x=0;x=x+2;x=0;x=x+3;,合法,調(diào)度,2,x=0; x=0;x=x+1; x=x+2;x=0;x=x+3;,合法,調(diào)度,3,x=0; x=0;x=x+1

7、; x=0;x=x+2; x=x+3;,不合法,④持久性(Durable)：如果事務(wù)處理成功完成、那么結(jié)果將永不消失，除非發(fā)生硬故障。,5.2.2 事務(wù)需求,,銀行根本業(yè)務(wù)效勞,,服務(wù)過程,,,,解釋,,,存款,(,賬號，數(shù)額,),,,將指定,數(shù)額,的款項(xiàng)存入給定,賬號,,,取款,(,賬號，數(shù)額,),,,從給定,賬號,取出指定,數(shù)額,的款項(xiàng),,,平衡,(,賬號,),,,返回給定,賬號,的當(dāng)前平衡,,,總平衡,(),,,返回該客戶所有賬號的總平衡,,,開始事務(wù)處理,(,標(biāo)號,),,,開始指定,標(biāo)號,的事務(wù)處理,,,結(jié)束事務(wù)處理,(,標(biāo)號,),,,結(jié)束指定,標(biāo)號,的事務(wù)處理,,,流產(chǎn)事務(wù)處理,(

8、,標(biāo)號,),,,迫使指定,標(biāo)號,的事務(wù)處理流產(chǎn),,,,銀行效勞的例子,開場事務(wù)處理(T) ；,K：取款(A，100) ；,K：存款(B，100) ；,K：取款(C，200) ；,K：存款(B，200) ；,完畢事務(wù)處理(T),我們將用T、U、V代表事務(wù)處理標(biāo)號，用K、M、N代表不同的銀行分行，用A、B、C代表客戶的分行賬號，一個(gè)客戶發(fā)出的一系列效勞過程調(diào)用就可以合并為一次事務(wù)處理。,5．3 并發(fā)控制,并發(fā)控制的主要目標(biāo)是滿足事務(wù)處理的一致性(串行等價(jià)性),最早的方法:,A.某一時(shí)刻只允許執(zhí)行一個(gè)事務(wù),B 在啟動多個(gè)事物操作之前先檢查是否滿足一致性,缺點(diǎn):,解決的不好.為彌補(bǔ)缺乏.提出下面三種方

9、法.,5.3.1 加鎖,當(dāng)某一事務(wù)訪問一共享數(shù)據(jù)項(xiàng)時(shí)，由效勞器對該數(shù)據(jù)項(xiàng)加鎖，當(dāng)完成訪問時(shí)，再由效勞器開鎖，以便于其它事務(wù)訪問。在上鎖期間，只有鎖定該數(shù)據(jù)項(xiàng)的事務(wù)才能對其訪問，這樣就保證了在某一時(shí)刻訪問數(shù)據(jù)進(jìn)程的唯一性和確定性。,一.根本原理,一個(gè)鎖可由三都分組成：,①一個(gè)二值邏輯變量，用以指示上鎖／開鎖；,②一個(gè)類似于信號燈的條件變量；,③訪問該鎖的宿主事務(wù)標(biāo)識符,實(shí)現(xiàn)上鎖機(jī)制時(shí)，需要注意鎖的粒度。粒度是指被加鎖的數(shù)據(jù)項(xiàng)的大小，粒度越細(xì)，那么并行度越高，反之，并行度越低。對整個(gè)文件加鎖是一種極端情況，這時(shí)候，事務(wù)串行執(zhí)行。在下面的討論中，上鎖一般施加于文件中的數(shù)據(jù)項(xiàng)上。,鎖定機(jī)制是分兩個(gè)階段

10、進(jìn)展的。一個(gè)事務(wù)在工作過程中，可分為“生長〞和“消亡〞兩個(gè)階段。生長階段需要上鎖，消亡階段需要開鎖，這就是兩階段鎖定機(jī)制。在生長階段，事務(wù)處于臨時(shí)狀態(tài)，其臨時(shí)數(shù)據(jù)不為其它事務(wù)所見。在消亡階段，臨時(shí)數(shù)據(jù)要變成永久數(shù)據(jù)，為了保持事務(wù)的特性，必須在事務(wù)關(guān)閉的最后，才能開鎖。,二、幾種加鎖方案,1．最簡單的加鎖方法,在這種方案中，文件效勞器對客戶事務(wù)訪問的每一個(gè)數(shù)據(jù)項(xiàng)加鎖，而在事務(wù)完成(或中止)時(shí)翻開所有的鎖，當(dāng)另一事務(wù)試圖訪問已上鎖的數(shù)據(jù)項(xiàng)時(shí)，它必須等待到開鎖為止。,2. 讀／寫鎖方案,由于簡單鎖定機(jī)制不必要地將所有訪問到的數(shù)據(jù)項(xiàng)鎖定，從而降低了事務(wù)的并發(fā)性。特別是當(dāng)事務(wù)中均是讀操作時(shí)，便沒有必要上

11、鎖。,基于這種分析，提出了讀／寫鎖方案，即允許多個(gè)事務(wù)并發(fā)讀同一數(shù)據(jù)項(xiàng)，只允許一個(gè)事務(wù)寫一個(gè)數(shù)據(jù)項(xiàng)。也稱為“多讀／單寫〞 方法。在這種方法中，對于讀操作，還不能放棄上鎖，因?yàn)椴簧湘i，可能會有其它事務(wù)修改它，造成不一致。為此，要采用兩種不同的鎖，即讀鎖和寫鎖 對于訪問的所有數(shù)據(jù)項(xiàng)均可上讀鎖，只對寫操作訪問的數(shù)據(jù)項(xiàng)上寫鎖。上寫鎖的數(shù)據(jù)項(xiàng)不能被其它事務(wù)所訪問，上讀鎖的數(shù)據(jù)項(xiàng)只能為其它事務(wù)讀，但不能寫。,上鎖和開鎖的根本規(guī)那么如示:,1．當(dāng)客戶在事務(wù)中訪問數(shù)據(jù)項(xiàng)時(shí)，有如下情況：,①如果數(shù)據(jù)項(xiàng)還未上鎖，效勞器將其鎖定，并讓客戶防問該數(shù)據(jù)項(xiàng)；,②如果數(shù)據(jù)項(xiàng)已被其它事務(wù)上鎖，客戶必須等待該鎖翻開：,③如果

12、效勞器已經(jīng)鎖定了本領(lǐng)務(wù)中的一個(gè)數(shù)據(jù)項(xiàng)，客戶可以繼續(xù)防問。,④如果事務(wù)想要寫自己已上有讀鎖的數(shù)據(jù)項(xiàng)，應(yīng)當(dāng)將讀鎖改為寫鎖。,2.當(dāng)事務(wù)提交或中止時(shí)，效勞器翻開它為該事務(wù)鎖定的所有數(shù)據(jù)項(xiàng)。,3.,讀寫鎖的死鎖問題,以上兩種方法都在一定程度上提高了并發(fā)性，但與此同時(shí)也會帶來另一個(gè)問題,——,死鎖。所謂死鎖就是一組事務(wù)中的每個(gè)操作都處于上鎖且又等待開鎖的狀態(tài)，例如以下兩個(gè)事務(wù),U,和,T,，在時(shí)間順序上依次采取如下動作，結(jié)果將導(dǎo)致死鎖。,,T,等待事務(wù),U,釋放讀鎖,b,，而它本身又對其加讀鎖引起事務(wù),U,對其解鎖的等待，由此，便導(dǎo)致了互相牽制。,解決方法有如下,4,種,①在事務(wù)開場執(zhí)行前便對其所要訪問

13、的數(shù)據(jù)加鎖，這雖能預(yù)防死鎖，但卻降低了資源共享率。,②給資源規(guī)定一個(gè)序號，申請資源時(shí)必須按序號單調(diào)遞增或遞減的方向申請，這種方法也降低了并行性。,③通過資源申請占有圖來檢測有無死鎖，一旦發(fā)現(xiàn)死鎖便由效勞器中止一個(gè)事務(wù)來打破循環(huán)占有等待，解決死鎖。,④“時(shí)限〞控制，是文件系統(tǒng)中較常用的方法，即給每個(gè)鎖規(guī)定一個(gè)時(shí)間段。在此時(shí)段內(nèi)，該鎖是穩(wěn)定的，假設(shè)超出此時(shí)限后，該鎖便變成易損鎖，假設(shè)此時(shí)沒有別的事務(wù)對上鎖數(shù)據(jù)項(xiàng)競爭，那么該鎖繼續(xù)保持；否那么的話，便打破此鎖，與此同時(shí)，原上鎖事務(wù)中止。這種方法也有兩個(gè)缺乏，第一是增加了系統(tǒng)開銷；第二是“時(shí)限〞的取值問題,4．意向?qū)戞i,讀／寫鎖中讀鎖的存在阻止了其它事

14、務(wù)對其進(jìn)展寫操作，在一定程度上降低了并發(fā)性。然而事務(wù)的執(zhí)行要經(jīng)過兩個(gè)階段，在臨時(shí)階段，寫操作實(shí)際上只是將改寫的內(nèi)容寫到一個(gè)臨時(shí)緩沖區(qū)中，并未改寫實(shí)際的數(shù)據(jù)項(xiàng)。只有在提交階段才寫回?cái)?shù)據(jù)項(xiàng)，基于此原理可把讀／寫鎖改成意向?qū)戞i和提交鎖來提高并發(fā)性.,5.3.2 樂觀的并發(fā)控制方法,一.問題的提出,使用鎖機(jī)制處理并發(fā)控制時(shí)存在一些缺陷：,①分布式系統(tǒng)中的鎖機(jī)制是一種額外的開銷。例如，在只有讀操作的事務(wù)中，鎖可以保證所讀的數(shù)據(jù)項(xiàng)不被別的事務(wù)修改，但這種鎖只有在最壞的情況下才有必要。又例如，兩個(gè)客戶進(jìn)程并發(fā)地對n個(gè)數(shù)據(jù)項(xiàng)進(jìn)展增值運(yùn)算，假設(shè)它們同時(shí)啟動，執(zhí)行時(shí)間量也一樣，以互不相關(guān)的序列訪問數(shù)據(jù)項(xiàng)，并且各

15、自使用一個(gè)事務(wù)來訪問和增值數(shù)據(jù)項(xiàng)，那么這兩個(gè)程序試圖同時(shí)訪問同一數(shù)據(jù)項(xiàng)的時(shí)機(jī)僅有1／n，也即每n個(gè)事務(wù)中實(shí)際有用的鎖只有一次。,②使用鎖機(jī)制會導(dǎo)致死鎖，并且沒有令人滿意的死鎖解決算法。在鎖機(jī)制中，只有在一個(gè)事務(wù)終止時(shí)才釋放它的所有鎖，這明顯有損于并發(fā)性。正是基于以上原因，有人提出另一種算法——樂觀的并發(fā)控制方法。之所以稱其為“樂觀〞，是基于這樣一種假設(shè)，兩個(gè)客戶的事務(wù)同時(shí)訪問某一數(shù)據(jù)的可能性很小, 因此兩個(gè)事務(wù)可以執(zhí)行下去，直至發(fā)出C1oseTransaction請求。當(dāng)產(chǎn)生沖突時(shí)，一般要中止一些事務(wù)，并由客戶重新啟動。這樣，每個(gè)事務(wù)便分為以下三個(gè)階段：,1.讀階段：在這一階段中，每個(gè)事務(wù)有一

16、個(gè)待更新數(shù)據(jù)的臨時(shí)版本。讀請求可以立即執(zhí)行，如果有臨時(shí)版本存在，那么要訪問最近提交的數(shù)據(jù)值。而寫請求以一種其它事務(wù)不可見的形式緩存起來，假設(shè)有幾個(gè)并發(fā)事務(wù)，可能會同時(shí)存在同一數(shù)據(jù)項(xiàng)的幾個(gè)不同的臨時(shí)值。另外，針對于每一個(gè)事務(wù)需要設(shè)置兩個(gè)集合：讀集合和寫集合，讀集合列出事務(wù)所讀的數(shù)據(jù)項(xiàng)的集合，而寫集合那么列出事務(wù)創(chuàng)立、修改、刪除的數(shù)據(jù)項(xiàng)集合。,2.確認(rèn)階段：當(dāng)效勞器收到CloseTransaction請求之后，進(jìn)入這個(gè)階段，在該階段中，對該事務(wù)進(jìn)展確認(rèn)是否可以將該事務(wù)的寫操作結(jié)果永久保存下來。,如果事務(wù)確認(rèn)成功，那么進(jìn)入寫階段(寫操作結(jié)果記錄到相關(guān)文件中，事務(wù)成功完成，發(fā)出commit);否那么，

17、要解決沖突，需要中止某些事務(wù)。確認(rèn)階段是建立在一致性根底上的，即如果事務(wù)執(zhí)行的結(jié)果等價(jià)于各個(gè)事務(wù)順序執(zhí)行的結(jié)果，那么該事務(wù)視為確認(rèn)成功。,3.寫階段：如果一個(gè)事務(wù)確認(rèn)成功，那么臨時(shí)版本記錄的所有修改均可以變?yōu)橛谰眯孕薷摹Ｖ蛔x事務(wù)可以在確認(rèn)通過后立即提交。寫事務(wù)在臨時(shí)版本中的數(shù)據(jù)變?yōu)橛谰脭?shù)據(jù)之后立即提交。,二、事務(wù)確實(shí)認(rèn),確認(rèn)是利用讀寫沖突規(guī)那么來保證一組重疊事務(wù)(即當(dāng)前事務(wù)還未提交便已開場的事務(wù))的調(diào)度符合一致性, 當(dāng)一個(gè)事務(wù)完成第一階段工作后,為其指定一個(gè)事務(wù)號，假設(shè)該事務(wù)確認(rèn)成功完成,那么事務(wù)號被保存下來：否那么，假設(shè)事務(wù)未被確認(rèn)，或事務(wù)是只讀事務(wù)，那么釋放該事務(wù)號．,確認(rèn)工作主要基于兩個(gè)

18、事務(wù)操作的沖突來完成的 對于兩個(gè)重疊事務(wù)Ti和TJ，必須滿足以下規(guī)那么。,確認(rèn)方法有兩種，一種叫做向后確認(rèn)(Backward Validation)，以正在執(zhí)行確認(rèn)的事務(wù)為基準(zhǔn)，檢查已經(jīng)進(jìn)入確認(rèn)階段的事務(wù)。一種叫做向前確認(rèn)(Forward Validation)，以正在執(zhí)行確認(rèn)的事務(wù)為基準(zhǔn)，檢查后續(xù)進(jìn)人確認(rèn)階段的事務(wù).,三. 餓死現(xiàn)象,事務(wù)中止后, 通常由客戶程序重新啟動, 但有可能該事務(wù)仍然無法通過確認(rèn), 于是其又被中止, 重啟, 再中止. 如此, 該事務(wù)那么被剝奪了提交能力 此現(xiàn)象即為餓死,時(shí)間戳,要利用時(shí)間戳完成并發(fā)控制，需要對每個(gè)事務(wù)的操作進(jìn)展有效性檢查，假設(shè)檢查未能通過,那么該

19、事務(wù)立即中止并重新啟動,根本的時(shí)間規(guī)那么:,①事務(wù)對數(shù)據(jù)項(xiàng)的寫請求，僅當(dāng)該數(shù)據(jù)項(xiàng)最近由前一個(gè)事務(wù)(有沖突)讀和寫，才能有效。,②事務(wù)對數(shù)據(jù)項(xiàng)的讀請求，僅當(dāng)該數(shù)據(jù)項(xiàng)剛剛由前一個(gè)事務(wù)(有沖突)寫，才能有效。,該規(guī)那么允許并發(fā)事務(wù)共享臨時(shí)數(shù)據(jù)項(xiàng)，從而確保每個(gè)數(shù)據(jù)項(xiàng)的臨時(shí)值按時(shí)間戳順序提交.,5．4 恢復(fù),事務(wù)的原子性要求事務(wù)要么提供完整的運(yùn)行結(jié)果，要么么作用都沒有，即持久性和失效原子性。這兩個(gè)需要并不是獨(dú)立的，可以由效勞器上的獨(dú)立機(jī)制來管理，我們稱這個(gè)機(jī)制叫做恢復(fù)管理器。,恢復(fù)管理器的主要任務(wù)是；,①將提交事務(wù)的數(shù)據(jù)保存到永久性存儲介質(zhì)(恢復(fù)文件)上；,②故障重啟后，恢復(fù)效勞器的數(shù)據(jù)；,③組織恢復(fù)

20、文件，改進(jìn)恢復(fù)性能；,④回收恢復(fù)文件涉及到的空間。,5．5 事務(wù)效勞中的文件版本,文件版本的實(shí)現(xiàn),通過在每個(gè)文件的索引表中擴(kuò)大一項(xiàng),即版本號,通過對影子頁的操作,到事務(wù)提交時(shí),假設(shè)無版本沖突,那么合并臨時(shí)版本與當(dāng)前版本得到最新版本.假設(shè)有沖突那么放棄臨時(shí)版本.,意向表的實(shí)現(xiàn),也可通過對影子頁的操作實(shí)現(xiàn)意向表,,意向表記錄:操作類型、事務(wù)標(biāo)識符、文件標(biāo)識符、頁號、影子頁面的指針,,文件版本方法,解決兩類問題,:,版本沖突和串行沖突,,版本沖突,:,并發(fā)事務(wù)訪問同一個(gè)文件的不同數(shù)據(jù)段,,,從而產(chǎn),生不同的版本,,,但無一版本包含所有的修改,.,,串行沖突,:,并發(fā)事務(wù)訪問同一數(shù)據(jù)段,,,從而有多

21、個(gè)寫操作,,,導(dǎo)致數(shù)據(jù)項(xiàng)決定于最后的版本,.,,版本沖突解決如圖,:,老版本,老版本,當(dāng)前版本,合并最新版本,事務(wù),T,的臨時(shí)版本,事務(wù),U,的臨時(shí)版本,,版本的合并,老版本,老版本,上一個(gè)版本,當(dāng)前版本,事務(wù),T,的臨時(shí)版本,事務(wù),U,的臨時(shí)版本,,串行沖突的解決,意向表方法,意向表實(shí)際上是一個(gè)事務(wù)操作的日志記錄,是兩階段提交的機(jī)制.即:第一階段,事務(wù)處于臨時(shí)狀態(tài),第二階段,事務(wù)進(jìn)入提交階段.如圖,,,,DATA為效勞器為待修改的數(shù)據(jù)的臨時(shí)拷貝.意向操作只是記錄到意向表并不是真的對文件操作,一個(gè)意向只有給出足夠的信息,才能到第二階段執(zhí)行.,,,,本領(lǐng)務(wù)的視圖,DATA1,DATA2,其它事務(wù)

22、的視圖,第六章,,分布事務(wù)與文件備份,6．1 合作效勞器,合作效勞器是由多個(gè)物理效勞器合作完成一個(gè)邏輯效勞器的功能,各個(gè)效勞器由網(wǎng)絡(luò)互連,每個(gè)效勞器可具備不同性能,可位于不同地點(diǎn), 并持有整個(gè)合作效勞器中所有文件的一局部,6．2 分布事務(wù),分布事務(wù)是指一個(gè)事務(wù)將涉及到多個(gè)效勞器的操作, 即該事務(wù)是由合作效勞器完成的, 構(gòu)造分布事務(wù)的方法有簡單分布事務(wù)和嵌套分布事務(wù)兩種,簡單分布事務(wù):客戶機(jī)可以屢次訪問不同的效勞器,效勞器僅響應(yīng)客戶機(jī)的請求,不引發(fā)其它效勞器的操作,嵌套分布事務(wù):一個(gè)效勞器上的操作可能引發(fā)其它效勞器操作,客戶機(jī),服務(wù)器,1,服務(wù)器,2,服務(wù)器,3,在分布事務(wù)中,多個(gè)效勞器需要相

23、互通信和合作,各自完成局部工作,最終是事務(wù)提交完成.在分布事務(wù)處理中,第一個(gè)響應(yīng)客戶機(jī)請求的效勞器為該事務(wù)的協(xié)調(diào)效勞器,負(fù)責(zé)中止、提交該事務(wù)，其后參加的效勞器為工作效勞器。,T,S,1,T,22,T,21,T,12,T,11,T,2,T,1,T,S,3,S,2,S,2,S,6,S,5,S,4,S,1,S,3,(a),分布式平面事務(wù)處理,,(b),分布式嵌套事務(wù)處理,,S,7,S,0,事務(wù)處理分類,,其中方框代表事務(wù)處理，圓形代表執(zhí)行操作的服務(wù)器,,分布式事務(wù)處理,分布式事務(wù)處理的關(guān)鍵在于效勞及數(shù)據(jù)的分布，即一個(gè)事務(wù)處理所需的效勞與數(shù)據(jù)可能分散在不同的效勞器上，因此，事務(wù)處理過程就必須在多臺效勞

24、器上執(zhí)行。,分布式事務(wù)處理的調(diào)度與同步,多臺效勞器聯(lián)合執(zhí)行一個(gè)事務(wù)處理時(shí)需要彼此協(xié)調(diào)，才能做到整個(gè)事務(wù)處理的成功提交,常用的方法是由一個(gè)協(xié)調(diào)者(coordinator)通過效勞器之間的通信來實(shí)現(xiàn)最終提交,分布式事務(wù)處理例子,開場事務(wù)處理(T) ；,K：取款(A，100) ；,M：存款(B，100) ；,N：取款(D，200) ；,M：存款(C，200) ；,完畢事務(wù)處理(T),某客戶要在K、M、N三個(gè)銀行分行的A、B、C、D四個(gè)賬號上執(zhí)行轉(zhuǎn)帳業(yè)務(wù)，即從K分行的A賬號取出100元，存入M分行的B賬號去，然后從N分行的D賬號取出200元并存入到M分行的C賬號。假定這三個(gè)分行的數(shù)據(jù)庫分別位于三臺效勞

25、器上，其中S1管理K分行的A賬號 ，S2管理M分行的B、C兩個(gè)賬號，S3管理N分行的D賬號,分布式銀行事務(wù)處理,,T,S,1,S,3,S,2,(1.1) 開場事務(wù)處理(T) ；,(1.2) K：取款(A，100) ；,(1.3) 完畢事務(wù)處理(T) ；,(2.1) 參加效勞器(T，S1) ；,(2.2) M：存款(B，100) ；,(2.3) M：存款(C，200) ；,(3.1) 參加效勞器(T，S1) ；,(3.2) N：取款(D，200) ；,K,分行,M,分行,N,分行,協(xié)調(diào)者,參與者,參與者,由于每個(gè)效勞器可能同時(shí)執(zhí)行不同的分布式事務(wù)處理，因此在整個(gè)系統(tǒng)中事務(wù)處理標(biāo)號必須是唯一的。首

26、先啟動分布式事務(wù)處理的那臺效勞器是整個(gè)事務(wù)處理的協(xié)調(diào)者效勞器,6．3 分布事務(wù)的提交協(xié)議,最簡單的方法:,1．一階段原子提交協(xié)議:,即由協(xié)調(diào)效勞器不斷查詢所有工作效勞器,直到所有工作效勞器都答復(fù)提交成功,完成整個(gè)事務(wù)提交,2．兩階段提交協(xié)議(2PC協(xié)議)，可以保證分布事務(wù)的原子性，在此協(xié)議中，任何效勞器都可以隨時(shí)中止自己的子事務(wù)而不影響客戶機(jī)事務(wù)的正常提交或中止。,協(xié)調(diào)效勞器分為兩階段工作(2PC)：,第一階段 投票階段,A協(xié)調(diào)效勞器向每個(gè)工作效勞期發(fā)出提交請求,B工作效勞器收到請求后,答復(fù)YES或NO,如答復(fù)有NO,那么終止,第二階段 完成階段,C協(xié)調(diào)效勞器查看搜集的票數(shù),假設(shè)無反對票,

27、協(xié)調(diào)效勞器那么提交該事務(wù)并通知所有工作效勞器,否那么,假設(shè)有反對票協(xié)調(diào)效勞器那么終止事務(wù),并向所有答復(fù)YES的工作效勞器發(fā)出終止請求,3 嵌套事務(wù)的兩階段提交協(xié)議,嵌套事務(wù)的兩階段提交協(xié)議的執(zhí)行過程的第一階段與非 嵌套事務(wù)不同，當(dāng)工作效勞器接到提交：,1)如果工作效勞器具有暫時(shí)提交且是頂層事務(wù)的子事務(wù),A.檢查它有沒有前輩事務(wù)處于中止事務(wù)表中，準(zhǔn)備提交,B 中止具有中止前輩事務(wù)的事務(wù),C 向協(xié)調(diào)效勞器投票YES,2)如果工作效勞器沒有處于暫時(shí)提交狀態(tài)的、且是頂層事務(wù)的子事務(wù)，它肯定已經(jīng)失敗，應(yīng)向協(xié)調(diào)效勞器投票NO,注意:,A.子事務(wù)的標(biāo)識符可以通過擴(kuò)大其父事務(wù)的標(biāo)識符;,B.子事務(wù)的提交決

28、定于其父事務(wù)的提交,但父事務(wù)的提,交并不決定于其子事務(wù)的提交,6,．,4,分布事務(wù)中的并發(fā)控制,,當(dāng)多個(gè)事務(wù)處理訪問同一個(gè)數(shù)據(jù)時(shí)，順序等價(jià)性要求必須把每一個(gè)事務(wù)處理對該數(shù)據(jù)的完整(讀/寫)訪問一一排序，嚴(yán)格制止任何沖突,,,開始事務(wù)處理,(T),：,,K,：取款,(A,，,40),；,,K,：存入,(B,，,40),；,結(jié)束事務(wù)處理,(T),；,,,,開始事務(wù)處理,(U),：,,K,：取款,(C,，,30),K,：存款,(B,，,30),結(jié)束事務(wù)處理,(U),；,,,分解操作,,,,平衡,,,,分解操作,,,,平衡,,,A,．平衡,?,,A,．讀出,(),,,(A) 100,元,,,,,,,,

29、,A,．寫入,(A,．平衡,– 40),,,(A) 60,元,,,,,,,,,,,,,,,C,．平衡,?,,C,．讀出,(),,,(C) 300,元,,,,,,,,,C,．寫入,(C,．平衡,– 30),,,(C) 270,元,,,B,．平衡,?,,B,．讀出,(),,,(B) 200,元,,,,,,,,,B,．寫入,(B,．平衡,+ 40),,,(B) 240,元,,,,,,,,,,,,,,,B,．平衡,?,,B,．讀出,(),,,(B) 240,元,,,,,,,,,B,．寫入,(B,．平衡,+ 30),,,(B) 270,元,,,,1. 分布事務(wù)中的鎖,每個(gè)效勞器都要提供鎖管理機(jī)制，本地的

30、鎖管理機(jī)制可以決定是否承受事務(wù)的請求操作。,,利用互斥鎖進(jìn)展事務(wù)處理并發(fā)控制,,,開始事務(wù)處理,(T),：,,K,：取款,(A,，,40),；,,K,：存款,(B,，,40),；,結(jié)束事務(wù)處理,(T),；,,,,,,,分解操作,,,,互斥鎖,,,,分解操作,,,,互斥鎖,,,開始事務(wù)處理,(T),,,,,,開始事務(wù)處理,(U),,,,,,A,．平衡,?,,A,．讀出,(),,,鎖定,A,,,C,．平衡,?,,C,．讀出,(),,,鎖定,C,,,A,．寫入,(A,．平衡,–,40),,,,,,C,．寫入,(C,．平衡,–,30),,,,,,B,．平衡,?,,B,．讀出,(),,,鎖定,B,,,,

31、,,,,,,,,,,,B,．平衡,?,,B,．讀出,(),,,等待,B,的鎖,,,B,．寫入,(B,．平衡,+ 40),,,,,,．,,,,,,結(jié)束事務(wù)處理,(T),,,釋放,A,，,B,,,．,,,,,,,,,,,,．,,,鎖定,B,,,,,,,,,B,．寫入,(B,．平衡,+ 30),,,,,,,,,,,,結(jié)束事務(wù)處理,(U),,,釋放,B,，,C,,,,開場事務(wù)處理(U) ：,K：取款(C， 30),K：存款(B， 30),完畢事務(wù)處理(U) ；,分布式死鎖,在各種涉及互斥的算法中，只要算法采用互斥鎖，就有可能發(fā)生“死鎖〞 現(xiàn)象。,死鎖的典型特征是一組事務(wù)處理形成了一條循環(huán)等待鏈,死鎖處

32、理：,置之不理 〔鴕鳥算法〕– 由程序員對其負(fù)責(zé),預(yù)防〔靜態(tài)的使死鎖在構(gòu)造上不可能〕 – 不存在運(yùn)行系統(tǒng)支持,防止 〔合理的分配資源〕– 運(yùn)行系統(tǒng)支持,檢測恢復(fù)〔允許死鎖發(fā)生，檢測到后恢復(fù)〕– 不同的算法,T,U,V,W,W,U,T,V,(a),簡單循環(huán)鏈,(b),復(fù)雜循環(huán)鏈,互斥,持有并等待,,(a) T,?U?V?W?T,不容搶占,,(b) V,?W?T?V,循環(huán)鏈,,V,?W?V,死鎖,-,循環(huán)等待鏈,,分布式事務(wù)處理的死鎖例子,,事務(wù)處理,U,,,事務(wù)處理,V,,,事務(wù)處理,W,,存款,(D,，,100),,鎖定,D @ S,3,,,,,,,,,,,,,,,,,,,,存款,(B,，,3

33、00),,,鎖定,B @ S,2,,,,,,,,,存款,(A,，,200),,鎖定,A @ S,1,,,,,,,,,,,,,,,,,,,,,,,,,,,存款,(C,，,500),,,鎖定,C @ S,3,,,取款,(B,，,200),,,等待,B @ S,2,,,,,,,,,,,,,,,,,,,,,取款,(C,，,100),,,等待,C @ S,3,,,,,,,,,,,,,,,,,,,,,取款,(A,，,300),,,等待,A @ S,1,,,死鎖,,,死鎖檢測,死鎖是一種穩(wěn)定的狀態(tài),盡管無法從局部狀態(tài)檢測分布式事務(wù)處理的死鎖，但死鎖依舊是環(huán)形等待鏈。,死鎖檢測算法：,中央式,,–,周期性地收

34、集等待狀態(tài),分布式,,–,推出等待狀態(tài),提示式,–,構(gòu)造檢測體系,2. 分布事務(wù)中的時(shí)間戳,利用時(shí)間戳進(jìn)展讀寫協(xié)作,3. 分布事務(wù)中的樂觀并發(fā)控制,分布事務(wù)通過一組獨(dú)立的效勞器進(jìn)展確定，每個(gè)效勞器都要確認(rèn)事務(wù)訪問的是自己的數(shù)據(jù)項(xiàng)，所有確認(rèn)均通過兩階段進(jìn)展。,,,[讀階段] 在讀階段，該事務(wù)處理所訪問的數(shù)據(jù)都有一套暫時(shí)版本，這套版本不對外，只由擁有者使用。采用暫時(shí)版本可以使事務(wù)處理流產(chǎn)而不會影響到長存數(shù)據(jù)。當(dāng)執(zhí)行一個(gè)讀操作時(shí)，如果數(shù)據(jù)的暫時(shí)版本已經(jīng)存在，那么讀操作立即訪問之，否那么，就必須訪問那個(gè)數(shù)據(jù)最近提交的值。寫操作把每一數(shù)據(jù)的新值作為暫時(shí)值記錄在案。顯然，如果假設(shè)干個(gè)并發(fā)事務(wù)處理共享同一個(gè)

35、數(shù)據(jù)，那么這個(gè)數(shù)據(jù)可能有不同的暫時(shí)值。除了上述規(guī)那么外，對每一個(gè)訪問的數(shù)據(jù)，事務(wù)處理還要維護(hù)兩個(gè)數(shù)值集合：讀集合包括該事務(wù)處理讀出的數(shù)據(jù)，寫集合囊括該事務(wù)處理寫入的數(shù)據(jù)。,[驗(yàn)證階段] 當(dāng)事務(wù)處理試圖提交時(shí)，就進(jìn)入驗(yàn)證階段，其目的是檢測是否它所訪問的數(shù)據(jù)與其它事務(wù)處理的操作有沖突。如果驗(yàn)證無沖突，該事務(wù)處理可以提交；否那么我們就必須消解沖突。消除沖突的方法很簡單：或者命令該事務(wù)處理流產(chǎn)，或者從卷入沖突的事務(wù)處理中選擇一個(gè)令其流產(chǎn)。,[寫階段] 如果該事務(wù)處理已經(jīng)通過驗(yàn)證，暫時(shí)版本中所記錄的數(shù)據(jù)更新就成為永久性的。如果該事務(wù)處理是只讀型事務(wù)處理，那么它馬上提交；否那么就要等到暫存數(shù)據(jù)全部寫入長存

36、存儲器后，執(zhí)行提交操作。,樂觀并發(fā)控制算法,,6．5 分布事務(wù)中的恢復(fù),分布事務(wù)的恢復(fù)工作,效勞器 狀態(tài) 恢復(fù)管理器的工作,協(xié)調(diào)效勞器 準(zhǔn)備提交 表示效勞器故障時(shí)還未做出仟何決定．將向所有工作,效勞器發(fā)出AbortTransaction，將中止?fàn)顟B(tài)參加到恢,復(fù)文件中．假設(shè)狀態(tài)是中止，工作一樣。,如果沒有工作效勞器，將以超時(shí)判斷，中止相應(yīng)事務(wù),協(xié)調(diào)效勞器 提交 表示效勞器故障時(shí)已做出提交決定．假設(shè)是還沒有做完．,要發(fā)送DoCommit，給各工作效勞器，從這一步開場恢,復(fù)兩階段提交協(xié)議的執(zhí)行。,工作效勞器 提交 表示已經(jīng)提交．如果還未向上

37、作效勞器發(fā)送HaveCommited,消息，那么發(fā)送之；然后，執(zhí)行整個(gè)事務(wù)中屬于自身的那一,局部操作(假設(shè)文件操作是可重復(fù)的，這樣做就不會引起不,一致性)。,工作效勞器 不確定 表示工作效勞器在知道事務(wù)輸出之前故障，必須等到協(xié)調(diào),效勞器作山?jīng)Q定，可以有GetDecison獲取。收到應(yīng)答后，,根據(jù)情況提交或中止。,工作效勞器 準(zhǔn)備提交 表示工作效勞器還沒有投票，可以中止事務(wù)．,協(xié)調(diào)效勞器 完成 不需要任何工作,6．6 備份,備份是與分布事務(wù)及合作效勞器密切相關(guān)的問題。一個(gè)備份對象(如文件或數(shù)據(jù)項(xiàng))由位于多個(gè)效勞器中的許多副本組成，我們稱組成一個(gè)備份對象的副本集合中的任意副本為

38、該備份對象的一個(gè)代理。備份對象有如下特點(diǎn)：,(1)減少分布式系統(tǒng)中的通信量，并通過為用戶提供本地副本而加快響應(yīng)時(shí)間；,(2)可以從多臺效勞器上訪問同一對象，從而提高系統(tǒng)有效性，降低效勞器故障的影響及通信失敗的可能性；,(3)可以在不同效勞器上并行執(zhí)行多個(gè)用戶對同一對象的請求，從而提高系統(tǒng)吞吐率。,按照客戶的觀點(diǎn)，備份事務(wù)效勞應(yīng)當(dāng)與非備份事務(wù)效勞一樣具有單副本可串行性，即通過并發(fā)控制，使多個(gè)事務(wù)表現(xiàn)為在一定順序下的串行執(zhí)行。,6.6.1 根本模型,最簡單的策略就是讀一／寫全,即讀時(shí)只讀一個(gè)副本，寫時(shí)要寫所有副本。這樣可以隨時(shí)保證各副本的一致性。但是由于多個(gè)客戶可能同時(shí)寫某一副本而產(chǎn)生寫沖突，所以

39、必須提供并發(fā)控制機(jī)制來保證分布事務(wù)的根本特性.,6.6.2 主／從模型,備份對象的效勞需求有一個(gè)根本效勞器及多個(gè)二級效勞器，根本效勞器擁有一個(gè)根本對象副本并響應(yīng)所有修改請求，其它的副本只響應(yīng)用戶的讀請求，不響應(yīng)用戶的寫請求。只接收來自根本效勞器的修改消息來修改副本或直接拷貝根本對象副本。,,客戶,客戶,,服務(wù)器,,服務(wù)器,,服務(wù)器,主副本,后備副本,后備副本,寫,讀,讀,寫,更新傳播,更新傳播,6.6.3 可用副本模型,主／從模型的主要缺乏在于：備份文件在根本效勞器失效時(shí)不能修改，并且僅適用于修改很少的對象。而讀一／寫全策略又是不現(xiàn)實(shí)的，因?yàn)楫?dāng)有些副本效勞器因故障或通信問題不能工作時(shí)，是絕對達(dá)

40、不到“寫全〞要求的,其根本思想是：即使有局部副本效勞器故障時(shí)系統(tǒng)仍可工作，其根本策略是，客戶的讀請求可以在任何可用副本上執(zhí)行，但客戶的寫請求必須在可用副本同時(shí)執(zhí)行。可用副本模型要求副本效勞器之間的通信無誤.,6.6.4 具有分布控制的系統(tǒng),我們要使用分布式控制機(jī)制，來完成副本管理，目的是即使一些副本失效，修改依然能進(jìn)展下去。在這種方法中，任何一個(gè)副本效勞器都能接收讀寫請求，并讓客戶得到有效一致的數(shù)據(jù)．,一.文件組:備份文件的副本集合,為支持備份策略，文件組必須存儲在每臺副本效勞器上。在完全一致的情況下，文件組中的副本有一樣的初始值，并且各次修改都是針對整個(gè)文件組而言的，所有副本自始至終保持一致

41、。,二. 版本號:,效勞器在讀副本之前，必須能從版本號和時(shí)間戳上判斷該代理是不是最新版本。副本的初態(tài)一般被認(rèn)為是第一版，以后每一次修改,就生成文件一個(gè)新版本.,三.多數(shù)一致算法:多數(shù)副本取得一致,即可完成操作,多數(shù)一致算法是最早提出的處理備份的分布控制算法，其原理可以應(yīng)用于兩個(gè)方面：,(1)備份：兩個(gè)多數(shù)集合中至少具有一個(gè)一樣元素，故多數(shù)原理能確保最新版副本的選擇。,(2)備份的并發(fā)控制：它對于非當(dāng)前版的文件可以作否決修改的決定。,6.6.5 分割與法定數(shù),分割是指某一時(shí)刻,副本所涉及到的全部效勞器之間不能兩兩相互通信而造成的一種難以保證副本一致性的狀況,相當(dāng)于將副本效勞器分成假設(shè)干個(gè)組,組內(nèi)

42、副本效勞器可以相互通信,但組間效勞器不能通信.,法定數(shù):一個(gè)組內(nèi)副本效勞器的個(gè)數(shù),目的是讓處于不同組的副本效勞器能夠獨(dú)立決定是否執(zhí)行客戶的請求.,6.6.6 法定數(shù)算法,原理:給文件組中的每個(gè)副本分配一個(gè)帶權(quán)的選票,不同效勞器權(quán)值不同,首先得到一個(gè)到達(dá)讀法定數(shù)R(即R個(gè)選票)后,才能從最新的副本執(zhí)行讀操作,在寫操作執(zhí)行前,必須到達(dá)寫法定數(shù)W(W個(gè)選票),R和W值的設(shè)定所要遵循的規(guī)那么:,①?? W > 選票總數(shù)的一半,②?? R + W >選票總數(shù),6.6.7 虛擬分割算法,可用副本算法和法定數(shù)算法結(jié)合而來,實(shí)現(xiàn):虛擬分割一個(gè)備份文件涉及的效勞器,劃分成假設(shè)干組,注意這是邏輯分組,一個(gè)組中含有足夠的副本效勞器,能滿足讀法定數(shù)和寫法定數(shù)那么事務(wù)可在該組效勞器上執(zhí)行,這時(shí)候?qū)嶋H是采用法定數(shù)算法.假設(shè)出現(xiàn)效勞器故障便試圖創(chuàng)立新的分割,使得分組可以滿足讀法定數(shù)和寫法定數(shù),從而保證單拷貝的可串行性.這種算法效率很高,在每個(gè)虛擬組內(nèi)使用的是可用副本算法,此方法是基于假設(shè)(實(shí)際分割較少產(chǎn)生,也是一種樂觀方法.),謝謝大家！,,,,,,,,結(jié) 語,,