本节书摘来异步社区《Hive编程指南》一书中的第1章，第1.1节，作者： 【美】Edward Capriolo , Dean Wampler , Jason Rutherglen 译者： 曹坤，更多章节内容可以访问云栖社区“异步社区”公众号查看。
1.1 Hadoop和MapReduce综述
如果用户已经熟悉Hadoop和MapReduce计算模型的话，那么可以跳过本节。虽然用户无需精通MapReduce就可以使用Hive，但是理解MapReduce的基本原理将帮有助于用户了解Hive在底层是如何运作的，以及了解如何才能更高效地使用Hive。
我们在这里提供了一个关于Hadoop和MapReduce的简要描述。更多细节，请参考Tom White (O’Reilly)所著的《Hadoop权威指南》一书。
MapReduce
MapReduce是一种计算模型，该模型可将大型数据处理任务分解成很多单个的、可以在服务器集群中并行执行的任务。这些任务的计算结果可以合并在一起来计算最终的结果。
MapReduce编程模型是由谷歌(Google)开发的。Google通过一篇很有影响力的论文对这个计算模型进行了描述，本书附录部分可查看到该论文，名为《MapReduce：大数据之上的简化数据处理》。一年后，另一篇名为《Google文件系统》的论文介绍了Google文件系统。这两篇论文启发了道·卡丁（Doug Cutting）开发了Hadoop。
MapReduce这个术语来自于两个基本的数据转换操作：map过程和reduce过程。一个map操作会将集合中的元素从一种形式转换成另一种形式。在这种情况下，输入的键-值对会被转换成零到多个键-值对输出。其中，输入和输出的键必须完全不同，而输入和输出的值则可能完全不同。
在MapReduce计算框架中，某个键的所有键-值对都会被分发到同一个reduce操作中。确切地说，这个键和这个键所对应的所有值都会被传递给同一个Reducer。reduce过程的目的是将值的集合转换成一个值（例如对一组数值求和或求平均值），或者转换成另一个集合。这个Reducer最终会产生一个键-值对。再次说明一下，输入和输出的键和值可能是不同的。需要说明的是，如果job不需要reduce过程的话，那么也是可以无reduce过程的。
Hadoop提供了一套基础设施来处理大多数困难的工作以保证任务能够执行成功。例如，Hadoop决定如果将提交的job分解成多个独立的map和reduce任务（task）来执行，它就会对这些task进行调度并为其分配合适的资源，决定将某个task分配到集群中哪个位置（如果可能，通常是这个task所要处理的数据所在的位置，这样可以最小化网络开销）。它会监控每一个task以确保其成功完成，并重启一些失败的task。
Hadoop分布式文件系统（也就是HDFS），或者一个同类的分布式文件系统，管理着集群中的数据。每个数据块（block）都会被冗余多份（通常默认会冗余3份），这样可以保证不会因单个硬盘或服务器的损坏导致数据丢失。同时，因为其目标是优化处理非常大的数据集，所以HDFS以及类似的文件系统所使用的数据块都非常大，通常是64MB或是这个值的若干倍。这么大的数据块可以在硬盘上连续进行存储，这样可以保证以最少的磁盘寻址次数来进行写入和读取，从而最大化提高读写性能。
为了更清晰地介绍MapReduce，让我们来看一个简单的例子。Word Count算法已经被称为是MapReduce计算框架中的“Hello World”程序[7]了。Word Count会返回在语料库（单个或多个文件）中出现的所有单词以及单词出现的次数。输出内容会显示每个单词和它的频数，每行显示一条。按照通常的习惯，单词（输出的键）和频数（输出的值）通常使用制表符进行分割。
图1-1 显示了在MapReduce计算框架中Word Count程序是如何运作的。
这里有很多内容要讲，所以我们会从左到右来讲解这个图。
图1-1中左边的每个Input（输入）框内都表示一个单独的文件。例子中有4个文件，其中第3个文件是个空文件，为了便于简单描述，其他3个文件都仅仅包含有少量几个单词。
默认情况下，每个文档都会触发一个Mapper进程进行处理。而在实际场景下，大文件可能会被划分成多个部分，而每个部分都会被发送给一个Mapper进行处理。同时，也有将多个小文件合并成一个部分供某个Mapper进行处理的方法。不过，我们当前不必深究这些细节性问题。
MapReduce计算框架中的输入和输出的基本数据结构是键-值对。当Mapper进程启动后，其将会被频繁调用来处理文件中的每行文本。每次调用中，传递给Mapper的键是文档中这行的起始位置的字符偏移量。对应的值是这行对应的文本。
在WordCount程序中，没有使用字符偏移量（也就是没有使用键）。值（也就是这行文本）可以使用很多种方式进行分割（例如，按照空格分隔是最简单的方式，但是这样会遗留下不需要的标点符号），最终这行文本会被分解成多个单词。我们同时假定Mapper会将每个单词转换成小写，因此对于“FUN”和“fun”会被认为是同一个单词。
最后，对于这行文本中的每个单词，Mapper都会输出一个键-值对，以单词作为键并以数字1作为值（这里1表示“出现1次”）。需要注意的是键和值的输出数据类型和输入数据类型是不同的。
Hadoop神奇的地方一部分在于后面要进行的Sort（排序）和Shuffle（重新分发）过程。Hadoop会按照键来对键-值对进行排序，然后“重新洗牌”，将所有具有相同键的键-值对分发到同一个Reducer中。这里有多种方式可以用于决定哪个Reducer获取哪个范围内的键对应的数据。这里我们先不必考虑这些问题。但是出于说明性目的，我们假设图中使用了一个特殊的按字母数字划分的过程（在实际执行中，会有所不同）。
对于Mapper而言如果只是简单地对每个单词输出计数1这样的处理的话，那么会在Sort和Shuffle过程中产生一定的网络和磁盘I/O浪费（不过，这样并不会减少Mapper的内存使用）。有一个优化就是跟踪每个单词的频数，然后在Mapper结束后只输出每个单词在这个Mapper中的总频数。对于这个优化有好几种实现方式，但是，最简单的方式应该是逻辑是正确的，而且对于这个讨论，理由是充足的。
每个Reducer的输入同样是键-值对，但是这次，每个键将是Mapper所发现的单词中的某一个单词，而这个键对应的值将是所有Mapper对于这个单词计算出的频数的一个集合。需要注意的是键的数据类型和值的集合中元素的数据类型和Mapper的输出是一致的。也就是说，键的类型是一个字符串，而集合中的元素的数据类型是整型。
为了完成这个算法，所有的Reducer需要做的事情就是将值集合中的频数进行求和然后写入每个单词和这个单词最终的频数组成的键-值对。
Word Count不是一个虚构的例子。这个程序所产生的数据可用于拼写检查程序、计算机语言检测和翻译系统，以及其他应用程序。
