云计算之分布式计算

1、云计算之分布式计算内容背景分布式计算批量计算(非实时计算)实时计算技术趋势内容背景分布式计算批量计算(非实时计算)实时计算技术趋势大数据时代移动互联网时代物联网互联网移动互联网信息时代早期：Google现在：Facebook未来：？大数据时代2009年加州大学研究报告多少信息？34GB：2008年每个美国人每天平均信息消费12TB： 2008年每个美国人平均年信息消费总量3.6ZB：2008年美国人年信息消费总量大数据时代2011年IDC研究报告 Extracting Value from Chaos 1.8ZB：2011年全球被创建和被复制的数据总量50%：数据年增长率2年：数据量翻番大数据

2、时代2012年纽约时报称“大数据时代”已经降临，决策行为将日益基于数据和分析而作出，而并非基于经验和直觉。这不是简单的数据增多的问题，而是全新的问题。分布式环境内容背景分布式计算批量计算(非实时计算)实时计算技术趋势Google批量处理MapReduce：海量数据离线计算框架Pregel：迭代计算框架增量处理（准实时计算）Percolator：数据增量更新系统Dremel：数据分析系统Tenzing：SQL查询引擎Google & ApacheGoogle & Apache 数据管理：BigTable/HBase数据存储：GFS/HDFS 计算框架：MapReduce/ Pregel/Hama

3、查询引擎：Tenzing/Hive 离线计算Google数据： PB量级应用：数以百计爬虫文档Web日志倒排索引问题计算并行数据分发错误处理离线计算Google2003年Google提出MapReduce批量计算框架抽象模型MapReduce用户只需要考虑如何对数据进行逻辑处理，而不需要考虑以下细节：并行化容错数据分布负载均衡MapReduce工作流程MasterSlaveSlaveSlave昨天小雨转多云今天多云转阵雨明天小雨转中雨统计天气预报中每个字出现的次数MapReduce工作流程MasterSlaveSlaveSlave昨天小雨转多云今天多云转阵雨明天小雨转中雨处理昨天的处理今天的处

4、理明天的小 1雨 1转 1多 1云 1多 1云 1转 1阵 1雨 1小 1雨 2转 1中 1Map计算MapReduce工作流程MasterSlaveSlaveSlave统计“小” “中”“多”统计“雨” “云”统计“转” “阵”小 1雨 1转 1多 1云 1多 1云 1转 1阵 1雨 1小 1雨 2转 1中 1Reduce计算划分MapReduce工作流程MasterSlaveSlaveSlave小 1中 1小 1多 1雨 1云 1转 1转 1阵 1云 1雨 1转 1雨 2多 1小 1中 1多 1雨 1云 1雨 2转 1转 1阵 1Reduce数据传输MapReduce工作流程MasterS

5、laveSlaveSlave小 1，1多 1，1中 1云 1，1雨 1，1，2转 1，1，1阵 1小 2多 2中 1云 2雨 4转 3阵 1统计任务完成统计任务完成统计任务完成任务完成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: 解决问题的时间是存在界限的，但是在这个时间内可以通过增加处理单元处理多个同类问题，加速比与处理器数目近似线性关系.技术分析Perfect：搜索类80%的计算缺点：处理有向图模型的算法效率很低有向无环图迭代模型执行1执行2执行4执行3迭代计算Google迭代计算PageRank计算图遍历最短路径迭代计算Google2010年Google推出Pregel迭代计算框架BSP模型显示同步模型SuperStep计算与通讯分离Pregel工作流程6Node13Node29Node31Node45Node56Node64Node7

7、Pregel工作流程MasterSlaveSlaveSlave选取图中权值最大的节点作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）计算结束任务完成技术分析算法的有向无环图（DAG）模型T1T2T3T4T5T6T1.a1=T2.b1T3.c1=T4.d1T7T

18、5.e1=T6.f1微软DryadDryad：DAG模型计算平台2009年公布学术版2010年公测2011年放弃，转投HadoopDryad工作流程MasterSlaveSlaveSlave（T1 join T2）join（T3 join T4）Dryad工作流程MasterSlaveSlaveSlave处理T1 join T2处理T1 join T2处理T3 join T4数据传输数据传输Dryad工作流程MasterSlaveSlaveSlave处理T5 join T6处理T5 join T6处理T5 join T6数据传输数据传输Dryad工作流程MasterSlaveSlaveSlav

19、e任务完成总结3类模型简单模型：MapReduce迭代模型：PregelDAG模型：Dryad内容背景分布式计算批量计算(非实时计算)实时计算技术趋势GoogleTenzingSQL查询引擎：借鉴于Hive反应时间：秒编译：MR执行计划优化：MR框架工作过程：同MR数据管理：BigTable/HBase数据存储：GFS/HDFS 计算框架：MapReduce/ Pregel/Hama查询引擎：Tenzing/Hive FaceBookStorm实时计算系统分布式的容错编程模型：DAG模型（topology）点：bolt边：streamStorm工作流程MasterSlaveSlaveSlave书籍推荐topologyStorm工作流程Master解析用户行为bolt1处理用户行为bolt2处理用户行为bolt3Storm工作流程MasterBolt1用户行为解析Bolt2书籍购买处理Bolt3异常行为处理输入发生书籍购买