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

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

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

Paxos算法10.2

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

Paxos算法10.2

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

Paxos算法10.2

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

封裝了一個節(jié)點的所有ApplicationState和HeartBeatState。HeartBeatState

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