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

單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,2021/3/13,,,南京理工大學(xué)計算機學(xué)院,,,,,,,,分布式系統(tǒng)與,WEB,服務(wù),,,,,,,單擊此處編輯母版標題樣式,*,,*,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,,*,,,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,,*,分布式系統(tǒng)與WEB服務(wù),5.1 共享文件的語義,兩個以上的用戶共享同一個文件時，會產(chǎn)生多種情況，從而產(chǎn)生不同的語義．故文件效勞時必須準確定義效勞的讀寫語義。,一.UNIX語義(時間順序),對于單處理機而言，在UNIX系統(tǒng)中，其讀操作的語義是，讀取的結(jié)果是它前面最近一次寫操作形成的結(jié)果。寫操作的語義是，假設(shè)先后連續(xù)有兩個寫操作，那么文件結(jié)果斷定于后面的寫操作。因此，最后形成的語義是嚴格意義下的時間序操作。,在對分布式文件系統(tǒng)中的文件進展讀操作時，能看到以前所有對該文件執(zhí)行寫操作的效果。特別是，客戶對于已翻開文件的寫操作可立即為其它翻開此文件的客戶所見?？蛻艨晒蚕砦募斍拔恢玫闹羔?。這樣，一個客戶將指針向前推進時將影響所有共享客戶的視圖。,此種語義的特點是易于理解和實現(xiàn)。,二.  會話語義,對于翻開文件的寫操作可以立即為本地客戶所見，遠程的客戶也同時翻開該文件，但卻不可見。一旦文件關(guān)閉，對此文件所作的修改僅為后面進展的操作所見，該文件已經(jīng)翻開的各副本不表現(xiàn)這些修改.,三.  不可改變文件語義,一但文件為共享文件，那么所有用戶均不能再修改它。這里的不可改變有兩個含義：一是其名字不可再變；二是其內(nèi)容不可改變。這樣，不可改變的文件的名字代表該文件的固定內(nèi)容，而不再是信息存儲機制。這一語義非常簡單，易于實現(xiàn)，但應(yīng)用起來，很不靈活．,四.   事務(wù)語義,用戶假設(shè)要訪問一個文件或了組文件，首先要執(zhí)行一個啟動事務(wù)的操作,表示下面的操作必須獨立執(zhí)行，然后對文件進展讀寫操作，當工作完成后，再執(zhí)行一個完畢事務(wù)的操作。,其關(guān)鍵特性是,保證事務(wù)期間的所有文件操作按序執(zhí)行，而不受其它用戶的干擾，也就是說，在事務(wù)內(nèi)部嚴格具有UNIX語義、顯然，事務(wù)語義是一種比較實用的文件語義。事務(wù)的完成要求一個客戶機與一個或幾個效勞器進展協(xié)作。,5,．,2,原子事務(wù),在分布式系統(tǒng)中，原子事物又簡稱事物，事務(wù)實際上就是一組邏輯上連續(xù)執(zhí)行的操作，其具有動態(tài)性，有三種狀態(tài)：,①提交 事務(wù)中的文件數(shù)據(jù)項的修改永久保存,②中止 由于同其他事務(wù)沖突或硬件故障導(dǎo)致事務(wù)中止,③臨時 事務(wù)執(zhí)行中的存在的臨時狀態(tài),5.2.1 事務(wù)的特性,事務(wù)具有以下四個特性,簡稱ACID特性,①原子性(Atomic):即事務(wù)的作用要么完整，要么沒有。,②一致性(Consistent)：事務(wù)處理不影響系統(tǒng)中的不變性：意思是，當系統(tǒng)具有某種不變特性需要保持時，在事務(wù)執(zhí)行前后該不變性一定要保持。例如，銀行業(yè)務(wù)系統(tǒng)中有一個關(guān)鍵的不變特性是“金錢不滅〞，經(jīng)過內(nèi)部任何轉(zhuǎn)帳之后，銀行的總錢數(shù)是不變的。,③孤立性(Isolated)：并發(fā)的事務(wù)不會相互影響，多個事務(wù)處理可并發(fā)執(zhí)行，其結(jié)果和各事務(wù)處理串行執(zhí)行結(jié)果一樣，也叫串行等價性。,三個事務(wù)A、B、C被三個獨立的進程同時執(zhí)行,假設(shè)順序執(zhí)行其結(jié)果為1、2或3,BEGIN_TRANSACTION A BEGIN_TRANSACTION 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,時間,調(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; x=0;x=x+2; x=x+3;,不合法,④持久性(Durable)：如果事務(wù)處理成功完成、那么結(jié)果將永不消失，除非發(fā)生硬故障。,5.2.2 事務(wù)需求,,銀行根本業(yè)務(wù)效勞,,服務(wù)過程,,,,解釋,,,存款,(,賬號，數(shù)額,),,,將指定,數(shù)額,的款項存入給定,賬號,,,取款,(,賬號，數(shù)額,),,,從給定,賬號,取出指定,數(shù)額,的款項,,,平衡,(,賬號,),,,返回給定,賬號,的當前平衡,,,總平衡,(),,,返回該客戶所有賬號的總平衡,,,開始事務(wù)處理,(,標號,),,,開始指定,標號,的事務(wù)處理,,,結(jié)束事務(wù)處理,(,標號,),,,結(jié)束指定,標號,的事務(wù)處理,,,流產(chǎn)事務(wù)處理,(,標號,),,,迫使指定,標號,的事務(wù)處理流產(chǎn),,,,銀行效勞的例子,開場事務(wù)處理(T) ；,K：取款(A，100) ；,K：存款(B，100) ；,K：取款(C，200) ；,K：存款(B，200) ；,完畢事務(wù)處理(T),我們將用T、U、V代表事務(wù)處理標號，用K、M、N代表不同的銀行分行，用A、B、C代表客戶的分行賬號，一個客戶發(fā)出的一系列效勞過程調(diào)用就可以合并為一次事務(wù)處理。,5．3 并發(fā)控制,并發(fā)控制的主要目標是滿足事務(wù)處理的一致性(串行等價性),最早的方法:,A.某一時刻只允許執(zhí)行一個事務(wù),B 在啟動多個事物操作之前先檢查是否滿足一致性,缺點:,解決的不好.為彌補缺乏.提出下面三種方法.,5.3.1 加鎖,當某一事務(wù)訪問一共享數(shù)據(jù)項時，由效勞器對該數(shù)據(jù)項加鎖，當完成訪問時，再由效勞器開鎖，以便于其它事務(wù)訪問。在上鎖期間，只有鎖定該數(shù)據(jù)項的事務(wù)才能對其訪問，這樣就保證了在某一時刻訪問數(shù)據(jù)進程的唯一性和確定性。,一.根本原理,一個鎖可由三都分組成：,①一個二值邏輯變量，用以指示上鎖／開鎖；,②一個類似于信號燈的條件變量；,③訪問該鎖的宿主事務(wù)標識符,實現(xiàn)上鎖機制時，需要注意鎖的粒度。粒度是指被加鎖的數(shù)據(jù)項的大小，粒度越細，那么并行度越高，反之，并行度越低。對整個文件加鎖是一種極端情況，這時候，事務(wù)串行執(zhí)行。在下面的討論中，上鎖一般施加于文件中的數(shù)據(jù)項上。,鎖定機制是分兩個階段進展的。一個事務(wù)在工作過程中，可分為“生長〞和“消亡〞兩個階段。生長階段需要上鎖，消亡階段需要開鎖，這就是兩階段鎖定機制。在生長階段，事務(wù)處于臨時狀態(tài)，其臨時數(shù)據(jù)不為其它事務(wù)所見。在消亡階段，臨時數(shù)據(jù)要變成永久數(shù)據(jù)，為了保持事務(wù)的特性，必須在事務(wù)關(guān)閉的最后，才能開鎖。,二、幾種加鎖方案,1．最簡單的加鎖方法,在這種方案中，文件效勞器對客戶事務(wù)訪問的每一個數(shù)據(jù)項加鎖，而在事務(wù)完成(或中止)時翻開所有的鎖，當另一事務(wù)試圖訪問已上鎖的數(shù)據(jù)項時，它必須等待到開鎖為止。,2. 讀／寫鎖方案,由于簡單鎖定機制不必要地將所有訪問到的數(shù)據(jù)項鎖定，從而降低了事務(wù)的并發(fā)性。特別是當事務(wù)中均是讀操作時，便沒有必要上鎖。,基于這種分析，提出了讀／寫鎖方案，即允許多個事務(wù)并發(fā)讀同一數(shù)據(jù)項，只允許一個事務(wù)寫一個數(shù)據(jù)項。也稱為“多讀／單寫〞 方法。在這種方法中，對于讀操作，還不能放棄上鎖，因為不上鎖，可能會有其它事務(wù)修改它，造成不一致。為此，要采用兩種不同的鎖，即讀鎖和寫鎖 對于訪問的所有數(shù)據(jù)項均可上讀鎖，只對寫操作訪問的數(shù)據(jù)項上寫鎖。上寫鎖的數(shù)據(jù)項不能被其它事務(wù)所訪問，上讀鎖的數(shù)據(jù)項只能為其它事務(wù)讀，但不能寫。,上鎖和開鎖的根本規(guī)那么如示:,1．當客戶在事務(wù)中訪問數(shù)據(jù)項時，有如下情況：,①如果數(shù)據(jù)項還未上鎖，效勞器將其鎖定，并讓客戶防問該數(shù)據(jù)項；,②如果數(shù)據(jù)項已被其它事務(wù)上鎖，客戶必須等待該鎖翻開：,③如果效勞器已經(jīng)鎖定了本領(lǐng)務(wù)中的一個數(shù)據(jù)項，客戶可以繼續(xù)防問。,④如果事務(wù)想要寫自己已上有讀鎖的數(shù)據(jù)項，應(yīng)當將讀鎖改為寫鎖。,2.當事務(wù)提交或中止時，效勞器翻開它為該事務(wù)鎖定的所有數(shù)據(jù)項。,3.,讀寫鎖的死鎖問題,以上兩種方法都在一定程度上提高了并發(fā)性，但與此同時也會帶來另一個問題,——,死鎖。所謂死鎖就是一組事務(wù)中的每個操作都處于上鎖且又等待開鎖的狀態(tài)，例如以下兩個事務(wù),U,和,T,，在時間順序上依次采取如下動作，結(jié)果將導(dǎo)致死鎖。,,T,等待事務(wù),U,釋放讀鎖,b,，而它本身又對其加讀鎖引起事務(wù),U,對其解鎖的等待，由此，便導(dǎo)致了互相牽制。,解決方法有如下,4,種,①在事務(wù)開場執(zhí)行前便對其所要訪問的數(shù)據(jù)加鎖，這雖能預(yù)防死鎖，但卻降低了資源共享率。,②給資源規(guī)定一個序號，申請資源時必須按序號單調(diào)遞增或遞減的方向申請，這種方法也降低了并行性。,③通過資源申請占有圖來檢測有無死鎖，一旦發(fā)現(xiàn)死鎖便由效勞器中止一個事務(wù)來打破循環(huán)占有等待，解決死鎖。,④“時限〞控制，是文件系統(tǒng)中較常用的方法，即給每個鎖規(guī)定一個時間段。在此時段內(nèi)，該鎖是穩(wěn)定的，假設(shè)超出此時限后，該鎖便變成易損鎖，假設(shè)此時沒有別的事務(wù)對上鎖數(shù)據(jù)項競爭，那么該鎖繼續(xù)保持；否那么的話，便打破此鎖，與此同時，原上鎖事務(wù)中止。這種方法也有兩個缺乏，第一是增加了系統(tǒng)開銷；第二是“時限〞的取值問題,4．意向?qū)戞i,讀／寫鎖中讀鎖的存在阻止了其它事務(wù)對其進展寫操作，在一定程度上降低了并發(fā)性。然而事務(wù)的執(zhí)行要經(jīng)過兩個階段，在臨時階段，寫操作實際上只是將改寫的內(nèi)容寫到一個臨時緩沖區(qū)中，并未改寫實際的數(shù)據(jù)項。只有在提交階段才寫回數(shù)據(jù)項，基于此原理可把讀／寫鎖改成意向?qū)戞i和提交鎖來提高并發(fā)性.,5.3.2 樂觀的并發(fā)控制方法,一.問題的提出,使用鎖機制處理并發(fā)控制時存在一些缺陷：,①分布式系統(tǒng)中的鎖機制是一種額外的開銷。例如，在只有讀操作的事務(wù)中，鎖可以保證所讀的數(shù)據(jù)項不被別的事務(wù)修改，但這種鎖只有在最壞的情況下才有必要。又例如，兩個客戶進程并發(fā)地對n個數(shù)據(jù)項進展增值運算，假設(shè)它們同時啟動，執(zhí)行時間量也一樣，以互不相關(guān)的序列訪問數(shù)據(jù)項，并且各自使用一個事務(wù)來訪問和增值數(shù)據(jù)項，那么這兩個程序試圖同時訪問同一數(shù)據(jù)項的時機僅有1／n，也即每n個事務(wù)中實際有用的鎖只有一次。,②使用鎖機制會導(dǎo)致死鎖，并且沒有令人滿意的死鎖解決算法。在鎖機制中，只有在一個事務(wù)終止時才釋放它的所有鎖，這明顯有損于并發(fā)性。正是基于以上原因，有人提出另一種算法——樂觀的并發(fā)控制方法。之所以稱其為“樂觀〞，是基于這樣一種假設(shè)，兩個客戶的事務(wù)同時訪問某一數(shù)據(jù)的可能性很小, 因此兩個事務(wù)可以執(zhí)行下去，直至發(fā)出C1oseTransaction請求。當產(chǎn)生沖突時，一般要中止一些事務(wù)，并由客戶重新啟動。這樣，每個事務(wù)便分為以下三個階段：,1.讀階段：在這一階段中，每個事務(wù)有一個待更新數(shù)據(jù)的臨時版本。讀請求可以立即執(zhí)行，如果有臨時版本存在，那么要訪問最近提交的數(shù)據(jù)值。而寫請求以一種其它事務(wù)不可見的形式緩存起來，假設(shè)有幾個并發(fā)事務(wù)，可能會同時存在同一數(shù)據(jù)項的幾個不同的臨時值。另外，針對于每一個事務(wù)需要設(shè)置兩個集合：讀集合和寫集合，讀集合列出事務(wù)所讀的數(shù)據(jù)項的集合，而寫集合那么列出事務(wù)創(chuàng)立、修改、刪除的數(shù)據(jù)項集合。,2.確認階段：當效勞器收到CloseTransaction請求之后，進入這個階段，在該階段中，對該事務(wù)進展確認是否可以將該事務(wù)的寫操作結(jié)果永久保存下來。,如果事務(wù)確認成功，那么進入寫階段(寫操作結(jié)果記錄到相關(guān)文件中，事務(wù)成功完成，發(fā)出commit);否那么，要解決沖突，需要中止某些事務(wù)。確認階段是建立在一致性根底上的，即如果事務(wù)執(zhí)行的結(jié)果等價于各個事務(wù)順序執(zhí)行的結(jié)果，那么該事務(wù)視為確認成功。,3.寫階段：如果一個事務(wù)確認成功，那么臨時版本記錄的所有修改均可以變?yōu)橛谰眯孕薷?。只讀事務(wù)可以在確認通過后立即提交。寫事務(wù)在臨時版本中的數(shù)據(jù)變?yōu)橛谰脭?shù)據(jù)之后立即提交。,二、事務(wù)確實認,確認是利用讀寫沖突規(guī)那么來保證一組重疊事務(wù)(即當前事務(wù)還未提交便已開場的事務(wù))的調(diào)度符合一致性, 當一個事務(wù)完成第一階段工作后,為其指定一個事務(wù)號，假設(shè)該事務(wù)確認成功完成,那么事務(wù)號被保存下來：否那么，假設(shè)事務(wù)未被確認，或事務(wù)是只讀事務(wù)，那么釋放該事務(wù)號．,確認工作主要基于兩個事務(wù)操作的沖突來完成的 對于兩個重疊事務(wù)Ti和TJ，必須滿足以下規(guī)那么。,確認方法有兩種，一種叫做向后確認(Backward Validation)，以正在執(zhí)行確認的事務(wù)為基準，檢查已經(jīng)進入確認階段的事務(wù)。一種叫做向前確認(Forward Validation)，以正在執(zhí)行確認的事務(wù)為基準，檢查后續(xù)進人確認階段的事務(wù).,三. 餓死現(xiàn)象,事務(wù)中止后, 通常由客戶程序重新啟動, 但有可能該事務(wù)仍然無法通過確認, 于是其又被中止, 重啟, 再中止. 如此, 該事務(wù)那么被剝奪了提交能力 此現(xiàn)象即為餓死,時間戳,要利用時間戳完成并發(fā)控制，需要對每個事務(wù)的操作進展有效性檢查，假設(shè)檢查未能通過,那么該事務(wù)立即中止并重新啟動,根本的時間規(guī)那么:,①事務(wù)對數(shù)據(jù)項的寫請求，僅當該數(shù)據(jù)項最近由前一個事務(wù)(有沖突)讀和寫，才能有效。,②事務(wù)對數(shù)據(jù)項的讀請求，僅當該數(shù)據(jù)項剛剛由前一個事務(wù)(有沖突)寫，才能有效。,該規(guī)那么允許并發(fā)事務(wù)共享臨時數(shù)據(jù)項，從而確保每個數(shù)據(jù)項的臨時值按時間戳順序提交.,5．4 恢復(fù),事務(wù)的原子性要求事務(wù)要么提供完整的運行結(jié)果，要么么作用都沒有，即持久性和失效原子性。這兩個需要并不是獨立的，可以由效勞器上的獨立機制來管理，我們稱這個機制叫做恢復(fù)管理器。,恢復(fù)管理器的主要任務(wù)是；,①將提交事務(wù)的數(shù)據(jù)保存到永久性存儲介質(zhì)(恢復(fù)文件)上；,②故障重啟后，恢復(fù)效勞器的數(shù)據(jù)；,③組織恢復(fù)文件，改進恢復(fù)性能；,④回收恢復(fù)文件涉及到的空間。,5．5 事務(wù)效勞中的文件版本,文件版本的實現(xiàn),通過在每個文件的索引表中擴大一項,即版本號,通過對影子頁的操作,到事務(wù)提交時,假設(shè)無版本沖突,那么合并臨時版本與當前版本得到最新版本.假設(shè)有沖突那么放棄臨時版本.,意向表的實現(xiàn),也可通過對影子頁的操作實現(xiàn)意向表,,意向表記錄:操作類型、事務(wù)標識符、文件標識符、頁號、影子頁面的指針,,文件版本方法,解決兩類問題,:,版本沖突和串行沖突,,版本沖突,:,并發(fā)事務(wù)訪問同一個文件的不同數(shù)據(jù)段,,,從而產(chǎn),生不同的版本,,,但無一版本包含所有的修改,.,,串行沖突,:,并發(fā)事務(wù)訪問同一數(shù)據(jù)段,,,從而有多個寫操作,,,導(dǎo)致數(shù)據(jù)項決定于最后的版本,.,,版本沖突解決如圖,:,老版本,老版本,當前版本,合并最新版本,事務(wù),T,的臨時版本,事務(wù),U,的臨時版本,,版本的合并,老版本,老版本,上一個版本,當前版本,事務(wù),T,的臨時版本,事務(wù),U,的臨時版本,,串行沖突的解決,意向表方法,意向表實際上是一個事務(wù)操作的日志記錄,是兩階段提交的機制.即:第一階段,事務(wù)處于臨時狀態(tài),第二階段,事務(wù)進入提交階段.如圖,,,,DATA為效勞器為待修改的數(shù)據(jù)的臨時拷貝.意向操作只是記錄到意向表并不是真的對文件操作,一個意向只有給出足夠的信息,才能到第二階段執(zhí)行.,,,,本領(lǐng)務(wù)的視圖,DATA1,DATA2,其它事務(wù)的視圖,第六章,,分布事務(wù)與文件備份,6．1 合作效勞器,合作效勞器是由多個物理效勞器合作完成一個邏輯效勞器的功能,各個效勞器由網(wǎng)絡(luò)互連,每個效勞器可具備不同性能,可位于不同地點, 并持有整個合作效勞器中所有文件的一局部,6．2 分布事務(wù),分布事務(wù)是指一個事務(wù)將涉及到多個效勞器的操作, 即該事務(wù)是由合作效勞器完成的, 構(gòu)造分布事務(wù)的方法有簡單分布事務(wù)和嵌套分布事務(wù)兩種,簡單分布事務(wù):客戶機可以屢次訪問不同的效勞器,效勞器僅響應(yīng)客戶機的請求,不引發(fā)其它效勞器的操作,嵌套分布事務(wù):一個效勞器上的操作可能引發(fā)其它效勞器操作,客戶機,服務(wù)器,1,服務(wù)器,2,服務(wù)器,3,在分布事務(wù)中,多個效勞器需要相互通信和合作,各自完成局部工作,最終是事務(wù)提交完成.在分布事務(wù)處理中,第一個響應(yīng)客戶機請求的效勞器為該事務(wù)的協(xié)調(diào)效勞器,負責(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ù)的分布，即一個事務(wù)處理所需的效勞與數(shù)據(jù)可能分散在不同的效勞器上，因此，事務(wù)處理過程就必須在多臺效勞器上執(zhí)行。,分布式事務(wù)處理的調(diào)度與同步,多臺效勞器聯(lián)合執(zhí)行一個事務(wù)處理時需要彼此協(xié)調(diào)，才能做到整個事務(wù)處理的成功提交,常用的方法是由一個協(xié)調(diào)者(coordinator)通過效勞器之間的通信來實現(xiàn)最終提交,分布式事務(wù)處理例子,開場事務(wù)處理(T) ；,K：取款(A，100) ；,M：存款(B，100) ；,N：取款(D，200) ；,M：存款(C，200) ；,完畢事務(wù)處理(T),某客戶要在K、M、N三個銀行分行的A、B、C、D四個賬號上執(zhí)行轉(zhuǎn)帳業(yè)務(wù)，即從K分行的A賬號取出100元，存入M分行的B賬號去，然后從N分行的D賬號取出200元并存入到M分行的C賬號。假定這三個分行的數(shù)據(jù)庫分別位于三臺效勞器上，其中S1管理K分行的A賬號 ，S2管理M分行的B、C兩個賬號，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)者,參與者,參與者,由于每個效勞器可能同時執(zhí)行不同的分布式事務(wù)處理，因此在整個系統(tǒng)中事務(wù)處理標號必須是唯一的。首先啟動分布式事務(wù)處理的那臺效勞器是整個事務(wù)處理的協(xié)調(diào)者效勞器,6．3 分布事務(wù)的提交協(xié)議,最簡單的方法:,1．一階段原子提交協(xié)議:,即由協(xié)調(diào)效勞器不斷查詢所有工作效勞器,直到所有工作效勞器都答復(fù)提交成功,完成整個事務(wù)提交,2．兩階段提交協(xié)議(2PC協(xié)議)，可以保證分布事務(wù)的原子性，在此協(xié)議中，任何效勞器都可以隨時中止自己的子事務(wù)而不影響客戶機事務(wù)的正常提交或中止。,協(xié)調(diào)效勞器分為兩階段工作(2PC)：,第一階段 投票階段,A協(xié)調(diào)效勞器向每個工作效勞期發(fā)出提交請求,B工作效勞器收到請求后,答復(fù)YES或NO,如答復(fù)有NO,那么終止,第二階段 完成階段,C協(xié)調(diào)效勞器查看搜集的票數(shù),假設(shè)無反對票,協(xié)調(diào)效勞器那么提交該事務(wù)并通知所有工作效勞器,否那么,假設(shè)有反對票協(xié)調(diào)效勞器那么終止事務(wù),并向所有答復(fù)YES的工作效勞器發(fā)出終止請求,3 嵌套事務(wù)的兩階段提交協(xié)議,嵌套事務(wù)的兩階段提交協(xié)議的執(zhí)行過程的第一階段與非 嵌套事務(wù)不同，當工作效勞器接到提交：,1)如果工作效勞器具有暫時提交且是頂層事務(wù)的子事務(wù),A.檢查它有沒有前輩事務(wù)處于中止事務(wù)表中，準備提交,B 中止具有中止前輩事務(wù)的事務(wù),C 向協(xié)調(diào)效勞器投票YES,2)如果工作效勞器沒有處于暫時提交狀態(tài)的、且是頂層事務(wù)的子事務(wù)，它肯定已經(jīng)失敗，應(yīng)向協(xié)調(diào)效勞器投票NO,注意:,A.子事務(wù)的標識符可以通過擴大其父事務(wù)的標識符;,B.子事務(wù)的提交決定于其父事務(wù)的提交,但父事務(wù)的提,交并不決定于其子事務(wù)的提交,6,．,4,分布事務(wù)中的并發(fā)控制,,當多個事務(wù)處理訪問同一個數(shù)據(jù)時，順序等價性要求必須把每一個事務(wù)處理對該數(shù)據(jù)的完整(讀/寫)訪問一一排序，嚴格制止任何沖突,,,開始事務(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,元,,,,,,,,,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ù)中的鎖,每個效勞器都要提供鎖管理機制，本地的鎖管理機制可以決定是否承受事務(wù)的請求操作。,,利用互斥鎖進展事務(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,,,,,,,,,,,,,,,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)等待鏈,死鎖處理：,置之不理 〔鴕鳥算法〕– 由程序員對其負責(zé),預(yù)防〔靜態(tài)的使死鎖在構(gòu)造上不可能〕 – 不存在運行系統(tǒng)支持,防止 〔合理的分配資源〕– 運行系統(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,，,300),,,鎖定,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)形等待鏈。,死鎖檢測算法：,中央式,,–,周期性地收集等待狀態(tài),分布式,,–,推出等待狀態(tài),提示式,–,構(gòu)造檢測體系,2. 分布事務(wù)中的時間戳,利用時間戳進展讀寫協(xié)作,3. 分布事務(wù)中的樂觀并發(fā)控制,分布事務(wù)通過一組獨立的效勞器進展確定，每個效勞器都要確認事務(wù)訪問的是自己的數(shù)據(jù)項，所有確認均通過兩階段進展。,,,[讀階段] 在讀階段，該事務(wù)處理所訪問的數(shù)據(jù)都有一套暫時版本，這套版本不對外，只由擁有者使用。采用暫時版本可以使事務(wù)處理流產(chǎn)而不會影響到長存數(shù)據(jù)。當執(zhí)行一個讀操作時，如果數(shù)據(jù)的暫時版本已經(jīng)存在，那么讀操作立即訪問之，否那么，就必須訪問那個數(shù)據(jù)最近提交的值。寫操作把每一數(shù)據(jù)的新值作為暫時值記錄在案。顯然，如果假設(shè)干個并發(fā)事務(wù)處理共享同一個數(shù)據(jù)，那么這個數(shù)據(jù)可能有不同的暫時值。除了上述規(guī)那么外，對每一個訪問的數(shù)據(jù)，事務(wù)處理還要維護兩個數(shù)值集合：讀集合包括該事務(wù)處理讀出的數(shù)據(jù)，寫集合囊括該事務(wù)處理寫入的數(shù)據(jù)。,[驗證階段] 當事務(wù)處理試圖提交時，就進入驗證階段，其目的是檢測是否它所訪問的數(shù)據(jù)與其它事務(wù)處理的操作有沖突。如果驗證無沖突，該事務(wù)處理可以提交；否那么我們就必須消解沖突。消除沖突的方法很簡單：或者命令該事務(wù)處理流產(chǎn)，或者從卷入沖突的事務(wù)處理中選擇一個令其流產(chǎn)。,[寫階段] 如果該事務(wù)處理已經(jīng)通過驗證，暫時版本中所記錄的數(shù)據(jù)更新就成為永久性的。如果該事務(wù)處理是只讀型事務(wù)處理，那么它馬上提交；否那么就要等到暫存數(shù)據(jù)全部寫入長存存儲器后，執(zhí)行提交操作。,樂觀并發(fā)控制算法,,6．5 分布事務(wù)中的恢復(fù),分布事務(wù)的恢復(fù)工作,效勞器 狀態(tài) 恢復(fù)管理器的工作,協(xié)調(diào)效勞器 準備提交 表示效勞器故障時還未做出仟何決定．將向所有工作,效勞器發(fā)出AbortTransaction，將中止狀態(tài)參加到恢,復(fù)文件中．假設(shè)狀態(tài)是中止，工作一樣。,如果沒有工作效勞器，將以超時判斷，中止相應(yīng)事務(wù),協(xié)調(diào)效勞器 提交 表示效勞器故障時已做出提交決定．假設(shè)是還沒有做完．,要發(fā)送DoCommit，給各工作效勞器，從這一步開場恢,復(fù)兩階段提交協(xié)議的執(zhí)行。,工作效勞器 提交 表示已經(jīng)提交．如果還未向上作效勞器發(fā)送HaveCommited,消息，那么發(fā)送之；然后，執(zhí)行整個事務(wù)中屬于自身的那一,局部操作(假設(shè)文件操作是可重復(fù)的，這樣做就不會引起不,一致性)。,工作效勞器 不確定 表示工作效勞器在知道事務(wù)輸出之前故障，必須等到協(xié)調(diào),效勞器作山?jīng)Q定，可以有GetDecison獲取。收到應(yīng)答后，,根據(jù)情況提交或中止。,工作效勞器 準備提交 表示工作效勞器還沒有投票，可以中止事務(wù)．,協(xié)調(diào)效勞器 完成 不需要任何工作,6．6 備份,備份是與分布事務(wù)及合作效勞器密切相關(guān)的問題。一個備份對象(如文件或數(shù)據(jù)項)由位于多個效勞器中的許多副本組成，我們稱組成一個備份對象的副本集合中的任意副本為該備份對象的一個代理。備份對象有如下特點：,(1)減少分布式系統(tǒng)中的通信量，并通過為用戶提供本地副本而加快響應(yīng)時間；,(2)可以從多臺效勞器上訪問同一對象，從而提高系統(tǒng)有效性，降低效勞器故障的影響及通信失敗的可能性；,(3)可以在不同效勞器上并行執(zhí)行多個用戶對同一對象的請求，從而提高系統(tǒng)吞吐率。,按照客戶的觀點，備份事務(wù)效勞應(yīng)當與非備份事務(wù)效勞一樣具有單副本可串行性，即通過并發(fā)控制，使多個事務(wù)表現(xiàn)為在一定順序下的串行執(zhí)行。,6.6.1 根本模型,最簡單的策略就是讀一／寫全,即讀時只讀一個副本，寫時要寫所有副本。這樣可以隨時保證各副本的一致性。但是由于多個客戶可能同時寫某一副本而產(chǎn)生寫沖突，所以必須提供并發(fā)控制機制來保證分布事務(wù)的根本特性.,6.6.2 主／從模型,備份對象的效勞需求有一個根本效勞器及多個二級效勞器，根本效勞器擁有一個根本對象副本并響應(yīng)所有修改請求，其它的副本只響應(yīng)用戶的讀請求，不響應(yīng)用戶的寫請求。只接收來自根本效勞器的修改消息來修改副本或直接拷貝根本對象副本。,,客戶,客戶,,服務(wù)器,,服務(wù)器,,服務(wù)器,主副本,后備副本,后備副本,寫,讀,讀,寫,更新傳播,更新傳播,6.6.3 可用副本模型,主／從模型的主要缺乏在于：備份文件在根本效勞器失效時不能修改，并且僅適用于修改很少的對象。而讀一／寫全策略又是不現(xiàn)實的，因為當有些副本效勞器因故障或通信問題不能工作時，是絕對達不到“寫全〞要求的,其根本思想是：即使有局部副本效勞器故障時系統(tǒng)仍可工作，其根本策略是，客戶的讀請求可以在任何可用副本上執(zhí)行，但客戶的寫請求必須在可用副本同時執(zhí)行?？捎酶北灸Ｐ鸵蟾北拘谄髦g的通信無誤.,6.6.4 具有分布控制的系統(tǒng),我們要使用分布式控制機制，來完成副本管理，目的是即使一些副本失效，修改依然能進展下去。在這種方法中，任何一個副本效勞器都能接收讀寫請求，并讓客戶得到有效一致的數(shù)據(jù)．,一.文件組:備份文件的副本集合,為支持備份策略，文件組必須存儲在每臺副本效勞器上。在完全一致的情況下，文件組中的副本有一樣的初始值，并且各次修改都是針對整個文件組而言的，所有副本自始至終保持一致。,二. 版本號:,效勞器在讀副本之前，必須能從版本號和時間戳上判斷該代理是不是最新版本。副本的初態(tài)一般被認為是第一版，以后每一次修改,就生成文件一個新版本.,三.多數(shù)一致算法:多數(shù)副本取得一致,即可完成操作,多數(shù)一致算法是最早提出的處理備份的分布控制算法，其原理可以應(yīng)用于兩個方面：,(1)備份：兩個多數(shù)集合中至少具有一個一樣元素，故多數(shù)原理能確保最新版副本的選擇。,(2)備份的并發(fā)控制：它對于非當前版的文件可以作否決修改的決定。,6.6.5 分割與法定數(shù),分割是指某一時刻,副本所涉及到的全部效勞器之間不能兩兩相互通信而造成的一種難以保證副本一致性的狀況,相當于將副本效勞器分成假設(shè)干個組,組內(nèi)副本效勞器可以相互通信,但組間效勞器不能通信.,法定數(shù):一個組內(nèi)副本效勞器的個數(shù),目的是讓處于不同組的副本效勞器能夠獨立決定是否執(zhí)行客戶的請求.,6.6.6 法定數(shù)算法,原理:給文件組中的每個副本分配一個帶權(quán)的選票,不同效勞器權(quán)值不同,首先得到一個到達讀法定數(shù)R(即R個選票)后,才能從最新的副本執(zhí)行讀操作,在寫操作執(zhí)行前,必須到達寫法定數(shù)W(W個選票),R和W值的設(shè)定所要遵循的規(guī)那么:,①   W > 選票總數(shù)的一半,②   R + W >選票總數(shù),6.6.7 虛擬分割算法,可用副本算法和法定數(shù)算法結(jié)合而來,實現(xiàn):虛擬分割一個備份文件涉及的效勞器,劃分成假設(shè)干組,注意這是邏輯分組,一個組中含有足夠的副本效勞器,能滿足讀法定數(shù)和寫法定數(shù)那么事務(wù)可在該組效勞器上執(zhí)行,這時候?qū)嶋H是采用法定數(shù)算法.假設(shè)出現(xiàn)效勞器故障便試圖創(chuàng)立新的分割,使得分組可以滿足讀法定數(shù)和寫法定數(shù),從而保證單拷貝的可串行性.這種算法效率很高,在每個虛擬組內(nèi)使用的是可用副本算法,此方法是基于假設(shè)(實際分割較少產(chǎn)生,也是一種樂觀方法.),謝謝大家！,,,,,,,,結(jié) 語,,