云计算之分布式计算.ppt

云计算之分布式计算,内容,背景分布式计算批量计算(非实时计算)实时计算技术趋势,内容,背景分布式计算批量计算(非实时计算)实时计算技术趋势,大数据时代,移动互联网时代物联网互联网移动互联网信息时代早期：Google现在：Facebook未来：？,大数据时代,2009年加州大学研究报告多少信息？34GB：2008年每个美国人每天平均信息消费12TB：2008年每个美国人平均年信息消费总量3.6ZB：2008年美国人年信息消费总量,大数据时代,2011年IDC研究报告 Extracting Value from Chaos 1.8ZB：2011年全球被创建和被复制的数据总量50%：数据年增长率2年：数据量翻番,大数据时代,2012年纽约时报称“大数据时代”已经降临，决策行为将日益基于数据和分析而作出，而并非基于经验和直觉。这不是简单的数据增多的问题，而是全新的问题。,分布式环境,内容,背景分布式计算批量计算(非实时计算)实时计算技术趋势,Google,批量处理MapReduce：海量数据离线计算框架Pregel：迭代计算框架增量处理（准实时计算）Percolator：数据增量更新系统Dremel：数据分析系统Tenzing：SQL查询引擎,Google&Apache,Google&Apache,数据管理：BigTable/HBase数据存储：GFS/HDFS,计算框架：MapReduce/Pregel/Hama,查询引擎：Tenzing/Hive,离线计算Google,数据：PB量级应用：数以百计爬虫文档Web日志倒排索引问题计算并行数据分发错误处理,离线计算Google,2003年Google提出MapReduce批量计算框架抽象模型MapReduce用户只需要考虑如何对数据进行逻辑处理，而不需要考虑以下细节：并行化容错数据分布负载均衡,MapReduce工作流程,Master,Slave,Slave,Slave,昨天小雨转多云,今天多云转阵雨,明天小雨转中雨,统计天气预报中每个字出现的次数,MapReduce工作流程,Master,Slave,Slave,Slave,昨天小雨转多云,今天多云转阵雨,明天小雨转中雨,处理昨天的,处理今天的,处理明天的,小 1雨 1转 1多 1云 1,多 1云 1转 1阵 1雨 1,小 1雨 2转 1中 1,Map计算,MapReduce工作流程,Master,Slave,Slave,Slave,统计“小”“中”“多”,统计“雨”“云”,统计“转”“阵”,小 1雨 1转 1多 1云 1,多 1云 1转 1阵 1雨 1,小 1雨 2转 1中 1,Reduce计算划分,MapReduce工作流程,Master,Slave,Slave,Slave,小 1中 1,小 1多 1,雨 1云 1,转 1,转 1阵 1,云 1雨 1,转 1,雨 2,多 1,小 1中 1,多 1,雨 1云 1,雨 2,转 1,转 1阵 1,Reduce数据传输,MapReduce工作流程,Master,Slave,Slave,Slave,小 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分钟),泡茶(2分钟),1+15+2=18分钟,并行定理,Gustafsons Law:解决问题的时间是存在界限的，但是在这个时间内可以通过增加处理单元处理多个同类问题，加速比与处理器数目近似线性关系.,技术分析,Perfect：搜索类80%的计算缺点：处理有向图模型的算法效率很低有向无环图迭代模型,执行1,执行2,执行4,执行3,迭代计算Google,迭代计算PageRank计算图遍历最短路径,迭代计算Google,2010年Google推出Pregel迭代计算框架BSP模型显示同步模型SuperStep计算与通讯分离,Pregel工作流程,Node1,Node2,Node3,Node4,Node5,Node6,Node7,Pregel工作流程,Master,Slave,Slave,Slave,选取图中权值最大的节点作leader,Pregel工作流程,Master,Slave,Slave,Slave,处理Node1，2，3,处理Node4，5,处理Node6，7,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step0：计算,Pregel工作流程,Master,Node1：6（4，5，7）Node2：3（3，6）Node3：9（2，4）,N1,N2,N3,N4,N5,N6,N7,Step0：通信,Node4：6,9Node5：6,Node2：9Node3：3,Node6：3Node7：6,Pregel工作流程,Master,Node4：1（1，3，5）Node5：5（1，4，6，7）,N1,N2,N3,N4,N5,N6,N7,Step0：通信,Node1：1，5Node3：1,Node4：5Node5：1,Node6：5Node7：5,Pregel工作流程,Master,Node6：6（2，5）Node7：4（1，5）,N1,N2,N3,N4,N5,N6,N7,Step0：通信,Node5：4，6,Node1：4Node2：6,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step1：计算,Node1：1，4，5Node2：6，9Node3：1，3,Node4：5，6，9Node5：1，4，6，6,Node6：3，5Node7：5，6,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step1：计算,Node1：1，4，5Node2：6，9Node3：1，3,Node4：5，6，9Node5：1，4，6，6,Node6：3，5Node7：5，6,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step1：通信,Node3：9,Node6：9,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step1：通信,Node1：9，6Node3：9,Node4：6Node5：9,Node6：6Node7：6,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step1：通信,Node5：6,Node1：6,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step2：计算,Node1：6，6，9Node3：9，9,Node4：6Node5：6，9,Node6：6，9Node7：6,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step2：计算,Node1：6，6，9Node3：9，9,Node4：6Node5：6，9,Node6：6，9Node7：6,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step2：通信,Node7：9,Node4：9Node5：9,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step2：通信,Node1：9,Node4：9,Node6：9Node7：9,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step2：通信,Node5：9,Node2：9,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step3：计算,Node1：9Node2：9,Node4：9，9Node5：9，9,Node6：9Node7：9，9,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step3：计算,Node1：9Node2：9,Node4：9，9Node5：9，9,Node6：9Node7：9，9,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step3：通信,Node5：9,Node1：9,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step4：计算,Node5：9,Node1：9,Pregel工作流程,Master,Node1：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）,N1,N2,N3,N4,N5,N6,N7,Step4：通信,Pregel工作流程,Master,Node1：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）模型,T1,T2,T3,T4,T5,T6,T1.a1=T2.b1,T3.c1=T4.d1,T7,T5.e1=T6.f1,微软Dryad,Dryad：DAG模型计算平台2009年公布学术版2010年公测2011年放弃，转投Hadoop,Dryad工作流程,Master,Slave,Slave,Slave,（T1 join T2）join（T3 join T4）,Dryad工作流程,Master,Slave,Slave,Slave,处理T1 join T2,处理T1 join T2,处理T3 join T4,数据传输,数据传输,Dryad工作流程,Master,Slave,Slave,Slave,处理T5 join T6,处理T5 join T6,处理T5 join T6,数据传输,数据传输,Dryad工作流程,Master,Slave,Slave,Slave,任务完成,总结,3类模型简单模型：MapReduce迭代模型：PregelDAG模型：Dryad,内容,背景分布式计算批量计算(非实时计算)实时计算技术趋势,GoogleTenzing,SQL查询引擎：借鉴于Hive反应时间：秒编译：MR执行计划优化：MR框架工作过程：同MR,数据管理：BigTable/HBase数据存储：GFS/HDFS,计算框架：MapReduce/Pregel/Hama,查询引擎：Tenzing/Hive,FaceBookStorm,实时计算系统分布式的容错编程模型：DAG模型（topology）点：bolt边：stream,Storm工作流程,Master,Slave,Slave,Slave,书籍推荐topology,Storm工作流程,Master,解析用户行为bolt1,处理用户行为bolt2,处理用户行为bolt3,Storm工作流程,Master,Bolt1用户行为解析,Bolt2书籍购买处理,Bolt3异常行为处理,输入,发生书籍购买,发生异常行为,输出,Storm工作流程,Master,Bolt1用户行为解析,Bolt2书籍购买处理,Bolt3异常行为处理,A买了一本C+编程入门,Storm工作流程,Master,Bolt1用户行为解析,Bolt2书籍购买处理,Bolt3异常行为处理,C+编程入门,Storm工作流程,Master,Bolt1用户行为解析,Bolt3异常行为处理,Bolt2找到跟C+编程入门相关的书籍C+编程实例,Storm工作流程,Master,Bolt1用户行为解析,Bolt2书籍购买处理,Bolt3异常行为处理,C+编程实例,Storm工作流程,Master,Bolt1用户行为解析,Bolt2书籍购买处理,Bolt3异常行为处理,A又买了一本C+编程入门,Storm工作流程,Master,Bolt1用户行为解析,Bolt2书籍购买处理,Bolt3异常行为处理,是不是买错了?,YahooS4,P2P实时计算系统分布式的编程模型：DAG模型点：PE边：XML配置文件,S4工作流程,解析用户行为bolt1,处理用户行为bolt2,处理用户行为bolt3,S4工作流程,Bolt1用户行为解析,Bolt2书籍购买处理,Bolt3异常行为处理,输入,发生书籍购买,发生异常行为,输出,总结,分布式流计算刚刚起步模型相似：DAG细节存在差异：配置、通信,内容,背景分布式计算批量计算(非实时计算)实时计算技术趋势,群雄逐鹿,大数据时代才刚刚开始互联网、移动互联网、物联网企业云、私有云、公有云数据=价值数据的价值随着时间的流逝而降低Google已经先行一步,胜者为王,趋势模型：DAG应用：简洁效率：高功能：强大,