《分布式系統(tǒng)與WEB服務(3)》由會員分享，可在線閱讀，更多相關《分布式系統(tǒng)與WEB服務(3)（64頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務第五章第五章分布式系統(tǒng)文件共享分布式系統(tǒng)文件共享南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務5.1 5.1 共享文件的語義共享文件的語義 兩兩個個以以上上的的用用戶戶共共享享同同一一個個文文件件時時，會會產(chǎn)產(chǎn)生生多多種種情情況況，從從而而產(chǎn)產(chǎn)生生不不同同的的語語義義故故文文件件服服務務時時必必須須精精確確定定義義服服務務的的讀讀寫語義。寫語義。一一.UNIX.UNIX語義語義(時間順序時間順序)對對于于單單處處理理機機而而言言，在在UNIXUNIX系系統(tǒng)統(tǒng)中中，其其讀讀操操作

2、作的的語語義義是是，讀讀取取的的結結果果是是它它前前面面最最近近一一次次寫寫操操作作形形成成的的結結果果。寫寫操操作作的的語語義義是是，若若先先后后連連續(xù)續(xù)有有兩兩個個寫寫操操作作，則則文文件件結結果果決決定定于于后后面面的的寫寫操操作作。因因此此，最最后后形形成成的的語語義義是是嚴嚴格格意意義義下下的的時時間間序序操操作。作。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務在在對對分分布布式式文文件件系系統(tǒng)統(tǒng)中中的的文文件件進進行行讀讀操操作作時時，能能看看到到以以前前所所有有對對該該文文件件執(zhí)執(zhí)行行寫寫操操作作的的效效果果。特特別別是是，客客戶戶對對于于已

3、已打打開開文文件件的的寫寫操操作作可可立立即即為為其其它它打打開開此此文文件件的的客客戶戶所所見見。客客戶戶可可共共享享文文件件當當前前位位置置的的指指針針。這這樣樣，一一個個客客戶戶將將指指針針向向前前推進時將影響所有共享客戶的視圖。推進時將影響所有共享客戶的視圖。此種語義的特點是易于理解和實現(xiàn)。此種語義的特點是易于理解和實現(xiàn)。二二.會話語義會話語義 對對于于打打開開文文件件的的寫寫操操作作可可以以立立即即為為本本地地客客戶戶所所見見，遠遠程程的的客客戶戶也也同同時時打打開開該該文文件件，但但卻卻不不可可見見。一一旦旦文文件件關關閉閉，對對此此文文件件所所作作的的修修改改僅僅為為后后面面進進

4、行行的的操操作作所所見見，該該文文件件已已經(jīng)經(jīng)打開的各副本不表現(xiàn)這些修改打開的各副本不表現(xiàn)這些修改.南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 三三.不可改變文件語義不可改變文件語義 一一但但文文件件為為共共享享文文件件，則則所所有有用用戶戶均均不不能能再再修修改改它它。這這里里的的不不可可改改變變有有兩兩個個含含義義：一一是是其其名名字字不不可可再再變變；二二是是其其內(nèi)內(nèi)容容不不可可改改變變。這這樣樣，不不可可改改變變的的文文件件的的名名字字代代表表該該文文件件的的固固定定內(nèi)內(nèi)容容，而而不不再再是是信信息息存存儲儲機機制制。這這一一語語義義非非常常簡簡

5、單單，易易于于實實現(xiàn)現(xiàn)，但但應應用起來，很不靈活用起來，很不靈活四四.事務語義事務語義 用用戶戶若若要要訪訪問問一一個個文文件件或或了了組組文文件件，首首先先要要執(zhí)執(zhí)行行一一個個啟啟動動事事務務的的操操作作,表表示示下下面面的的操操作作必必須須獨獨立立執(zhí)執(zhí)行行，然然后后對對文文件件進進行行讀讀寫操作，當工作完成后，再執(zhí)行一個結束事務的操作。寫操作，當工作完成后，再執(zhí)行一個結束事務的操作。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務其其關關鍵鍵特特性性是是,保保證證事事務務期期間間的的所所有有文文件件操操作作按按序序執(zhí)執(zhí)行行，而而不不受受其其它它用用戶戶的的

6、干干擾擾，也也就就是是說說，在在事事務務內(nèi)內(nèi)部部嚴嚴格格具具有有UNIXUNIX語語義義、顯顯然然，事事務務語語義義是是一一種種比比較較實實用用的的文文件件語語義義。事事務務的的完完成成要要求求一一個個客客戶戶機機與與一一個個或或幾幾個個服服務務器器進進行行協(xié)作。協(xié)作。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務5 52 2 原子事務原子事務 在在分分布布式式系系統(tǒng)統(tǒng)中中，原原子子事事物物又又簡簡稱稱事事物物，事事務務實實際際上上就就是一組邏輯上連續(xù)執(zhí)行的操作，其具有動態(tài)性，有三種狀態(tài)：是一組邏輯上連續(xù)執(zhí)行的操作，其具有動態(tài)性，有三種狀態(tài)：提交提交 事務中

7、的文件數(shù)據(jù)項的修改永久保存事務中的文件數(shù)據(jù)項的修改永久保存 中止中止 由于同其他事務沖突或硬件故障導致事務中止由于同其他事務沖突或硬件故障導致事務中止 臨時臨時 事務執(zhí)行中的存在的臨時狀態(tài)事務執(zhí)行中的存在的臨時狀態(tài)南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 5.2.1 5.2.1 事務的特性事務的特性 事務具有以下四個特性事務具有以下四個特性,簡稱簡稱ACIDACID特性特性 原子性原子性(Atomic):(Atomic):即事務的作用要么完整，要么沒有。即事務的作用要么完整，要么沒有。一一致致性性(Consistent)Consistent)：事事務務

8、處處理理不不影影響響系系統(tǒng)統(tǒng)中中的的不不變變性性：意意思思是是，當當系系統(tǒng)統(tǒng)具具有有某某種種不不變變特特性性需需要要保保持持時時，在在事事務務執(zhí)執(zhí)行行前前后后該該不不變變性性一一定定要要保保持持。例例如如，銀銀行行業(yè)業(yè)務務系系統(tǒng)統(tǒng)中中有有一一個個關關鍵鍵的的不不變變特特性性是是“金金錢錢不不滅滅”，經(jīng)經(jīng)過過內(nèi)內(nèi)部部任任何何轉(zhuǎn)轉(zhuǎn)帳帳之之后后，銀銀行行的的總總錢錢數(shù)是不變的。數(shù)是不變的。孤孤立立性性(Isolated)(Isolated)：并并發(fā)發(fā)的的事事務務不不會會相相互互影影響響，多多個個事事務務處處理理可可并并發(fā)發(fā)執(zhí)執(zhí)行行，其其結結果果和和各各事事務務處處理理串串行行執(zhí)執(zhí)行行結結果果一一樣樣

9、，也也叫叫串行等價性。串行等價性。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 三個事務三個事務A A、B B、C C被三個獨立的進程同時執(zhí)行被三個獨立的進程同時執(zhí)行,若順序執(zhí)行其結果為若順序執(zhí)行其結果為1 1、2 2或或3 3 BEGIN_TRANSACTION A BEGIN_TRANSACTION B BEGIN_TRANSACTION C BEGIN_TRANSACTION A BEGIN_TRANSACTION B BEGIN_TRANSACTION C X=0;X=0;X=0;X=0;X=0;X=0;X=X+1;X=X+2;X=X+3;X=X+

10、1;X=X+2;X=X+3;END_TRANSACTION END_TRANSACTION END_TRANSACTION END_TRANSACTION END_TRANSACTION END_TRANSACTION 時間時間調(diào)度1x=0;x=x+1;x=0;x=x+2;x=0;x=x+3;合法調(diào)度2x=0;x=0;x=x+1;x=x+2;x=0;x=x+3;合法調(diào)度3x=0;x=0;x=x+1;x=0;x=x+2;x=x+3;不合法南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 持持久久性性(Durable)(Durable)：如如果果事事務務處處理理成

11、成功功完完成成、則則結結果果將將永永不不消失，除非發(fā)生硬故障。消失，除非發(fā)生硬故障。5.2.2 5.2.2 事務需求事務需求 銀行基本業(yè)務服務服務過程解釋存款存款(賬號，數(shù)號，數(shù)額)將指定數(shù)數(shù)額的款項存入給定賬號號取款取款(賬號，數(shù)號，數(shù)額)從給定賬號號取出指定數(shù)數(shù)額的款項平衡平衡(賬號號)返回給定賬號號的當前平衡總平衡平衡()()返回該客戶所有賬號的總平衡開始事開始事務處理理(標號號)開始指定標號號的事務處理結束事束事務處理理(標號號)結束指定標號號的事務處理流流產(chǎn)事事務處理理(標號號)迫使指定標號號的事務處理流產(chǎn)南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務

12、服務銀行服務的例子開始事開始事務處理理(T)(T)；K K：取款：取款(A(A，100)100)；K K：存款：存款(B(B，100)100)；K K：取款：取款(C(C，200)200)；K K：存款：存款(B(B，200)200)；結束事束事務處理理(T)(T)我們將用T、U、V代表事務處理標號，用K、M、N代表不同的銀行分行，用A、B、C代表客戶的分行賬號，一個客戶發(fā)出的一系列服務過程調(diào)用就可以合并為一次事務處理。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務5 53 3 并發(fā)控制并發(fā)控制 并并發(fā)發(fā)控控制制的的主主要要目目標標是是滿滿足足事事務務處處理

13、理的的一一致致性性(串串行行等等價性價性),),最早的方法最早的方法:A.A.某一時刻只允許執(zhí)行一個事務某一時刻只允許執(zhí)行一個事務 B B 在啟動多個事物操作之前先檢查是否滿足一致性在啟動多個事物操作之前先檢查是否滿足一致性 缺點缺點:解決的不好解決的不好.為彌補不足為彌補不足.提出提出下面三種方法下面三種方法.南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 5.3.15.3.1 加鎖加鎖 當當某某一一事事務務訪訪問問一一共共享享數(shù)數(shù)據(jù)據(jù)項項時時，由由服服務務器器對對該該數(shù)數(shù)據(jù)據(jù)項項加加鎖鎖，當當完完成成訪訪問問時時，再再由由服服務務器器開開鎖鎖，以以便便于

14、于其其它它事事務務訪訪問問。在在上上鎖鎖期期間間，只只有有鎖鎖定定該該數(shù)數(shù)據(jù)據(jù)項項的的事事務務才才能能對對其其訪訪問問，這這樣樣就保證了在某一時刻訪問數(shù)據(jù)進程的唯一性和確定性。就保證了在某一時刻訪問數(shù)據(jù)進程的唯一性和確定性。一一.基本原理基本原理 一個鎖可由三都分組成：一個鎖可由三都分組成：一個二值邏輯變量，用以指示上鎖開鎖；一個二值邏輯變量，用以指示上鎖開鎖；一個類似于信號燈的條件變量；一個類似于信號燈的條件變量；訪問該鎖的宿主事務標識符訪問該鎖的宿主事務標識符南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務實實現(xiàn)現(xiàn)上上鎖鎖機機制制時時，需需要要注注意意鎖鎖

15、的的粒粒度度。粒粒度度是是指指被被加加鎖鎖的的數(shù)數(shù)據(jù)據(jù)項項的的大大小小，粒粒度度越越細細，則則并并行行度度越越高高，反反之之，并并行行度度越越低低。對對整整個個文文件件加加鎖鎖是是一一種種極極端端情情況況，這這時時候候，事事務務串串行行執(zhí)行。執(zhí)行。在下面的討論中，上鎖一般施加于文件中的數(shù)據(jù)項上。在下面的討論中，上鎖一般施加于文件中的數(shù)據(jù)項上。鎖鎖定定機機制制是是分分兩兩個個階階段段進進行行的的。一一個個事事務務在在工工作作過過程程中中，可可分分為為“生生長長”和和“消消亡亡”兩兩個個階階段段。生生長長階階段段需需要要上上鎖鎖，消消亡亡階階段段需需要要開開鎖鎖，這這就就是是兩兩階階段段鎖鎖定定機

16、機制制。在在生生長長階階段段，事事務務處處于于臨臨時時狀狀態(tài)態(tài)，其其臨臨時時數(shù)數(shù)據(jù)據(jù)不不為為其其它它事事務務所所見見。在在消消亡亡階階段段，臨臨時時數(shù)數(shù)據(jù)據(jù)要要變變成成永永久久數(shù)數(shù)據(jù)據(jù)，為為了了保保持持事事務務的的特特性性，必必須在事務關閉的最后，才能開鎖。須在事務關閉的最后，才能開鎖。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 二、幾種加鎖方案二、幾種加鎖方案 1 1最簡單的加鎖方法最簡單的加鎖方法 在在這這種種方方案案中中，文文件件服服務務器器對對客客戶戶事事務務訪訪問問的的每每一一個個數(shù)數(shù)據(jù)據(jù)項項加加鎖鎖，而而在在事事務務完完成成(或或中中止止)時

17、時打打開開所所有有的的鎖鎖，當當另另一一事務試圖訪問已上鎖的數(shù)據(jù)項時，它必須等待到開鎖為止。事務試圖訪問已上鎖的數(shù)據(jù)項時，它必須等待到開鎖為止。2.2.讀寫鎖方案讀寫鎖方案 由由于于簡簡單單鎖鎖定定機機制制不不必必要要地地將將所所有有訪訪問問到到的的數(shù)數(shù)據(jù)據(jù)項項鎖鎖定定，從從而而降降低低了了事事務務的的并并發(fā)發(fā)性性。特特別別是是當當事事務務中中均均是是讀讀操操作作時時，便沒有必要上鎖便沒有必要上鎖。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務基基于于這這種種分分析析，提提出出了了讀讀寫寫鎖鎖方方案案，即即允允許許多多個個事事務務并并發(fā)發(fā)讀讀同同一一數(shù)數(shù)據(jù)據(jù)

18、項項，只只允允許許一一個個事事務務寫寫一一個個數(shù)數(shù)據(jù)據(jù)項項。也也稱稱為為“多多讀讀單單寫寫”方方法法。在在這這種種方方法法中中，對對于于讀讀操操作作，還還不不能能放放棄棄上上鎖鎖，因因為為不不上上鎖鎖，可可能能會會有有其其它它事事務務修修改改它它，造造成成不不一一致致。為為此此，要要采采用用兩兩種種不不同同的的鎖鎖，即即讀讀鎖鎖和和寫寫鎖鎖 對對于于訪訪問問的的所所有有數(shù)數(shù)據(jù)據(jù)項項均均可可上上讀讀鎖鎖，只只對對寫寫操操作作訪訪問問的的數(shù)數(shù)據(jù)據(jù)項項上上寫寫鎖鎖。上上寫寫鎖鎖的的數(shù)數(shù)據(jù)據(jù)項項不不能能被被其其它它事事務務所所訪訪問問，上上讀讀鎖鎖的的數(shù)數(shù)據(jù)據(jù)項只能為其它事務讀，但不能寫項只能為其它事

19、務讀，但不能寫。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 上鎖和開鎖的基本規(guī)則如示上鎖和開鎖的基本規(guī)則如示:1 1當客戶在事務中訪問數(shù)據(jù)項時，有如下情況當客戶在事務中訪問數(shù)據(jù)項時，有如下情況：如如果果數(shù)數(shù)據(jù)據(jù)項項還還未未上上鎖鎖，服服務務器器將將其其鎖鎖定定，并并讓讓客客戶戶防防問問該數(shù)據(jù)項；該數(shù)據(jù)項；如果數(shù)據(jù)項已被其它事務上鎖，客戶必須等待該鎖打開：如果數(shù)據(jù)項已被其它事務上鎖，客戶必須等待該鎖打開：如如果果服服務務器器已已經(jīng)經(jīng)鎖鎖定定了了本本事事務務中中的的一一個個數(shù)數(shù)據(jù)據(jù)項項，客客戶戶可可以繼續(xù)防問。以繼續(xù)防問。如如果果事事務務想想要要寫寫自自己己

20、已已上上有有讀讀鎖鎖的的數(shù)數(shù)據(jù)據(jù)項項，應應當當將將讀讀鎖鎖改為寫鎖。改為寫鎖。2.2.當當事事務務提提交交或或中中止止時時，服服務務器器打打開開它它為為該該事事務務鎖鎖定定的的所所有有數(shù)數(shù)據(jù)項。據(jù)項。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 3.3.讀寫鎖的死鎖問題讀寫鎖的死鎖問題 以以上上兩兩種種方方法法都都在在一一定定程程度度上上提提高高了了并并發(fā)發(fā)性性，但但與與此此同同時時也也會會帶帶來來另另一一個個問問題題死死鎖鎖。所所謂謂死死鎖鎖就就是是一一組組事事務務中中的的每每個個操操作作都都處處于于上上鎖鎖且且又又等等待待開開鎖鎖的的狀狀態(tài)態(tài)，例例如如

21、以以下下兩兩個個事事務務U U和和T T，在在時時間間順順序序上上依依次次采采取取如如下下動動作作，結結果果將將導導致致死死鎖。鎖。T T等等待待事事務務U U釋釋放放讀讀鎖鎖b b，而而它它本本身身又又對對其其加加讀讀鎖鎖引引起起事事務務U U對其解鎖的等待，由此，便導致了對其解鎖的等待，由此，便導致了互相牽制。互相牽制。解決方法有如下解決方法有如下4 4種種南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 在在事事務務開開始始執(zhí)執(zhí)行行前前便便對對其其所所要要訪訪問問的的數(shù)數(shù)據(jù)據(jù)加加鎖鎖，這這雖雖能能預預防死鎖，但卻降低了資源共享率。防死鎖，但卻降低了資源共

22、享率。給給資資源源規(guī)規(guī)定定一一個個序序號號，申申請請資資源源時時必必須須按按序序號號單單調(diào)調(diào)遞遞增增或或遞減的方向申請，這種方法也降低了并行性。遞減的方向申請，這種方法也降低了并行性。通通過過資資源源申申請請占占有有圖圖來來檢檢測測有有無無死死鎖鎖，一一旦旦發(fā)發(fā)現(xiàn)現(xiàn)死死鎖鎖便便由由服務器中止一個事務來打破循環(huán)占有等待服務器中止一個事務來打破循環(huán)占有等待，解決死鎖。，解決死鎖。“時時限限”控控制制，是是文文件件系系統(tǒng)統(tǒng)中中較較常常用用的的方方法法，即即給給每每個個鎖鎖規(guī)規(guī)定定一一個個時時間間段段。在在此此時時段段內(nèi)內(nèi)，該該鎖鎖是是穩(wěn)穩(wěn)定定的的，若若超超出出此此時時限限后后，該該鎖鎖便便變變成成易

23、易損損鎖鎖，若若此此時時沒沒有有別別的的事事務務對對上上鎖鎖數(shù)數(shù)據(jù)據(jù)項項競競爭爭，則則該該鎖鎖繼繼續(xù)續(xù)保保持持；否否則則的的話話，便便打打破破此此鎖鎖，與與此此同同時時，原原上上鎖鎖事事務務中中止止。這這種種方方法法也也有有兩兩個個不不足足，第第一一是是增增加加了了系系統(tǒng)統(tǒng)開開銷；第二是銷；第二是“時限時限”的取值問題的取值問題南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 4 4意向?qū)戞i意向?qū)戞i 讀讀寫寫鎖鎖中中讀讀鎖鎖的的存存在在阻阻止止了了其其它它事事務務對對其其進進行行寫寫操操作作，在在一一定定程程度度上上降降低低了了并并發(fā)發(fā)性性。然然而而事事務務的

24、的執(zhí)執(zhí)行行要要經(jīng)經(jīng)過過兩兩個個階階段段，在在臨臨時時階階段段，寫寫操操作作實實際際上上只只是是將將改改寫寫的的內(nèi)內(nèi)容容寫寫到到一一個個臨臨時時緩緩沖沖區(qū)區(qū)中中，并并未未改改寫寫實實際際的的數(shù)數(shù)據(jù)據(jù)項項。只只有有在在提提交交階階段段才才寫寫回回數(shù)數(shù)據(jù)據(jù)項項，基基于于此此原原理理可可把把讀讀寫寫鎖鎖改改成成意意向向?qū)憣戞i鎖和和提提交交鎖來提高并發(fā)性鎖來提高并發(fā)性.南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 5.3.2 5.3.2 樂觀的并發(fā)控制方法樂觀的并發(fā)控制方法 一一.問題的提出問題的提出 使用鎖機制處理并發(fā)控制時存在一些缺陷：使用鎖機制處理并發(fā)控制時存

25、在一些缺陷：分分布布式式系系統(tǒng)統(tǒng)中中的的鎖鎖機機制制是是一一種種額額外外的的開開銷銷。例例如如，在在只只有有讀讀操操作作的的事事務務中中，鎖鎖可可以以保保證證所所讀讀的的數(shù)數(shù)據(jù)據(jù)項項不不被被別別的的事事務務修修改改，但但這這種種鎖鎖只只有有在在最最壞壞的的情情況況下下才才有有必必要要。又又例例如如，兩兩個個客客戶戶進進程程并并發(fā)發(fā)地地對對n n個個數(shù)數(shù)據(jù)據(jù)項項進進行行增增值值運運算算，若若它它們們同同時時啟啟動動，執(zhí)執(zhí)行行時時間間量量也也相相同同，以以互互不不相相關關的的序序列列訪訪問問數(shù)數(shù)據(jù)據(jù)項項，并并且且各各自自使使用用一一個個事事務務來來訪訪問問和和增增值值數(shù)數(shù)據(jù)據(jù)項項，則則這這兩兩個個

26、程程序序試試圖圖同同時時訪訪問問同同一一數(shù)數(shù)據(jù)據(jù)項項的的機機會會僅僅有有1 1n n，也也即即每每n n個個事事務務中中實實際際有有用用的的鎖只有一次。鎖只有一次。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務使使用用鎖鎖機機制制會會導導致致死死鎖鎖，并并且且沒沒有有令令人人滿滿意意的的死死鎖鎖解解決決算算法法。在在鎖鎖機機制制中中，只只有有在在一一個個事事務務終終止止時時才才釋釋放放它它的的所所有有鎖鎖，這這明明顯顯有有損損于于并并發(fā)發(fā)性性。正正是是基基于于以以上上原原因因，有有人人提提出出另另一一種種算算法法樂樂觀觀的的并并發(fā)發(fā)控控制制方方法法。之之所所

27、以以稱稱其其為為“樂樂觀觀”，是是基基于于這這樣樣一一種種假假設設，兩兩個個客客戶戶的的事事務務同同時時訪訪問問某某一一數(shù)數(shù)據(jù)據(jù)的的可可能能性性很很小小,因因此此兩兩個個事事務務可可以以執(zhí)執(zhí)行行下下去去，直直至至發(fā)發(fā)出出C1oseTransactionC1oseTransaction請請求求。當當產(chǎn)產(chǎn)生生沖沖突突時時，一一般般要要中中止止一一些些事事務務，并并由由客客戶戶重重新新啟啟動動。這這樣樣，每每個個事事務務便便分分為為以以下下三三個個階階段：段：南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 1.1.讀讀階階段段：在在這這一一階階段段中中，每每個個事

28、事務務有有一一個個待待更更新新數(shù)數(shù)據(jù)據(jù)的的臨臨時時版版本本。讀讀請請求求可可以以立立即即執(zhí)執(zhí)行行，如如果果有有臨臨時時版版本本存存在在，則則要要訪訪問問最最近近提提交交的的數(shù)數(shù)據(jù)據(jù)值值。而而寫寫請請求求以以一一種種其其它它事事務務不不可可見見的的形形式式緩緩存存起起來來，若若有有幾幾個個并并發(fā)發(fā)事事務務，可可能能會會同同時時存存在在同同一一數(shù)數(shù)據(jù)據(jù)項項的的幾幾個個不不同同的的臨臨時時值值。另另外外，針針對對于于每每一一個個事事務務需需要要設設置置兩兩個個集集合合：讀讀集集合合和和寫寫集集合合，讀讀集集合合列列出出事事務務所所讀讀的的數(shù)數(shù)據(jù)據(jù)項項的的集集合合，而寫集合則列出事務創(chuàng)建、修改、刪除的

29、數(shù)據(jù)項集合。而寫集合則列出事務創(chuàng)建、修改、刪除的數(shù)據(jù)項集合。2.2.確確認認階階段段：當當服服務務器器收收到到CloseTransactionCloseTransaction請請求求之之后后，進進入入這這個個階階段段，在在該該階階段段中中，對對該該事事務務進進行行確確認認是是否否可可以以將將該該事務的寫操作結果永久保存下來。事務的寫操作結果永久保存下來。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務如如果果事事務務確確認認成成功功，則則進進入入寫寫階階段段(寫寫操操作作結結果果記記錄錄到到相相關關文文件件中中，事事務務成成功功完完成成，發(fā)發(fā)出出commit)

30、;commit);否否則則，要要解解決決沖沖突突，需需要要中中止止某某些些事事務務。確確認認階階段段是是建建立立在在一一致致性性基基礎礎上上的的，即即如如果果事事務務執(zhí)執(zhí)行行的的結結果果等等價價于于各各個個事事務務順順序序執(zhí)執(zhí)行行的的結結果果，則則該該事務視為確認成功。事務視為確認成功。3.3.寫寫階階段段：如如果果一一個個事事務務確確認認成成功功，則則臨臨時時版版本本記記錄錄的的所所有有修修改改均均可可以以變變?yōu)闉橛烙谰镁眯孕孕扌薷母摹Ｖ恢蛔x讀事事務務可可以以在在確確認認通通過過后后立立即即提提交交。寫寫事事務務在在臨臨時時版版本本中中的的數(shù)數(shù)據(jù)據(jù)變變?yōu)闉橛烙谰镁脭?shù)數(shù)據(jù)據(jù)之之后后立即提交。立

31、即提交。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務二、二、事務的確認事務的確認 確確認認是是利利用用讀讀寫寫沖沖突突規(guī)規(guī)則則來來保保證證一一組組重重疊疊事事務務(即即當當前前事事務務還還未未提提交交便便已已開開始始的的事事務務)的的調(diào)調(diào)度度符符合合一一致致性性,當當一一個個事事務務完完成成第第一一階階段段工工作作后后,為為其其指指定定一一個個事事務務號號，若若該該事事務務確確認認成成功功完完成成,則則事事務務號號被被保保留留下下來來：否否則則，若若事事務務未未被被確確認認，或或事事務是只讀事務，則釋放該事務號務是只讀事務，則釋放該事務號 確確認認工工作作

32、主主要要基基于于兩兩個個事事務務操操作作的的沖沖突突來來完完成成的的 對對于于兩個重疊事務兩個重疊事務TiTi和和TJTJ，必須滿足下列規(guī)則必須滿足下列規(guī)則。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務確確認認方方法法有有兩兩種種，一一種種叫叫做做向向后后確確認認(Backward(Backward Validation)Validation)，以以正正在在執(zhí)執(zhí)行行確確認認的的事事務務為為基基準準，檢檢查查已已經(jīng)經(jīng)進進入入 確確 認認 階階 段段 的的 事事 務務。一一 種種 叫叫 做做 向向 前前 確確 認認(Forward Forward Valida

33、tion)Validation)，以以正正在在執(zhí)執(zhí)行行確確認認的的事事務務為為基基準準，檢檢查查后后續(xù)續(xù)進進人確認階段的事務人確認階段的事務.三三.餓死現(xiàn)象餓死現(xiàn)象 事事務務中中止止后后,通通常常由由客客戶戶程程序序重重新新啟啟動動,但但有有可可能能該該事事務務仍仍然然無無法法通通過過確確認認,于于是是其其又又被被中中止止,重重啟啟,再再中中止止.如此如此,該事務則被剝奪了提交能力該事務則被剝奪了提交能力 此現(xiàn)象即為餓死此現(xiàn)象即為餓死南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 5.3.3 5.3.3 時間戳時間戳 要要利利用用時時間間戳戳完完成成并并發(fā)發(fā)

34、控控制制，需需要要對對每每個個事事務務的的操操作作進進行行有效性檢查，若檢查未能通過有效性檢查，若檢查未能通過,則該事務立即中止并重新啟動則該事務立即中止并重新啟動 基本的時間規(guī)則基本的時間規(guī)則:事事務務對對數(shù)數(shù)據(jù)據(jù)項項的的寫寫請請求求，僅僅當當該該數(shù)數(shù)據(jù)據(jù)項項最最近近由由前前一一個個事事務務(有沖突有沖突)讀和寫，才能有效。讀和寫，才能有效。事事務務對對數(shù)數(shù)據(jù)據(jù)項項的的讀讀請請求求，僅僅當當該該數(shù)數(shù)據(jù)據(jù)項項剛剛剛剛由由前前一一個個事事務務(有沖突有沖突)寫，才能有效。寫，才能有效。該該規(guī)規(guī)則則允允許許并并發(fā)發(fā)事事務務共共享享臨臨時時數(shù)數(shù)據(jù)據(jù)項項，從從而而確確保保每每個個數(shù)數(shù)據(jù)據(jù)項的臨時值按時

35、間戳順序提交項的臨時值按時間戳順序提交.南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務5 54 4 恢復恢復 事事務務的的原原子子性性要要求求事事務務要要么么提提供供完完整整的的運運行行結結果果，要要么么么么作作用用都都沒沒有有，即即持持久久性性和和失失效效原原子子性性。這這兩兩個個需需要要并并不不是是獨獨立立的的，可可以以由由服服務務器器上上的的獨獨立立機機制制來來管管理理，我我們們稱稱這這個個機機制制叫叫做做恢恢復復管管理器。理器?；謴凸芾砥鞯闹饕蝿帐牵换謴凸芾砥鞯闹饕蝿帐?；將提交事務的數(shù)據(jù)保存到永久性存儲介質(zhì)將提交事務的數(shù)據(jù)保存到永久性存儲介質(zhì)(恢

36、復文件恢復文件)上；上；故障重啟后，恢復服務器的數(shù)據(jù)；故障重啟后，恢復服務器的數(shù)據(jù)；組織恢復文件，改進恢復性能；組織恢復文件，改進恢復性能；回收恢復文件涉及到的空間。回收恢復文件涉及到的空間。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務5 55 5 事務服務中的文件版本事務服務中的文件版本 5.5.15.5.1文件版本的實現(xiàn)文件版本的實現(xiàn) 通通過過在在每每個個文文件件的的索索引引表表中中擴擴充充一一項項,即即版版本本號號,通通過過對對影影子子頁頁的的操操作作,到到事事務務提提交交時時,若若無無版版本本沖沖突突,則則合合并并臨臨時時版版本本與當前版本得到最新

37、版本與當前版本得到最新版本.若有沖突則放棄臨時版本若有沖突則放棄臨時版本.5.5.2 5.5.2意向表的實現(xiàn)意向表的實現(xiàn) 也可通過對影子頁的操作實現(xiàn)意向表也可通過對影子頁的操作實現(xiàn)意向表,意意向向表表記記錄錄:操操作作類類型型、事事務務標標識識符符、文文件件標標識識符符、頁頁號號、影子頁面的指針影子頁面的指針南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務文件版本方法文件版本方法解決兩類問題解決兩類問題:版本沖突和串行沖突版本沖突和串行沖突 版本沖突版本沖突:并發(fā)事務訪問同一個文件的不同數(shù)據(jù)段并發(fā)事務訪問同一個文件的不同數(shù)據(jù)段,從而產(chǎn)從而產(chǎn)生不同的版本生不同的

38、版本,但無一版本包含所有的修改但無一版本包含所有的修改.串行沖突串行沖突:并發(fā)事務訪問同一數(shù)據(jù)段并發(fā)事務訪問同一數(shù)據(jù)段,從而有多個寫操作從而有多個寫操作,導致數(shù)據(jù)項決定于最后的版本導致數(shù)據(jù)項決定于最后的版本.版本沖突解決如圖版本沖突解決如圖:南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務老版本老版本老版本老版本當前版本當前版本合并最新版本合并最新版本事事務務T的的臨臨時時版版本本事事務務U的的臨臨時時版版本本版本的合并版本的合并南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務老版本老版本老版本老版本上一個版本上一個版本當前版

39、本當前版本事事務務T的的臨臨時時版版本本事事務務U的的臨臨時時版版本本串行沖突的解決串行沖突的解決南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 意向表方法意向表方法 意意向向表表實實際際上上是是一一個個事事務務操操作作的的日日志志記記錄錄,是是兩兩階階段段提提交交的的機機制制.即即:第第一一階階段段,事事務務處處于于臨臨時時狀狀態(tài)態(tài),第第二二階階段段,事事務務進進入入提交階段提交階段.如圖如圖 DATADATA為為服服務務器器為為待待修修改改的的數(shù)數(shù)據(jù)據(jù)的的臨臨時時拷拷貝貝.意意向向操操作作只只是是記記錄錄到到意意向向表表并并不不是是真真的的對對文文件件操

40、操作作,一一個個意意向向只只有有給給出出足足夠夠的信息的信息,才能到第二階段執(zhí)行才能到第二階段執(zhí)行.本事務的視圖本事務的視圖DATA1DATA1DATA2DATA2其它事務的視圖其它事務的視圖南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務第六章第六章 分布事務與文件備份分布事務與文件備份南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務6 61 1 合作服務器合作服務器 合合作作服服務務器器是是由由多多個個物物理理服服務務器器合合作作完完成成一一個個邏邏輯輯服服務務器器的的功功能能,各各個個服服務務器器由由網(wǎng)網(wǎng)絡絡互互連連,每

41、每個個服服務務器器可可具具備備不不同同性性能能,可可位位于于不不同同地地點點,并并持持有有整整個個合合作作服服務務器器中中所所有有文文件的一部分件的一部分南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務6 62 2 分布事務分布事務 分分布布事事務務是是指指一一個個事事務務將將涉涉及及到到多多個個服服務務器器的的操操作作,即即該該事事務務是是由由合合作作服服務務器器完完成成的的,構構造造分分布布事事務務的的方方法法有有簡簡單單分布事務和嵌套分布事務兩種分布事務和嵌套分布事務兩種 簡簡單單分分布布事事務務:客客戶戶機機可可以以多多次次訪訪問問不不同同的的服服務務

42、器器,服服務務器僅響應客戶機的請求器僅響應客戶機的請求,不引發(fā)其它服務器的操作不引發(fā)其它服務器的操作 嵌嵌套套分分布布事事務務:一一個個服服務務器器上上的的操操作作可可能能引引發(fā)發(fā)其其它它服服務務器操作器操作南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務客戶機服務器1服務器2服務器3 在在分分布布事事務務中中,多多個個服服務務器器需需要要相相互互通通信信和和合合作作,各各自自完完成成部部分分工工作作,最最終終是是事事務務提提交交完完成成.在在分分布布事事務務處處理理中中,第第一一個個響響應應客客戶戶機機請請求求的的服服務務器器為為該該事事務務的的協(xié)協(xié)調(diào)調(diào)服服

43、務務器器,負負責責中中止止、提交該事務，其后加入的服務器為工作服務器。提交該事務，其后加入的服務器為工作服務器。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務TS1T22T21T12T11T2T1TS3S2S2S6S5S4S1S3(a)分布式平面事務處理(b)分布式嵌套事務處理S7S0事務處理分類其中方框代表事務處理，圓形代表執(zhí)行操作的服務器南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務分布式事務處理n分布式事務處理的關鍵在于服務及數(shù)據(jù)的分布，即一個事務處理所需的服務與數(shù)據(jù)可能分散在不同的服務器上，因此，事務處理過程就必須

44、在多臺服務器上執(zhí)行。n分布式事務處理的調(diào)度與同步-多臺服務器聯(lián)合執(zhí)行一個事務處理時需要彼此協(xié)調(diào)，才能做到整個事務處理的成功提交-常用的方法是由一個協(xié)調(diào)者(coordinator)通過服務器之間的通信來實現(xiàn)最終提交南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務分布式事務處理例子開始事務處理(T)；K：取款(A，100)；M：存款(B，100)；N：取款(D，200)；M：存款(C，200)；結束事務處理(T)某客戶要在K、M、N三個銀行分行的A、B、C、D四個賬號上執(zhí)行轉(zhuǎn)帳業(yè)務，即從K分行的A賬號取出100元，存入M分行的B賬號去，然后從N分行的D賬號取出20

45、0元并存入到M分行的C賬號。假定這三個分行的數(shù)據(jù)庫分別位于三臺服務器上，其中S1管理K分行的A賬號，S2管理M分行的B、C兩個賬號，S3管理N分行的D賬號 南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務分布式銀行事務處理TS1S3S2(1.1)開始事務處理(T)；(1.2)K：取款(A，100)；(1.3)結束事務處理(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)者協(xié)調(diào)者參與者參與者參與者參與者由于每個服務

46、器可能同時執(zhí)行不同的分布式事務處理，因此在整個系統(tǒng)中事務處理標號必須是唯一的。首先啟動分布式事務處理的那臺服務器是整個事務處理的協(xié)調(diào)者服務器 南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務6 63 3 分布事務的提交協(xié)議分布事務的提交協(xié)議 最簡單的方法最簡單的方法:1 1一階段原子提交協(xié)議一階段原子提交協(xié)議:即即由由協(xié)協(xié)調(diào)調(diào)服服務務器器不不斷斷查查詢詢所所有有工工作作服服務務器器,直直到到所所有有工工作服務器都回答提交成功作服務器都回答提交成功,完成整個事務提交完成整個事務提交 2 2兩兩階階段段提提交交協(xié)協(xié)議議(2PC(2PC協(xié)協(xié)議議)，可可以以保保證證分

47、分布布事事務務的的原原子子性性，在在此此協(xié)協(xié)議議中中，任任何何服服務務器器都都可可以以隨隨時時中中止止自自己己的的子子事事務而不影響客戶機事務的正常提交或中止。務而不影響客戶機事務的正常提交或中止。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 協(xié)調(diào)服務器分為兩階段工作協(xié)調(diào)服務器分為兩階段工作(2PC)(2PC)：第一階段第一階段 投票階段投票階段 A A協(xié)調(diào)服務器向每個工作服務期發(fā)出提交請求協(xié)調(diào)服務器向每個工作服務期發(fā)出提交請求 B B工作服務器收到請求后工作服務器收到請求后,回答回答YESYES或或NO,NO,如回答有如回答有NO,NO,則終止則終止 第

48、二階段第二階段 完成階段完成階段 C C協(xié)協(xié)調(diào)調(diào)服服務務器器查查看看搜搜集集的的票票數(shù)數(shù),若若無無反反對對票票,協(xié)協(xié)調(diào)調(diào)服服務務器器則則提提交交該該事事務務并并通通知知所所有有工工作作服服務務器器,否否則則,若若有有反反對對票票協(xié)協(xié)調(diào)調(diào)服服務務器則終止事務器則終止事務,并向所有回答并向所有回答YESYES的工作服務器發(fā)出終止請求的工作服務器發(fā)出終止請求南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 3 3 嵌套事務的兩階段提交協(xié)議嵌套事務的兩階段提交協(xié)議 嵌嵌套套事事務務的的兩兩階階段段提提交交協(xié)協(xié)議議的的執(zhí)執(zhí)行行過過程程的的第第一一階階段段與與非非 嵌套事

49、務不同，當工作服務器接到提交：嵌套事務不同，當工作服務器接到提交：1)1)如果工作服務器具有暫時提交且是頂層事務的子事務如果工作服務器具有暫時提交且是頂層事務的子事務 A.A.檢查它有沒有前輩事務處于中止事務表中，準備提交檢查它有沒有前輩事務處于中止事務表中，準備提交 B B 中止具有中止前輩事務的事務中止具有中止前輩事務的事務 C C 向協(xié)調(diào)服務器投票向協(xié)調(diào)服務器投票YESYES南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 2)2)如如果果工工作作服服務務器器沒沒有有處處于于暫暫時時提提交交狀狀態(tài)態(tài)的的、且且是是頂頂層層事務的子事務，它肯定已經(jīng)失敗，應向

50、協(xié)調(diào)服務器投票事務的子事務，它肯定已經(jīng)失敗，應向協(xié)調(diào)服務器投票NONO 注意注意:A.A.子事務的標識符可以通過擴充其父事務的標識符子事務的標識符可以通過擴充其父事務的標識符;B.B.子事務的提交決定于其父事務的提交子事務的提交決定于其父事務的提交,但父事務的提但父事務的提 交并不決定于其子事務的提交交并不決定于其子事務的提交 南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務6 64 4 分布事務中的并發(fā)控制分布事務中的并發(fā)控制 當多個事務處理訪問同一個數(shù)據(jù)時，順序等價性要求必須把每一個事當多個事務處理訪問同一個數(shù)據(jù)時，順序等價性要求必須把每一個事務處理對該數(shù)

51、據(jù)的完整務處理對該數(shù)據(jù)的完整(讀讀/寫寫)訪問一一排序，嚴格禁止任何沖突訪問一一排序，嚴格禁止任何沖突開始事務處理(T)：K：取款(A，40)；K：存入(B，40)；結束事務處理(T)；開始事務處理(U)：K：取款(C，30)K：存款(B，30)結束事務處理(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元南京理工大學計算機學

52、院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 1.1.分布事務中的鎖分布事務中的鎖 每每個個服服務務器器都都要要提提供供鎖鎖管管理理機機制制，本本地地的的鎖鎖管管理理機機制制可可以決定是否接受事務的請求操作。以決定是否接受事務的請求操作。利用互斥鎖進行事務處理并發(fā)控制南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務開始事務處理(T)：K：取款(A，40)；K：存款(B，40)；結束事務處理(T)；分解操作分解操作互斥互斥鎖分解操作分解操作互斥互斥鎖開始事務處理(T)開始事務處理(U)A平衡 A讀出()鎖定AC平衡 C讀出()鎖定CA寫入(A平

53、衡 40)C寫入(C平衡 30)B平衡 B讀出()鎖定BB平衡 B讀出()等待B的鎖B寫入(B平衡+40)結束事務處理(T)釋放A，B鎖定BB寫入(B平衡+30)結束事務處理(U)釋放B，C開始事務處理(U)：K：取款(C，30)K：存款(B，30)結束事務處理(U)；南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務分布式死鎖分布式死鎖n在各種涉及互斥的算法中，只要算法采用互斥鎖，就有在各種涉及互斥的算法中，只要算法采用互斥鎖，就有可能發(fā)生可能發(fā)生“死鎖死鎖”現(xiàn)象?，F(xiàn)象。n死鎖的典型特征是一組事務處理形成了一條循環(huán)等待鏈n死鎖處理：-置之不理（鴕鳥算法（鴕鳥算

54、法）由程序員對其負責-預防（靜態(tài)的使死鎖在結構上不可能）（靜態(tài)的使死鎖在結構上不可能）不存在運行系統(tǒng)支持-避免（合理的分配資源）（合理的分配資源）運行系統(tǒng)支持-檢測恢復（允許死鎖發(fā)生，檢測到后恢復）（允許死鎖發(fā)生，檢測到后恢復）不同的算法南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務TUVWWUTV(a)簡單循環(huán)鏈簡單循環(huán)鏈(b)復雜循環(huán)鏈復雜循環(huán)鏈n互斥n持有并等待(a)TUVWTn不容搶占(b)VWTVn循環(huán)鏈VWV死鎖-循環(huán)等待鏈南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務分布式事務處理的死鎖例子事務處理U事務處理

55、V事務處理W存款(D，100)鎖定D S3存款(B，300)鎖定B S2存款(A，200)鎖定A S1存款(C，500)鎖定C S3取款(B，200)等待B S2取款(C，100)等待C S3取款(A，300)等待A S1死鎖南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務死鎖檢測死鎖檢測n死鎖是一種穩(wěn)定的狀態(tài)n盡管無法從局部狀態(tài)檢測分布式事務處理的死鎖，但死鎖依舊是環(huán)形等待鏈。n死鎖檢測算法：-中央式周期性地收集等待狀態(tài)-分布式推出等待狀態(tài)-提示式構造檢測體系南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 2.2.分布事務

56、中的時間戳分布事務中的時間戳 利用時間戳進行讀寫協(xié)作利用時間戳進行讀寫協(xié)作 3.3.分布事務中的樂觀并發(fā)控制分布事務中的樂觀并發(fā)控制 分分布布事事務務通通過過一一組組獨獨立立的的服服務務器器進進行行確確定定，每每個個服服務務器器都都要要確確認認事事務務訪訪問問的的是是自自己己的的數(shù)數(shù)據(jù)據(jù)項項，所所有有確確認認均均通通過過兩兩階階段進行。段進行。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務n讀階段讀階段在讀階段，該事務處理所訪問的數(shù)據(jù)都有一套暫時版本，這套版本不對外，只由擁有者使用。采用暫時版本可以使事務處理流產(chǎn)而不會影響到長存數(shù)據(jù)。當執(zhí)行一個讀操作時，如果

57、數(shù)據(jù)的暫時版本已經(jīng)存在，則讀操作立即訪問之，否則，就必須訪問那個數(shù)據(jù)最近提交的值。寫操作把每一數(shù)據(jù)的新值作為暫時值記錄在案。顯然，如果若干個并發(fā)事務處理共享同一個數(shù)據(jù)，則這個數(shù)據(jù)可能有不同的暫時值。除了上述規(guī)則外，對每一個訪問的數(shù)據(jù)，事務處理還要維護兩個數(shù)值集合：讀集合包括該事務處理讀出的數(shù)據(jù)，寫集合囊括該事務處理寫入的數(shù)據(jù)。n驗證階段驗證階段當事務處理試圖提交時，就進入驗證階段，其目的是檢測是否它所訪問的數(shù)據(jù)與其它事務處理的操作有沖突。如果驗證無沖突，該事務處理可以提交；否則我們就必須消解沖突。消除沖突的方法很簡單：或者命令該事務處理流產(chǎn)，或者從卷入沖突的事務處理中選擇一個令其流產(chǎn)。n寫階段

58、寫階段如果該事務處理已經(jīng)通過驗證，暫時版本中所記錄的數(shù)據(jù)更新就成為永久性的。如果該事務處理是只讀型事務處理，則它馬上提交；否則就要等到暫存數(shù)據(jù)全部寫入長存存儲器后，執(zhí)行提交操作。樂觀并發(fā)控制算法樂觀并發(fā)控制算法南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務6 65 5 分布事務中的恢復分布事務中的恢復 分布事務的恢復工作分布事務的恢復工作 服務器服務器 狀態(tài)狀態(tài) 恢復管理器的工作恢復管理器的工作 協(xié)調(diào)服務器協(xié)調(diào)服務器 準備提交準備提交 表示服務器故障時還未做出仟何決定將向所有工作表示服務器故障時還未做出仟何決定將向所有工作 服務器發(fā)出服務器發(fā)出AbortTr

59、ansactionAbortTransaction，將中止狀態(tài)加入到恢，將中止狀態(tài)加入到恢 復文件中若狀態(tài)是中止，工作相同。復文件中若狀態(tài)是中止，工作相同。如果沒有工作服務器，將以超時判斷，中止相應事務如果沒有工作服務器，將以超時判斷，中止相應事務協(xié)調(diào)服務器協(xié)調(diào)服務器 提交提交 表示服務器故障時已做出提交決定若是還沒有做完表示服務器故障時已做出提交決定若是還沒有做完 要發(fā)送要發(fā)送DoCommitDoCommit，給各工作服務器，從這一步開始恢，給各工作服務器，從這一步開始恢 復兩階段提交協(xié)議的執(zhí)行。復兩階段提交協(xié)議的執(zhí)行。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WE

60、B服務服務工作服務器工作服務器 提交提交 表示已經(jīng)提交如果還未向上作服務器發(fā)送表示已經(jīng)提交如果還未向上作服務器發(fā)送HaveCommitedHaveCommited 消息，則發(fā)送之；然后，執(zhí)行整個事務中屬于自身的那一消息，則發(fā)送之；然后，執(zhí)行整個事務中屬于自身的那一 部分操作部分操作(若文件操作是可重復的，這樣做就不會引起不若文件操作是可重復的，這樣做就不會引起不 一致性一致性)。工作服務器工作服務器 不確定不確定 表示工作服務器在知道事務輸出之前故障，必須等到協(xié)調(diào)表示工作服務器在知道事務輸出之前故障，必須等到協(xié)調(diào) 服務器作山?jīng)Q定，可以有服務器作山?jīng)Q定，可以有GetDecisonGetDecis

61、on獲取。收到應答后，獲取。收到應答后，根據(jù)情況提交或中止。根據(jù)情況提交或中止。工作服務器工作服務器 準備提交準備提交 表示工作服務器還沒有投票，可以中止事務表示工作服務器還沒有投票，可以中止事務 協(xié)調(diào)服務器協(xié)調(diào)服務器 完成完成 不需要任何工作不需要任何工作 南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務6 66 6 備份備份 備備份份是是與與分分布布事事務務及及合合作作服服務務器器密密切切相相關關的的問問題題。一一個個備備份份對對象象(如如文文件件或或數(shù)數(shù)據(jù)據(jù)項項)由由位位于于多多個個服服務務器器中中的的許許多多副副本本組組成成，我我們們稱稱組組成成一一個

62、個備備份份對對象象的的副副本本集集合合中中的的任任意意副副本本為為該該備份對象的一個代理。備份對象的一個代理。備份對象有如下特點：備份對象有如下特點：(1)(1)減減少少分分布布式式系系統(tǒng)統(tǒng)中中的的通通信信量量，并并通通過過為為用用戶戶提提供供本本地地副本而加快響應時間；副本而加快響應時間；(2)(2)可可以以從從多多臺臺服服務務器器上上訪訪問問同同一一對對象象，從從而而提提高高系系統(tǒng)統(tǒng)有有效性，降低服務器故障的影響及通信失敗的可能性；效性，降低服務器故障的影響及通信失敗的可能性；(3)(3)可可以以在在不不同同服服務務器器上上并并行行執(zhí)執(zhí)行行多多個個用用戶戶對對同同一一對對象象的的請求，從而

63、提高系統(tǒng)吞吐率。請求，從而提高系統(tǒng)吞吐率。南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務按按照照客客戶戶的的觀觀點點，備備份份事事務務服服務務應應當當與與非非備備份份事事務務服服務務一一樣樣具具有有單單副副本本可可串串行行性性，即即通通過過并并發(fā)發(fā)控控制制，使使多多個個事事務務表表現(xiàn)現(xiàn)為在一定順序下的串行執(zhí)行。為在一定順序下的串行執(zhí)行。6.6.1 6.6.1 基本模型基本模型 最最簡簡單單的的策策略略就就是是讀讀一一寫寫全全,即即讀讀時時只只讀讀一一個個副副本本，寫寫時時要要寫寫所所有有副副本本。這這樣樣可可以以隨隨時時保保證證各各副副本本的的一一致致性性。

64、但但是是由由于于多多個個客客戶戶可可能能同同時時寫寫某某一一副副本本而而產(chǎn)產(chǎn)生生寫寫沖沖突突，所所以以必必須提供并發(fā)控制機制來保證分布事務的基本特性須提供并發(fā)控制機制來保證分布事務的基本特性.南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 6.6.2 6.6.2 主從模型主從模型 備備份份對對象象的的服服務務需需求求有有一一個個基基本本服服務務器器及及多多個個二二級級服服務務器器，基基本本服服務務器器擁擁有有一一個個基基本本對對象象副副本本并并響響應應所所有有修修改改請請求求，其其它它的的副副本本只只響響應應用用戶戶的的讀讀請請求求，不不響響應應用用戶戶的的

65、寫寫請請求求。只只接接收收來來自基本服務器的修改消息來修改副本或直接拷貝基本對象副本。自基本服務器的修改消息來修改副本或直接拷貝基本對象副本。客戶客戶服務器服務器服務器主副本后備副本后備副本寫讀讀寫更新傳播更新傳播南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 6.6.3 6.6.3 可用副本模型可用副本模型 主主從從模模型型的的主主要要不不足足在在于于：備備份份文文件件在在基基本本服服務務器器失失效效時時不不能能修修改改，并并且且僅僅適適用用于于修修改改很很少少的的對對象象。而而讀讀一一寫寫全全策策略略又又是是不不現(xiàn)現(xiàn)實實的的，因因為為當當有有些些副副本本

66、服服務務器器因因故故障障或或通通信信問題不能工作時，是絕對達不到問題不能工作時，是絕對達不到“寫全寫全”要求的要求的其其基基本本思思想想是是：即即使使有有部部分分副副本本服服務務器器故故障障時時系系統(tǒng)統(tǒng)仍仍可可工工作作，其其基基本本策策略略是是，客客戶戶的的讀讀請請求求可可以以在在任任何何可可用用副副本本上上執(zhí)執(zhí)行行，但但客客戶戶的的寫寫請請求求必必須須在在可可用用副副本本同同時時執(zhí)執(zhí)行行?？煽捎糜酶备北颈灸Ｐ鸵蟾北痉掌髦g的通信無誤模型要求副本服務器之間的通信無誤.南京理工大學計算機學院南京理工大學計算機學院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務服務 6.6.4 6.6.4 具有分布控制的系統(tǒng)具有分布控制的系統(tǒng) 我我們們要要使使用用分分布布式式控控制制機機制制，來來完完成成副副本本管管理理，目目的的是是即即使使一一些些副副本本失失效效，修修改改依依然然能能進進行行下下去去。在在這這種種方方法法中中，任任何何一一個個副副本本服服務務器器都都能能接接收收讀讀寫寫請請求求，并并讓讓客客戶戶得得到到有有效效一致的數(shù)據(jù)一致的數(shù)據(jù) 一一.文件組文件組:備份文件的副本集合備份文件的副本集合 為為支