(汇总)Google获得MapReduce专利

感谢网友共享：在将近六年等待之后，Google的一个专利申请近日终于获得批准。这个编号为7 650 331，名为 System and method for efficient large-scale data processing（高效大规模数据处理）的专利可是非同小可。它所指的是Google最引为自豪的成果之一，也是云最重要的核心技术之一：

MapReduce

专利的摘要是这一重要技术不错的定义，我们不妨来研究一下：
A large-scale data processing system and method includes one or more application-independent map modules configured to read input data and to apply at least one application-specific map operation to the input data to produce intermediate data values, wherein the map operation is automatically parallelized across multiple processors in the parallel processing environment. A plurality of intermediate data structures are used to store the intermediate data values. One or more application-independent reduce modules are configured to retrieve the intermediate data values and to apply at least one application-specific reduce operation to the intermediate data values to provide output data.【译文】一种大规模数据处理系统和方法。其中包括一个或者多个独立于应用的Map模块和一个或者多个独立于应用的Reduce模块。Map模块是这样配置的，它们读取输入数据，并对此数据进行至少一个特定于应用的Map操作，以生成中间数据值，其中Map操作将在并行处理环境中的多个处理器实现自动并行化。存储这些中间数据值将运用许多中间数据结构。而Reduce模块是这样配置的，它们获取这些中间数据值，并对此数据应用至少一个特定于应用的Reduce操作，以提供输出数据。

众所周知，MapReduce广泛用于各种数据挖掘应用中
，除了Google自己，还有Yahoo的搜索基础设施，Amazon的Elastic MapReduce服务，IBM的M2平台，等等。当然，最重要的实现应该是开源项目
[color=]Apache Hadoop
。事实上，Hadoop已经成为Yahoo整个Web基础设施的核心，用户还包括Facebook、Last.fm、Joost、Meebo、Ning等2.0新贵和《纽约时报》网站、Rackspace等云公司。


那么，出来了：首先，Google是否应该获得这项技术的专利呢吗？
的确，回顾历史，Map和Reduce函数是Lisp和其他函数式语言非常常见的特性。而Lisp语言诞生于上世纪50年代。事实上MapReduce的发明者也不讳言这一点。在2004年操作系统设计与实现学术会议上发表的开创性论文《MapReduce: Simplified Data Processing on Large Clusters》（MapReduce：大型群集上的数据处理简化）中，除了Lisp语言之外，Jeffrey Dean和Sanjay Ghemawat还提到了Bulk Synchronous Programming、MPI、Active Disk、Condor系统、NOW-Sort算法、River系统、BAD-FS、TACC等等。


[color=]但是，任何创新都不是从无到有的，这些相关工作总体上只是相关而已，将MapReduce思想应用于大型群集上的数据处理，并形成完整的框架，有大量成功的应用，的确是Google的独门武功。


其次，这样一个应用广泛的技术成为专利，影响怎样呢吗？
必须承认，在专利纠纷满天飞的今天，运用其他人的专利，总是存在诉讼风险。对此，Google的发言人用了法律味道很重的措辞回复：
与其他负责任的创新公司一样，Google会对自己研发的各种技术申请专利。虽然我们不会对这项专利以及我们其他的专利技术的运用进行评论，但是我们感到迄今为止Google的表现与公司的价值观和优先级是相符的。

听其言，观其行，我们也许有理由对Google放心。毕竟，在可见的未来，它不会指望靠这种专利挣钱。此外，Google对Hadoop项目一贯支持，将其作为大学推广项目的重要组成部分，使大学生也能在不涉及Google专有技术的情况下，研究Web规模的编程。
http://database.cs.brown.edu/projects/mapreduce-vs-dbms/



MapReduce介绍 Introduction
-------------
MapReduce是一个最先由Google提出的分布式计算软件构架，它可以支持大数据量的分布式处理。这个架构最初起源于函数式程式的map和reduce两个函数组成，但它们在MapReduce架构中的应用和原来的运用上的大相径庭。
OverView
---------
MapReduce架构是用来解决大数据量的分布式计算，然后把计算后的结果放入文件系统或者数据库中。
"Map":主结点读入输入数据，把它分成可以用相同方法解决的小数据块（这里是一个分而治之的思想），然后把这些小数据块分发到不同的工作节点上(worder nodes)上，每一个工作节点(worder node)循环做同样的事，这就行成了一个树行结构（分布式计算中的很多模型都和图论有关，pageRank也是），而每一个叶子节点有来处理每一个具体的小数据块，再把这些处理结果返回给父节点。
"Reduce":主结节得到所有子节点的处理结果，然后把所有结果组合并且返回到输出。

MapReduce的一个特点是可以用map和reduceion方法来处理分布式计算的（这里有一个移动计算而不是移动数据的概念，因为移动计算比移动数据代价更小）。这里的每一个mapping操作都是相对独立的，所有的maps都是并行运行的，虽然实践中会受到数据源和cpu个数的影响。同样的，这里用一个reducer集合来运行reduction操作，所有带有相同key的map输出会聚集到同一个reducer。虽然这个过程看上去没有串行计算来得高效，但是MapReduce能够处理一般服务器所不能处理的大数据量处理。大型的服务器集群可以在几个小时内处理petabyte数据量的排序。而并行处理可以提供部分容错和出错恢复的功能。当一个mapper或reducer失效时，整个工作就会被重新安排，从而不会影响工作的连续性。
Logical view


------------
MpaReduce的Map和Reduce过程都定义了数据结构(key,value)对，Map操作在一个数据域中用一种类型表达一个数据对，然后在另一个不同的域中返回一个数据队列：
Map(k1,v1) ->　list(k2,v2)
Map过程并行应用于每一个输入的数据集，每一次调用都会产生一个(k2,v2)的队列。然后，MapReduce构架收集输出队列中有相同key的数据对，把它们聚集在一起，因为构建了一个不同key的数据对集合。
Reduce方法应用于上面产生的每一个数据对集合，从而产生相同域中的数据集合。
Reduce(k2,list(v2)) -> list(v3)
每一个被调用的Reduce方法产生一个v3数据集或者一个空集，这里也可以返回多个value。所有返回的调用结果组成一个结果队列。
Example
---------
void map(String name, String document):
  // name: document name
  // document: document contents
  for each word w in document:
    EmitIntermediate(w, 1);

void reduce(String word, Iterator partialCounts):
  // word: a word
  // partialCounts: a list of aggregated partial counts
  int result = 0;
  for each pc in partialCounts:
    result += ParseInt(pc);
  Emit(result);
这里，每一个文档被分成了一个个词，通过调用Map方法，每一个词都初始化的个数为1。MapReduce架构把所有相同的词聚合在一起，把它们传送给Reduce，Reduce计算所有同相词的出现个数。
Dataflow
--------
MapReduce架构的操作模块：
1. 输入流模块:输入模块负责把输入数据分成16MB或者128MB的小数据块，然后把它们传给Map模块
2. Map模块：Map模块得到每一个key/value对，处理后产生一个或多个key/value对。这里的输入key/value对与输出key/value对是不一样的。
3. Partition模块：它用于负责把上面输出的key映射到不同的reduce方法中去
4. comapre模块：对reduce所读入的数据进行比较
5. Reduce模块：对上面已经排好序的并且带有相同key的数据进行迭代计算
6. 输出模块：把reduce的输出结果写到存储系统中去，一般都会用分布式文件系统，如GFS
Distribution and reliability
----------------------------
MapReduce通过把大工作分成不同的小工作再分发给不同的工作者来实现数据的可靠性。每一个单独的工作者处理分发的工作，然后把结果和状态返回给父节点。如果一个节点失效了，主节点会发现和记录这个失效的节点，把分配给这个节点的工作再分发给别的节点。
而实践中也不一定都是高可靠性的，如Hadoop的NameNode是一个单节点的文件系统，一但JobTracker失效，所有的工作都会丢失。
MapReduce技术的开源C语言实现


一、Stanford大学的Phoenix系统（单机多核的应用）

1、Phoenix是在共享内存的体系结构上的MapReduce实现。它的目标是在多核平台上，使程序运行得更高效，而且使程序员不必关心并发的管理。事实上并发管理，尽管是经验丰富的程序员，也难免在这上面出错。
2、Phoenix由一组对程序应用研发者开放的简单API和一个高效的运行时组成。运行时系统处理程序的并发、资源管理和错误修复，
它的实现是建立在P-thread之上的，当然也可以很方便地移植到其它的共享内存线程库上。
3、网站http://mapreduce.stanford.edu/可以下载到最新程序和源码。


二、Eucalyptus 开源云平台

1、Eucalyptus 项目(Elastic Utility Computing Architecture for LinkingYour Programs To Useful Systems)是 Amazon EC2 的一个开源实现，它与商业服务接口兼容。和 EC2一样，Eucalyptus 依赖于 Linux 和 Xen 进行操作系统虚拟化。
2、Eucalyptus 是加利福尼亚大学(SantaBarbara)为进行云研究而研发的。
3、网站http://eucalyptus.cs.ucsb.edu/可以下载到最新程序和源码。
三、Enomalism 弹性计算平台

1、Enomaly's Elastic Computing Platform (ECP)是一个可编程的虚拟云架构，ECP平台可以简化在云架构中发布应用的操作。
2、云平台是一个 EC2 风格的 IaaS 。Enomalism 是一个开放源代码项目，它提供了一个功能类似于 EC2的云框架。Enomalism 基于 Linux，同时支持 Xen 和 Kernel Virtual Machine(KVM)。与其他纯IaaS 解决方案不同的是，Enomalism 提供了一个基于 TurboGears Web 应用程序框架和 Python 的软件栈。　
3、网站http://www.enomaly.com可以下载到最新程序和源码。
http://user.qzone.qq.com/799035233/infocenter?ptlang=2052

Google也是Hadoop的贡献者，根据Google的习惯，这个专利多半只会是象征性的

一般企业和个人用，Google估计不会管的。但很难说如果竞争对手如微软运用会咋样。IBM、Yahoo、Facebook、Amazon目前还不算是Google在这方面的竞争对手，但未来也很难说。
作为大公司，很难想象会把自己的核心架构建立在潜在对手的专利上面，不管这个对手是谁，是咋的“不作恶”