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(xiàn)任中國云計算專家咨詢委員會中國信息協(xié)會大數(shù)據(jù)分會副會長、工業(yè)與信息化部云計算研究中心

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

3、工作需要一系列資源和任務調度算法，良好的調度算法可以提高集群處理能力，有效分配資源，加速作業(yè)進度。三種核心算法of434解決分布式環(huán)境下信息高效分發(fā)問題解決分布式網(wǎng)絡的應用層選路問題解決分布式系統(tǒng)中信息一致性問題Gossip協(xié)議DHT算法Paxos算法目錄10 . 1Paxos算法10 . 2DHT算法1 0 . 3G o s s i p 協(xié)議Paxos算法解決的問題是一個分布式系統(tǒng)如何就某個value（決議）達成一致。Paxos算法作為分布式系統(tǒng)中最著名的算法之一，在目前所有的一致性算法中， 該算法最常用而且被認為是最有效的。云計算第三版配套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算法的核心是，只要滿足下面三個條件就能保證數(shù)據(jù)的一致性：of1034value只有被choose之后才能被learners所獲取。3每次只有一個value被choose；2一個value只有在被proposer 提出之后才可以被choose；110 . 1Paxos算法云計算第三版配套PPT課件Paxos 算法

6、詳解 proposer選擇一個編號n，并向accepter多數(shù)派發(fā)出一個prepare請求of1134 如果accepter接受到一個accept請求，如果該accepter之前沒有對任何編號大于n的prepare請求做出過promise，則接受該proposal 如果proposer收到了accepter多數(shù)派對它所發(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 的提出和接受做一個系統(tǒng)的描述，這個過程分為請求和提出兩個階段。10 . 1Paxos算法云計算第三版配套PPT課件Paxos 算法詳解PR：prepare request（假設p1到a3的PR丟失）a1和a2是第一次接受到prepare請求，所以返回promise（不帶回proposal），此時p1收到了a1和a2的promise，但是根據(jù)提出階段的proposer必須接受來自多數(shù)派的promise才可以提出accept 請求，因此不會出現(xiàn)

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 的一個多數(shù)派子集發(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 算法舉例 步驟二 如果通信順利，所有的多數(shù)派都收到了PR 如果通信部分失敗導致接受到PR的節(jié)點不構成多數(shù)派則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接收到多數(shù)派的Paromise，向集合database發(fā)出帶有第一個SQL命令（這里的SQL命令就是之前的value）的Proposal，編號為1，因為Promise沒有帶回Proposal所以這里的SQL命令沒有限制。of163410 . 1Paxos算法云計算第三版配套PPT課件Paxos 算法舉例 步驟四通信順利接收Proposal決議產生S2（Accepter）構成多數(shù)派通信失敗決議不產生不構成多數(shù)派S3（Accepter） SQL SQL SQL S1（Proposer） SQL S4（Accep

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

12、。 Client/Server計算模式采用中央集中式架構，中央節(jié)點（服務器）對整個網(wǎng)絡服務具有決定性的作用。 Client/Server計算模式（即客戶服務器計算模式）主要應用于小規(guī)模的網(wǎng)絡環(huán)境。10 . 2DHT算法云計算第三版配套PPT課件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計算模式of213410 . 2DHT算法云計算第三版配套P

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

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

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