分布式系統(tǒng)教學(xué)課件DOSCH6Syncv15

1、第6章 分布式同步控制 第1頁(yè)，共82頁(yè)。2主要內(nèi)容6.1 物理時(shí)鐘同步6.2 邏輯時(shí)鐘同步6.3 互斥控制6.4 選舉算法6.5 *分布式事務(wù)管理6.6 *分布式死鎖處理6.7 小結(jié)6.8 習(xí)題第2頁(yè)，共82頁(yè)。36.1物理時(shí)鐘同步分布式協(xié)同處理基于時(shí)間的同步分布式算法的特點(diǎn)相關(guān)信息散布在多個(gè)場(chǎng)地上應(yīng)避免因單點(diǎn)失敗造成整個(gè)系統(tǒng)的失敗不存在公共時(shí)鐘或精確的全局時(shí)間第3頁(yè)，共82頁(yè)。4時(shí)鐘同步問(wèn)題例：makefile誤差時(shí)間#腳本命令output.o ： cc C output.c第4頁(yè)，共82頁(yè)。5遙遠(yuǎn)的星系遙遠(yuǎn)的星系在n天后的日中天，地球旋轉(zhuǎn)不到360物理時(shí)鐘與現(xiàn)實(shí)時(shí)鐘日中天（transit

2、 of the sun）：太陽(yáng)升到一天的最高點(diǎn)太陽(yáng)日：連續(xù)的兩次日中天的時(shí)間太陽(yáng)年：地球圍繞太陽(yáng)旋轉(zhuǎn)360（一周）。太陽(yáng)秒：solar-day/24*3600=solar-day/86400平均太陽(yáng)秒：n solar-days/n*86400如，格林威治時(shí)間第0個(gè)日中天第n個(gè)日中天第5頁(yè)，共82頁(yè)。6現(xiàn)實(shí)時(shí)鐘TAI秒：國(guó)際原子時(shí)間銫133原子鐘：9,192,631,770次躍遷/1秒巴黎BIH統(tǒng)計(jì)50個(gè)實(shí)驗(yàn)室原子鐘后的平均值UTC秒：世界時(shí)間在TAI秒中加入閏秒（TAI秒長(zhǎng)度恒定，但比太陽(yáng)秒短）時(shí)間服務(wù)：美國(guó)WWV電臺(tái)(NIST)、GEOS衛(wèi)星1020UTC- 在TAI中引入閏秒，以與太陽(yáng)秒同

3、步第6頁(yè)，共82頁(yè)。7例：時(shí)間的應(yīng)用-GPS全球定位系統(tǒng)GPS衛(wèi)星使用4個(gè)原子時(shí)鐘周期地廣播定位消息即，接收器接收di = c(tnow ti)d =di+ci d = i 時(shí)鐘誤差(1)(2)(3)第7頁(yè)，共82頁(yè)。8例：GPS全球定位系統(tǒng)求解方程組（擴(kuò)展到3維，需4顆衛(wèi)星）可求出（xr,yr,zr）,以及r誤差因素衛(wèi)星的位置衛(wèi)星、接收器的時(shí)鐘精度；信號(hào)傳播速度第8頁(yè)，共82頁(yè)。9時(shí)鐘同步算法如何與現(xiàn)實(shí)時(shí)鐘同步如何使不同機(jī)器之間相互同步設(shè)進(jìn)程P的機(jī)器時(shí)鐘值Cp(t),t 為UTC時(shí)間最大偏移率（）精確時(shí)鐘： dC/dt =1快時(shí)鐘： dC/dt 1慢時(shí)鐘： dC/dt 1第9頁(yè)，共82頁(yè)。1

4、0時(shí)鐘同步算法時(shí)鐘校正設(shè)兩個(gè)時(shí)鐘都存在誤差率，允許兩者之間誤差；由于最大可能誤差2t ，則t /2需每隔/(2)校準(zhǔn)時(shí)間，進(jìn)行校正校準(zhǔn)原則：?jiǎn)握{(diào)遞增假設(shè)：每秒產(chǎn)生100次中斷，每次中斷將時(shí)間加10毫秒若調(diào)慢時(shí)鐘，中斷服務(wù)程序每次只加9毫秒；若加快時(shí)鐘，則加11毫秒。第10頁(yè)，共82頁(yè)。11網(wǎng)絡(luò)時(shí)間協(xié)議Christian算法時(shí)間服務(wù)器，可接受WWV的UTC時(shí)間每隔/(2)，客戶機(jī)向服務(wù)器詢問(wèn)時(shí)間服務(wù)器返回CUTC客戶機(jī)校正自己時(shí)間=CUTC+傳播時(shí)間傳播時(shí)間=(T1-T0-I)/2T0:請(qǐng)求時(shí)間，T1:到達(dá)時(shí)間I:中斷處理時(shí)間假定雙向路徑相同優(yōu)化處理設(shè)定傳播閾值,超出閾值，認(rèn)定無(wú)效第11頁(yè)，共8

5、2頁(yè)。12網(wǎng)絡(luò)時(shí)間協(xié)議時(shí)間服務(wù)請(qǐng)求過(guò)程參數(shù)假定雙向路徑相同T1:A請(qǐng)求時(shí)間， T2:B接收時(shí)間T3:B發(fā)送時(shí)間， T4:A接收時(shí)間傳輸延時(shí) = dTreqdTres時(shí)間偏差T1=T2 - dTreq + T4=T3+dTres+ 平均延時(shí)=(dTreq+dTres)/2 =T4-T3-dTres=T4 -T3 - =時(shí)間服務(wù)器客戶第12頁(yè)，共82頁(yè)。13Berkeley 算法 主動(dòng)式方法時(shí)間監(jiān)控器定期查詢其他機(jī)器時(shí)間計(jì)算出平均值通知其他機(jī)器調(diào)整時(shí)間第13頁(yè)，共82頁(yè)。14平均值算法 非集中式方法劃分固定時(shí)間間隔R;在每個(gè)間隔，所有機(jī)器廣播自己的時(shí)鐘時(shí)間啟動(dòng)本地計(jì)時(shí)器收集在S時(shí)間間隔中到達(dá)的其他

6、機(jī)器廣播的時(shí)間執(zhí)行平均時(shí)間計(jì)算算法，得到新的時(shí)間值第14頁(yè)，共82頁(yè)。15多重外部時(shí)間源法消除傳播延遲造成的誤差例：OSF DCE方法接受所有時(shí)間源的當(dāng)前UTC區(qū)間去掉與其他區(qū)間不相交的區(qū)間將相交部分的中點(diǎn)作為校準(zhǔn)時(shí)間時(shí)間第15頁(yè)，共82頁(yè)。16無(wú)線網(wǎng)絡(luò)中的時(shí)鐘同步參考廣播同步協(xié)議（RBS）普通的網(wǎng)絡(luò)延時(shí)關(guān)鍵路徑RBS的網(wǎng)絡(luò)延時(shí)關(guān)鍵路徑第16頁(yè)，共82頁(yè)。17無(wú)線網(wǎng)絡(luò)中的時(shí)鐘同步參考廣播同步協(xié)議（RBS）一個(gè)節(jié)點(diǎn)廣播一個(gè)消息m后，其他節(jié)點(diǎn)p記錄接收時(shí)間Tp,m第17頁(yè)，共82頁(yè)。18同步時(shí)鐘的應(yīng)用最多一次消息遞交每個(gè)消息攜帶一個(gè)連接ID和一個(gè)時(shí)間戳ts服務(wù)器的登記表T中，記錄每個(gè)連接C最近的時(shí)

7、間戳t對(duì)到達(dá)的消息m，如果ts(m)t, 則拒絕m登記表的維護(hù)例：服務(wù)器中設(shè)置全局變量G G = CurrentTime MaxLifetime MaxClockSkew所有G的時(shí)間戳從表T中清除對(duì)于具有新的ID的到達(dá)消息m,如果ts(m)G則拒絕m,否則，接受m按照T，定期地將G寫入磁盤。當(dāng)系統(tǒng)重啟后，G=G+T第18頁(yè)，共82頁(yè)。19同步時(shí)鐘的應(yīng)用基于時(shí)鐘的緩存一致性當(dāng)客戶讀取一個(gè)副本到緩存時(shí)，設(shè)置一個(gè)租期（lease）在租期過(guò)期之前，客戶可更新副本，重續(xù)租期如果已經(jīng)過(guò)期，緩存中的副本失效優(yōu)化策略： 改進(jìn)的一致性協(xié)議當(dāng)客戶修改文件時(shí)，只需將所有沒(méi)有到期的緩存副本設(shè)為無(wú)效如果某個(gè)客戶崩潰，則

8、等待，直到該客戶的租期過(guò)期第19頁(yè)，共82頁(yè)。206.2 邏輯時(shí)鐘同步計(jì)時(shí)器：石英晶體+計(jì)數(shù)器時(shí)鐘偏差（clock skew）物理時(shí)鐘：真實(shí)時(shí)間邏輯時(shí)鐘：相對(duì)時(shí)間“之前”關(guān)系: 事件a在b之前出現(xiàn)，則aba為發(fā)送消息m，b為接收m，則ab具有傳遞性：ab, bc,則ac并發(fā)事件（concurrent）兩個(gè)事件相互對(duì)立。既不ab，不 b a第20頁(yè)，共82頁(yè)。21Lamport算法C(a)表示事件a的時(shí)鐘值。性質(zhì)：if ab;則C(a)C(b)a,b C(a) C(b)C是遞增的校正算法ab，if C(b)C(a), 則C(b) = C(a) +1第21頁(yè)，共82頁(yè)。22Lamport算法時(shí)間慢

9、快慢快三個(gè)進(jìn)程，各有自己的局部時(shí)鐘，它們速率不同通過(guò)Lamport算法，校正時(shí)鐘第22頁(yè)，共82頁(yè)。23Lamport算法Pi在執(zhí)行一個(gè)事件之前，Pi執(zhí)行CiCi+1Pi在發(fā)送消息m給Pj時(shí)，時(shí)間戳ts(m) CiPj接受到消息m后，CjmaxCj，ts(m)第23頁(yè)，共82頁(yè)。24舉例：全序多播（1） 問(wèn)題：兩個(gè)進(jìn)程分別對(duì)同一個(gè)復(fù)制數(shù)據(jù)庫(kù)進(jìn)行更新時(shí)，造成不一致狀態(tài) 原因：全局次序不一致。u1u2; u2u1第24頁(yè)，共82頁(yè)。25舉例：全序多播（2）解決方案：全序多播發(fā)送進(jìn)程多播發(fā)送消息m時(shí)，給m帶上當(dāng)前時(shí)間戳ts當(dāng)接收進(jìn)程收到消息m后，存放其局部隊(duì)列q，并按時(shí)間戳排序接收進(jìn)程向所有進(jìn)程多播

10、發(fā)送應(yīng)答當(dāng)消息m被所有進(jìn)程應(yīng)答，且排在隊(duì)列q隊(duì)首后，方可處理（遞交給接收進(jìn)程，從隊(duì)列中刪除）定理：各個(gè)進(jìn)程的局部隊(duì)列的值最終都相同第25頁(yè)，共82頁(yè)。26舉例：全序多播（3）舉例q1q2u1u2(1)u1u2u1u2(2）u1u2a11u1u2a22(3)q1q2u1u2a11a22u1u2a11a22(4)u1u2a11a22a12u1u2a11a22a21(5)q1q2u1u2a11a22a12a21u1u2a11a22a12a21(6)a11, a22本地消息a12,a21遠(yuǎn)地消息第26頁(yè)，共82頁(yè)。27向量時(shí)鐘因果性(causality):如果事件a，b存在因果關(guān)系。a為因，b為果，則

11、C(a)C(b)Vector Clock如果VC(a)VC(b)，則a與b為因果關(guān)系進(jìn)程Pi上的向量時(shí)鐘VCi的基本性質(zhì)VCii=n, 在Pi中發(fā)生了n個(gè)事件VCij=k，Pi已知在Pj中發(fā)生了k個(gè)事件第27頁(yè)，共82頁(yè)。28向量時(shí)鐘(2)向量修改規(guī)則Pi在執(zhí)行一個(gè)事件之前，Pi執(zhí)行VCiiVCii+1當(dāng)進(jìn)程Pi發(fā)送消息m時(shí),ts(m)=VCi當(dāng)進(jìn)程Pj收到m后,置VCjk=maxVCjk,ts(m)kPi的消息m在進(jìn)程Pk正確遞交的條件:ts(m)i = VCki+1tsmjVCkj for all ij第28頁(yè)，共82頁(yè)。29有序的消息遞交例：A發(fā)一個(gè)帖子M1,B回一個(gè)帖子M2第29頁(yè)，共

12、82頁(yè)。30強(qiáng)制因果有序通信第30頁(yè)，共82頁(yè)。31強(qiáng)制因果有序通信012345433323675767888888222223111111555555進(jìn)程0的向量 進(jìn)程1-5的向量發(fā)送消息接收拒絕第31頁(yè)，共82頁(yè)。32全局狀態(tài)（1）*局部狀態(tài)：進(jìn)程正在處理的變量值、對(duì)象狀態(tài)等例：分布庫(kù)系統(tǒng)中的數(shù)據(jù)庫(kù)記錄全局狀態(tài)：由每個(gè)進(jìn)程的局部狀態(tài)和正在傳遞的消息組成一致性狀態(tài)：符合邏輯關(guān)系-時(shí)鐘次序例：P Q,如有Q的接收狀態(tài)，必有P的發(fā)送狀態(tài)m第32頁(yè)，共82頁(yè)。33全局狀態(tài)（2）*分布式快照（snapshot）反映分布式系統(tǒng)的一致性全局狀態(tài)割集：全局部狀態(tài)的圖形表示(a) 一致性割集 (b) 不一致

13、性割集第33頁(yè)，共82頁(yè)。34全局狀態(tài)（3）*分布式割集的實(shí)現(xiàn)通信通道結(jié)構(gòu)：?jiǎn)蜗虻狞c(diǎn)對(duì)點(diǎn)通信輸入通道：接收消息輸出通道：發(fā)出消息標(biāo)記(Marker)：指示收集狀態(tài)進(jìn)程第34頁(yè)，共82頁(yè)。35全局狀態(tài)（4）*算法：發(fā)起者進(jìn)程P向所有輸出通道發(fā)送marker消息進(jìn)程 Q第一次收到marker，記錄其局部狀態(tài)，并傳遞marker（圖1）進(jìn)程 Q記錄所有的到來(lái)消息（圖2）進(jìn)程Q 再次收到marker后，完成對(duì)該輸入通道的狀態(tài)記錄（圖3）進(jìn)程Q記錄完所有進(jìn)入通道的狀態(tài)后，向發(fā)起者返回局部狀態(tài)和通道狀態(tài)第35頁(yè)，共82頁(yè)。36全局狀態(tài)（5）*舉例：終止檢測(cè)檢查一個(gè)分布式計(jì)算是否結(jié)束前趨者：發(fā)送marker

14、的進(jìn)程后繼者：接收marker的進(jìn)程基本算法(遞歸算法)發(fā)起者進(jìn)程P向所有后繼者發(fā)送marker請(qǐng)求快照當(dāng)進(jìn)程Q完成快照后，向其前趨者返回DONE消息當(dāng)P收到所有后繼者返回DONE消息后，結(jié)束第36頁(yè)，共82頁(yè)。37全局狀態(tài)（6）修正算法：不允許有正在傳送中的消息，即所有通道必須為空。如果滿足以下條件，返回DONE消息給前趨者進(jìn)程Q的所有后繼者都返回DONE消息進(jìn)程Q在記錄局部狀態(tài)和收到marker之間不再?gòu)娜魏屋斎胪ǖ朗盏较⒎駝t，返回CONTINUE消息給前趨者發(fā)起者進(jìn)程P接到CONTINUE消息后，繼續(xù)發(fā)起另一個(gè)snapshot。第37頁(yè)，共82頁(yè)。386.3 互斥算法基本概念當(dāng)一個(gè)進(jìn)程

15、使用某個(gè)共享資源，其他進(jìn)程不允許對(duì)這個(gè)資源操作臨界區(qū)：對(duì)共享資源進(jìn)行操作的程序段基本方法：信號(hào)量、管程問(wèn)題：死鎖饑餓第38頁(yè)，共82頁(yè)。39集中式算法協(xié)調(diào)者：確定那個(gè)進(jìn)程可進(jìn)入臨界區(qū)通信量：3個(gè)消息：請(qǐng)求-許可-釋放缺點(diǎn)：?jiǎn)吸c(diǎn)失敗CCC第39頁(yè)，共82頁(yè)。40分布式算法（Ricart-Agrawala算法）在一個(gè)進(jìn)程P打算進(jìn)入臨界區(qū)R之前，向所有其他進(jìn)程廣播消息 當(dāng)一個(gè)進(jìn)程P收到消息后，做如下決定：若P不在臨界區(qū)R中，也不想進(jìn)入R，它就向P發(fā)送OK；若P已經(jīng)在臨界區(qū)R中，則不回答，并將P放入請(qǐng)求隊(duì)列；若P也同時(shí)要進(jìn)入臨界區(qū)R，但是還沒(méi)有進(jìn)入時(shí)，則將發(fā)來(lái)的消息和它發(fā)送給其余進(jìn)程的時(shí)間戳對(duì)比。如果

16、P時(shí)間戳小，則向P發(fā)送OK;否則，不回答，并將P放入請(qǐng)求隊(duì)列；當(dāng)P收到所有的OK消息后，進(jìn)入R。否則，等待。當(dāng)P退出R時(shí)，如果存在等待隊(duì)列，則取出一個(gè)請(qǐng)求者，向其發(fā)送OK消息。第40頁(yè)，共82頁(yè)。41分布式算法舉例舉例： 共有0，1，2三個(gè)進(jìn)程。進(jìn)程0，2申請(qǐng)進(jìn)入臨界區(qū)020022第41頁(yè)，共82頁(yè)。42分布式算法評(píng)價(jià)缺點(diǎn)：n點(diǎn)失敗n點(diǎn)瓶頸2（n-1)個(gè)消息改進(jìn)方案：超時(shí)重發(fā)組通信（進(jìn)程少且不改變組成員時(shí)）簡(jiǎn)單多數(shù)同意（1/2）第42頁(yè)，共82頁(yè)。43令牌環(huán)算法構(gòu)造一個(gè)邏輯環(huán)，得到令牌才可進(jìn)入臨界區(qū)問(wèn)題：令牌丟失檢測(cè)第43頁(yè)，共82頁(yè)。44三種互斥算法的比較算法每次進(jìn)出需要的消息進(jìn)入前的延遲（

17、按消息次數(shù)）存在問(wèn)題集中式32協(xié)調(diào)者崩潰分布式2（n-1）2（n-1）任何一個(gè)進(jìn)程崩潰令牌環(huán)1到0到n-1丟失令牌，進(jìn)程崩潰第44頁(yè)，共82頁(yè)。456.4 選舉算法作用：在分布式進(jìn)程之間做出統(tǒng)一的的決定例如：確定協(xié)調(diào)者前提：每個(gè)進(jìn)程具有唯一的號(hào)碼，如IP地址每個(gè)進(jìn)程知道其它進(jìn)程的號(hào)碼選舉標(biāo)準(zhǔn)：確定具有最大號(hào)碼的進(jìn)程第45頁(yè)，共82頁(yè)。46霸道（Bully）算法將進(jìn)程進(jìn)行排序P向高的進(jìn)程發(fā)E消息如果沒(méi)有響應(yīng)，P選舉獲勝如果有進(jìn)程Q響應(yīng),則P結(jié)束，Q接管選舉并繼續(xù)下去。456564656第46頁(yè)，共82頁(yè)。47環(huán)算法所有進(jìn)程按邏輯或物理次序排序，形成一個(gè)環(huán)當(dāng)一個(gè)進(jìn)程P發(fā)現(xiàn)協(xié)調(diào)者C失效后，向后續(xù)進(jìn)程

18、發(fā)送E消息每個(gè)進(jìn)程繼續(xù)向后傳遞E消息，直到返回PP再將新確定的協(xié)調(diào)者C傳給所有進(jìn)程52第47頁(yè)，共82頁(yè)。48無(wú)線網(wǎng)絡(luò)系統(tǒng)的選舉算法例：選舉一個(gè)協(xié)調(diào)者，它具有最大的能力1、發(fā)起者，提出選舉第48頁(yè)，共82頁(yè)。49無(wú)線網(wǎng)絡(luò)系統(tǒng)的選舉算法2、向鄰居節(jié)點(diǎn)擴(kuò)展，形成一個(gè)生成樹（spanning tree）第49頁(yè)，共82頁(yè)。50無(wú)線網(wǎng)絡(luò)系統(tǒng)的選舉算法3、沿生成樹向父節(jié)點(diǎn)返回i，cmax，cmax為最大值4、發(fā)起者，向其余節(jié)點(diǎn)發(fā)布協(xié)調(diào)者第50頁(yè)，共82頁(yè)。51大型系統(tǒng)的選舉大型系統(tǒng)中需要選舉多個(gè)節(jié)點(diǎn)如p2p系統(tǒng)中的超級(jí)節(jié)點(diǎn)對(duì)如何選擇超級(jí)節(jié)點(diǎn)（superpeer）的要求:普通節(jié)點(diǎn)對(duì)超級(jí)節(jié)點(diǎn)的訪問(wèn)延遲要小超

19、級(jí)節(jié)點(diǎn)應(yīng)均勻地分布在覆蓋網(wǎng)絡(luò)中相對(duì)于覆蓋網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量，應(yīng)有一定數(shù)量的預(yù)先定義好的超級(jí)節(jié)點(diǎn)每個(gè)超級(jí)節(jié)點(diǎn)所服務(wù)的普通節(jié)點(diǎn)個(gè)數(shù)不能超過(guò)規(guī)定的數(shù)量例：一個(gè)小型chord系統(tǒng)m=8(長(zhǎng)度), k=3(預(yù)留)P AND 11100000作為超級(jí)節(jié)點(diǎn)的鍵值N個(gè)節(jié)點(diǎn)中平均有2k個(gè)超級(jí)節(jié)點(diǎn)第51頁(yè)，共82頁(yè)。52大型系統(tǒng)的選舉M維空間中的超級(jí)節(jié)點(diǎn)選舉首先，在N個(gè)隨機(jī)選擇的節(jié)點(diǎn)中，放置N個(gè)令牌每個(gè)節(jié)點(diǎn)不允許擁有一個(gè)以上的令牌每個(gè)令牌具有排斥力，推動(dòng)另一個(gè)令牌移動(dòng)通過(guò)互相排斥，最終達(dá)到在空間中的均勻分布例：使用排斥力在二維空間中移動(dòng)令牌第52頁(yè)，共82頁(yè)。536.5 分布式事務(wù)管理*事務(wù)原子性： 組成原子事務(wù)的

20、一組操作要么全部執(zhí)行，要么一個(gè)也不執(zhí)行，并且事務(wù)失敗后能返回到最初狀態(tài)例1： 老式磁帶系統(tǒng)（備份）例2：匯款（提款存款）第53頁(yè)，共82頁(yè)。54事務(wù)的性質(zhì) 原子性（Atomic）：對(duì)外部世界來(lái)說(shuō)，事務(wù)的發(fā)生是不可分割的；一致性（Consistent）：事務(wù)不會(huì)破壞系統(tǒng)的不變式；隔離性（Isolated）：并發(fā)的事務(wù)之間不會(huì)互相干擾；可串行性（Serializable）:多個(gè)事務(wù)并發(fā)執(zhí)行的結(jié)果，與它們順序地執(zhí)行效果相同。持久性（Durable）：一旦一個(gè)事務(wù)提交，它的更新結(jié)果不會(huì)因故障而丟失。第54頁(yè)，共82頁(yè)。55事務(wù)模型穩(wěn)定存儲(chǔ)器（Stable Storage）：通過(guò)一對(duì)雙工磁盤實(shí)現(xiàn)第55頁(yè)

21、，共82頁(yè)。56事務(wù)原語(yǔ)（1）BEGIN_TRA NSACTION：標(biāo)記一個(gè)事務(wù)的開始；（2）END_TRANSACTION：結(jié)束事務(wù)并設(shè)法提交；（3）ABORT_TRANSACTION：取消事務(wù)并恢復(fù)舊值；（4） READ：從一個(gè)文件（或其他類型的對(duì)象，如數(shù)據(jù)庫(kù)）讀取數(shù)據(jù)；（5） WRITE：將數(shù)據(jù)寫入一個(gè)文件（或其他類型的對(duì)象，如數(shù)據(jù)庫(kù)）第56頁(yè)，共82頁(yè)。57事務(wù)舉例BEGIN TRANSACTION reserve WPJFK reserve JFKNairobi reserve NairobiMalindi END TRANSACTION BEGIN TRANSACTION rese

22、rve WPJFK reserve JFKNairobi NairobiMalindi fullABORT TRASACTION 當(dāng)?shù)谌齻€(gè)航班的機(jī)票預(yù)定失敗后事務(wù)中止預(yù)定三個(gè)航班機(jī)票：中轉(zhuǎn)站是JFK、Nairobi第57頁(yè)，共82頁(yè)。58分布式事務(wù)嵌套式事務(wù)(nested)：由子事務(wù)樹組成分布式事務(wù)：由分布式數(shù)據(jù)操作組成第58頁(yè)，共82頁(yè)。59事務(wù)的實(shí)現(xiàn)（1） 私有工作空間與影子更新方法當(dāng)進(jìn)程啟動(dòng)事務(wù)T時(shí)，分配一個(gè)私有工作空間W，在提交或中止T前所有的讀寫操作都是在W中進(jìn)行03影子塊第59頁(yè)，共82頁(yè)。60事務(wù)的實(shí)現(xiàn)（1）日志方法：就地更新（in-place）日志紀(jì)錄事務(wù)標(biāo)識(shí)，文件標(biāo)識(shí)，塊號(hào)，

23、前像，后像例：第60頁(yè)，共82頁(yè)。61先寫日志協(xié)議（WAL）回滾（Rollback）:反做（undo）廢棄事務(wù)的更新結(jié)果只有當(dāng)日志成功地寫入穩(wěn)存之后，才可以修改文件。如果事務(wù)執(zhí)行成功并被提交，則它的提交記錄將被寫入日志。如果事務(wù)異常中止，則用日志來(lái)備份初始狀態(tài)。從日志的未尾開始，向回逐個(gè)讀取日志記錄，反做記錄中描述的修改，即回滾處理。在系統(tǒng)崩潰后,日志也可用來(lái)進(jìn)行的恢復(fù)。第61頁(yè)，共82頁(yè)。62兩階段提交協(xié)議（2PC）準(zhǔn)備階段：取得一致決定執(zhí)行階段：執(zhí)行命令（提交或廢棄）第62頁(yè)，共82頁(yè)。63并發(fā)控制(Concurrency Control)正確性標(biāo)準(zhǔn)：可串行性（serializable）B

24、EGIN_TRANSACTION x = 0; x = x + 1;END_TRANSACTION 事務(wù)1可能的調(diào)度策略BEGIN_TRANSACTION x = 0; x = x + 2;END_TRANSACTION事務(wù)2BEGIN_TRANSACTION x = 0; x = x + 3;END_TRANSACTION事務(wù)3調(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

25、= x + 1; x = 0; x = x + 2; x = x + 3;非法第63頁(yè)，共82頁(yè)。64并發(fā)控制事務(wù)管理系統(tǒng)的結(jié)構(gòu)第64頁(yè)，共82頁(yè)。65并發(fā)控制分布式事務(wù)管理系統(tǒng)的結(jié)構(gòu)第65頁(yè)，共82頁(yè)。66基于鎖的方法封鎖加鎖：獲得資源上的封鎖解鎖：釋放已擁有的鎖封鎖的類型和相容性讀鎖(R)寫鎖(W)鎖的粒度細(xì)粒度：如字段粗粒度：如文件RWRW第66頁(yè)，共82頁(yè)。67兩階段封鎖協(xié)議(2PL)兩階段封鎖協(xié)議(2PL)1. 加鎖階段2. 開鎖階段第67頁(yè)，共82頁(yè)。68兩階段封鎖協(xié)議(2PL)嚴(yán)格的2PL與2PC結(jié)合避免級(jí)聯(lián)廢棄（cascaded abort)死鎖：等待圖（WFG）超時(shí)檢測(cè)（ti

26、meout)第68頁(yè)，共82頁(yè)。69時(shí)間戳法(Timestamp)每個(gè)事務(wù)的操作帶有該事務(wù)的時(shí)間印ts(T)每個(gè)文件帶有對(duì)它操作的最后一個(gè)提交事務(wù)的讀時(shí)間戳tsr(x)、寫時(shí)間戳tsw(x)算法：如果當(dāng)前事務(wù)T的時(shí)間戳文件的時(shí)間戳，則執(zhí)行；否則 ，廢棄T;第69頁(yè)，共82頁(yè)。70時(shí)間戳法舉例設(shè)有三個(gè)事務(wù)T1, T2 , T3 , ts(T1)ts(T2)ts(T3)；T1, T3已調(diào)度執(zhí)行，T2請(qǐng)求調(diào)度寫操作讀操作第70頁(yè)，共82頁(yè)。71樂(lè)觀法(Optimistic CC)算法讀階段：將文件讀入私有工作區(qū)確認(rèn)階段：提交前，檢查是否有沖突有，則廢棄事務(wù)，重啟。無(wú)，則提交事務(wù)寫階段：如可以提交，則

27、將修改內(nèi)容從私有工作區(qū)，寫入文件。第71頁(yè)，共82頁(yè)。72三種方法比較算法并發(fā)度死鎖性能2PL低有中時(shí)間印法較高無(wú)較高樂(lè)觀法高無(wú)高（廢棄度低時(shí)）第72頁(yè)，共82頁(yè)。736.6 分布式系統(tǒng)的死鎖處理*死鎖解決策略鴕鳥法：留給用戶考慮檢測(cè)法：發(fā)現(xiàn)死鎖，進(jìn)行處理預(yù)防法：在設(shè)計(jì)上使死鎖不可能發(fā)生避免法：在運(yùn)行中，防止出現(xiàn)死鎖銀行家算法Dijkstra,1965P, free第73頁(yè)，共82頁(yè)。74集中式檢測(cè)方法進(jìn)程-資源等待圖節(jié)點(diǎn)：進(jìn)程P、資源R有向邊:(1)PR請(qǐng)求關(guān)系; (2) R P擁有關(guān)系;死鎖檢測(cè)協(xié)調(diào)者負(fù)責(zé)檢測(cè)死鎖資源圖的維護(hù)策略：當(dāng)資源圖中，有一條邊加入/刪除時(shí)，通知協(xié)調(diào)者每個(gè)進(jìn)程周期性地向協(xié)調(diào)者發(fā)送圖的更新消息協(xié)調(diào)者在需要時(shí)，向參入者請(qǐng)求第74頁(yè)，共82頁(yè)。75假死鎖問(wèn)題：B釋放R,請(qǐng)求T。若請(qǐng)求T消息先到達(dá)協(xié)調(diào)者解決方案一：協(xié)調(diào)者確認(rèn)