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

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

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

3、已打打開開文文件件的的寫寫操操作作可可立立即即為為其其它它打打開開此此文文件件的的客客戶戶所所見見?？涂蛻魬艨煽晒补蚕硐砦奈募?dāng)當(dāng)前前位位置置的的指指針針。這這樣樣，一一個(gè)個(gè)客客戶戶將將指指針針向向前前推進(jìn)時(shí)將影響所有共享客戶的視圖。推進(jìn)時(shí)將影響所有共享客戶的視圖。此種語義的特點(diǎn)是易于理解和實(shí)現(xiàn)。此種語義的特點(diǎn)是易于理解和實(shí)現(xiàn)。二二.會(huì)話語義會(huì)話語義 對對于于打打開開文文件件的的寫寫操操作作可可以以立立即即為為本本地地客客戶戶所所見見，遠(yuǎn)遠(yuǎn)程程的的客客戶戶也也同同時(shí)時(shí)打打開開該該文文件件，但但卻卻不不可可見見。一一旦旦文文件件關(guān)關(guān)閉閉，對對此此文文件件所所作作的的修修改改僅僅為為后后面面進(jìn)進(jìn)

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

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

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

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

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

9、，也也叫叫串行等價(jià)性。串行等價(jià)性。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 三個(gè)事務(wù)三個(gè)事務(wù)A A、B B、C C被三個(gè)獨(dú)立的進(jìn)程同時(shí)執(zhí)行被三個(gè)獨(dú)立的進(jìn)程同時(shí)執(zhí)行,若順序執(zhí)行其結(jié)果為若順序執(zhí)行其結(jié)果為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 時(shí)間時(shí)間調(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;不合法南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 持持久久性性(Durable)(Durable)：如如果果事事務(wù)務(wù)處處理理成

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

12、服務(wù)銀行服務(wù)的例子開始事開始事務(wù)處理理(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)；結(jié)束事束事務(wù)處理理(T)(T)我們將用T、U、V代表事務(wù)處理標(biāo)號(hào)，用K、M、N代表不同的銀行分行，用A、B、C代表客戶的分行賬號(hào)，一個(gè)客戶發(fā)出的一系列服務(wù)過程調(diào)用就可以合并為一次事務(wù)處理。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)5 53 3 并發(fā)控制并發(fā)控制 并并發(fā)發(fā)控控制制的的主主要要目目標(biāo)標(biāo)是是滿滿足足事事務(wù)務(wù)處處理

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

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

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

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

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

18、項(xiàng)項(xiàng)，只只允允許許一一個(gè)個(gè)事事務(wù)務(wù)寫寫一一個(gè)個(gè)數(shù)數(shù)據(jù)據(jù)項(xiàng)項(xiàng)。也也稱稱為為“多多讀讀單單寫寫”方方法法。在在這這種種方方法法中中，對對于于讀讀操操作作，還還不不能能放放棄棄上上鎖鎖，因因?yàn)闉椴徊簧仙湘i鎖，可可能能會(huì)會(huì)有有其其它它事事務(wù)務(wù)修修改改它它，造造成成不不一一致致。為為此此，要要采采用用兩兩種種不不同同的的鎖鎖，即即讀讀鎖鎖和和寫寫鎖鎖 對對于于訪訪問問的的所所有有數(shù)數(shù)據(jù)據(jù)項(xiàng)項(xiàng)均均可可上上讀讀鎖鎖，只只對對寫寫操操作作訪訪問問的的數(shù)數(shù)據(jù)據(jù)項(xiàng)項(xiàng)上上寫寫鎖鎖。上上寫寫鎖鎖的的數(shù)數(shù)據(jù)據(jù)項(xiàng)項(xiàng)不不能能被被其其它它事事務(wù)務(wù)所所訪訪問問，上上讀讀鎖鎖的的數(shù)數(shù)據(jù)據(jù)項(xiàng)只能為其它事務(wù)讀，但不能寫項(xiàng)只能為其它事

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

35、間戳順序提交項(xiàng)的臨時(shí)值按時(shí)間戳順序提交.南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)5 54 4 恢復(fù)恢復(fù) 事事務(wù)務(wù)的的原原子子性性要要求求事事務(wù)務(wù)要要么么提提供供完完整整的的運(yùn)運(yùn)行行結(jié)結(jié)果果，要要么么么么作作用用都都沒沒有有，即即持持久久性性和和失失效效原原子子性性。這這兩兩個(gè)個(gè)需需要要并并不不是是獨(dú)獨(dú)立立的的，可可以以由由服服務(wù)務(wù)器器上上的的獨(dú)獨(dú)立立機(jī)機(jī)制制來來管管理理，我我們們稱稱這這個(gè)個(gè)機(jī)機(jī)制制叫叫做做恢恢復(fù)復(fù)管管理器。理器。恢復(fù)管理器的主要任務(wù)是；恢復(fù)管理器的主要任務(wù)是；將提交事務(wù)的數(shù)據(jù)保存到永久性存儲(chǔ)介質(zhì)將提交事務(wù)的數(shù)據(jù)保存到永久性存儲(chǔ)介質(zhì)(恢

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

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

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

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

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

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

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

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

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

45、0元并存入到M分行的C賬號(hào)。假定這三個(gè)分行的數(shù)據(jù)庫分別位于三臺(tái)服務(wù)器上，其中S1管理K分行的A賬號(hào)，S2管理M分行的B、C兩個(gè)賬號(hào)，S3管理N分行的D賬號(hào) 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)分布式銀行事務(wù)處理TS1S3S2(1.1)開始事務(wù)處理(T)；(1.2)K：取款(A，100)；(1.3)結(jié)束事務(wù)處理(T)；(2.1)加入服務(wù)器(T，S1)；(2.2)M：存款(B，100)；(2.3)M：存款(C，200)；(3.1)加入服務(wù)器(T，S1)；(3.2)N：取款(D，200)；K分行M分行N分行協(xié)調(diào)者協(xié)調(diào)者參與者參與者參與者參與者由于每個(gè)服務(wù)

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

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

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

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

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

51、據(jù)的完整務(wù)處理對該數(shù)據(jù)的完整(讀讀/寫寫)訪問一一排序，嚴(yán)格禁止任何沖突訪問一一排序，嚴(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元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元南京理工大學(xué)計(jì)算機(jī)學(xué)

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

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

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

55、V事務(wù)處理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死鎖南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)死鎖檢測死鎖檢測n死鎖是一種穩(wěn)定的狀態(tài)n盡管無法從局部狀態(tài)檢測分布式事務(wù)處理的死鎖，但死鎖依舊是環(huán)形等待鏈。n死鎖檢測算法：-中央式周期性地收集等待狀態(tài)-分布式推出等待狀態(tài)-提示式構(gòu)造檢測體系南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 2.2.分布事務(wù)

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

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

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

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

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

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

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

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

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

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

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