Cloud Computing Google云计算原理

主要内容（6学时） 概念回顾 Google云计算背景 分布式文件系统GFS 并行数据处理模型MapReduce 分布式锁服务Chubby 分布式数据库BigTable Google AppEngine Google云计算技术小结

Google云计算原理 并行数据处理模型MapReduce

并行计算基础 摩尔定律 集成电路芯片上所集成的电路的数目， 每隔18个月就翻一番，同时性能也提升 一倍 集成电路芯片上所集成的电路的数目， 每隔18个月就翻一番，同时性能也提升 一倍 经验总结，12个月-18个月-24个月 Gordon Moore

并行计算基础 “免费的性能大餐”？ 免费的午餐已经结束！！ Andy giveth, and Bill taketh away 软件算法、数据结构似乎不再重要，因为处理器性能不断 提升 免费的午餐已经结束！！ Intel Microsoft

并行计算基础 摩尔定律正在走向终结… 未来的发展：多核 单芯片容纳晶体管的增加，对制造工艺提出要求 CPU制造18nm技术，电子泄漏问题 CPU主频已达3GHz时代，难以继续提高 散热问题（发热太大，且难以驱散） 功耗太高 未来的发展：多核

并行计算基础 在多核时代生存，必须考虑并发问题 不存在解决多核编程问题的银弹， 不存在可以简单地将并发编程问题化 解掉的工具， 开发高性能的并行程序 必须要求开发者从根本上改变其编程 方法 从某种意义上来说，这不仅仅是要改 变50年来顺序程序设计的工艺传统， 而且是要改变数百万年来人类顺序化思考问题的习 惯 Herb Sutter

并行计算基础 串行编程 并行编程 早期的计算里，程序一般是被串行执行的 程序是指令的序列，在单处理器的机器里，程序从开始 到结束，这些指令一条接一条的执行 并行编程 一道处理可以被划分为几部分,然后它们可以并发地执行 各部分的指令分别在不同的CPU上同时运行，这些CPU 可以存在于单台机器中,也可以存在于多台机器上,它们 通过连接起来共同运作

并行计算基础 什么样的问题适合并行计算？ 斐波那契序列(Fibonacci)的计算？

并行计算基础 什么样的问题适合并行计算？ 如果有大量结构一致的数据要处理，且数据可以分解成 相同大小的部分， 那我们就可以设法使这道处理变成并 行

并行计算基础 并行计算模式 Master Worker 并行计算与分布式计算有何联系与区别？

分析搜索趋势(Google Trends) 为什么需要MapReduce？ Google拥有海量数据，并且需要快速处理 Google 全球Web数据 邮件数据 地图数据 卫星照片 …… 对爬虫获取的网页进行倒排索引 计算网站的PageRank 分析搜索趋势(Google Trends) 计算网页的访问量 …… “Greatness is never a given, it Must be earned.” 美国总统奥巴马

为什么需要MapReduce？ 简单的问题，计算并不简单！ 计算问题简单，但求解困难 待处理数据量巨大（PB级），只有分布在成百上千个节点 上并行计算才能在可接受的时间内完成 如何进行并行分布式计算？ 如何分发待处理数据？ 如何处理分布式计算中的错误？ 简单的问题，计算并不简单！

为什么需要MapReduce？ Jeffery Dean设计一个新的抽象模型， 使我们只要执行的简单计算，而将并行化、容错、数据分布、负载均衡的等杂乱细节放在一个库里，使并行编程时不必关心它们 这就是MapReduce Google MapReduce 架构设计师 Jeffrey Dean

MapReduce 一个软件架构，是一种处理海量数据的并行编程模 式 用于大规模数据集（通常大于1TB）的并行运算 MapReduce实现了Map和Reduce两个功能 Map把一个函数应用于集合中的所有成员，然后返回一个 基于这个处理的结果集 Reduce对结果集进行分类和归纳 Map()和 Reduce() 两个函数可能会并行运行，即使不是 在同一的系统的同一时刻

MapReduce示例：单词计数 案例：单词记数问题(Word Count) 给定一个巨大的文本（如1TB），如何计算单词出现的数 目？

MapReduce示例：单词计数 使用MapReduce求解该问题 定义Map和Reduce函数

MapReduce示例：单词计数 使用MapReduce求解该问题 Step 1: 自动对文本进行分割

MapReduce示例：单词计数 使用MapReduce求解该问题 Step 2:在分割之后的每一对<key,value>进行用户定义 的Map进行处理，再生成新的<key,value>对

MapReduce示例：单词计数 使用MapReduce求解该问题 Step 3:对输出的结果集归拢、排序(系统自动完成）

MapReduce示例：单词计数 使用MapReduce求解该问题 Step 4:通过Reduce操作生成最后结果

Google MapReduce执行流程 1、处理流程 2、分片方式

文件存储位置 源文件：GFS Map处理结果：本地存储 Reduce处理结果：GFS 日志：GFS

Google MapReduce计算架构有什么问题？ 思考 Google MapReduce计算架构有什么问题？

MapReduce的容错 Worker故障 Master故障 Master 周期性的ping每个worker。如果master在一 个确定的时间段内没有收到worker返回的信息，那么它 将把这个worker标记成失效 重新执行该节点上已经执行或尚未执行的Map任务 重新执行该节点上未完成的Reduce任务，已完成的不 再执行 Master故障 定期写入检查点数据 从检查点恢复

MapReduce的优化 任务备份机制 慢的workers 会严重地拖延整个执行完成的时间 由于其他的任务占用了资源 磁盘损坏 解决方案: 在临近结束的时候，启动多个进程来执行尚未 完成的任务 谁先完成，就算谁 可以十分显著地提高执行效率

MapReduce的优化 本地处理 Master 调度策略: 效果 向GFS询问获得输入文件blocks副本的位置信息 Map tasks 的输入数据通常按 64MB来划分 (GFS block 大小) 按照blocks所在的机器或机器所在机架的范围 进行调度 效果 绝大部分机器从本地读取文件作为输入，节省大量带宽

MapReduce的优化 跳过有问题的记录 一些特定的输入数据常导致Map/Reduce无法运行 最好的解决方法是调试或者修改 不一定可行~ 可能需要第三方库或源码 在每个worker里运行一个信号处理程序，捕获map或 reduce任务崩溃时发出的信号，一旦捕获，就会向master 报告，同时报告输入记录的编号信息。如果master看到一 条记录有两次崩溃信息，那么就会对该记录进行标记，下 次运行的时候，跳过该记录

“实践是检验真理的唯一标准” 实践证明，MapReduce是出色的分布式计算模型 Google宣布，其对分布于1000台计算机上的1TB数据进 行排序仅仅需要68s 对4000台计算机上的1PB数据进行排序处理仅需要6小时 2分钟（每次测试至少会损坏1块硬盘） 在08年1月份，Google MapReduce平均每天的数据处理 量是20PB，相当于美国国会图书馆当年5月份存档网络数 据的240倍

课程小结 “免费的午餐”已经结束 并行思维 MapReduce 并行分布式数据处理框架 屏蔽各种并行分布式计算的难题

如何使用MapReduce实现海量数据的并行分布式排序？ 云计算应用实践 如何使用MapReduce实现海量数据的并行分布式排序？

讨论 云计算有没有什么问题？