云計(jì)算（典藏版）課件 第10章 云計(jì)算核心算法

1云計(jì)算的基礎(chǔ)技術(shù)是集群技術(shù)，支撐集群高效協(xié)同工作需要一系列資源和任務(wù)調(diào)度算法，良好的調(diào)度算法可以提高集群處理能力，有效分配資源，加速作業(yè)進(jìn)度。三種核心算法Paxos算法DHT算法Gossip協(xié)議解決分布式系統(tǒng)中信息一致性問題解決分布式網(wǎng)絡(luò)的應(yīng)用層選路問題解決分布式環(huán)境下信息高效分發(fā)問題《云計(jì)算》第三版配套PPT課件第十章云計(jì)算核心算法(一)10.1

Paxos算法10.2DHT算法10.3Gossip協(xié)議of392高級(jí)人工智能人才培養(yǎng)叢書Paxos算法解決的問題是一個(gè)分布式系統(tǒng)如何就某個(gè)value（決議）達(dá)成一致。Paxos算法作為分布式系統(tǒng)中最著名的算法之一，在目前所有的一致性算法中，該算法最常用而且被認(rèn)為是最有效的。10.1Paxos算法10.1.1Paxos算法背景知識(shí)10.1.2Paxos算法詳解10.1.3Paxos算法舉例10.1.4Chubby中Paxos算法的具體實(shí)現(xiàn)510.1Paxos算法Paxos算法背景知識(shí)processor可以擔(dān)任三個(gè)角色“proposer”、“accepter”和“l(fā)earner”中的一個(gè)或多個(gè)角色。proposal和value：proposal一般譯為“提案”，value一般譯為“決議”。proposer可以propose（提出）proposal；accepter可以accept（接受）proposal各個(gè)processor之間信息的傳遞可以延遲、丟失，但是在這個(gè)算法中假設(shè)傳達(dá)到的信息都是正確的1234《云計(jì)算》第三版配套PPT課件10.1Paxos算法10.1.1Paxos算法背景知識(shí)10.1.2Paxos算法詳解10.1.3Paxos算法舉例10.1.4Chubby中Paxos算法的具體實(shí)現(xiàn)710.1Paxos算法Paxos算法詳解Paxos算法的核心是，只要滿足下面三個(gè)條件就能保證數(shù)據(jù)的一致性：1一個(gè)value只有在被proposer提出之后才可以被choose；2每次只有一個(gè)value被choose；3value只有被choose之后才能被learners所獲取?！对朴?jì)算》第三版配套PPT課件810.1Paxos算法Paxos算法詳解對(duì)一個(gè)proposal的提出和接受做一個(gè)系統(tǒng)的描述，這個(gè)過(guò)程分為請(qǐng)求和提出兩個(gè)階段。請(qǐng)求階段提出階段proposer選擇一個(gè)編號(hào)n，并向accepter多數(shù)派發(fā)出一個(gè)prepare請(qǐng)求如果accepter接受到的prepare所帶有的編號(hào)n比它之前所做出過(guò)回應(yīng)的prepare請(qǐng)求的編號(hào)都要高，則該accepter回應(yīng)proposer一個(gè)promise如果proposer收到了accepter多數(shù)派對(duì)它所發(fā)出的prepare請(qǐng)求所做的回應(yīng)，則它發(fā)出帶有proposal的accept請(qǐng)求，proposal=(num,value)，value為回應(yīng)所帶回的proposal的value值如果accepter接受到一個(gè)accept請(qǐng)求，如果該accepter之前沒有對(duì)任何編號(hào)大于n的prepare請(qǐng)求做出過(guò)promise，則接受該proposal《云計(jì)算》第三版配套PPT課件9PR：preparerequest（假設(shè)p1到a3的PR丟失）a1和a2是第一次接受到prepare請(qǐng)求，所以返回promise（不帶回proposal），此時(shí)p1收到了a1和a2的promise，但是根據(jù)提出階段的proposer必須接受來(lái)自多數(shù)派的promise才可以提出accept請(qǐng)求，因此不會(huì)出現(xiàn)先前例子中的情況。10.1Paxos算法Paxos算法詳解p1a1a2a3PRPRPR《云計(jì)算》第三版配套PPT課件10.1Paxos算法10.1.1Paxos算法背景知識(shí)10.1.2Paxos算法詳解10.1.3Paxos算法舉例10.1.4Chubby中Paxos算法的具體實(shí)現(xiàn)1110.1Paxos算法Paxos算法舉例S2（Accepter）S3（Accepter）S4（Accepter）S5（Accepter）S1（Proposer）PrepareRequestPrepareRequestPrepareRequestPrepareRequestS1選定編號(hào)1（假設(shè)第一個(gè)命令編號(hào)為1），向集合database={s2,s3,s4,s5}的一個(gè)多數(shù)派子集發(fā)送PrepareRequest（PR）步驟一《云計(jì)算》第三版配套PPT課件1210.1Paxos算法Paxos算法舉例S2（Accepter）S3（Accepter）S4（Accepter）S5（Accepter）S1（Proposer）PromiseProposalPromiseProposalPromiseProposalPromiseProposal步驟二如果通信順利，所有的多數(shù)派都收到了PR如果通信部分失敗導(dǎo)致接受到PR的節(jié)點(diǎn)不構(gòu)成多數(shù)派則S1重復(fù)步驟1（PR編號(hào)遞增）《云計(jì)算》第三版配套PPT課件13S1接收到多數(shù)派的Paromise，向集合database發(fā)出帶有第一個(gè)SQL命令（這里的SQL命令就是之前的value）的Proposal，編號(hào)為1，因?yàn)镻romise沒有帶回Proposal所以這里的SQL命令沒有限制。10.1Paxos算法Paxos算法舉例步驟三《云計(jì)算》第三版配套PPT課件1410.1Paxos算法Paxos算法舉例S2（Accepter）S3（Accepter）S4（Accepter）S5（Accepter）S1（Proposer）SQLSQLSQLSQL步驟四通信順利決議產(chǎn)生接收Proposal通信失敗構(gòu)成多數(shù)派決議不產(chǎn)生不構(gòu)成多數(shù)派《云計(jì)算》第三版配套PPT課件15重復(fù)以上操作，注意Proposal、Prepare以及Promise的編號(hào)遞增，以及Promise根據(jù)情況帶回Proposal。10.1Paxos算法Paxos算法舉例步驟五《云計(jì)算》第三版配套PPT課件10.1Paxos算法10.1.1Paxos算法背景知識(shí)10.1.2Paxos算法詳解10.1.3Paxos算法舉例10.1.4Chubby中Paxos算法的具體實(shí)現(xiàn)1710.1Paxos算法Chubby中Paxos算法的具體實(shí)現(xiàn)Chubby是一個(gè)為松散耦合分布式系統(tǒng)提供粗粒度的鎖服務(wù)以及可靠性存儲(chǔ)。Chubby的底層一致性實(shí)現(xiàn)是以Paxos算法為基礎(chǔ)。Chubby的整個(gè)系統(tǒng)結(jié)構(gòu)主要由服務(wù)端和客戶端兩部分組成，客戶端通過(guò)RPC調(diào)用和服務(wù)端進(jìn)行通信。《云計(jì)算》第三版配套PPT課件1810.1Paxos算法Chubby中Paxos算法的具體實(shí)現(xiàn)Chubby服務(wù)端的基本架構(gòu)大致分為三層：最底層是容錯(cuò)日志系統(tǒng)，通過(guò)Paxos算法保證集群所有機(jī)器上日志的一致性。中間層是容錯(cuò)數(shù)據(jù)庫(kù)，其通過(guò)下層的日志來(lái)保證一致性和容錯(cuò)性。最頂層是Chubby對(duì)外提供的分布式鎖服務(wù)和小文件存儲(chǔ)服務(wù)?！对朴?jì)算》第三版配套PPT課件1910.1Paxos算法Chubby中Paxos算法的具體實(shí)現(xiàn)Chubby事務(wù)日志中的Value對(duì)應(yīng)Paxos算法中的Instance。Chubby通過(guò)選舉一個(gè)副本節(jié)點(diǎn)作為Paxos算法的Master節(jié)點(diǎn)來(lái)避免提出提案陷入多個(gè)PaxosRound并存的情況。Chubby為了在保證正確性的前提下盡可能地提高算法運(yùn)行性能，可以讓多個(gè)Instance共用一套序號(hào)分配機(jī)制，并將Prepare->Promise合并為一個(gè)階段?！对朴?jì)算》第三版配套PPT課件2010.1Paxos算法Chubby中Paxos算法的具體實(shí)現(xiàn)當(dāng)某個(gè)副本節(jié)點(diǎn)選舉成為Master，通過(guò)新分配的編號(hào)N廣播一個(gè)Prepare消息，Prepare消息會(huì)被所有未達(dá)成一致的Instance和目前還未開始的Instance共用。若是Acceptor接收到Prepare消息，可以通過(guò)將反饋信息封裝在一個(gè)數(shù)據(jù)包中來(lái)實(shí)現(xiàn)對(duì)多個(gè)Instance同時(shí)做出回應(yīng)。Master服務(wù)器對(duì)所有未做決定的Instance和所有未來(lái)的Instance分別執(zhí)行Propose->Accept階段的處理。如果Master服務(wù)器能夠一直穩(wěn)定運(yùn)行的話，在接下來(lái)的算法運(yùn)行過(guò)程中，就不再需要進(jìn)行Prepare->Promise處理了123《云計(jì)算》第三版配套PPT課件10.1

Paxos算法10.2

DHT算法10.3Gossip協(xié)議of3921高級(jí)人工智能人才培養(yǎng)叢書第十章云計(jì)算核心算法(一)2210.2DHT算法Client/Server計(jì)算模式（即客戶—服務(wù)器計(jì)算模式）主要應(yīng)用于小規(guī)模的網(wǎng)絡(luò)環(huán)境。Client/Server計(jì)算模式采用中央集中式架構(gòu)，中央節(jié)點(diǎn)（服務(wù)器）對(duì)整個(gè)網(wǎng)絡(luò)服務(wù)具有決定性的作用。大部分的計(jì)算都集中在服務(wù)器端，因而引起負(fù)載的不平衡。即所謂的“服務(wù)器端的計(jì)算瓶頸”，而客戶機(jī)端則存在資源浪費(fèi)的情況。集中式計(jì)算模式對(duì)用戶的隱私以及數(shù)據(jù)安全也將存在不可能解決的難題。《云計(jì)算》第三版配套PPT課件2310.2DHT算法P2P計(jì)算模式是一種非集中計(jì)算模式。P2P網(wǎng)絡(luò)中的每臺(tái)計(jì)算機(jī)（或稱對(duì)等點(diǎn)），具有同樣的地位，既可以請(qǐng)求服務(wù)，也可以提供服務(wù)。P2P計(jì)算模式具有資源充分利用，網(wǎng)絡(luò)規(guī)模可擴(kuò)展（節(jié)點(diǎn)越多網(wǎng)絡(luò)越穩(wěn)定，不存在瓶頸）等優(yōu)點(diǎn)。下一代計(jì)算機(jī)網(wǎng)絡(luò)（即云計(jì)算和物聯(lián)網(wǎng)）都是巨大的網(wǎng)絡(luò)，因此，未來(lái)的計(jì)算模式應(yīng)該是P2P計(jì)算模式《云計(jì)算》第三版配套PPT課件2410.2DHT算法P2P按照拓?fù)浣Y(jié)構(gòu)的不同可以分為三種：集中式拓?fù)淠Ｊ竭@種模式必須有中央服務(wù)器。當(dāng)系統(tǒng)中節(jié)點(diǎn)數(shù)增多時(shí)，中央服務(wù)器就成為系統(tǒng)的瓶頸。分布式非結(jié)構(gòu)化拓?fù)淠Ｊ皆诜墙Y(jié)構(gòu)化P2P系統(tǒng)中，信息搜索的算法難免會(huì)帶有一定的盲目性。分布式結(jié)構(gòu)化拓?fù)淠Ｊ接捎谟脩纛A(yù)先知道應(yīng)該搜索哪些節(jié)點(diǎn)，避免了非結(jié)構(gòu)化P2P系統(tǒng)中使用的泛洪式查找，提高了信息搜索的效率?！对朴?jì)算》第三版配套PPT課件10.2DHT算法10.2.1DHT原理介紹10.2.2Chord中DHT的具體實(shí)現(xiàn)10.2.3Pastry中DHT的具體實(shí)現(xiàn)10.2.4CAN中DHT的具體實(shí)現(xiàn)10.2.5Tapestry中DHT的具體實(shí)現(xiàn)26DHT技術(shù)的基本概念10.2DHT算法DHT原理介紹事件通知網(wǎng)絡(luò)存儲(chǔ)其他應(yīng)用DHTTCP/IP應(yīng)用層DHT層網(wǎng)絡(luò)層DHT分布式哈希表采用Hash函數(shù)加速了查找速度和增強(qiáng)了安全性，而且便于管理，同時(shí)不會(huì)占用太多的網(wǎng)絡(luò)帶寬《云計(jì)算》第三版配套PPT課件27DHT應(yīng)用層的接口10.2DHT算法DHT原理介紹應(yīng)用層DHTNodeNodeNodeInsert（Key，data）LookUp（Key）……通過(guò)DHT層的LookUp(Key)操作，可以把應(yīng)用層的數(shù)據(jù)均勻分布在網(wǎng)絡(luò)的各個(gè)節(jié)點(diǎn)內(nèi)，這種方法使下層網(wǎng)絡(luò)完全不受中心控制《云計(jì)算》第三版配套PPT課件2810.2DHT算法DHT原理介紹所有的DHT路由算法都主要包括三個(gè)方面:第一方面第二方面第三方面DHT的散列值空間的描述DHT中各節(jié)點(diǎn)如何分配管理散列空間路由發(fā)現(xiàn)算法即如何進(jìn)行散列即散列后的信息如何決定其存儲(chǔ)的節(jié)點(diǎn)位置即對(duì)散列值進(jìn)行查詢時(shí)節(jié)點(diǎn)如何高效地路由到存儲(chǔ)目標(biāo)信息的節(jié)點(diǎn)《云計(jì)算》第三版配套PPT課件本章未完待續(xù)第十章云計(jì)算核心算法(二)10.1

Paxos算法10.2

DHT算法10.3Gossip協(xié)議of3930高級(jí)人工智能人才培養(yǎng)叢書10.2DHT算法10.2.1DHT原理介紹10.2.2Chord中DHT的具體實(shí)現(xiàn)10.2.3Pastry中DHT的具體實(shí)現(xiàn)10.2.4CAN中DHT的具體實(shí)現(xiàn)10.2.5Tapestry中DHT的具體實(shí)現(xiàn)10.2DHT算法第十章云計(jì)算核心算法(二)1．Chord中DHT的具體實(shí)現(xiàn)ChordChord中所有節(jié)點(diǎn)按節(jié)點(diǎn)ID大小順時(shí)針排列并首尾相接組成一個(gè)擁有2m（m一般為160）個(gè)節(jié)點(diǎn)的環(huán)空間后繼節(jié)點(diǎn)successor消息的目標(biāo)節(jié)點(diǎn)就是節(jié)點(diǎn)ID大于或者等于消息Key值的節(jié)點(diǎn)中節(jié)點(diǎn)ID最小的一個(gè)完全分布可擴(kuò)展性可用性好負(fù)載均衡Chord環(huán)of393210.2DHT算法第十章云計(jì)算核心算法(二)Chord模型示意圖Chord中DHT的具體實(shí)現(xiàn)m=6且只有10個(gè)節(jié)點(diǎn)的查找示意圖，其中節(jié)點(diǎn)標(biāo)識(shí)前加上N而關(guān)鍵字標(biāo)識(shí)前加上K加以區(qū)別，圖中給出了節(jié)點(diǎn)N8、N42、N51的finger表。of393310.2DHT算法第十章云計(jì)算核心算法(二)Chord中DHT的具體實(shí)現(xiàn)節(jié)點(diǎn)N的加入過(guò)程初始化新節(jié)點(diǎn)的指針表更新現(xiàn)有其他節(jié)點(diǎn)的指針表從后繼節(jié)點(diǎn)把關(guān)鍵字傳遞到節(jié)點(diǎn)N節(jié)點(diǎn)的退出過(guò)程在Chord中，當(dāng)節(jié)點(diǎn)N失效時(shí)，所有指針表中包括N的節(jié)點(diǎn)都必須把N替換成N的后繼節(jié)點(diǎn)。在失效處理中最關(guān)鍵的步驟是維護(hù)正確的后繼指針of393410.2DHT算法10.2.1DHT原理介紹10.2.2Chord中DHT的具體實(shí)現(xiàn)10.2.3Pastry中DHT的具體實(shí)現(xiàn)10.2.4CAN中DHT的具體實(shí)現(xiàn)10.2.5Tapestry中DHT的具體實(shí)現(xiàn)10.2DHT算法第十章云計(jì)算核心算法(二)Pastry中DHT的具體實(shí)現(xiàn)1．節(jié)點(diǎn)的加入假定新加入節(jié)點(diǎn)的節(jié)點(diǎn)號(hào)為N，節(jié)點(diǎn)號(hào)的分配過(guò)程是由應(yīng)用程序決定的。N的加入過(guò)程主要包括初始化自己的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)，并通知其他節(jié)點(diǎn)自己已經(jīng)加入系統(tǒng)。N在加入Pastry之前，需要知道一個(gè)相鄰節(jié)點(diǎn)A的位置信息。2．節(jié)點(diǎn)的退出Pastry網(wǎng)絡(luò)中的節(jié)點(diǎn)可能會(huì)隨時(shí)失效或者不發(fā)出通知離開系統(tǒng)。當(dāng)相鄰節(jié)點(diǎn)不能和某個(gè)Pastry節(jié)點(diǎn)通信時(shí)，就認(rèn)為該節(jié)點(diǎn)發(fā)生了失效。of393610.2DHT算法10.2.1DHT原理介紹10.2.2Chord中DHT的具體實(shí)現(xiàn)10.2.3Pastry中DHT的具體實(shí)現(xiàn)10.2.4CAN中DHT的具體實(shí)現(xiàn)10.2.5Tapestry中DHT的具體實(shí)現(xiàn)10.2DHT算法第十章云計(jì)算核心算法(二)CAN中DHT的具體實(shí)現(xiàn)CAN是內(nèi)容可編址網(wǎng)絡(luò)（Content-AddressableNetwork）的縮寫CAN可以在Internet規(guī)模的大型對(duì)等網(wǎng)絡(luò)上提供類似哈希表的功能。CAN具有可擴(kuò)展、容錯(cuò)和完全自組織等特點(diǎn)。CAN類似于一張大哈希表，基本操作包括插入、查找和刪除。CAN由大量自治的節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)保存哈希表的一部分，稱為一個(gè)區(qū)。CAN的設(shè)計(jì)完全是分布式的，不需要任何形式的中央控制點(diǎn)。CAN具有很好的可擴(kuò)展性，節(jié)點(diǎn)只需要維護(hù)少量的控制狀態(tài)而且狀態(tài)數(shù)量獨(dú)立于系統(tǒng)中的節(jié)點(diǎn)數(shù)量。CAN支持容錯(cuò)特性，節(jié)點(diǎn)可以繞過(guò)錯(cuò)誤節(jié)點(diǎn)進(jìn)行路由。of393810.2DHT算法第十章云計(jì)算核心算法(二)二維坐標(biāo)空間中CAN的節(jié)點(diǎn)示意圖CAN中DHT的具體實(shí)現(xiàn)C(0-0.5,0.5-1.0)D(0.5-0.75,0.5-1.0)E(0.75-1.0,0.5-1.0)A(0-0.5,0-0.5)B(0.5-1.0,0-0.5)0.01.01.0整個(gè)區(qū)域坐標(biāo)由5個(gè)節(jié)點(diǎn)A，B，C，D，E組成，每個(gè)節(jié)點(diǎn)負(fù)責(zé)部分區(qū)域，CAN中通過(guò)哈希函數(shù)把資源映射到d維空間中的一點(diǎn)，資源對(duì)象就發(fā)布在該節(jié)點(diǎn)上。of393910.2DHT算法第十章云計(jì)算核心算法(二)CAN路由模型的路由過(guò)程CAN中DHT的具體實(shí)現(xiàn)(0,1)(1,0)(0,0)(1,1)Key=(0,8,0,9)Node=(0.75,0,0.75,1)查詢操作通過(guò)在d維笛卡兒坐標(biāo)空間中轉(zhuǎn)發(fā)查詢消息被執(zhí)行，轉(zhuǎn)發(fā)從查詢初始化點(diǎn)沿著坐標(biāo)系上最接近直線的路徑到達(dá)存儲(chǔ)關(guān)鍵字的節(jié)點(diǎn)。of394010.2DHT算法10.2.1DHT原理介紹10.2.2Chord中DHT的具體實(shí)現(xiàn)10.2.3Pastry中DHT的具體實(shí)現(xiàn)10.2.4CAN中DHT的具體實(shí)現(xiàn)10.2.5Tapestry中DHT的具體實(shí)現(xiàn)10.2DHT算法第十章云計(jì)算核心算法(二)Tapestry中DHT的具體實(shí)現(xiàn)Tapestry分層路由和組織結(jié)構(gòu)的查詢算法，它為面向廣域網(wǎng)的分布式應(yīng)用提供了一個(gè)分布式查找和路由定位基礎(chǔ)平臺(tái)。Tapestry網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)和文檔通過(guò)哈希變換得到各自160位比特的唯一標(biāo)識(shí)符Tapestry基于文檔標(biāo)識(shí)符的后綴進(jìn)行路由Tapestry基于Plaxton中提出的定位和路由機(jī)制進(jìn)行優(yōu)化Tapestry采用的基本定位和路由機(jī)制和Plaxton很類似Tapestry中的每個(gè)節(jié)點(diǎn)都可以用Plaxton中描述的算法轉(zhuǎn)發(fā)消息of394210.2DHT算法第十章云計(jì)算核心算法(二)Tapestry中DHT的具體實(shí)現(xiàn)1．節(jié)點(diǎn)的加入Tapestry的節(jié)點(diǎn)加入算法和Pastry很類似。構(gòu)造完自己的數(shù)據(jù)結(jié)構(gòu)后，節(jié)點(diǎn)N將通知網(wǎng)絡(luò)中的其他節(jié)點(diǎn)，自己已經(jīng)加入網(wǎng)絡(luò)。構(gòu)造過(guò)程中還需要進(jìn)行一些優(yōu)化工作。2．節(jié)點(diǎn)的退出一種情況是節(jié)點(diǎn)從網(wǎng)絡(luò)中自行消失，在這種情況下，它的鄰居可以檢測(cè)到它已經(jīng)退出網(wǎng)絡(luò)并可以相應(yīng)地調(diào)整路由表；另一種機(jī)制是節(jié)點(diǎn)在退出系統(tǒng)之前，利用后向指針確定所有把它作為鄰居的節(jié)點(diǎn)，這些節(jié)點(diǎn)會(huì)相應(yīng)調(diào)整路由表并通知對(duì)象服務(wù)器該節(jié)點(diǎn)已經(jīng)退出網(wǎng)絡(luò)。of3943第十章云計(jì)算核心算法(二)10.1

Paxos算法10.2

DHT算法10.3Gossip協(xié)議of3944高級(jí)人工智能人才培養(yǎng)叢書10.3Gossip協(xié)議10.3.1Gossip協(xié)議的特點(diǎn)10.3.2Gossip協(xié)議的通信方式及收斂性10.3.3Gossip節(jié)點(diǎn)管理算法10.3.4Cassandra中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.5CoolStreaming系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.6H.F.系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.7Chord網(wǎng)絡(luò)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3Gossip協(xié)議第十章云計(jì)算核心算法(二)Gossip協(xié)議的特點(diǎn)Gossip協(xié)議具有以下幾個(gè)優(yōu)點(diǎn):分布式容錯(cuò)最終一致性去中心化當(dāng)系統(tǒng)中有節(jié)點(diǎn)因?yàn)殄礄C(jī)而重啟，或有新節(jié)點(diǎn)加入，經(jīng)過(guò)一段時(shí)間后，這些節(jié)點(diǎn)的狀態(tài)仍會(huì)與系統(tǒng)中其他節(jié)點(diǎn)達(dá)成一致，也就是說(shuō)Gossip天然具有分布式容錯(cuò)的特點(diǎn)。Gossip協(xié)議雖然無(wú)法保證在某個(gè)時(shí)刻所有節(jié)點(diǎn)狀態(tài)保持一致，但可以保證在“最終”所有節(jié)點(diǎn)一致?！白罱K”是一個(gè)現(xiàn)實(shí)中存在，但理論上難以證明的時(shí)間點(diǎn)。Gossip協(xié)議不要求節(jié)點(diǎn)知道系統(tǒng)中所有節(jié)點(diǎn)的狀態(tài)，節(jié)點(diǎn)之間完全對(duì)等，不需要任何中心節(jié)點(diǎn)。of3946of3947Gossip協(xié)議的缺點(diǎn)也很明顯冗余通信會(huì)大大增加網(wǎng)絡(luò)和CPU的負(fù)載并進(jìn)一步影響算法收斂的速度10.3Gossip協(xié)議10.3.1Gossip協(xié)議的特點(diǎn)10.3.2Gossip協(xié)議的通信方式及收斂性10.3.3Gossip節(jié)點(diǎn)管理算法10.3.4Cassandra中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.5CoolStreaming系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.6H.F.系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.7Chord網(wǎng)絡(luò)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3Gossip協(xié)議第十章云計(jì)算核心算法(二)Gossip協(xié)議的通信方式及收斂性傳染病算法（EpidemicAlgorithm）中存在三種不同單元：人口（population）交互（asetofinteractive）交流（communicating）這三個(gè)單元通過(guò)既定規(guī)則決定如何傳遞信息。規(guī)則可以由用戶自由設(shè)定，但是任意單元在特定時(shí)間內(nèi)必須處于以下三種狀態(tài)之一。易受感染（Susceptible）傳染（Infective）恢復(fù)（Recovered）單元不了解信息的內(nèi)容，但可以收到這條信息。單元知道（接收到）信息，按照指定規(guī)則進(jìn)行傳播。單元知道（接收到）信息，但不進(jìn)行轉(zhuǎn)發(fā)。of394910.3Gossip協(xié)議第十章云計(jì)算核心算法(二)Gossip協(xié)議的通信方式及收斂性1．感染-傳染（Susceptible-Infective，SI）該類算法中幾乎每個(gè)單元最初都設(shè)定為感染狀態(tài)，當(dāng)一個(gè)單元接收到更新的信息后立即轉(zhuǎn)為傳染狀態(tài)，并保持這種狀態(tài)直到所有單元都成為傳染狀態(tài)。與SI算法模型不同，SIS算法可以決定在全部人口被傳染前停止傳播。SIR算法和SIS算法唯一區(qū)別是恢復(fù)單元在停止傳播信息之后便不再收到傳染。2．感染—傳染—感染（SIS）3．感染—傳染—恢復(fù)（SIR）of395010.3Gossip協(xié)議10.3.1Gossip協(xié)議的特點(diǎn)10.3.2Gossip協(xié)議的通信方式及收斂性10.3.3Gossip節(jié)點(diǎn)管理算法10.3.4Cassandra中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.5CoolStreaming系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.6H.F.系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.7Chord網(wǎng)絡(luò)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3Gossip協(xié)議第十章云計(jì)算核心算法(二)Gossip節(jié)點(diǎn)管理算法1．節(jié)點(diǎn)加入接觸Contact新加入Newsubscription轉(zhuǎn)發(fā)加入Forwardsubscription保持加入Keepingasubscription運(yùn)行初期，節(jié)點(diǎn)的局部視圖只包含這些接觸記錄當(dāng)一個(gè)節(jié)點(diǎn)收到一個(gè)新加入請(qǐng)求時(shí)，它會(huì)把新節(jié)點(diǎn)的標(biāo)識(shí)符轉(zhuǎn)發(fā)到局部視圖里的所有成員這些被轉(zhuǎn)發(fā)的加入請(qǐng)求或者被某個(gè)節(jié)點(diǎn)保留，或者被轉(zhuǎn)發(fā)，直到一些節(jié)點(diǎn)將其保留才會(huì)消失群體中每個(gè)節(jié)點(diǎn)都會(huì)維護(hù)兩張表：局部視圖（PartialView）、入度視圖（InView）of395210.3Gossip協(xié)議第十章云計(jì)算核心算法(二)2．節(jié)點(diǎn)離開離開機(jī)制是用來(lái)控制節(jié)點(diǎn)局部視圖大小的。機(jī)制的缺陷是一個(gè)節(jié)點(diǎn)可能需要在局部視圖中保存某個(gè)節(jié)點(diǎn)的多個(gè)副本，或者保存自己的ID，此時(shí)只需要把相關(guān)ID刪除即可。Gossip節(jié)點(diǎn)管理算法of395310.3Gossip協(xié)議10.3.1Gossip協(xié)議的特點(diǎn)10.3.2Gossip協(xié)議的通信方式及收斂性10.3.3Gossip節(jié)點(diǎn)管理算法10.3.4Cassandra中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.5CoolStreaming系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.6H.F.系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.7Chord網(wǎng)絡(luò)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3Gossip協(xié)議第十章云計(jì)算核心算法(二)Cassandra中Gossip協(xié)議的具體實(shí)現(xiàn)方式有4臺(tái)機(jī)器，分別用A、B、C、D表示，并且配置它們都是seed節(jié)點(diǎn)，當(dāng)它們同時(shí)啟動(dòng)時(shí)，可能會(huì)出現(xiàn)如下情形。1324A節(jié)點(diǎn)啟動(dòng)了，發(fā)現(xiàn)不存在其他在線節(jié)點(diǎn)，走到步驟c，和任意一個(gè)seed節(jié)點(diǎn)同步，假設(shè)選擇了seed節(jié)點(diǎn)B。B節(jié)點(diǎn)和A節(jié)點(diǎn)完成同步，則認(rèn)為A在線，它將和A同步，由于A是種子，B將不再和其他種子節(jié)點(diǎn)同步。C節(jié)點(diǎn)啟動(dòng)后發(fā)現(xiàn)沒有其他節(jié)點(diǎn)在線，同樣走到步驟c，和任意一個(gè)seed節(jié)點(diǎn)同步，假設(shè)這次恰好選擇了seed節(jié)點(diǎn)D。D節(jié)點(diǎn)和C節(jié)點(diǎn)完成同步，則認(rèn)為C在線，它將和C同步，由于C是種子，D將不再和其他種子節(jié)點(diǎn)同步。of395510.3Gossip協(xié)議第十章云計(jì)算核心算法(二)Cassandra中Gossip協(xié)議的具體實(shí)現(xiàn)方式下面介紹一下Cassandra中Gossip協(xié)議的數(shù)據(jù)結(jié)構(gòu)。Gossip協(xié)議通信的狀態(tài)信息主要有三種：EndPointState

封裝了一個(gè)節(jié)點(diǎn)的所有ApplicationState和HeartBeatState。HeartBeatState

由generation和version組成：generation每次啟動(dòng)都會(huì)變化，用于區(qū)分機(jī)器重啟前后的狀態(tài)；version只能增長(zhǎng)，每次心跳之前進(jìn)行遞增。pplicationState用于表示系統(tǒng)的狀態(tài)，由state和version組成：state表示節(jié)點(diǎn)的狀態(tài)；version是遞增的，每個(gè)對(duì)象表示節(jié)點(diǎn)一種狀態(tài)。of395610.3Gossip協(xié)議10.3.1Gossip協(xié)議的特點(diǎn)10.3.2Gossip協(xié)議的通信方式及收斂性10.3.3Gossip節(jié)點(diǎn)管理算法10.3.4Cassandra中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.5CoolStreaming系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.6H.F.系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.7Chord網(wǎng)絡(luò)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3Gossip協(xié)議第十章云計(jì)算核心算法(二)2．?dāng)?shù)據(jù)表示CoolStreaming系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式（1）伙伴節(jié)點(diǎn)（partner）（2）請(qǐng)求節(jié)點(diǎn)（requester）與活動(dòng)節(jié)點(diǎn)（supplier）節(jié)點(diǎn)和伙伴需要相互知道所緩存的數(shù)據(jù)的內(nèi)容。節(jié)點(diǎn)和伙伴通過(guò)不斷交換BM來(lái)了解相互間的緩存情況。1．節(jié)點(diǎn)管理of395810.3Gossip協(xié)議第十章云計(jì)算核心算法(二)CoolStreaming系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式（1）每個(gè)數(shù)據(jù)塊必須在播放的最大延遲之前獲取，錯(cuò)過(guò)最大延遲的數(shù)據(jù)塊應(yīng)盡可能少。（2）每個(gè)伙伴的帶寬情況不同。如果某個(gè)數(shù)據(jù)塊的提供者越少，就越難滿足最大延遲的要求，因此在CoolStreaming中，采用最少塊優(yōu)先的算法。在CoolStreaming系統(tǒng)中，節(jié)點(diǎn)同樣會(huì)在任意時(shí)刻離開或者中斷。因?yàn)槊總€(gè)節(jié)點(diǎn)既是提供者，也是接收者，所以考慮了兩個(gè)方向的分?jǐn)?shù)。4．錯(cuò)誤恢復(fù)與伙伴節(jié)點(diǎn)優(yōu)化3．?dāng)?shù)據(jù)調(diào)度of395910.3Gossip協(xié)議10.3.1Gossip協(xié)議的特點(diǎn)10.3.2Gossip協(xié)議的通信方式及收斂性10.3.3Gossip節(jié)點(diǎn)管理算法10.3.4Cassandra中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.5CoolStreaming系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.6H.F.系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3.7Chord網(wǎng)絡(luò)中Gossip協(xié)議的具體實(shí)現(xiàn)方式10.3Gossip協(xié)議第十章云計(jì)算核心算法(二)2．共識(shí)機(jī)制HyperledgerFabric系統(tǒng)中Gossip協(xié)議的具體實(shí)現(xiàn)方式（1）鏈碼(Chaincode)（4）排序節(jié)點(diǎn)(Orderer)