Mapreduce实验报告.doc

Mapreduce实验报告

前言和简介
MapReduce是Google提出的一种编程模型，在这个模型的支持下可以实现大规模并行化计算。在Mapreduce框架下一个计算机群通过统一的任务调度将一个巨型任务分成许多部分，分别解决然后合并得到最终结果。Mapreduce可以让程序员以简单的程序来解决实际问题，而隐藏了诸如分布、工作调度、容错、机器间通信，使得大规模任务简单而迅速地完成。
一． Mapreduce的基本原理
1. 核心思想。
“Divide and Conquer”是Mapreduce的核心思想。面对一个规模庞大的问题，要处理是以TB计的数据，Mapreduce采用“输入”------“分解”------“解决”------“聚合”------“输出结果”的基本过程。
2. 基本原理
Map和Reduce是两个核心操作，用户定义的map函数接收被切割过的原始的key/value对集并且计算出一个中间key/value对集。Mapreduce库函数将所有的具有相同key值的value聚合在一起交给用户定义的reduce函数处理。reduce函数将同一key值的所有value合并成得到输出文件。在整个过程中，Mapreduce库函数负责原始数据的切割，中间key/value对集的聚合，以及任务的调度，容错、通信控制等基础工作。而用户定义的map和reduce函数则根据实际问题确定具体操作。
二． 框架的基本结构和执行流程
基本结构
Mapreduce框架的主要程序分为三种即Master，Map和Reduce。
1. Master：主要功能有两个，任务的分割和任务的调度。Master把输入文件切成许多个split，每个split文件一般为几十M。Master同时还要调度任务监视各个map worker和reduce worker的工作状态，以做出相应的安排。Master还要监视各个子任务的完成进展情况。
Master用到的数据结构
Struct Split[] //文件切割后的信息
struct MapSTATE[] //记录各个map任务的情况。
struct ReduceSTATE[R] //各个reduce任务的情况。
Type Map=0，Reduce=0 //记录map任务和reduce任务的完成个数。
MapWorkerSTATE[]
ReduceWorkerSTATE[] //各个工作机器的忙闲状态
FileSplit(string inputfilename) //输入文件切割
JobAssign（） //工作任务分配
2. Map：主要功能是读取经过切割split文件形成一个map任务，分析map任务，得到中间结构并且将同一类型的中间文件存放在同一个区域内等待特定的reduce程序读取。
3. Reduce：不同的Reduce读取各个Map得到的特定的中间文件，将所有相同的中间文件整合成最后的输出文件。
任务执行基本流程
基本流程图见下一页
首先输入收据文件被Mapreduce库函数分割成M个split集。用户定义的程序被拷贝到机群中，其中一个是master，其它的都是worker。M个map任务和R个reduce任务将被分配。Master负责调度任务和过程监视。随时检测worker的工作状况，任务的完成进度。Map worker每完成一个子任务向master报告。
一个被分配了map任务的worker读取一个split集，该worker从这个split集中分析出key/value对，然后有map函数来处理这些key/value对并得到中间key/value对，这些key/value对将最终存放在map worker的本地硬盘上。每完成一个任务报告master。
中间key/value对被存在本地硬盘的R个不同的区域中，由于可能的key值很可能不止R个，故必须利用一个分割函数来划分中间文件，常用的是散列的方法（如hash(key) mod R）。保证key值相同的key/value对被存放同一区域中，并且将位置报告给master。如果同一个key的中间文件多而小可以考虑用cmobine函数在本地进行合并。
当所有的split都被分析完成之后，reduce worker开始工作，每个reduce根据master的安排和信息指示利用机群的内部文件系统读取map worker本地磁盘中特定位置的中间文件。
Reduce开始聚合中间文件，得到自己的输出文件。在聚合的过程中由于有很多key值，一般将用到排序。Reduce worker完成自己的工作后向master报告。

输入文件

控制

Split0 split1 split2 …... split n

Master

Map
Workerr
Map
Workerr
Map Worker

分析key/value对
分区写入磁盘

读取
Reduce
Worker
Reduce
Workerr
Reduce
Workerr

输出文件

输出文件
输出文件

*单向箭头表示控制，双向箭头表示控制和反馈
*某些操作中Mapworker硬盘上的key/value在被Reducerworker读取之前可以有combine操作，将相同key的value合并以减少读取次数
*分散的输出文件也可以合并成一个输出文件而对于有些操作如求最大值则必须合并输出文件才能得到最终结果
三． 一些操作的伪码
1. 查找
查找文件存在机群的存储机器上，可以查找其中若干个单词的出现位置。Master 根据文件的大小将文件切成合适的分数，切割信息（如起始位置，终止位置，切片长度等）存储在master上。 Map根据master 的切割信息读取各小规模文件，分析文件内容，每遇到一个要查找的单词形成一个key/value，这里的key是待查找的单词，value是单词的位置，周期性地更新中间文件。Reduce读取每一个map worker同一个区域中的所有中间文件将所有具有相同key值也就是同一个单词的文件合并，将所有的位置汇总成一个输出文件。
Map(String key,String value)
{
  //key:文档的名字
 //value:文档的内容
String word；
Struct position；
While（！FileEnd） //读取整个文件
{
word=WordRead（key）； //读取文件中的单词
position=PositionRead（key）；//单词位置读取
EmitIntermediateFile（word，position）//形成中间文件
}
}

Reduce(String key,String value)
{
//key:中间文件名即待查单词
 //value:单词位置列表
For every key readed
Emit（value ，position（key））；//每读到一个单词将其位置写入其位置列表}
2. 词频统计
被统计的的文件被切割后，map读取切割文件，统计该文件中的单词数目，形成中间文件，reduce读取相同单词的中间文件，合并得到单词总数。由于单词很多，而reduce worker有限，故应在map中用散列的方法将不同单词的中间文件映射到不同的区域，同一单词的中间文件必须保证存放在同一区域。
Map（string key，string value）
{
//Key：文件名
//value：文件内容
String Word；
While（！FileEnd）
{
Word = WordRead（key）；
EmitIntermediateFile（word，1）；形成中间文件
}
}

Reduce（string key，string value）
{
//Key：文件名及单词名
//value：单词计数列表
Int Result=0；
String word；
While（！FileEnd）
{
Word = WordRead（key）；
If （Word in vlaue）
Result++； //单词累加
}
Filewrite（result）； //将结果写入文件
}

3. 反向链接
输入文件包括所有的URL及其链接信息。可以考虑将同一个源URL的信息切割成一个文件。Map读取切割文件，将每个被链接的URL生成中间文件，key是被链接的URL，value是源URL。Reduce读取所有中间文件同一被链接URL的中间文件合并，得到反链接表。
Map（string key，string value）
{
//Key：文件名
//value：文件内容
String URLlinked; //被链接URL
While（！FileEnd）
{
URLRead（URLlinked）；
EmitIntermediateFile（URLlinked）；形成中间文件
}
}

Reduce（string key，string value）
{
//Key：文件名
//value：反向链接列表
For every key readed
Emit（value，sourceURL(key)）；//每读到一个中间文件将其源URL存放到源URL列表
}

4. 倒排索引
根反向链接向类似，搜索输入文件中的某些单词，将所有包含特定单词的文件的ID形成一个索引列表。map函数分析每个文档,然后产生一个(词,文档号)对的序列.reduce函数接受一个给定词的所有对,排序相应的文档ID,并且产生一个(词,文档ID列表)对.所有的输出对集形成一个的倒排索引。
Map（string key，string value）
{
//Key：文件名
//value：文件内容
String Word；
While（！FileEnd）
{
Word = WordRead（key）；
EmitIntermediateFile（word，FileID）；形成中间文件
}
}

Reduce（string key，string value）
{
//Key：文件名
//value：源文件列表
For every key readed
Emit（value，fileID(key)）；//每读到一个中间文件将其源文件的ID存放到源文件列表
}
四． 总结和评价
Mapreduce的原理很简单，通过对任务划分和分而治之的方法，使得大型问题得到迅速地解决。Mapreduce的关键贡献是各种实际问题抽象的解决过程抽象成map（映射）和reduce（化简）两个主要过程，着使得程序员在解决实际问题事只要分析什么map过程什么是reduce过程，它们的key/value对分别是什么。而不用去关心mapreduce库函数做的复杂的底层工作。Mapreduce 是典型的以空间的消耗换取时间的节省的例子。为解决一个问题可能要动用很多台机器。在机器间的信息传递和信息延迟都会影响问题解决的速度和效果。这里有几个关键：
一是机群内部使用的文件存储系统要能高效地工作，google 使用的分布式文件系统GFS能达到这个要求。
然后是机群中的网络通信，网络带宽和网络通信质量决定的信息传递的延迟，当大量的文件被通过网络远程读取时，网络可能会成为问题解决速度的瓶颈。
另外，一个高效的调度和容错机制是非常关键的。Master必须能及时地了解全局的运行情况并采取相应的措施。采取什么的方式和策略进行控制和反馈，将很大程度上影响任务完成的速度和质量。在分布式系统上各种意外事故随时可能发生，master必须针对事故进行预处理（如将同一个任务拷贝多分，交给不同机器处理，接受最先完成的）和错误处理（启动备选拷贝任务）。大量的网络传输可能导致传输错误，采取什么样的检错和纠错机制也很重要。而且各种控制可能是矛盾的，必须协调和折中得到综合性能最优的方案。
所以我认为，控制可能成为mapreduce的一个关键之处。若能运用自动化领域的控制论相关知识来指导mapreduce的全局任务调度可能会取得新的突破。