云計算之分布式計算

1、云計算之分布式計算內(nèi)容背景分布式計算批量計算(非實時計算)實時計算技術(shù)趨勢內(nèi)容背景分布式計算批量計算(非實時計算)實時計算技術(shù)趨勢大數(shù)據(jù)時代移動互聯(lián)網(wǎng)時代物聯(lián)網(wǎng)互聯(lián)網(wǎng)移動互聯(lián)網(wǎng)信息時代早期：Google現(xiàn)在：Facebook未來：？大數(shù)據(jù)時代2009年加州大學(xué)研究報告多少信息？34GB：2008年每個美國人每天平均信息消費12TB： 2008年每個美國人平均年信息消費總量3.6ZB：2008年美國人年信息消費總量大數(shù)據(jù)時代2011年IDC研究報告 Extracting Value from Chaos 1.8ZB：2011年全球被創(chuàng)建和被復(fù)制的數(shù)據(jù)總量50%：數(shù)據(jù)年增長率2年：數(shù)據(jù)量翻番大數(shù)據(jù)

2、時代2012年紐約時報稱“大數(shù)據(jù)時代”已經(jīng)降臨，決策行為將日益基于數(shù)據(jù)和分析而作出，而并非基于經(jīng)驗和直覺。這不是簡單的數(shù)據(jù)增多的問題，而是全新的問題。分布式環(huán)境內(nèi)容背景分布式計算批量計算(非實時計算)實時計算技術(shù)趨勢Google批量處理MapReduce：海量數(shù)據(jù)離線計算框架Pregel：迭代計算框架增量處理（準(zhǔn)實時計算）Percolator：數(shù)據(jù)增量更新系統(tǒng)Dremel：數(shù)據(jù)分析系統(tǒng)Tenzing：SQL查詢引擎Google & ApacheGoogle & Apache 數(shù)據(jù)管理：BigTable/HBase數(shù)據(jù)存儲：GFS/HDFS 計算框架：MapReduce/ Pregel/Hama

3、查詢引擎：Tenzing/Hive 離線計算Google數(shù)據(jù)： PB量級應(yīng)用：數(shù)以百計爬蟲文檔Web日志倒排索引問題計算并行數(shù)據(jù)分發(fā)錯誤處理離線計算Google2003年Google提出MapReduce批量計算框架抽象模型MapReduce用戶只需要考慮如何對數(shù)據(jù)進(jìn)行邏輯處理，而不需要考慮以下細(xì)節(jié)：并行化容錯數(shù)據(jù)分布負(fù)載均衡MapReduce工作流程MasterSlaveSlaveSlave昨天小雨轉(zhuǎn)多云今天多云轉(zhuǎn)陣雨明天小雨轉(zhuǎn)中雨統(tǒng)計天氣預(yù)報中每個字出現(xiàn)的次數(shù)MapReduce工作流程MasterSlaveSlaveSlave昨天小雨轉(zhuǎn)多云今天多云轉(zhuǎn)陣雨明天小雨轉(zhuǎn)中雨處理昨天的處理今天的處

4、理明天的小 1雨 1轉(zhuǎn) 1多 1云 1多 1云 1轉(zhuǎn) 1陣 1雨 1小 1雨 2轉(zhuǎn) 1中 1Map計算MapReduce工作流程MasterSlaveSlaveSlave統(tǒng)計“小” “中”“多”統(tǒng)計“雨” “云”統(tǒng)計“轉(zhuǎn)” “陣”小 1雨 1轉(zhuǎn) 1多 1云 1多 1云 1轉(zhuǎn) 1陣 1雨 1小 1雨 2轉(zhuǎn) 1中 1Reduce計算劃分MapReduce工作流程MasterSlaveSlaveSlave小 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ù)傳輸MapReduce工作流程MasterS

5、laveSlaveSlave小 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)計任務(wù)完成統(tǒng)計任務(wù)完成統(tǒng)計任務(wù)完成任務(wù)完成Reduce計算并行定理Amdahls Law: 對于工作量為1的問題，若子問題的最大工作量為f，那么并行加速比不超過1/f。洗開水壺(1分鐘)燒開水(15分鐘)拿茶葉(2分鐘)洗茶壺(3分鐘)洗茶杯(2分鐘)泡茶(2分鐘)并行定理Amdahls Law: 對于工作量為1的問題，若子問題的最大工作量為f，那么并行加速比不超過1/f。洗開水壺(1分鐘)燒開水(15分鐘)拿茶葉(2分鐘)洗茶壺(3分鐘)洗茶杯(2分鐘

6、)泡茶(2分鐘)1+15+2=18分鐘并行定理Gustafsons Law: 解決問題的時間是存在界限的，但是在這個時間內(nèi)可以通過增加處理單元處理多個同類問題，加速比與處理器數(shù)目近似線性關(guān)系.技術(shù)分析Perfect：搜索類80%的計算缺點：處理有向圖模型的算法效率很低有向無環(huán)圖迭代模型執(zhí)行1執(zhí)行2執(zhí)行4執(zhí)行3迭代計算Google迭代計算PageRank計算圖遍歷最短路徑迭代計算Google2010年Google推出Pregel迭代計算框架BSP模型顯示同步模型SuperStep計算與通訊分離Pregel工作流程6Node13Node29Node31Node45Node56Node64Node7

7、Pregel工作流程MasterSlaveSlaveSlave選取圖中權(quán)值最大的節(jié)點作leaderPregel工作流程MasterSlaveSlaveSlave處理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：計算Pregel工作流程MasterNode1：6（4，5，7）Node2：3（3，6）Node3：9（2，4）6N13N29N31N45N56

8、N64N7Step0：通信Node4：6,9Node5：6Node2：9Node3：3Node6：3Node7：6Pregel工作流程MasterNode4：1（1，3，5）Node5：5（1，4，6，7）6N13N29N31N45N56N64N7Step0：通信Node1：1，5Node3：1Node4：5Node5：1Node6：5Node7：5Pregel工作流程MasterNode6：6（2，5）Node7：4（1，5）6N13N29N31N45N56N64N7Step0：通信Node5：4，6Node1：4Node2：6Pregel工作流程MasterNode1：6（4，5，7）No

9、de2：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：計算Node1：1，4，5Node2：6，9Node3：1，3Node4：5，6，9Node5：1，4，6，6Node6：3，5Node7：5，6Pregel工作流程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）6N13N29N31N45N56

10、N64N7Step1：計算Node1：1，4，5Node2：6，9Node3：1，3Node4：5，6，9Node5：1，4，6，6Node6：3，5Node7：5，6Pregel工作流程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：通信Node3：9Node6：9Pregel工作流程MasterNode1：6（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3

11、，5）Node5：6（1，4，6，7）Node6：6（2，5）Node7：6（1，5）6N13N29N31N45N56N64N7Step1：通信Node1：9，6Node3：9Node4：6Node5：9Node6：6Node7：6Pregel工作流程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：6Pregel工作流程MasterNode1：6（4，5，7）Nod

12、e2：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：計算Node1：6，6，9Node3：9，9Node4：6Node5：6，9Node6：6，9Node7：6Pregel工作流程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：6

13、，6，9Node3：9，9Node4：6Node5：6，9Node6：6，9Node7：6Pregel工作流程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：9Pregel工作流程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）N

14、ode7：6（1，5）6N13N29N31N45N56N64N7Step2：通信Node1：9Node4：9Node6：9Node7：9Pregel工作流程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：通信Node5：9Node2：9Pregel工作流程MasterNode1：9（4，5，7）Node2：9（3，6）Node3：9（2，4）Node4：9（1，3，5）Node5：9（1，4，6

15、，7）Node6：9（2，5）Node7：6（1，5）6N13N29N31N45N56N64N7Step3：計算Node1：9Node2：9Node4：9，9Node5：9，9Node6：9Node7：9，9Pregel工作流程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：計算Node1：9Node2：9Node4：9，9Node5：9，9Node6：9Node7：9，9Pregel工作流程M

16、asterNode1：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：9Pregel工作流程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：計算Node5：9Node1：9Pregel工作流

17、程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：通信Pregel工作流程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）計算結(jié)束任務(wù)完成技術(shù)分析算法的有向無環(huán)圖（DAG）模型T1T2T3T4T5T6T1.a1=T2.b1T3.c1=T4.d1T7T

18、5.e1=T6.f1微軟DryadDryad：DAG模型計算平臺2009年公布學(xué)術(shù)版2010年公測2011年放棄，轉(zhuǎn)投HadoopDryad工作流程MasterSlaveSlaveSlave（T1 join T2）join（T3 join T4）Dryad工作流程MasterSlaveSlaveSlave處理T1 join T2處理T1 join T2處理T3 join T4數(shù)據(jù)傳輸數(shù)據(jù)傳輸Dryad工作流程MasterSlaveSlaveSlave處理T5 join T6處理T5 join T6處理T5 join T6數(shù)據(jù)傳輸數(shù)據(jù)傳輸Dryad工作流程MasterSlaveSlaveSlav

19、e任務(wù)完成總結(jié)3類模型簡單模型：MapReduce迭代模型：PregelDAG模型：Dryad內(nèi)容背景分布式計算批量計算(非實時計算)實時計算技術(shù)趨勢GoogleTenzingSQL查詢引擎：借鑒于Hive反應(yīng)時間：秒編譯：MR執(zhí)行計劃優(yōu)化：MR框架工作過程：同MR數(shù)據(jù)管理：BigTable/HBase數(shù)據(jù)存儲：GFS/HDFS 計算框架：MapReduce/ Pregel/Hama查詢引擎：Tenzing/Hive FaceBookStorm實時計算系統(tǒng)分布式的容錯編程模型：DAG模型（topology）點：bolt邊：streamStorm工作流程MasterSlaveSlaveSlave書籍推薦topologyStorm工作流程Master解析用戶行為bolt1處理用戶行為bolt2處理用戶行為bolt3Storm工作流程MasterBolt1用戶行為解析Bolt2書籍購買處理Bolt3異常行為處理輸入發(fā)生書籍購買