MapReduce极简教程
一个有趣的例子
你想数出一摞牌中有多少张黑桃。直观方式是一张一张检查并且数出有多少张是黑桃？
MapReduce方法则是：
- 给在座的所有玩家中分配这摞牌
- 让每个玩家数自己手中的牌有几张是黑桃，然后把这个数目汇报给你
- 你把所有玩家告诉你的数字加起来，得到最后的结论
拆分
MapReduce合并了两种经典函数：
- 映射（Mapping）对集合里的每个目标应用同一个操作。即，如果你想把表单里每个单元格乘以二，那么把这个函数单独地应用在每个单元格上的操作就属于mapping。
- 化简（Reducing ）遍历集合中的元素来返回一个综合的结果。即，输出表单里一列数字的和这个任务属于reducing。
重新审视上面的例子
重新审视我们原来那个分散纸牌的例子，我们有MapReduce数据分析的基本方法。友情提示：这不是个严谨的例子。在这个例子里，人代表计算机，因为他们同时工作，所以他们是个集群。在大多数实际应用中，我们假设数据已经在每台计算机上了 – 也就是说把牌分发出去并不是MapReduce的一步。（事实上，在计算机集群中如何存储文件是Hadoop的真正核心。）
通过把牌分给多个玩家并且让他们各自数数，你就在并行执行运算，因为每个玩家都在同时计数。这同时把这项工作变成了分布式的，因为多个不同的人在解决同一个问题的过程中并不需要知道他们的邻居在干什么。
通过告诉每个人去数数，你对一项检查每张牌的任务进行了映射。 你不会让他们把黑桃牌递给你，而是让他们把你想要的东西化简为一个数字。
另外一个有意思的情况是牌分配得有多均匀。MapReduce假设数据是洗过的（shuffled）- 如果所有黑桃都分到了一个人手上，那他数牌的过程可能比其他人要慢很多。
如果有足够的人的话，问一些更有趣的问题就相当简单了 - 比如“一摞牌的平均值（二十一点算法）是什么”。你可以通过合并“所有牌的值的和是什么”及“我们有多少张牌”这两个问题来得到答案。用这个和除以牌的张数就得到了平均值。
MapReduce算法的机制要远比这复杂得多，但是主体思想是一致的 – 通过分散计算来分析大量数据。无论是Facebook、NASA，还是小创业公司，MapReduce都是目前分析互联网级别数据的主流方法。
什么是大数据？
大数据是大量数据的集合，数据量之大以至于用传统的计算方法无法处理如此庞大的数据。比如，Facebook和Youtube在日常中搜集和管理的大量数据就属于大数据的范畴。大数据不仅仅是指数据的规模和数量庞大，它通常还包括以下一个或多个方面：处理数据的速度、数据的种类、体积以及复杂度。
为什么是MapReduce?
传统的企业系统有一个中央服务器来保存和处理数据。下图为传统的企业系统的原理图。传统的模型不适合处理海量的数据，也不适用于标准的数据库。而且，中央处理系统在同时处理多个文件的时候遇到了瓶颈。
Google使用了一个叫MapReduce的算法解决了这个瓶颈。MapReduce把一个任务拆分成了多个小任务，并把子任务分配到多台计算机上进行工作。最终，每台计算机上的计算结果会被搜集起来并合并成最终的结果。
MapReduce是如何工作的？
MapReduce算法包含两部分重要的任务：Map和Reduce.
- Map任务把一个数据集转化成另一个数据集，单独的元素会被拆分成键值对(key-value pairs).
- Reduce任务把Map的输出作为输入，把这些键值对的数据合并成一个更小的键值对数据集.
让我们通过下图了解一下MapReduce每个阶段的工作，并理解他们的重要性。
- Input Phase - 在本阶段我们使用一个Record Reader对输入文件中的每一条数据转换为键值对的形式，并把这些处理好的数据发送给Mapper。
- Map - Map是是用户自定义的一个函数，此函数接收一系列的键值对数据并对它们进行处理，最后生成0个或多个键值对数据。
- Intermediate Keys - 由mapper生成的键值对数据被称为中间状态的键值对。
- Shuffle and Sort - Reducer任务通常以Shuffle（搅动）和Sort（排序）开始。程序把分好组的键值对数据下载到本机，Reducer会在本机进行运行。这些独立的键值对数据会按照键值进行排序并形成一个较大的数据序列，数据序列中键值相等的键值对数据会被分在相同的一组，这样易于在Reducer任务中进行迭代操作。
- Reducer - Reducer任务把分好组的键值对数据作为输入，并且对每一个键值对都执行Reducer函数。在这个阶段，程序会以不同的方式对数据进行合并、筛选。一旦执行完毕，Reducer会生成0个或多个键值对数据，并提供给最后一个处理步骤。
- Output Phase - 在输出阶段，通过record writer把从Reducer函数输出的键值对数据按照一定的格式写入到文件中。
让我们通过下图来进一步了解Map和Reduce这两个任务是如何工作的。
MapReduce例子
让我们以一个真实的例子来理解MapReduce的威力。Twitter每天都会收到50亿条（有那么多？）推特，约每秒3000条。下图展示了Twitter是如何利用MapReduce来管理这些数据的。
从上述插图中我们可以看到MapReduce执行了以下这些行为 -
- Tokenize - 处理器把推文以键值对的形式存放在maps中。
- Filter - 把不想要的数据从maps中剔除，把筛选好的数据以键值对的形式保存。
- Count - 对每个单词生成一个计数器。
- Aggregate Counter - Prepares an aggregate of similar counter values into small manageable units.
基于MapReduce的处理过程示例--文档词频统计：WordCount
设有4组原始文本数据：
Text 1: the weather is good Text 2: today is good
Text 3: good weather is good Text 4: today has good weather
传统的串行处理方式(Java)：
String[] text = new String[] { “hello world”, “hello every one”, “say hello to everyone in the world” ｝;
HashTable ht = new HashTable(); for(i = 0; i < 3; ++i) {
StringTokenizer st = new StringTokenizer(text[i]);
while (st.hasMoreTokens()) {
String word = st.nextToken(); if(!ht.containsKey(word)) {
ht.put(word, new Integer(1));
} else { int wc = ((Integer)ht.get(word)).intValue() +1;// 计数加1
ht.put(word, new Integer(wc));
}
}
}for (Iterator itr=ht.KeySet().iterator(); itr.hasNext(); ) {
String word = (String)itr.next();
System.out.print(word+ “: ”+ (Integer)ht.get(word)+“; ”);
}输出：good: 5; has: 1; is: 3; the: 1; today: 2; weather: 3
基于MapReduce的处理过程示例--文档词频统计：WordCount
MapReduce处理方式
使用4个map节点：
map节点1:
输入：(text1, “the weather is good”)
输出：(the, 1), (weather, 1), (is, 1), (good, 1)
map节点2:
输入：(text2, “today is good”)
输出：(today, 1), (is, 1), (good, 1)
map节点3:
输入：(text3, “good weather is good”)
输出：(good, 1), (weather, 1), (is, 1), (good, 1)
map节点4:
输入：(text3, “today has good weather”)
输出：(today, 1), (has, 1), (good, 1), (weather, 1)
使用3个reduce节点：
MapReduce处理方式
MapReduce伪代码(实现Map和Reduce两个函数)：
Class Mapper method map(String input_key, String input_value): // input_key: text document name
// input_value: document contents
for each word w in input_value:
EmitIntermediate(w, "1");
Class Reducer method reduce(String output_key, Iterator intermediate_values):
// output_key: a word
// output_values: a list of counts
int result = 0;
for each v in intermediate_values:
result += ParseInt(v);
Emit(output_key， result);3.上升到构架-自动并行化并隐藏低层细节
如何提供统一的计算框架
MapReduce提供一个统一的计算框架，可完成：
计算任务的划分和调度
数据的分布存储和划分
处理数据与计算任务的同步
结果数据的收集整理(sorting, combining, partitioning,…)
系统通信、负载平衡、计算性能优化处理
处理系统节点出错检测和失效恢复
MapReduce最大的亮点
通过抽象模型和计算框架把需要做什么(what need to do)与具体怎么做(how to do)分开了，为程序员提供一个抽象和高层的编程接口和框架
程序员仅需要关心其应用层的具体计算问题，仅需编写少量的处理应用本身计算问题的程序代码
如何具体完成这个并行计算任务所相关的诸多系统层细节被隐藏起来,交给计算框架去处理：从分布代码的执行，到大到数千小到单个节点集群的自动调度使用
MapReduce提供的主要功能
任务调度：提交的一个计算作业(job)将被划分为很多个计算任务(tasks), 任务调度功能主要负责为这些划分后的计算任务分配和调度计算节点(map节点或reducer节点); 同时负责监控这些节点的执行状态, 并负责map节点执行的同步控制(barrier); 也负责进行一些计算性能优化处理, 如对最慢的计算任务采用多备份执行、选最快完成者作为结果
数据/代码互定位：为了减少数据通信，一个基本原则是本地化数据处理(locality)，即一个计算节点尽可能处理其本地磁盘上所分布存储的数据，这实现了代码向数据的迁移；当无法进行这种本地化数据处理时，再寻找其它可用节点并将数据从网络上传送给该节点(数据向代码迁移)，但将尽可能从数据所在的本地机架上寻找可用节点以减少通信延迟
出错处理：以低端商用服务器构成的大规模MapReduce计算集群中,节点硬件(主机、磁盘、内存等)出错和软件有bug是常态，因此,MapReducer需要能检测并隔离出错节点，并调度分配新的节点接管出错节点的计算任务
分布式数据存储与文件管理：海量数据处理需要一个良好的分布数据存储和文件管理系统支撑,该文件系统能够把海量数据分布存储在各个节点的本地磁盘上,但保持整个数据在逻辑上成为一个完整的数据文件；为了提供数据存储容错机制,该文件系统还要提供数据块的多备份存储管理能力
Combiner和Partitioner:为了减少数据通信开销,中间结果数据进入reduce节点前需要进行合并(combine)处理,把具有同样主键的数据合并到一起避免重复传送; 一个reducer节点所处理的数据可能会来自多个map节点, 因此, map节点输出的中间结果需使用一定的策略进行适当的划分(partitioner)处理，保证相关数据发送到同一个reducer节点