Hadoop是使用非常广泛的一种云计算平台，研究生阶段的研究方向就是Hadoop资源调度，我即将去面试Hadoop研发工程师，下面是我准备的一些面试资料。

MapReduce排序过程 MapReduce中排序发生在哪几个阶段？这些排序是否可以避免，为什么？

答：一个MapReduce作业由Map阶段和Reduce阶段两部分组成，这两个阶段会对数据排序，从这个意义上说，MapReduce框架本质上就是一个Distributed Sort。在Map阶段，Map Task会在本地磁盘输出一个按照key排序（采用的是快速排序）的文件（中间可能产生多个文件，但最终会合并成一个），在Reduce阶段，每个Reduce Task会对收到的数据排序，这样，数据便按照key分成了若干组，之后以组为单位交给reduce()处理。很多人的误解在Map阶段，以为如果不使用Combiner便不会排序，这是错误的，不管你用不用Combiner，Map Task均会对产生的数据进行排序（如果没有Reduce Task，则不会排序，实际上Map阶段的排序就是为了减轻Reduce端排序负载）。由于这些排序是MapReduce系统自动完成的，用户无法控制，因此，在hadoop 1.x中无法避免，也不可以关闭，但hadoop 2.x是可以关闭的。

二次排序编写MapReduce作业时，如何做到在Reduce阶段，先对key排序，再对value排序？

答：该问题通常称为“二次排序”，最常用的方法是将value放到key中，实现一个组合Key，然后自定义key排序规则（为key实现一个WritableComparable）。

全排序如何使用MapReduce实现全排序（即数据整体key有序）？你给出的算法可能要求仅启动一个Reduce Task，那么如何对算法改进，可以同时启动多个Reduce Task提高排序效率。

答：直接可以想到的方法是“多个map task”+“一个reduce task”，其中各个map task对自己负责的数据进行排序，而唯一的reduce task则实现全局排序。这种方法最大的问题是reduce task只有一个，存在性能瓶颈。一种常见的优化方法是基于采样的排序方法，Hadoop自带的terasort例子便是这么实现的，有兴趣的读者可阅读我的这篇文章（直接在google中搜索文章标题即可找到）：“Hadoop中TeraSort算法分析”。

作业运行调优如何对MapReduce作业进行调优（可从参数配置、程序编写等角度说明）

答：参考《Hadoop技术内幕：深入解析MapReduce架构设计与实现原理》中“9.3从用户角度进行调优”。

系统调优如果对MapReduce系统进行调优（可从操作系统配置、参数配置等角度说明）

答：参考Hadoop技术内幕：深入解析MapReduce架构设计与实现原理》中“9.2　从管理员角度进行调优”。

资源管理模型Hadoop MapReduce中资源管理模型是怎样的，有什么缺点，如何改进？

答：MapReduce将资源划分成map slot和reduce slot，其中map slot供map task使用，reduce slot供reduce slot使用，这种模型存在以下几个问题：（1）slot之间不能共享，导致资源利用率低（比如map slot空闲而reduce slot紧缺时，Reduce Task不能使用空闲的map slot），（2）slot数目静态配置，不能动态修改（3）slot这种划分资源方式粒度过大，导致集群资源利用情况不好精细化控制，比如一个map task可能无法充分利用一个map slot对应的资源。具体改进方法可参考《Hadoop技术内幕：深入解析MapReduce架构设计与实现原理》中“6.7.4　Hadoop资源管理优化”

join实现

1. reduce side join
   reduce side join是一种最简单的join方式，其主要思想如下：
   在map阶段，map函数同时读取两个文件File1和File2，为了区分两种来源的key/value数据对，对每条数据打一个标签（tag）,比如：tag=0表示来自文件File1，tag=2表示来自文件File2。即：map阶段的主要任务是对不同文件中的数据打标签。
   在reduce阶段，reduce函数获取key相同的来自File1和File2文件的value list，然后对于同一个key，对File1和File2中的数据进行join（笛卡尔乘积）。即：reduce阶段进行实际的连接操作。

2. map side join
   之所以存在reduce side join，是因为在map阶段不能获取所有需要的join字段，即：同一个key对应的字段可能位于不同map中。Reduce side join是非常低效的，因为shuffle阶段要进行大量的数据传输。
   Map side join是针对以下场景进行的优化：两个待连接表中，有一个表非常大，而另一个表非常小，以至于小表可以直接存放到内存中。这样，我们可以将小表复制多份，让每个map task内存中存在一份（比如存放到hash table中），然后只扫描大表：对于大表中的每一条记录key/value，在hash table中查找是否有相同的key的记录，如果有，则连接后输出即可。
   为了支持文件的复制，Hadoop提供了一个类DistributedCache，使用该类的方法如下：
   （1）用户使用静态方法DistributedCache.addCacheFile()指定要复制的文件，它的参数是文件的URI（如果是HDFS上的文件，可以这样：hdfs://namenode:9000/home/XXX/file，其中9000是自己配置的NameNode端口号）。JobTracker在作业启动之前会获取这个URI列表，并将相应的文件拷贝到各个TaskTracker的本地磁盘上。（2）用户使用DistributedCache.getLocalCacheFiles()方法获取文件目录，并使用标准的文件读写API读取相应的文件。

3. SemiJoin
   SemiJoin，也叫半连接，是从分布式数据库中借鉴过来的方法。它的产生动机是：对于reduce side join，跨机器的数据传输量非常大，这成了join操作的一个瓶颈，如果能够在map端过滤掉不会参加join操作的数据，则可以大大节省网络IO。
   实现方法很简单：选取一个小表，假设是File1，将其参与join的key抽取出来，保存到文件File3中，File3文件一般很小，可以放到内存中。在map阶段，使用DistributedCache将File3复制到各个TaskTracker上，然后将File2中不在File3中的key对应的记录过滤掉，剩下的reduce阶段的工作与reduce side join相同。
   更多关于半连接的介绍，可参考：半连接介绍：http://wenku.baidu.com/view/ae7442db7f1922791688e877.html
4. reduce side join + BloomFilter
   在某些情况下，SemiJoin抽取出来的小表的key集合在内存中仍然存放不下，这时候可以使用BloomFiler以节省空间。
   BloomFilter最常见的作用是：判断某个元素是否在一个集合里面。它最重要的两个方法是：add() 和contains()。最大的特点是不会存在false negative，即：如果contains()返回false，则该元素一定不在集合中，但会存在一定的true negative，即：如果contains()返回true，则该元素可能在集合中。
   因而可将小表中的key保存到BloomFilter中，在map阶段过滤大表，可能有一些不在小表中的记录没有过滤掉（但是在小表中的记录一定不会过滤掉），这没关系，只不过增加了少量的网络IO而已。

url排序给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
分而治之/hash映射：遍历文件a，对每个url求取，然后根据所取得的值将url分别存储到1000个小文件（记为）中。这样每个小文件的大约为300M。遍历文件b，采取和a相同的方式将url分别存储到1000小文件中（记为）。这样处理后，所有可能相同的url都在对应的小文件中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
hash统计：求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

压缩Hadoop中的压缩算法及压缩的好处

gzip：压缩格式不能被分块，并行的处理
bzip2：支持分块处理，但是解压的过程非常的缓慢，使job的瓶颈转移到了cpu上
lzo：支持分块并行的处理，速度也非常的快
好处：在hadoop中使用lzo的压缩算法可以减小数据的大小和数据的磁盘读写时间，在HDFS中存储压缩数据，可以使集群能保存更多的数据，延长集群的使用寿命。不仅如此，由于mapreduce作业通常瓶颈都在IO上，存储压缩数据就意味这更少的IO操作，job运行更加的高效

常用链接

        Hadoop 自动安装脚本：http://metooxi.iteye.com/blog/1517552

        云创存储解决方案：http://www.cstor.cn/Download_1026.html