分布式系統(tǒng)協(xié)調(diào)和協(xié)定

分布式系統(tǒng)協(xié)調(diào)和協(xié)定第1頁，課件共47頁，創(chuàng)作于2023年2月第七章協(xié)調(diào)和協(xié)定簡介分布式互斥選舉組播通信共識問題2第2頁，課件共47頁，創(chuàng)作于2023年2月7.1簡介分布式系統(tǒng)的一個基本目的：供一組進(jìn)程來協(xié)調(diào)他們的動作或?qū)σ粋€或多個值達(dá)成協(xié)議避免固定的主－從關(guān)系的原因：經(jīng)常需要系統(tǒng)即使在故障出現(xiàn)時也能保持正確的工作，因此需要避免單結(jié)點(diǎn)例如固定的主控器的故障3第3頁，課件共47頁，創(chuàng)作于2023年2月共享資源訪問方式故障的處理故障和故障的檢測同步系統(tǒng)：可靠的故障檢測異步系統(tǒng)：不可靠的故障檢測4第4頁，課件共47頁，創(chuàng)作于2023年2月故障檢測完整性：有失效的進(jìn)程就能被檢測出來正確性：正常的進(jìn)程不會被認(rèn)為失效強(qiáng)完整性、弱完整性強(qiáng)準(zhǔn)確性、弱準(zhǔn)確性、最終強(qiáng)準(zhǔn)確性、最終弱準(zhǔn)確性不可靠的故障檢測消息的延遲消息的丟失5第5頁，課件共47頁，創(chuàng)作于2023年2月7.2分布式互斥分布式互斥共享資源的協(xié)調(diào)基于消息的傳遞互斥算法臨界區(qū)要求ME1(安全性)：最多一個進(jìn)程進(jìn)入臨界區(qū)ME2(活性)：進(jìn)入和離開臨界區(qū)的請求最終成功ME3(順序)：先請求，先進(jìn)入性能評價消耗的帶寬：進(jìn)入和退出臨界區(qū)的消息數(shù)目延遲：每次進(jìn)入和退出導(dǎo)致的客戶延遲吞吐量：系統(tǒng)吞吐量6第6頁，課件共47頁，創(chuàng)作于2023年2月中央服務(wù)器法服務(wù)器專門授理訪問臨界區(qū)的請求，令牌為進(jìn)入臨界區(qū)每個進(jìn)程需向該服務(wù)器發(fā)出請求允許進(jìn)入，服務(wù)器授予令牌，應(yīng)答令牌被占用，放入緩沖區(qū)等待退出臨界區(qū)，進(jìn)程發(fā)送消息，則令牌釋放，取出等待隊(duì)列中的進(jìn)程，授予令牌，應(yīng)答7第7頁，課件共47頁，創(chuàng)作于2023年2月中央服務(wù)器法滿足ME1？滿足ME2？滿足ME3？滿足ME1，滿足ME2不能滿足ME3性能帶寬：3個消息（請求、授權(quán)、離開）；延遲：請求進(jìn)入2～N個消息間隔，退出：1個消息間隔吞吐量：2個消息的間隔8第8頁，課件共47頁，創(chuàng)作于2023年2月基于環(huán)的算法地位對等，不需要單獨(dú)的服務(wù)器令牌令牌連續(xù)的單向傳輸只有獲得令牌才有權(quán)進(jìn)入臨界區(qū)獲得令牌->占用令牌->進(jìn)入臨界區(qū)->退出臨界區(qū)->釋放令牌9第9頁，課件共47頁，創(chuàng)作于2023年2月基于環(huán)的算法滿足ME1，滿足ME2，不滿足ME3性能帶寬：1～N個消息進(jìn)入臨界區(qū)0～N-1個消息退出臨界區(qū)1個消息延遲：1～N個消息的間隔吞吐量：1～N個消息的間隔10第10頁，課件共47頁，創(chuàng)作于2023年2月使用組播和邏輯時鐘的算法(RicartandAgrawala)引入邏輯時鐘，確定動作的先后關(guān)系狀態(tài)變量：RELEASED,WANTED,HELD進(jìn)程Pi初始化：state:=RELEASED;Task1：state:=WANTED;T:=時間戳；

send(Ti,Pi)toallprocess; Waituntil(receiveN-1answer);state:=HELD;11第11頁，課件共47頁，創(chuàng)作于2023年2月使用組播和邏輯時鐘的算法(RicartandAgrawala)Task2：receiveamassage(Ti,Pi);if(state:=HELDor((state:=WANTED)and(Tj,Pj)<(Ti,Pi)))

將(TiPi)放入請求隊(duì)列;elseanswer(Pi);Task3：

state:=RELEASED;answer隊(duì)列中的所有請求；12第12頁，課件共47頁，創(chuàng)作于2023年2月算法討論滿足ME1,滿足ME2,滿足ME3性能帶寬：進(jìn)入臨界區(qū)2（N-1）個消息，N-1個用于組播，N-1個用于應(yīng)答退出0-(N-1)個消息延遲：請求進(jìn)入2～N個消息間隔吞吐率：1個消息的間隔13第13頁，課件共47頁，創(chuàng)作于2023年2月Maekawa算法選舉的方法獲得部分支持就可以進(jìn)入臨界區(qū)定義:進(jìn)程集合{P1,P2…Pi…PN}

對任意進(jìn)程的選舉集合Vi是進(jìn)程集合的真子集有：Pi∈Vi;

Vi∩Vj≠Φ;|

Vi|=|Vj|=K;14第14頁，課件共47頁，創(chuàng)作于2023年2月進(jìn)程Pi初始化:state:=RELEASED;voted:=FALSE;Task1:state:=WANTED;sendrequesttoVi-{Pi} waituntil(thenumberofanswer=(K-1))state:=HELDTask2:receivetherequestfromPi;if(state=HELDorvoted=true)

將Pi放入請求隊(duì)列

else answerPi

；

voted:=true;15第15頁，課件共47頁，創(chuàng)作于2023年2月Task3:state:=RELEASED; sendreleasedmessagetoVi-{Pi};Task4:Pj（j≠i）receivethereleasedmessagefromPi; if(請求隊(duì)列非空)

刪除隊(duì)列頭部的Pk;answerPk; voted:=TRUE; else voted:=FALSE;16第16頁，課件共47頁，創(chuàng)作于2023年2月討論ME1?YesME2?Yes?（p1，p2，p3）都申請ME3?No改進(jìn)加入邏輯時鐘ME2，ME3yes性能帶寬：進(jìn)入2(K-1)個消息，退出K-1個消息延遲：請求進(jìn)入2～N個消息間隔，與RicartandAgrawala相同吞吐率：2個消息間隔17第17頁，課件共47頁，創(chuàng)作于2023年2月容錯？消息的丟失？不能容忍進(jìn)程崩潰？中央服務(wù)器法可以容忍一個既不申請，也不持有令牌的進(jìn)程崩潰，基于環(huán)的算法不能容忍任一個進(jìn)程崩潰Maekawa算法，如不在一個投票集中，可以容忍RicartandAgrawala算法不能容忍任一個進(jìn)程崩潰18第18頁，課件共47頁，創(chuàng)作于2023年2月7.3選舉選舉對象：扮演特定角色的唯一進(jìn)程目的：找到一個大家認(rèn)可的替代者屬性：定義變量electedE1(安全性)：elected為未決，或?yàn)镻，E2(活性)：所有進(jìn)程都參加且最終elected不為空，或崩潰性能：帶寬使用：發(fā)送消息的總數(shù)算法的回轉(zhuǎn)時間：從啟動算法到中止算法，串行消息的傳輸次數(shù)19第19頁，課件共47頁，創(chuàng)作于2023年2月基于環(huán)的選舉算法(ChangandRoberts)邏輯環(huán)排列的進(jìn)程順時針發(fā)送過程：選舉出一個協(xié)調(diào)者1、最初，所有進(jìn)程都是選舉中的非參加者，所有進(jìn)程都有一個標(biāo)示2、開始一次選舉，自己標(biāo)為參加者，將自己的標(biāo)示放到消息中發(fā)到下一個進(jìn)程20第20頁，課件共47頁，創(chuàng)作于2023年2月基于環(huán)的選舉算法(ChangandRoberts)3、當(dāng)一個進(jìn)程收到一個選舉消息。1）如果消息內(nèi)的標(biāo)示比自己的標(biāo)示大，則轉(zhuǎn)發(fā)消息到下一個鄰居，標(biāo)自己為參加者。2）標(biāo)示比自己的小且自己不是參加者，則選舉消息替換成自己的標(biāo)示，發(fā)送，標(biāo)自己為參加者；3）標(biāo)示比自己的小且自己是參加者，則不轉(zhuǎn)發(fā)消息4、如果收到的標(biāo)示是接收者自己的，則自己被選舉成為協(xié)調(diào)者。向鄰居發(fā)送當(dāng)選消息，并標(biāo)記為非參加者5、任一個進(jìn)程收到當(dāng)選消息，置變量elected，并標(biāo)記為非參加者，轉(zhuǎn)發(fā)當(dāng)選消息21第21頁，課件共47頁，創(chuàng)作于2023年2月討論E1（安全性）：滿足所有的標(biāo)識都比較一個進(jìn)程當(dāng)選必須收回自己的標(biāo)識任意兩個進(jìn)程，標(biāo)識較大的不會傳遞標(biāo)識較小的進(jìn)程標(biāo)識，不可能兩者都收到自己的標(biāo)識E2（活性）：滿足遍歷環(huán)，所有人都參加22第22頁，課件共47頁，創(chuàng)作于2023年2月性能當(dāng)只有一個進(jìn)程啟動選舉最壞的情況，3N-1個消息逆時針鄰居具有最大標(biāo)識，到達(dá)該鄰居需要N-1個消息回路N個消息當(dāng)選發(fā)送N個消息最好的情況，2N個消息算法的限制假設(shè)消息傳輸是可靠的假設(shè)無進(jìn)程崩潰23第23頁，課件共47頁，創(chuàng)作于2023年2月霸道算法假設(shè)消息傳輸是可靠的，且有上界假設(shè)可能會發(fā)生進(jìn)程崩潰同步（環(huán)：異步）可以和所有進(jìn)程通信且知道標(biāo)識較高的進(jìn)程（環(huán)：鄰居）消息的類型選舉消息：選舉某進(jìn)程為協(xié)調(diào)者的消息回答消息：回復(fù)選舉的結(jié)果協(xié)調(diào)者消息：“新協(xié)調(diào)者”宣布當(dāng)選24第24頁，課件共47頁，創(chuàng)作于2023年2月25過程：任一個進(jìn)程開始選舉1、知道自己是最大標(biāo)示的進(jìn)程，直接認(rèn)為自己是協(xié)調(diào)者進(jìn)程，并發(fā)送協(xié)調(diào)者消息2、具有較低標(biāo)示的進(jìn)程開始一次選舉，發(fā)選舉消息給比自己標(biāo)示大的進(jìn)程，等待應(yīng)答消息若無應(yīng)答消息，則認(rèn)定自己是協(xié)調(diào)者有消息應(yīng)答，則等待接受協(xié)調(diào)者消息無協(xié)調(diào)者消息，則再進(jìn)行一次選舉3、若收到一個選舉消息，回送應(yīng)答。若自己沒開始選舉，則自己開始一次選舉4、若收到協(xié)調(diào)者消息，則認(rèn)定新的協(xié)調(diào)者第25頁，課件共47頁，創(chuàng)作于2023年2月討論E1（安全性）：滿足沒有進(jìn)程被替換E2（活性）：滿足根據(jù)可靠消息傳遞的假設(shè)性能最好的情況N-2個消息標(biāo)識最大的進(jìn)程發(fā)現(xiàn)協(xié)調(diào)者錯誤，發(fā)送N-2個協(xié)調(diào)者消息最壞情況O(N2)個消息標(biāo)識最小的進(jìn)程發(fā)現(xiàn)協(xié)調(diào)者錯誤，然后N-1個進(jìn)程開始選舉，每個進(jìn)程都發(fā)送消息到較大標(biāo)識的進(jìn)程26第26頁，課件共47頁，創(chuàng)作于2023年2月7.4組播通信特點(diǎn)一個進(jìn)程只調(diào)用一個組播操作來發(fā)送一個消息到組中的每個進(jìn)程不是多次發(fā)送同一個消息到不同進(jìn)程效率：程序員方便，硬件的支持傳遞保證：無法保證系統(tǒng)模型組標(biāo)識：G封閉組：只有G內(nèi)的成員可以發(fā)送消息給G開放組：組G外的成員也可以發(fā)送消息給G27第27頁，課件共47頁，創(chuàng)作于2023年2月靜態(tài)組與動態(tài)組靜態(tài)組：組內(nèi)成員不可變更的組，組成員按照某種方式事先定義，以后無論發(fā)生什么情況都不可變更動態(tài)組：允許組成員動態(tài)地加入退出。一個進(jìn)程可以提出請求，加入（Join）一個組，從而成為這個組的成員，也可以要求離開或由于失效而退出（Leave）這個組28第28頁，課件共47頁，創(chuàng)作于2023年2月靜態(tài)組與動態(tài)組動態(tài)組提供面向視圖（View-Oriented）的組成員服務(wù)（GroupMembershipService）視圖（View）是組中當(dāng)前活躍的成員（進(jìn)程）列表，每個視圖都有一個唯一的標(biāo)志，組成員服務(wù)跟蹤組的成員關(guān)系隨時間的變化。當(dāng)組成員列表發(fā)生變化，組成員服務(wù)負(fù)責(zé)通知組的各個成員，組成員就會安裝（Install）新的視圖29第29頁，課件共47頁，創(chuàng)作于2023年2月消息通信服務(wù)根據(jù)消息傳輸是否可靠，消息通信服務(wù)可分為不可靠多播（UnreliableMulticast）和可靠多播（ReliableMuticast）不可靠多播類似UDP提供的數(shù)據(jù)報服務(wù)，不保證消息安全到達(dá)所有接收方。可靠多播保證消息被所有接收方安全收到（Receive），但并不保證被接收方安全接收（Deliver）區(qū)分接收（Deliver）和收到（Receive）。一個進(jìn)程收到消息后可以先不接收它（送交上層應(yīng)用），即接收是應(yīng)用層行為，而收到在通信層行為30第30頁，課件共47頁，創(chuàng)作于2023年2月消息通信服務(wù)按照消息的順序特性，消息通信服務(wù)可分為無序、先入先出順序（FIFOOrder）、因果序（CausalOrder）、全序（TotalOrder）等。31第31頁，課件共47頁，創(chuàng)作于2023年2月基本組播原語B-multicast(g,m)：對每個屬于組g的進(jìn)程p,send(p,m)，可靠的一對一send操作進(jìn)程p執(zhí)行receive(m)時：進(jìn)程執(zhí)行B-deliver(m)可靠組播完整性（安全性）：任何傳遞的消息與發(fā)送的消息相同，且不會被重復(fù)傳遞有效性（活性）：任何消息都會被傳送到目的地協(xié)定：如果一個正確的進(jìn)程收到消息，則組中所有正確成員都終將收到該消息32第32頁，課件共47頁，創(chuàng)作于2023年2月用B-multicast實(shí)現(xiàn)可靠組播算法每個消息被發(fā)給每個進(jìn)程|g|次滿足有效性，可靠的通信保證完整性，B-deliver(m)保證協(xié)定33過程：進(jìn)程P,組g初始化：

Received:={};發(fā)送,進(jìn)程PR-Multicast(m)：進(jìn)程P,B-Multicast(g,m)；接受： 進(jìn)程QB-deliver(m)時,其中g(shù)=group（m） ifm∈Received; then Received:=Received∪{m}; if(P≠Q(mào))thenP,B-Multicast(g,m)；

endif R-deliver(m); endif第33頁，課件共47頁，創(chuàng)作于2023年2月基于IP組播實(shí)現(xiàn)可靠組播每個進(jìn)程有一個唯一的消息順序數(shù)Sp每個進(jìn)程記載一組消息順序數(shù)（Sp,Sq………）進(jìn)程P,R-Multicast(m)時，Sp=Sp+1，所有send上攜帶Sgp，并分別攜帶確認(rèn)<q，Rgq>進(jìn)程V接收m，如S=Rgp+1，則R-deliver(m)，并且接收后Rgp+1；進(jìn)程V接收m，如S≤Rgp

，則丟掉此消息進(jìn)程V接收m，如S>Rgp+1，則表明漏掉了進(jìn)程P的某些個消息，保留m到隊(duì)列，發(fā)送重發(fā)的確認(rèn)34第34頁，課件共47頁，創(chuàng)作于2023年2月有序組播FIFO排序：一個進(jìn)程的Multicast(g,m)在Multicast(g,m’)前面，則每個正確傳遞m’的進(jìn)程將在m’前傳遞m因果排序：如果Multicast(g,m)->Multicast(g,m’),則每個正確傳遞m’的進(jìn)程將在m’前傳遞m全排序：如果一個正確傳遞m’的進(jìn)程在m’前傳遞m，那么其他正確傳遞m’的進(jìn)程將在m’前傳遞m35第35頁，課件共47頁，創(chuàng)作于2023年2月性質(zhì)因果排序隱含F(xiàn)IFO排序全排序不一定是因果排序或FIFO排序全排序消息在不同進(jìn)程中是順序一樣的前提下允許消息隨機(jī)排序有序組播不一定隱含可靠組播正確進(jìn)程p傳遞消息m然后傳遞m‘，q傳遞m，不一定傳遞m’36第36頁，課件共47頁，創(chuàng)作于2023年2月實(shí)現(xiàn)FIFO排序兩個順序數(shù)變量SPg,進(jìn)程p發(fā)送到g的消息計數(shù)Rqg,進(jìn)程p傳遞進(jìn)程q并發(fā)往組g的最近的消息順序數(shù)過程Multicast消息附帶SPg；檢查收到的進(jìn)程q的消息序數(shù)與Rqg+1的關(guān)系，等于則接受，否則，放入等待隊(duì)列37第37頁，課件共47頁，創(chuàng)作于2023年2月全排序組播維持一個組特定的順序數(shù)S協(xié)調(diào)者進(jìn)程sequence(g)來管理標(biāo)識進(jìn)程PMulticast(g,m)的消息中帶有本進(jìn)程的順序數(shù)Rp，同時也被發(fā)給sequence(g)進(jìn)程sequence(g)，收到該消息，S=S+1，Multicast(g,<Rp,S>);進(jìn)程Q收到消息m，放入等待隊(duì)列，直到收到,<Rp,S>消息，判斷S的值是否順序，然后從等待隊(duì)列中取出消息m38第38頁，課件共47頁，創(chuàng)作于2023年2月7.5共識問題(Consensus)共識一個協(xié)定一個或多個進(jìn)程提議了一個值應(yīng)當(dāng)是什么后，所有進(jìn)程對這個值達(dá)成協(xié)定系統(tǒng)模型一組通過消息傳遞進(jìn)行通信的進(jìn)程通信是可靠的可能出現(xiàn)故障：拜占庭故障和崩潰故障39第39頁，課件共47頁，創(chuàng)作于2023年2月共識的定義每個進(jìn)程處于未決狀態(tài)，并提議集合D中的一個值vi。進(jìn)程間相互通信，交換值。最后，每個進(jìn)程設(shè)定一個約定變量di的值共識算法的要求是在每次運(yùn)行中滿足以下條件：終止性：每個正確的進(jìn)程最終設(shè)定它的決定變量協(xié)定性：所有正確進(jìn)程的決定變量都相同完整性：如果正確的進(jìn)程都提議相同的值，那么在決定狀態(tài)的任何正確進(jìn)程已選擇了該值40第40頁，課件共47頁，創(chuàng)作于2023年2月同步的，不出故障的系統(tǒng)的共識問題解決每個進(jìn)程采用可靠的組播，發(fā)出自己的協(xié)議值每個進(jìn)程收到協(xié)議值，采用設(shè)定的函數(shù)選取決定變量終止性由可靠組播的有效性和協(xié)定性保證協(xié)定性由可靠組播的完整性和設(shè)定的函數(shù)保證41第41頁，課件共47頁，創(chuàng)作于2023年2月同步的，崩潰的故障中的共識問題通信