Cloud Computing Google云计算原理

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

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

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

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

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

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

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

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

分析搜索趋势(Google Trends) 为什么需要MapReduce？ Google拥有海量数据，并且需要快速处理 Google 全球Web数据 邮件数据 地图数据 卫星照片 …… 对爬虫获取的网页进行倒排索引 计算网站的PageRank 分析搜索趋势(Google Trends) 计算网页的访问量 …… Inverted list: keyword->id lists pageRank:

倒排索引 T0："it is what it is" T1："what is it" T2："it is a banana“ 反向文件索引： "a": {2} "banana": {2} "is": {0, 1, 2} "it": {0, 1, 2} "what": {0, 1} 检索的条件：“what”, “is” 和 “it” ： {0, 1} ∩ {0, 1, 2} ∩ {0, 1, 2} ={0,1} 带位置的反向文件索引： "a": {(2, 2)} "banana": {(2, 3)} "is": {(0, 1), (0, 4), (1, 1), (2, 1)} "it": {(0, 0), (0, 3), (1, 2), (2, 0)} "what": {(0, 2), (1, 0)} 连续检索的条件： “what is it” ：{1}

PageRank（简化算法） 假设一个由4个页面组成的小团体：A，B，C和D。 如果所有页面都链向A，那么A的PR（PageRank） 值将是B，C及D的和。 继续假设B也有链接到C，并且D也有链接到包括A的 3个页面。一个页面不能投票2次。所以B给每个页 面半票。

为什么需要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执行流程

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

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实现海量数据的并行分布式 排序？ 后续课程：《云计算编程实践》 云计算编程实践: gfs; mapreduce; hbase; chubby; google app engine; amazon ec2; ali yun; 形式：介绍+编程