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

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

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

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

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

對任意進程的選舉集合Vi是進程集合的真子集有：Pi∈Vi;

Vi∩Vj≠Φ;|

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

將Pi放入請求隊列

else answerPi

；

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

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

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

endif R-deliver(m); endif第三十三頁，共四十七頁，編輯于2023年，星期日基于IP組播實現(xiàn)可靠組播每個進程有一個唯一的消息順序數(shù)Sp每個進程記載一組消息順序數(shù)（Sp,Sq………）進程P,R-Multicast(m)時，Sp=Sp+1，所有send上攜帶Sgp，并分別攜帶確認<q，Rgq>進程V接收m，如S=Rgp+1，則R-deliver(m)，并且接收后Rgp+1；進程V接收m，如S≤Rgp

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