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

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

send(Ti,Pi)toallprocess; Waituntil(receiveN-1answer);state:=HELD;11第十一頁(yè)，共四十七頁(yè)，編輯于2023年，星期日使用組播和邏輯時(shí)鐘的算法(RicartandAgrawala)Task2：receiveamassage(Ti,Pi);if(state:=HELDor((state:=WANTED)and(Tj,Pj)<(Ti,Pi)))

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

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

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

Vi∩Vj≠Φ;|

Vi|=|Vj|=K;14第十四頁(yè)，共四十七頁(yè)，編輯于2023年，星期日進(jìn)程Pi初始化:state:=RELEASED;voted:=FALSE;Task1:state:=WANTED;sendrequesttoVi-{Pi} waituntil(thenumberofanswer=(K-1))state:=HELDTask2:receivetherequestfromPi;if(state=HELDorvoted=true)

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

else answerPi

；

voted:=true;15第十五頁(yè)，共四十七頁(yè)，編輯于2023年，星期日Task3:state:=RELEASED; sendreleasedmessagetoVi-{Pi};Task4:Pj（j≠i）receivethereleasedmessagefromPi; if(請(qǐng)求隊(duì)列非空)

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

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