34 云計算配套ppt之三十四第10章 云計算核心算法一

1、of 34電子工業(yè)云計算(第三版)配套課件云 計 算（第三版）CLOUD COMPUTING Third Edition第 10 章云計算核心算法(一)主編：教授電子工業(yè)云計算(第三版)配套課件 本套PPT下載地址：/list.aspx?cid=20云計算的紅寶書書籍購買地址：/item.html?itemID=1469775685&p=-1（包郵且有教授親筆簽名）微信掃描二維碼關注云計算頭條教授、博導、學科帶頭人，清華大學博士?，F任中國云計算專家咨詢委員會中國信息協會大數據分會副會長、工業(yè)與信息化部云計算研究中心

2、專家。主持完成科研項目25項，發(fā)表論文80余篇，出版專業(yè)書籍15本。獲部級科技進步、二等獎4項、三等獎4項。主編了國內第一本云計算教材云計算和第一本云計算編程書籍實戰(zhàn)Hadoop。創(chuàng)辦了知名的中國云計算（）和中國大數據（）網站。曾率隊奪得2002 PennySort國際計算機排序比賽冠軍，兩次奪得全國高?？萍急荣愖罡擢劊⑷螉Z得清華大學科技比賽最高獎。榮獲“全軍十大學習成才標兵”（排名第一）、南京“十大杰出青年”、江蘇省“333高層次人才培養(yǎng)工程”中青年科學技術帶頭人、清華大學“學術新秀”等稱號。云計算的基礎技術是集群技術，支撐集群高效協同

3、工作需要一系列資源和任務調度算法，良好的調度算法可以提高集群處理能力，有效分配資源，加速作業(yè)進度。三種核心算法of434解決分布式環(huán)境下信息高效分發(fā)問題解決分布式網絡的應用層選路問題解決分布式系統中信息一致性問題Gossip協議DHT算法Paxos算法目錄10 . 1Paxos算法10 . 2DHT算法1 0 . 3G o s s i p 協議Paxos算法解決的問題是一個分布式系統如何就某個value（決議）達成一致。Paxos算法作為分布式系統中最著名的算法之一，在目前所有的一致性算法中， 該算法最常用而且被認為是最有效的。云計算第三版配套PPT課件of 3410.110 . 1 . 11

4、0 . 1 . 210 . 1 . 3Paxos算法PaxosPaxos Paxos算法背景知識算法詳解算法舉例10 . 1Paxos算法云計算第三版配套PPT課件Paxos 算法背景知識of834各個processor之間信息的傳遞可以延遲、丟失，但是在這個算法中假設傳達到的信息都是正確的4proposer可以propose（提出）proposal； accepter可以accept（接受）proposal3proposal和value：proposal一般譯為“提案”，value一般譯為“決議”。2processor可以擔任三個角色“proposer”、“accepter”和“l(fā)earne

5、r” 中的一個或多個角色。1云計算第三版配套PPT課件of 3410.110 . 1 . 110 . 1 . 210 . 1 . 3Paxos算法PaxosPaxos Paxos算法背景知識算法詳解算法舉例10 . 1Paxos算法云計算第三版配套PPT課件Paxos 算法詳解Paxos算法的核心是，只要滿足下面三個條件就能保證數據的一致性：of1034value只有被choose之后才能被learners所獲取。3每次只有一個value被choose；2一個value只有在被proposer 提出之后才可以被choose；110 . 1Paxos算法云計算第三版配套PPT課件Paxos 算法

6、詳解 proposer選擇一個編號n，并向accepter多數派發(fā)出一個prepare請求of1134 如果accepter接受到一個accept請求，如果該accepter之前沒有對任何編號大于n的prepare請求做出過promise，則接受該proposal 如果proposer收到了accepter多數派對它所發(fā)出的prepare請求所做的回 應 ， 則 它 發(fā) 出 帶 有 proposal 的 accept 請 求 ，proposal = (num,value)，value為回應所帶回的proposal的value值提出階段 如果accepter接受到的prepare所帶有的編號n比

7、它之前所做出過回應的prepare請求的編號都要高，則該accepter回應proposer一個promise請求階段對一個p r o p o s a l 的提出和接受做一個系統的描述，這個過程分為請求和提出兩個階段。10 . 1Paxos算法云計算第三版配套PPT課件Paxos 算法詳解PR：prepare request（假設p1到a3的PR丟失）a1和a2是第一次接受到prepare請求，所以返回promise（不帶回proposal），此時p1收到了a1和a2的promise，但是根據提出階段的proposer必須接受來自多數派的promise才可以提出accept 請求，因此不會出現

8、先前例子中的情況。of1234a1PRPRp1a2PRa3云計算第三版配套PPT課件of 3410.110 . 1 . 110 . 1 . 210 . 1 . 3Paxos算法PaxosPaxos Paxos算法背景知識算法詳解算法舉例10 . 1Paxos算法云計算第三版配套PPT課件Paxos 算法舉例 步驟一S1選定編號1（假設第一個命令編號為1），向集合database=s2, s3, s4, s5 的一個多數派子集發(fā)送PrepareS2（Accepter）Request（PR） Prepare Request S3（Accepter） Prepare Request Prepare

9、Request S4（Accepter）S1（Proposer） Prepare Request S5（Accepter）of143410 . 1Paxos算法云計算第三版配套PPT課件Paxos 算法舉例 步驟二 如果通信順利，所有的多數派都收到了PR 如果通信部分失敗導致接受到PR的節(jié)點不構成多數派則S1重復步驟1S2（Accepter）（PR編號遞增） Promise Proposal S3（Accepter）S4（Accepter）S1（Proposer） Promise Proposal S5（Accepter）of1534Promise ProposalPromise Propos

10、al10 . 1Paxos算法云計算第三版配套PPT課件Paxos 算法舉例 步驟三S1接收到多數派的Paromise，向集合database發(fā)出帶有第一個SQL命令（這里的SQL命令就是之前的value）的Proposal，編號為1，因為Promise沒有帶回Proposal所以這里的SQL命令沒有限制。of163410 . 1Paxos算法云計算第三版配套PPT課件Paxos 算法舉例 步驟四通信順利接收Proposal決議產生S2（Accepter）構成多數派通信失敗決議不產生不構成多數派S3（Accepter） SQL SQL SQL S1（Proposer） SQL S4（Accep

11、ter）S5（Accepter）of173410 . 1Paxos算法云計算第三版配套PPT課件Paxos 算法舉例 步驟五重復以上操作，注意Proposal、Prepare以及Promise的編號遞增，以及Promise根據情況帶回Proposal。of1834目錄10 . 1Paxos算法10 . 2DHT算法1 0 . 3G o s s i p 協議10 . 2DHT算法云計算第三版配套PPT課件of2034 集中式計算模式對用戶的隱私以及數據安全也將存在不可能解決的難題。 大部分的計算都集中在服務器端，因而引起負載的不平衡。即所謂的“服務器端的計算瓶頸”，而客戶機端則存在資源浪費的情況

12、。 Client/Server計算模式采用中央集中式架構，中央節(jié)點（服務器）對整個網絡服務具有決定性的作用。 Client/Server計算模式（即客戶服務器計算模式）主要應用于小規(guī)模的網絡環(huán)境。10 . 2DHT算法云計算第三版配套PPT課件P2P計算模式是一種非集中計算模式。P2P網絡中的每臺計算機（或稱對等點），具有同樣的地位，既可以請求服務，也可以提供服務。P2P計算模式具有資源充分利用，網絡規(guī)?？蓴U展（節(jié)點越多網絡越穩(wěn)定，不存在瓶頸）等優(yōu)點。下一代計算機網絡（即云計算和物聯網）都是巨大的網絡，因此，未來的計算模式應該是P2P計算模式of213410 . 2DHT算法云計算第三版配套P

13、PT課件P2P按照拓撲結構的不同可以分為三種：of2234由于用戶預先知道應該搜索哪些節(jié)點，避免了非結構化P2P系統中使用的泛洪式查找，提高了信息搜索的效率。分布式結構化拓撲模式在非結構化P2P系統中，信息搜索的算法難免會帶有一定的盲目性。分布式非結構化拓撲模式這種模式必須有中央服務器。當系統中節(jié)點數增多時， 中央服務器就成為系統的瓶頸。集中式拓撲模式云計算第三版配套PPT課件of 3410.210 . 2 . 110 . 2 . 210 . 2 . 310 . 2 . 410 . 2 . 5DHT算法DHT原理介紹Chord中DHT的具體實現Pastr y中DHT的具體實現CAN中DHT的具

14、體實現Tapestr y中DHT的具體實現10 . 2DHT算法云計算第三版配套PPT課件DHT原理介紹DHT分布式哈希表采用Hash函數加速了查找速度和增強了安全性，而且便于管理，同時不會占用太多的網絡帶寬 網絡存儲 其他應用應用層DHT層 DHT網絡層 TCP/IPDHT技術的基本概念of243410 . 2DHT算法云計算第三版配套PPT課件DHT原理介紹通過DHT層的LookUp(Key)操作，可以把應用層的數據均勻分布在網絡的各個節(jié)點內，這種方法使下層網絡完全不受中心控制Insert（Key，data）LookUp（Key） Node NodeDHT應用層的接口 Node of253

15、4DHT應用層10 . 2DHT算法云計算第三版配套PPT課件DHT原理介紹所有的DHT路由算法都主要包括三個方面: 第一方面 第二方面 第三方面of2634即對散列值進行查詢時節(jié)點如何高效地路由到存儲目標信息的節(jié)點即散列后的信息如何決定其存儲的節(jié)點位置即如何進行散列路由發(fā)現算法DHT中各節(jié)點如何分配管理散列空間DHT的散列值空間的描述 百度排名首位的大數據資料和交流中心 百度排名首位的云計算資料和交流中心 終生免費的智能硬件大數據托管平臺 掃一掃，進入萬物云 終 生 免 費 的 環(huán) 境 大 數 據 共 享 平 臺 掃一掃，進入環(huán)境云 高校Hadoop教學科研一攬子解決方案云計算、大數據時代，社會亟需相關人才！而高校缺平臺、缺人才、缺經驗！怎么辦？云創(chuàng)大數據給您一步到位的解決方案！建設一個Hadoop實驗平臺一套開源的Hadoop一體機和開發(fā)環(huán)境，詳細的指導書籍和實驗設計。培養(yǎng)一支云計算師資隊伍來自云計算高手的系列培訓，早在2010年就培訓了全國第一批云計算師資力量。營造一個大數據科研環(huán)境為科研提供技術支持，與大數據應用相結合，讓科研邁上新臺階。了解詳情 知名微信公眾號推薦 學習云計算必須關注的公眾號看未來 微信號：lpoutlook云計算頭條 微信號： chinacloudnj 資源豐富、分析深入、更新及時的云計算知 識共享平臺。