云計(jì)算之分布式計(jì)算

1、云計(jì)算之分布式計(jì)算云計(jì)算之分布式計(jì)算內(nèi)容背景分布式計(jì)算批量計(jì)算(非實(shí)時(shí)計(jì)算)實(shí)時(shí)計(jì)算技術(shù)趨勢(shì)第2頁(yè)，共74頁(yè)幻燈片。內(nèi)容背景第2頁(yè)，共74頁(yè)幻燈片。內(nèi)容背景分布式計(jì)算批量計(jì)算(非實(shí)時(shí)計(jì)算)實(shí)時(shí)計(jì)算技術(shù)趨勢(shì)第3頁(yè)，共74頁(yè)幻燈片。內(nèi)容背景第3頁(yè)，共74頁(yè)幻燈片。大數(shù)據(jù)時(shí)代移動(dòng)互聯(lián)網(wǎng)時(shí)代物聯(lián)網(wǎng)互聯(lián)網(wǎng)移動(dòng)互聯(lián)網(wǎng)信息時(shí)代早期：Google現(xiàn)在：Facebook未來：？第4頁(yè)，共74頁(yè)幻燈片。大數(shù)據(jù)時(shí)代移動(dòng)互聯(lián)網(wǎng)時(shí)代第4頁(yè)，共74頁(yè)幻燈片。大數(shù)據(jù)時(shí)代2009年加州大學(xué)研究報(bào)告多少信息？34GB：2019年每個(gè)美國(guó)人每天平均信息消費(fèi)12TB： 2019年每個(gè)美國(guó)人平均年信息消費(fèi)總量3.6ZB：2019年美

2、國(guó)人年信息消費(fèi)總量第5頁(yè)，共74頁(yè)幻燈片。大數(shù)據(jù)時(shí)代2009年加州大學(xué)研究報(bào)告多少信息？第5頁(yè)，共大數(shù)據(jù)時(shí)代2019年IDC研究報(bào)告 Extracting Value from Chaos 1.8ZB：2019年全球被創(chuàng)建和被復(fù)制的數(shù)據(jù)總量50%：數(shù)據(jù)年增長(zhǎng)率2年：數(shù)據(jù)量翻番第6頁(yè)，共74頁(yè)幻燈片。大數(shù)據(jù)時(shí)代2019年IDC研究報(bào)告 Extracting 大數(shù)據(jù)時(shí)代2019年紐約時(shí)報(bào)稱“大數(shù)據(jù)時(shí)代”已經(jīng)降臨，決策行為將日益基于數(shù)據(jù)和分析而作出，而并非基于經(jīng)驗(yàn)和直覺。這不是簡(jiǎn)單的數(shù)據(jù)增多的問題，而是全新的問題。第7頁(yè)，共74頁(yè)幻燈片。大數(shù)據(jù)時(shí)代2019年紐約時(shí)報(bào)稱“大數(shù)據(jù)時(shí)代”已經(jīng)降臨，決分布式

3、環(huán)境第8頁(yè)，共74頁(yè)幻燈片。分布式環(huán)境第8頁(yè)，共74頁(yè)幻燈片。內(nèi)容背景分布式計(jì)算批量計(jì)算(非實(shí)時(shí)計(jì)算)實(shí)時(shí)計(jì)算技術(shù)趨勢(shì)第9頁(yè)，共74頁(yè)幻燈片。內(nèi)容背景第9頁(yè)，共74頁(yè)幻燈片。Google批量處理MapReduce：海量數(shù)據(jù)離線計(jì)算框架Pregel：迭代計(jì)算框架增量處理（準(zhǔn)實(shí)時(shí)計(jì)算）Percolator：數(shù)據(jù)增量更新系統(tǒng)Dremel：數(shù)據(jù)分析系統(tǒng)Tenzing：SQL查詢引擎第10頁(yè)，共74頁(yè)幻燈片。Google批量處理第10頁(yè)，共74頁(yè)幻燈片。Google & ApacheGoogleApache文件系統(tǒng)GFSHDFS分布式數(shù)據(jù)庫(kù)BigTableHBase批量計(jì)算框架MapReduceMapR

4、educe迭代計(jì)算框架PregelHamaSQL查詢引擎TenzingHive第11頁(yè)，共74頁(yè)幻燈片。Google & ApacheGoogleApache文件系Google & Apache 數(shù)據(jù)管理：BigTable/HBase數(shù)據(jù)存儲(chǔ)：GFS/HDFS 計(jì)算框架：MapReduce/ Pregel/Hama查詢引擎：Tenzing/Hive 第12頁(yè)，共74頁(yè)幻燈片。Google & Apache 數(shù)據(jù)管理：BigTable/離線計(jì)算Google數(shù)據(jù)： PB量級(jí)應(yīng)用：數(shù)以百計(jì)爬蟲文檔Web日志倒排索引問題計(jì)算并行數(shù)據(jù)分發(fā)錯(cuò)誤處理第13頁(yè)，共74頁(yè)幻燈片。離線計(jì)算Google數(shù)據(jù)： PB

5、量級(jí)第13頁(yè)，共74頁(yè)幻離線計(jì)算Google2019年Google提出MapReduce批量計(jì)算框架抽象模型MapReduce用戶只需要考慮如何對(duì)數(shù)據(jù)進(jìn)行邏輯處理，而不需要考慮以下細(xì)節(jié)：并行化容錯(cuò)數(shù)據(jù)分布負(fù)載均衡第14頁(yè)，共74頁(yè)幻燈片。離線計(jì)算Google2019年Google提出MapReMapReduce工作流程MasterSlaveSlaveSlave昨天小雨轉(zhuǎn)多云今天多云轉(zhuǎn)陣雨明天小雨轉(zhuǎn)中雨統(tǒng)計(jì)天氣預(yù)報(bào)中每個(gè)字出現(xiàn)的次數(shù)第15頁(yè)，共74頁(yè)幻燈片。MapReduce工作流程MasterSlaveSlaveSMapReduce工作流程MasterSlaveSlaveSlave昨天小雨轉(zhuǎn)多

6、云今天多云轉(zhuǎn)陣雨明天小雨轉(zhuǎn)中雨處理昨天的處理今天的處理明天的小 1雨 1轉(zhuǎn) 1多 1云 1多 1云 1轉(zhuǎn) 1陣 1雨 1小 1雨 2轉(zhuǎn) 1中 1Map計(jì)算第16頁(yè)，共74頁(yè)幻燈片。MapReduce工作流程MasterSlaveSlaveSMapReduce工作流程MasterSlaveSlaveSlave統(tǒng)計(jì)“小” “中”“多”統(tǒng)計(jì)“雨” “云”統(tǒng)計(jì)“轉(zhuǎn)” “陣”小 1雨 1轉(zhuǎn) 1多 1云 1多 1云 1轉(zhuǎn) 1陣 1雨 1小 1雨 2轉(zhuǎn) 1中 1Reduce計(jì)算劃分第17頁(yè)，共74頁(yè)幻燈片。MapReduce工作流程MasterSlaveSlaveSMapReduce工作流程MasterSl

7、aveSlaveSlave小 1中 1小 1多 1雨 1云 1轉(zhuǎn) 1轉(zhuǎn) 1陣 1云 1雨 1轉(zhuǎn) 1雨 2多 1小 1中 1多 1雨 1云 1雨 2轉(zhuǎn) 1轉(zhuǎn) 1陣 1Reduce數(shù)據(jù)傳輸?shù)?8頁(yè)，共74頁(yè)幻燈片。MapReduce工作流程MasterSlaveSlaveSMapReduce工作流程MasterSlaveSlaveSlave小 1，1多 1，1中 1云 1，1雨 1，1，2轉(zhuǎn) 1，1，1陣 1小 2多 2中 1云 2雨 4轉(zhuǎn) 3陣 1統(tǒng)計(jì)任務(wù)完成統(tǒng)計(jì)任務(wù)完成統(tǒng)計(jì)任務(wù)完成任務(wù)完成Reduce計(jì)算第19頁(yè)，共74頁(yè)幻燈片。MapReduce工作流程MasterSlaveSlaveS并行

8、定理Amdahls Law: 對(duì)于工作量為1的問題，若子問題的最大工作量為f，那么并行加速比不超過1/f。洗開水壺(1分鐘)燒開水(15分鐘)拿茶葉(2分鐘)洗茶壺(3分鐘)洗茶杯(2分鐘)泡茶(2分鐘)第20頁(yè)，共74頁(yè)幻燈片。并行定理Amdahls Law: 對(duì)于工作量為1的問題，若并行定理Amdahls Law: 對(duì)于工作量為1的問題，若子問題的最大工作量為f，那么并行加速比不超過1/f。洗開水壺(1分鐘)燒開水(15分鐘)拿茶葉(2分鐘)洗茶壺(3分鐘)洗茶杯(2分鐘)泡茶(2分鐘)1+15+2=18分鐘第21頁(yè)，共74頁(yè)幻燈片。并行定理Amdahls Law: 對(duì)于工作量為1的問題，

9、若并行定理Gustafsons Law: 解決問題的時(shí)間是存在界限的，但是在這個(gè)時(shí)間內(nèi)可以通過增加處理單元處理多個(gè)同類問題，加速比與處理器數(shù)目近似線性關(guān)系.第22頁(yè)，共74頁(yè)幻燈片。并行定理Gustafsons Law: 解決問題的時(shí)間是存技術(shù)分析Perfect：搜索類80%的計(jì)算缺點(diǎn)：處理有向圖模型的算法效率很低有向無(wú)環(huán)圖迭代模型執(zhí)行1執(zhí)行2執(zhí)行4執(zhí)行3第23頁(yè)，共74頁(yè)幻燈片。技術(shù)分析Perfect：搜索類80%的計(jì)算執(zhí)行1執(zhí)行2執(zhí)行4迭代計(jì)算Google迭代計(jì)算PageRank計(jì)算圖遍歷最短路徑第24頁(yè)，共74頁(yè)幻燈片。迭代計(jì)算Google迭代計(jì)算第24頁(yè)，共74頁(yè)幻燈片。迭代計(jì)算Goo

10、gle2019年Google推出Pregel迭代計(jì)算框架BSP模型顯示同步模型SuperStep計(jì)算與通訊分離第25頁(yè)，共74頁(yè)幻燈片。迭代計(jì)算Google2019年Google推出PregePregel工作流程6Node13Node29Node31Node45Node56Node64Node7第26頁(yè)，共74頁(yè)幻燈片。Pregel工作流程6Node13Node29Node31NPregel工作流程MasterSlaveSlaveSlave選取圖中權(quán)值最大的節(jié)點(diǎn)作leader第27頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterSlaveSlaveSlavPregel工作流程MasterS

11、laveSlaveSlave處理Node1，2，3處理Node4，5處理Node6，7Node1：6（4，5，7）Node2：3（3，6）Node3：9（2，4）Node4：1（1，3，5）Node5：5（1，4，6，7）Node6：6（2，5）Node7：4（1，5）6N13N29N31N45N56N64N7Step0：計(jì)算第28頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterSlaveSlaveSlavPregel工作流程MasterNode1：6（4，5，7）Node2：3（3，6）Node3：9（2，4）6N13N29N31N45N56N64N7Step0：通信Node4：6,9N

12、ode5：6Node2：9Node3：3Node6：3Node7：6第29頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：66N13NPregel工作流程MasterNode4：1（1，3，5）Node5：5（1，4，6，7）6N13N29N31N45N56N64N7Step0：通信Node1：1，5Node3：1Node4：5Node5：1Node6：5Node7：5第30頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode4：16N13NPregel工作流程MasterNode6：6（2，5）Node7：4（1，5）6N13N29N31N45N56N64N7Step

13、0：通信Node5：4，6Node1：4Node2：6第31頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode6：66N13NPregel工作流程MasterNode1：6（4，5，7）Node2：3（3，6）Node3：9（2，4）Node4：1（1，3，5）Node5：5（1，4，6，7）Node6：6（2，5）Node7：4（1，5）6N13N29N31N45N56N64N7Step1：計(jì)算Node1：1，4，5Node2：6，9Node3：1，3Node4：5，6，9Node5：1，4，6，6Node6：3，5Node7：5，6第32頁(yè)，共74頁(yè)幻燈片。Pregel工作流程M

14、asterNode1：6Node4Pregel工作流程MasterNode1：6（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：6（1，4，6，7）Node6：6（2，5）Node7：6（1，5）6N13N29N31N45N56N64N7Step1：計(jì)算Node1：1，4，5Node2：6，9Node3：1，3Node4：5，6，9Node5：1，4，6，6Node6：3，5Node7：5，6第33頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：6Node4Pregel工作流程MasterNode1：6（4，5，7）Node

15、2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：6（1，4，6，7）Node6：6（2，5）Node7：6（1，5）6N13N29N31N45N56N64N7Step1：通信Node3：9Node6：9第34頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：6Node4Pregel工作流程MasterNode1：6（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：6（1，4，6，7）Node6：6（2，5）Node7：6（1，5）6N13N29N31N45N56N64N7Step1：通信Node1

16、：9，6Node3：9Node4：6Node5：9Node6：6Node7：6第35頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：6Node4Pregel工作流程MasterNode1：6（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：6（1，4，6，7）Node6：6（2，5）Node7：6（1，5）6N13N29N31N45N56N64N7Step1：通信Node5：6Node1：6第36頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：6Node4Pregel工作流程MasterNode1：6（4，5，

17、7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：6（1，4，6，7）Node6：6（2，5）Node7：6（1，5）6N13N29N31N45N56N64N7Step2：計(jì)算Node1：6，6，9Node3：9，9Node4：6Node5：6，9Node6：6，9Node7：6第37頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：6Node4Pregel工作流程MasterNode1：9（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：9（1，4，6，7）Node6：9（2，5）No

18、de7：6（1，5）6N13N29N31N45N56N64N7Step2：計(jì)算Node1：6，6，9Node3：9，9Node4：6Node5：6，9Node6：6，9Node7：6第38頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：9Node4Pregel工作流程MasterNode1：9（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：9（1，4，6，7）Node6：9（2，5）Node7：6（1，5）6N13N29N31N45N56N64N7Step2：通信Node7：9Node4：9Node5：9第39頁(yè)，共74頁(yè)幻

19、燈片。Pregel工作流程MasterNode1：9Node4Pregel工作流程MasterNode1：9（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：9（1，4，6，7）Node6：9（2，5）Node7：6（1，5）6N13N29N31N45N56N64N7Step2：通信Node1：9Node4：9Node6：9Node7：9第40頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：9Node4Pregel工作流程MasterNode1：9（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1

20、，3，5）Node5：9（1，4，6，7）Node6：9（2，5）Node7：6（1，5）6N13N29N31N45N56N64N7Step2：通信Node5：9Node2：9第41頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：9Node4Pregel工作流程MasterNode1：9（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：9（1，4，6，7）Node6：9（2，5）Node7：6（1，5）6N13N29N31N45N56N64N7Step3：計(jì)算Node1：9Node2：9Node4：9，9Node5：9，9No

21、de6：9Node7：9，9第42頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：9Node4Pregel工作流程MasterNode1：9（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：9（1，4，6，7）Node6：9（2，5）Node7：9（1，5）6N13N29N31N45N56N64N7Step3：計(jì)算Node1：9Node2：9Node4：9，9Node5：9，9Node6：9Node7：9，9第43頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：9Node4Pregel工作流程MasterNod

22、e1：9（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：9（1，4，6，7）Node6：9（2，5）Node7：9（1，5）6N13N29N31N45N56N64N7Step3：通信Node5：9Node1：9第44頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：9Node4Pregel工作流程MasterNode1：9（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：9（1，4，6，7）Node6：9（2，5）Node7：9（1，5）6N13N29N31N45N56N64

23、N7Step4：計(jì)算Node5：9Node1：9第45頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：9Node4Pregel工作流程MasterNode1：9（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：9（1，4，6，7）Node6：9（2，5）Node7：9（1，5）6N13N29N31N45N56N64N7Step4：通信第46頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：9Node4Pregel工作流程MasterNode1：9（4，5，7）Node2：9（3，6）Node3：9（2，4）Nod

24、e4：9（1，3，5）Node5：9（1，4，6，7）Node6：9（2，5）Node7：9（1，5）計(jì)算結(jié)束任務(wù)完成第47頁(yè)，共74頁(yè)幻燈片。Pregel工作流程MasterNode1：9Node4技術(shù)分析算法的有向無(wú)環(huán)圖（DAG）模型T1T2T3T4T5T6T1.a1=T2.b1T3.c1=T4.d1T7T5.e1=T6.f1第48頁(yè)，共74頁(yè)幻燈片。技術(shù)分析算法的有向無(wú)環(huán)圖（DAG）模型T1T2T3T4T5T微軟DryadDryad：DAG模型計(jì)算平臺(tái)2009年公布學(xué)術(shù)版2019年公測(cè)2019年放棄，轉(zhuǎn)投Hadoop第49頁(yè)，共74頁(yè)幻燈片。微軟DryadDryad：DAG模型計(jì)算平臺(tái)第

25、49頁(yè)，共74Dryad工作流程MasterSlaveSlaveSlave（T1 join T2）join（T3 join T4）第50頁(yè)，共74頁(yè)幻燈片。Dryad工作流程MasterSlaveSlaveSlaveDryad工作流程MasterSlaveSlaveSlave處理T1 join T2處理T1 join T2處理T3 join T4數(shù)據(jù)傳輸數(shù)據(jù)傳輸?shù)?1頁(yè)，共74頁(yè)幻燈片。Dryad工作流程MasterSlaveSlaveSlaveDryad工作流程MasterSlaveSlaveSlave處理T5 join T6處理T5 join T6處理T5 join T6數(shù)據(jù)傳輸數(shù)據(jù)傳輸?shù)?/p>

26、52頁(yè)，共74頁(yè)幻燈片。Dryad工作流程MasterSlaveSlaveSlaveDryad工作流程MasterSlaveSlaveSlave任務(wù)完成第53頁(yè)，共74頁(yè)幻燈片。Dryad工作流程MasterSlaveSlaveSlave總結(jié)3類模型簡(jiǎn)單模型：MapReduce迭代模型：PregelDAG模型：Dryad第54頁(yè)，共74頁(yè)幻燈片?？偨Y(jié)3類模型第54頁(yè)，共74頁(yè)幻燈片。內(nèi)容背景分布式計(jì)算批量計(jì)算(非實(shí)時(shí)計(jì)算)實(shí)時(shí)計(jì)算技術(shù)趨勢(shì)第55頁(yè)，共74頁(yè)幻燈片。內(nèi)容背景第55頁(yè)，共74頁(yè)幻燈片。GoogleTenzingSQL查詢引擎：借鑒于Hive反應(yīng)時(shí)間：秒編譯：MR執(zhí)行計(jì)劃優(yōu)化：MR框

27、架工作過程：同MR數(shù)據(jù)管理：BigTable/HBase數(shù)據(jù)存儲(chǔ)：GFS/HDFS 計(jì)算框架：MapReduce/ Pregel/Hama查詢引擎：Tenzing/Hive 第56頁(yè)，共74頁(yè)幻燈片。GoogleTenzingSQL查詢引擎：借鑒于HiveFaceBookStorm實(shí)時(shí)計(jì)算系統(tǒng)分布式的容錯(cuò)編程模型：DAG模型（topology）點(diǎn)：bolt邊：stream第57頁(yè)，共74頁(yè)幻燈片。FaceBookStorm實(shí)時(shí)計(jì)算系統(tǒng)第57頁(yè)，共74頁(yè)Storm工作流程MasterSlaveSlaveSlave書籍推薦topology第58頁(yè)，共74頁(yè)幻燈片。Storm工作流程MasterSl

28、aveSlaveSlaveStorm工作流程Master解析用戶行為bolt1處理用戶行為bolt2處理用戶行為bolt3第59頁(yè)，共74頁(yè)幻燈片。Storm工作流程Master解析用戶行為bolt1處理用戶Storm工作流程MasterBolt1用戶行為解析Bolt2書籍購(gòu)買處理Bolt3異常行為處理輸入發(fā)生書籍購(gòu)買發(fā)生異常行為輸出第60頁(yè)，共74頁(yè)幻燈片。Storm工作流程MasterBolt1Bolt2Bolt3Storm工作流程MasterBolt1用戶行為解析Bolt2書籍購(gòu)買處理Bolt3異常行為處理A買了一本C+編程入門第61頁(yè)，共74頁(yè)幻燈片。Storm工作流程MasterBolt1Bolt2Bolt3Storm工作流程MasterBolt1用戶行為解析Bolt2書籍購(gòu)買處理Bolt3異常行為處理C+編程入門第62頁(yè)，共74頁(yè)幻燈片。Storm工作流程MasterBolt1Bolt2Bolt3Storm工作流程MasterBolt1用戶行為解析Bolt3異常行為處理Bolt2找到跟C+編