云架构及并行计算平台和并行计算架构.ppt

* * * * * * * * * * * * * * * * * MapReduce:  更多的例子 MapReduce : PageRank PageRank 是描述“random surfer”行为的模型 C(t) 是t的链接数, (1-d) 是阻尼系数(随机跳转) “random surfer”指的的是随机的链接情况并不考虑具体的网页内容 将pages rank平均分配给所有的链接网页 阻尼系数用于描述“无聊”和随意的URL PageRank : 关键理解 每次迭代的影响是有限的，第i+1次迭代仅仅依赖于第i次迭代 第i次迭代，每个节点的PageRank可以独立地计算 PageRank 使用 MapReduce M表示为系数矩阵 M的每行是分配给链接网页的PageRank值 这些值通过reduce聚集得到网页的PageRank值 PageRank 使用 MapReduce Map: 将PageRank 值分配给链接目标 Reduce: 从多个源聚集PageRank值计算得到新的PageRank值 不断迭代 直至收敛 Source of Image: Lin 2008 阶段 1: HTML处理 Map任务输入(URL, content) 对进行map后输出(URL, (PRinit, list-of-urls)) PRinit是URL初始的PageRank值 list-of-urls包含URL所指向的所有网页 Reduce任务只是验证函数 阶段 2: PageRank分配 Reduce 任务输入(URL, url_list) 和许多(URL, val) 值 计算vals 并且计算d 来获得新的PR值 输出(URL, (new_rank, url_list)) 非并行地检查是否收敛 MapReduce: 更多的例子 分布式Grep. URL点击频率计算 聚类(K-means) 图像算法. 索引系统 MapReduce Programs In Google Source Tree MapReduce: 扩展和相似应用平台 PIG (Yahoo) Hadoop (Apache) DryadLinq (Microsoft) 使用MapReduce的大规模系统构架 概述 基础设施层 平台层 应用层 分布式计算软件构架MapReduce介绍 分布式计算开源框架Hadoop介绍 小结 Hadoop相关书籍 我们关于云计算和Hadoop的新书 《分布式系统和云计算概论》 《Hadoop实战》 可以通过以下网址下载部分章节： /course/cloudcomputing2010/index.html 概述 Hadoop 分布式文件系统构架 Hadoop 在Facebook的使用 为什么使用Hadoop? 需要处理Petabyte级别的数据集 为每个应用程序的建立可靠的平台代价较大 每天都有节点坏掉 – 节点坏掉是可以预料到的 – 集群中节点的数量不是稳定的 只需要普通的基础设施 –高效、可信、开源 Hadoop 历史 Dec 2004 – Google GFS 论文发表 July 2005 – Nutch 使用 MapReduce Feb 2006 – 成为 Lucene 子项目 Apr 2007 – Yahoo! 建立 1000个节点的集群 Jan 2008 – 成为 Apache顶级项目 Jul 2008 – 建立 4000 节点的测试集群 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 HDFS目标 超长规模分布式文件系统 – 10K 个节点, 1亿个文件, 10 PB大小 使用普通商业硬件 – 对文件进行复制应对硬件坏掉的情况 – 检测硬件错误并进行恢复 分组处理优化 – 计算任务可以移植到数据所在的节点上 – 提供非常高的聚集带宽 用户空间，运行在不同的操作系统上 构架 分布式文件系统 整个集群使用一个命名空间 数据一致性 – 一次写入多次读取 – 用户在已有文件中只能追加内容 文件拆分到数据块中 – 默认数据块大小为128MB – 每个数据块复制后放入不