前面两篇分别是 分别简单介绍了Hadoop出现之前的故事，以及Hadoop出现的过程，本次我们尝试简单介绍一下Hadoop的两大组件Map-reduce和HDFS，分别是存储和计算引擎。
对于了解或者听说过Map-reduce的同学，大概了解Map-reduce最核心的部分和持续优化的部分是shuffle过程，这里我们只是简单介绍一下shuffle为什么需要排序，排序和Map-reduce之间的关系。
先跳出来看一下，Map-reduce在各个公司大行其道之后，主要用来做什么，OLAP，On-Line Analytical Processing，在进一步剖析一下，OLAP主要用来做什么，这个涉及到数据仓库里面的一些问题，简单说一下基本就是rollup和drilldown，在mart表和各个fact表上面的上卷和下钻，下钻基本是通过拆分更加的粒度来实现的，在上卷基本就是group聚集之后求各种统计值，Sum，Max，Mean，Min，count，distinctcount等。我们重点看一下上卷的问题。
我们尝试用一个具体业务场景来说明这个问题，假设我们是一个网站，现在想统计一下每一篇文章的DAU。即daily的uniq user访问数量，为了表达问题更加简单，假设用户的访问日志只有两列，分别是用户ID和url位置。例如下表所示。
<table><tbody>USER
URL
Id1
www.test.com/doc1
Id2
www.test.com/doc2
Id3
www.test.com/doc3
Id4
www.test.com/doc1
Id2
www.test.com/doc3
Id1
www.test.com/doc1
基于上图进行统计的话对应的url的DAU如下所示
<table><tbody>URL
DAU
www.test.com/doc1
2
www.test.com/doc2
1
www.test.com/doc3
2
对于这样一个问题，首先注意，用户访问的顺序基本是按照服务器接到访问请求为顺序的，所以会存一个用户在不同时间点击了同一个文章，在现实世界中也是存在这个情景的。
问题介绍清楚了，下面在想一下解决方案，先从简单的入手，假设只有一个文件还很小100M左右，方法其实很容易想到，基本刚学过数据结构大二的学生就可以想到一个解决方法，使用Hash表来解决，key为url，value利用一个list来代表，里面存储所有的userid，当有一条新纪录时，先利用key来查找，如果没有直接插入新元素，如果已经存在则在基于list判断userid是否出现过，如果出现过直接抛弃，没有出现过则append上去。最后统计一下各个key后面list的长度即可。
上面看来问题似乎解决了，但是我们要求的条件太完美了，文件足够小内存足够大，但是现实中往往不是这样，现在用户量访问量过亿的大有存在，即便是千万的也不在少数，在这种情况下单机很难处理情况下，怎么做呢？
先来刨析一下这个问题，难处理的原因主要是我们需要在内存中保存一个完整的Hash结构，Hash本省就非常的耗内存。那有什么办法用尽量少的内存来解决呢。我们先来想一个最理想的状态，假设内存只占用一条记录，我们每次读到文件里面的的一条可以做出判断，要么在内存中进行累加要么结束。这样基本不占内存。但是在现实情况下这个是实现不了了，因为我们必须在内存中保存多个url的信息，因为我们无法判断后续是否还有当前url的访问。
好，到目前位置，我们只要能解决，我知道当前之后在没有这个url的信息了，就可以达到内存只保留一条的情况了。怎么做到这一点呢？对排序。
其实排序算法出来之后很多时候都用来做数据统计当中了。
假设我们将原来的url和user进行排序后的效果
<table><tbody>USER
URL
Id1
www.test.com/doc1
Id1
www.test.com/doc1
Id4
www.test.com/doc1
Id2
www.test.com/doc2
Id2
www.test.com/doc3
Id3
www.test.com/doc3
这样每次进来一条日志，如果url相同直接并且user不同，则apeend，否则丢弃，如果url不同，则刷新到结果，修改要累加的url。那用什么方法排序呢？现在重新回到Mapreduce，既然作为一个生成环境大量使用的系统，稳定是第一位的，尤其是在数据量出现波动的情况，这个不由得想起来鹿晗十一爆发恋情，搞挂微博服务器的情况。所以mapreduce选择了经典的外排序方法mergesort，他可能不是效率最高的排序算法，但是他可以在数据量增大的情况下仍旧稳定运行，并且很容易进行横向扩展。
閱讀更多 北京IT民工 的文章
