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

1、of 34電子工業(yè)云計(jì)算(第三版)配套課件云 計(jì) 算（第三版）CLOUD COMPUTING Third Edition第 10 章云計(jì)算核心算法(一)主編：教授電子工業(yè)云計(jì)算(第三版)配套課件 本套PPT下載地址：/list.aspx?cid=20云計(jì)算的紅寶書(shū)書(shū)籍購(gòu)買(mǎi)地址：/item.html?itemID=1469775685&p=-1（包郵且有教授親筆簽名）微信掃描二維碼關(guān)注云計(jì)算頭條教授、博導(dǎo)、學(xué)科帶頭人，清華大學(xué)博士。現(xiàn)任中國(guó)云計(jì)算專(zhuān)家咨詢(xún)委員會(huì)中國(guó)信息協(xié)會(huì)大數(shù)據(jù)分會(huì)副會(huì)長(zhǎng)、工業(yè)與信息化部云計(jì)算研究中心

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

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

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

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

6、詳解 proposer選擇一個(gè)編號(hào)n，并向accepter多數(shù)派發(fā)出一個(gè)prepare請(qǐng)求of1134 如果accepter接受到一個(gè)accept請(qǐng)求，如果該accepter之前沒(méi)有對(duì)任何編號(hào)大于n的prepare請(qǐng)求做出過(guò)promise，則接受該proposal 如果proposer收到了accepter多數(shù)派對(duì)它所發(fā)出的prepare請(qǐng)求所做的回 應(yīng) ， 則 它 發(fā) 出 帶 有 proposal 的 accept 請(qǐng) 求 ，proposal = (num,value)，value為回應(yīng)所帶回的proposal的value值提出階段 如果accepter接受到的prepare所帶有的編號(hào)n比

7、它之前所做出過(guò)回應(yīng)的prepare請(qǐng)求的編號(hào)都要高，則該accepter回應(yīng)proposer一個(gè)promise請(qǐng)求階段對(duì)一個(gè)p r o p o s a l 的提出和接受做一個(gè)系統(tǒng)的描述，這個(gè)過(guò)程分為請(qǐng)求和提出兩個(gè)階段。10 . 1Paxos算法云計(jì)算第三版配套PPT課件Paxos 算法詳解PR：prepare request（假設(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)

8、先前例子中的情況。of1234a1PRPRp1a2PRa3云計(jì)算第三版配套PPT課件of 3410.110 . 1 . 110 . 1 . 210 . 1 . 3Paxos算法PaxosPaxos Paxos算法背景知識(shí)算法詳解算法舉例10 . 1Paxos算法云計(jì)算第三版配套PPT課件Paxos 算法舉例 步驟一S1選定編號(hào)1（假設(shè)第一個(gè)命令編號(hào)為1），向集合database=s2, s3, s4, s5 的一個(gè)多數(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算法云計(jì)算第三版配套PPT課件Paxos 算法舉例 步驟二 如果通信順利，所有的多數(shù)派都收到了PR 如果通信部分失敗導(dǎo)致接受到PR的節(jié)點(diǎn)不構(gòu)成多數(shù)派則S1重復(fù)步驟1S2（Accepter）（PR編號(hào)遞增） Promise Proposal S3（Accepter）S4（Accepter）S1（Proposer） Promise Proposal S5（Accepter）of1534Promise ProposalPromise Propos

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

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

12、。 Client/Server計(jì)算模式采用中央集中式架構(gòu)，中央節(jié)點(diǎn)（服務(wù)器）對(duì)整個(gè)網(wǎng)絡(luò)服務(wù)具有決定性的作用。 Client/Server計(jì)算模式（即客戶(hù)服務(wù)器計(jì)算模式）主要應(yīng)用于小規(guī)模的網(wǎng)絡(luò)環(huán)境。10 . 2DHT算法云計(jì)算第三版配套PPT課件P2P計(jì)算模式是一種非集中計(jì)算模式。P2P網(wǎng)絡(luò)中的每臺(tái)計(jì)算機(jī)（或稱(chēng)對(duì)等點(diǎn)），具有同樣的地位，既可以請(qǐng)求服務(wù)，也可以提供服務(wù)。P2P計(jì)算模式具有資源充分利用，網(wǎng)絡(luò)規(guī)?？蓴U(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ì)算模式of213410 . 2DHT算法云計(jì)算第三版配套P

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

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

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