1 mapreduce介绍.doc

MapReduce 分布式计算平台 MapReduce 分布式计算平台 项目名称 Hadoop分布式系统研究，改进，应用 作者 李相娜，王守彦，马如悦，朱冠胤 文档提交日期 2008-4-3 版本 Version 1.0 1. MapReduce介绍 1 1.1 编程模式 1 2.2 简单例子 1 2 用户自定义接口 3 2.1 map函数 3 2.2 Reduce函数 3 2.3输入和输出格式 4 2.4 partitioner函数 4 2.5 Combiner函数 4 3 Hadoop MapReduce平台使用 5 3.1 streaming介绍 5 3.2 C语言Map-Reduce程序示例 6 3.2.1计算任务 6 3.2.2 Mapper算法设计 7 3.2.3 Reducer算法设计 8 3.2.4 作业提交命令 9 3.3 shell Map-Reduce程序示例 9 3.3.1计算任务 9 3.3.2 map实现 10 3.3.3 reduce实现 11 3.3.4 作业提交命令 11 4技巧 12 4.1 顺序保证 12 4.2 本地执行 12 4.3 状态信息 13 5 实际经验 13 5.1 spider rubbish-mine全库挖掘项目 13 5.2 Rank组page共现信息计算 14 5.3 PS日志分析计算 15 5.4 用户访问信息展现 16 6 参考资料 17 附录一 18 1. MapReduce介绍这个诸如分布、工作调度、容错、机器间通信并发处理分布式系统经验.1 编程模式 MapReduce基于“分而治之”的思想，将计算任务抽象成Map和Reduce“分散运算—合并结果”过程。键值对键值对键值对将同属于一个键（key）的值（value）组合在一起（key/list of values）2.2 简单例子 下面给出一个词频统计的简单例子来演示一下Map-Reduce的过程： 输入两篇文档： doc1: MapReduce is a programming modeldoc2: MapReduce is easy to use Map任务负责统计每篇文档中出现的单词，Reduce任务负责对每个单词出现的总次数进行统计。如果将每一篇文档作为一个输入划分，计算结果只输出到一个文件中；MapReduce将启动2个map任务和1个reduce任务进行处理。数据转换过程如下： Map 输出： MapMapReduce, 1), (is, 1), (a, 1), (programming, 1), (model, 1). Map 2: (MapReduce, 1), (is, 1), (easy, 1), (to, 1), (use, 1). Reduce输入： (MapReduce, [1,1]), (is, [1,1]), (a, [1]), (programming, [1]), (model, [1]), (easy, [1]), (to, [1]), (use, [1]). Reduce输出： (MapReduce, 2), (is, 2), (a, 1), (programming, 1), (model, 1), (easy, 1), (to, 1), (use, 1). 还有一些有趣的例子，也可以简单通过MapReduce计算模型来展示：分布式Grep： 如果map函数检查输入行，满足条件的时候，map函数就把本行输出。reduce函数就是一个直通函数，简单的把中间数据输出就可以了。 URL访问频率统计： map函数处理webpag请求和应答（URL，1）的log。Reduce函数把所有相同的URL的值合并，并且输出一个成对的（URL，总个数）。 逆向Web-Link 图： map函数输出所有包含指向target URL的source网页，用（target,source）这样的结构对输出。Reduce函数局和所有关联相同target URL的source列表，并且输出一个(target,list(source))这样的结构。 主机关键向量指标（Term-Vector per Hosts）: 关键词向量指标简言之就是在一个文档或者一组文档中的重点次出现的频率，用(word,frequency)表达。map函数计算每一个输入文档（主机名字是从文档的URL取出的）的关键词向量，然后输出（hostname,关键词向量(Term-Vector)）。reduce函数处理所有相同host的文档关键词向量。去掉不常用的关键词，并且输出最终的(hostname，关键词向量)对。 逆序索引 map函数分析每一个文档，并且产生一个序列（word，documentID）组。reduce函数处