共享一个实例，同时又能够按需满足不同的客户要求
• 概述 • 基础设施层 • 平台层 • 应用层 • 分布式计算软件构架MapReduce介绍 • 分布式计算开源框架Hadoop介绍 • 小结
MapReduce在线测试平台
• 使用mapreduce框架编程解决问题 • 在线检测系统允许测试自己的程序 • /index.jsp
result += ParseInt(v); Emit(AsString(result));
MapReduce: 执行情况
分布式文件系统
输入文件
Map阶段
中间文件
reduce阶段
输出文件
MapReduce: 例子
并行MapReduce : 例子
MapReduce: 容错性
通过重新执行任务解决出错问题 任务执行由master控制
• Sept 2008 – Hive 成为Hadoop 子项目
谁在使用Hadoop?
• Amazon/A9 • Facebook • Google • IBM • Joost • Last.fm • New York Times • PowerSet • Veoh • Yahoo!
商业硬件
典型的2层构架 – 节点是普通的商业PC机 – 30-40 节点/rack – 顶层到rack 带宽 3-4 gigabit – Rack到节点带宽1 gigabit
Hadoop 历史
• Dec 2004 – Google GFS 论文发表 • July 2005 – Nutch 使用 MapReduce • Feb 2006 – 成为 Lucene 子项目 • Apr 2007 – Yahoo! 建立 1000个节点的集群 • Jan 2008 – 成为 Apache顶级项目 • Jul 2008 – 建立 4000 节点的测试集群
map后输出(URL, (PRinit, list-of-urls))
– PRinit是URL初始的PageRank值 – list-of-urls包含URL所指向的所有网页
• Reduce任务只是验证函数
阶段 2: PageRank分配
• Reduce 任务输入(URL, url_list) 和许多(URL, val) 值
– 开发平台
• 应用模型、API代码库、开发测试环境
• 运行时环境
– 验证、配置、部署、激活
• 运营环境
– 升级、监控、淘汰、计费
平台层服务示例
Google App Engine
• 在Google的基础架构上运行自己的网络应用 程序
• 提供网址抓取、邮件、memcache、图像操 作、计划任务等服务
云构架
主要内容
• 概述 • 基础设施层 • 平台层 • 应用层 • 分布式计算软件构架MapReduce介绍 • 分布式计算开源框架Hadoop介绍 • 小结
• 概述
– 云计算的服务层次
• 基础设施层 • 平台层 • 应用层 • 分布式计算软件构架MapReduce介绍 • 分布式计算开源框架Hadoop介绍 • 小结
–计算vals 并且计算d 来获得新的PR值
–输出(URL, (new_rank, url_list))
• 非并行地检查是否收敛
MapReduce: 更多的例子
• 分布式Grep.
MapReduce Programs In Google Source Tree
• URL点击频率计算
• 聚类(K-means)
• 概述 • 基础设施层 • 平台层 • 应用层 • 分布式计算软件构架MapReduce介绍 • 分布式计算开源框架Hadoop介绍 • 小结
Hadoop相关书籍
• 我们关于云计算和Hadoop的新书
– 《分布式系统和云计算概论》 – 《Hadoop实战》
• 可以通过以下网址下载部分章节：
– /course/cloudcomputing 2010/index.html
Map 操作
• Map操作主要由用户实现，输入为键/值对，输出 为一些列键/值对的集合
– 如 (doc—id, doc-content)
• map类似于SQL聚集请求中的group-by子句
Reduce 操作
• map阶段完成后，中间结果的键/值对则根 据键的大小结合成列表传递给reducer
• 可以看作聚集函数（如求平均），这需要 在所有的具有相同group-by属性的记录上进 行计算
分布式文件系统
• 整个集群使用一个命名空间 • 数据一致性
– 一次写入多次读取 – 用户在已有文件中只能追加内容 • 文件拆分到数据块中 – 默认数据块大小为128MB – 每个数据块复制后放入不同的DataNodes • 智能客户端 – 客户端可以获得数据块的位置 –客户端可以直接从DataNode获取数据
• 目前支持Java和Python
• 概述 • 基础设施层 • 平台层 • 应用层
– 特征、分类、案例
• 分布式计算软件构架MapReduce介绍 • 分布式计算开源框架Hadoop介绍 • 小结
应用层的特征
• 可以通过浏览器访问，具有开放的API • 在使用的过程中根据实际使用情况付费 • 较强的云应用之间的整合能力
值
PageRank 使用 MapReduce
Map: 将PageRank 值分配给链接目标
Reduce: 从多个源聚集PageRank值计算得到新的PageRank值
Source of Image: Lin 2008
不断迭代 直至收敛
阶段 1: HTML处理 • Map任务输入(URL, page-content) 对进行
PageRank : 关键理解
• 每次迭代的影响是有限的，第i+1次迭代仅 仅依赖于第i次迭代
• 第i次迭代，每个节点的PageRank可以独立 地计算
PageRank 使用 MapReduce
• M表示为系数矩阵
• M的每行是分配给链接网页的PageRank值 • 这些值通过reduce聚集得到网页的PageRank
HDFS目标
• 超长规模分布式文件系统 – 10K 个节点, 1亿个文件, 10 PB大小
• 使用普通商业硬件 – 对文件进行复制应对硬件坏掉的情况 – 检测硬件错误并进行恢复
• 分组处理优化 – 计算任务可以移植到数据所在的节点上 – 提供非常高的聚集带宽
• 用户空间，运行在不同的操作系统上
构架
reduce(String output_key, Iterator intermediate_values): // output_key: a word // output_values: a list of counts
int result = 0; for each v in intermediate_values:
应用层的分类
• 标准应用
– 如文档处理、电子邮件、日程管理等 – 提供商往往是实力雄厚的IT业巨头
• 客户应用
– 如客户管理系统CRM、企业资源计划系统ERP – 提供商是规模较小的专业公司
• 多元应用
– 如地铁时刻表服务Mutiny、期权交易方案提供The Option Lab
– 提供商多是规模较小的开发团队
• 按照用户使用资源的数量和时间计费 • 网址/ec2/
• 概述 • 基础设施层 • 平台层
– 基本功能、实例、案例
• 应用层 • 分布式计算软件构架MapReduce介绍 • 分布式计算开源框架Hadoop介绍 • 小结
平台层的基本功能
• 开发测试环境
• 数据块报告 – 周期性地向NameNode发送所以数据块的状态报告
长尾理论
• 核心思想
– 在微小的需求如果能够得到满足就可以创造价 值
• 多元应用 • 初创型公司和创新团队利用云计算快速将构
想化为现实
Google Docs & Docs for Facebook
•在线文档编辑 •多人协作编辑
பைடு நூலகம்
Web QQ
• 一站式网络服务

• 客户应用的典型代表 • 采用了多租户的架构，使得所有用户和用户和应用程序
– 提供虚拟化的计算资源、存储资源、网络资源 – Amazon EC2
• 平台即服务
– 使软件开发人员充分利用开放的资源来开发定制化 的应用
– Google AppEngine
• 软件即服务
– 软件或应用通过租用的形式提供给用户使用 – – Google Gmail、Docs
• 概述 • 基础设施层
– 基本功能、示例、案例
• 平台层 • 应用层 • 分布式计算软件构架MapReduce介绍 • 分布式计算开源框架Hadoop介绍 • 小结
基础设施层的基本功能
资源抽象
计费管理
资源监控
安全管理
复杂管理
资源部署 数据管理
基础设施层示例
Amazon EC2
• 底层采用Xen虚拟化技术，以Xen虚拟机的 形式向用户动态提供计算资源
• 图像算法.
• 索引系统
MapReduce: 扩展和相似应用平台
• PIG (Yahoo) • Hadoop (Apache) • DryadLinq (Microsoft)
使用MapReduce的大规模系统构架
User App
MapReduce Distributed File Systems (GFS)
云构架层次
共有云
（通过Internet提 供公共服务）
混合云
（通过Internet和 Intranet提供公共
和私有服务）
私有云
（通过Intranet提 供私有服务）