本栏目（数据挖掘）下海量数据挖掘专题是个人对Coursera公开课海量数据挖掘（2015）的学习心得与笔记。所有内容均来自Coursera公开课MiningMassive Datasets中Jure Leskovec, Anand Rajaraman以及Jeff Ullman老师的讲解。（https://class.coursera.org/mmds-002/lecture）
第1讲——-MapReduce and PageRank
一、Distributed File System
随着海量数据的I/O与计算需求越来越大，受到带宽与单个CPU计算能力有限的限制，原来的Singles Node Architecture（单CPU，，单Memory以及单Disk）已经不能满足需求。这时传统的Cluster Architecture应运而生，如下图所示，用以解决大数据的存储与挖掘。
但是，传统的Cluster Architecture并没有完全解决问题，有如下的局限性：
MapReduce的出现就是为了解决传统Cluster Architecture的局限性。将数据冗余地存储在多个node上；Move computation close to data以减少数据的移动；提供Simple Programming Model影藏了分布式架构的复杂性。这三部分的内容都将会在接下来的内容中讲到。
其中第一个挑战的解决方案就是冗余存储架构，也就是经常提到的Distributed File System，例如Google GFS，Hadoop HDFS。它提供了全局的文件命名空间、冗余性以及可用性。典型的特点是Huge files；数据很少有update in place；常见的是数据的读取与文件末尾的添加。
Distributed File System的数据被切分成块chunks，每一个数据块都被复制多份保存在不同的machine上，这种情况下machine本身被称为chunk server。如下图所示，一个file被且分为C1-C6的数据块。chunk servers同时也扮演着compute servers的角色，这样就能实现Bring computation to data的目标。
总的来说，Distributed File System由如下的三部分组成：
二、 The MapReduce Computational Model
从经典的Word count的例子出发。假设有一个huge text document，需要统计其中distinct word出现的次数。对于Unix Shell来说，就是如下的一句命令：
这一条命令实际上已经道出了MapReduce用于word count的精髓。这三个步骤实际上都是可以并行化的，实际上也可以对应到MapReduce的如下三个过程。MapReduce的总体框架都是一样的，不同的问题只是Map和Reduce function相应的变化。具体的Map与Reduce的过程很简单，这里就不画图进行解释了。
那么更正式一点的来说，MapReduce Computational Model如下图所示。MapReduce的输入就是一系列的key-value对；Map就是对键值对进行映射；Reduce则针对相同的unique key进行需要的操作，然后输出结果。需要注意的是，当有多个reduce node的时候，map是通过hash函数讲相同的key放到同一个reduce函数上的。而且，使用的是sequence reading，节省时间。
三、Scheduling and Data Flow
接下来，稍微深入一些MapReduce具体在分布式上的实现机制，如下图所示。实际上有多个nodes，每个node都有多个Map或者Reduce在运行。途中的Partitioning Function其实就是一个Hash Function，当有多个reduce node的时候，map是通过hash函数讲相同的key放到同一个reduce函数上的。这样的话可能会有多个key放到同一个reduce上，Group by key的操作就是针对key进行排序，分成多拨跑reduce函数。
所以Programmer只需要提供Map和Reduce两个函数，然后MapReduce环境承担了剩下所有的事情：将输入数据划分成块；调度程序在一系列的机器中运行；Map操作之后运行Group by key步骤；处理node会fail的情况；负责机器之间的通信等。所以从Data Flow的角度来说，Input和final output都存储在DFS上，Scheduler尝试让map task在输入数据块的chunk server上执行，bring computation to data。Map或者Reduce产生的中间结果都只保存在worker的local FS上，一个Map/Reduce对的输出往往是另一个Map/Reduce对的输入。
Master node主要负责task的调度。task分为idle，in-progress以及completed。当有空闲的worker时，idle task即准备执行。当Map task完成的时候，会将产生的R个中间文件的位置info发送给master，Master则负责将这些信息发送给各个reducer。Master node会周期性地ping每一个work确保他们没有fail。
当Map worker fail的时候，所有completed以及in-progress task都会被reset为idle，会被重新调度在别的worker上执行；当Reduce worker fail的时候，只有in-progress task会被重新调度在别的worker执行，因为Reduce的输出就是final output，它已经被写入到DFS中而不是local DFS中，所以completed task没必要重新调度执行。那如果Master fail呢？MapReduce task终止并且发出警告，Master node没有复制对于它fail的概率也很低。
那一般来说需要多少的Map和Reduce的job？M要比集群中的node数量大很多，每一个DFS chunk分配一个Map是很常见的，这样提高了动态负载平衡以及加速了worker failures的恢复。R一般比M要少，因为最终的输出是需要将R个输出文件集中起来的，所以少的数量会比较好。
四、Combiners and Partition Functions
接下来介绍几个让MapReduce得以更高效率运行的改进。一个是Combiners。一个Map会经常产生大量的相同key的pair，例如在之前word count例子中的高频词汇。如果将这些Map产生的pair直接发送给Reduce，则需要大量的网络带宽损耗。Combiner的作用就是在每一个Mapper里将Map的输出结果进行一次结果的前期收集pre-aggregating，Combiner的操作usually和reduce function是一样的，如下图所示。
伟人所达到并保持着的高处，并不是一飞就到的，
