Google MapReduce介绍

              Google MapReduce介绍

 

MapReduce是Google开发的C++编程工具，用于大规模数据集（大于1TB）的并行运算。概念"Map（映射）"和"Reduce（化简）"，和他们的主要思想，都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。[1]

当前的软件实现是指定一个Map（映射）函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce（化简）函数，用来保证所有映射的键值对中的每一个共享相同的键组。

映射和化简

　　简单说来，一个映射函数就是对一些独立元素组成的概念上的列表（例如，一个测试成绩的列表）的每一个元素进行指定的操作（比如前面的例子里，有人发现所有学生的成绩都被高估了一分，他可以定义一个“减一”的映射函数，用来修正这个错误。）。事实上，每个元素都是被独立操作的，而原始列表没有被更改，因为这里创建了一个新的列表来保存新的答案。这就是说，Map操作是可以高度并行的，这对高性能要求的应用以及并行计算领域的需求非常有用。

而化简操作指的是对一个列表的元素进行适当的合并（继续看前面的例子，如果有人想知道班级的平均分该怎么做？他可以定义一个化简函数，通过让列表中的元素跟自己的相邻的元素相加的方式把列表减半，如此递归运算直到列表只剩下一个元素，然后用这个元素除以人数，就得到了平均分。）。虽然他不如映射函数那么并行，但是因为化简总是有一个简单的答案，大规模的运算相对独立，所以化简函数在高度并行环境下也很有用。

分布和可靠性

MapReduce通过把对数据集的大规模操作分发给网络上的每个节点实现可靠性；每个节点会周期性的把完成的工作和状态的更新报告回来。如果一个节点保持沉默超过一个预设的时间间隔，主节点（类同Google File System中的主服务器）记录下这个节点状态为死亡，并把分配给这个节点的数据发到别的节点。每个操作使用命名文件的原子操作以确保不会发生并行线程间的冲突；当文件被改名的时候，系统可能会把他们复制到任务名以外的另一个名字上去。（避免副作用）。

化简操作工作方式很类似，但是由于化简操作在并行能力较差，主节点会尽量把化简操作调度在一个节点上，或者离需要操作的数据尽可能进的节点上了；这个特性可以满足Google的需求，因为他们有足够的带宽，他们的内部网络没有那么多的机器。

用途

在Google，MapReduce用在非常广泛的应用程序中，包括“分布grep，分布排序，web连接图反转，每台机器的词矢量，web访问日志分析，反向索引构建，文档聚类,机器学习，基于统计的机器翻译...”值得注意的是，MapReduce实现以后，它被用来重新生成Google的整个索引，并取代老的ad hoc程序去更新索引。

MapReduce会生成大量的临时文件，为了提高效率，它利用Google文件系统来管理和访问这些文件。

相关:

-----------------------------------------------------
以下是田春峰提供的

   对goole这样需要分析处理海量数据的公司来说，普通的编程方法已经不够用了。于是 google开发了MapReduce。简单来说，语法上MapReduce就像Lisp,使用MapReduce模型你可以指定一个Map方法来处理诸如key/value这样的数据，并生成中间形式的　key/value 对，然后再使用 Reduce方法合并所有相同key的中间　key/value　对生成最终结果。google的MapReduce是运行在数千台机器上的处理TB数据的编程工具。

     据说在MapReduce这样的编程模型下，程序可以自动的集群机器中在按照并行方式分布执行。就如同java程序员可以不考虑内存泄露一样，MapReduce程序员也不许要关心海量数据如何被分配到多台机器上，不需要考虑如果参加计算的机器出现故障应该怎么办，不需要考虑这些机器间如何协作共同完成工作的。

     举个例子吧：最近我在做贝叶斯论坛垃圾帖屏蔽演示系统 Beta 1 的时候，就需要计算样本数据中每个词语出现的频率。我的计算步骤就是先分词，然后用hash表处理。要是碰到TB的数据，我的赛扬CPU可是吃不消。那么放在MapReduce下面会是什么样子呢？

     下面是一个伪实现：
第一步：
     map(String key, String value):
     // key: 文档名称
     // value: 文档内容
     for each word w in value:
         EmitIntermediate(w, "1");
第二步：
     reduce(String key, Iterator values):
     // key: 一个词
     // values: 关于这个词的频率数据
     int result = 0;
         for each v in values:
             result += ParseInt(v);
         Emit(AsString(result));
  

     如果你看过向量空间模型就知道，这就是计算　TF 和　IDF 的语义实现。