MapReduce原理及shuffle机制

一、环形缓冲区

1.数据在环形缓冲区以KV的形式存在，索引和数据同向增长，当增长到缓冲区大小（默认128M）的80%时（只是80%左右，不是必须80%）开始溢写

2.索引占用四个int长度，以一个四元组的形式存在：value的起始位置，key的起始位置，partition值，value的长度。每进一条数据，指针每次向下跳动4个格子，然后补齐上面的值

3.发生在环形缓冲区的排序是对索引的排序，再具体是对partition值和key进行排序，将相同的partition放到一起，同一个partition内按照key进行排序（快排）

4.当第一次溢写后，索引和数据文件相遇，然后以中间空出来的空间的中间位置作为新的分界线，反向增长。

 二、maptask机制后半段（溢写之后）

1.对多次溢写的文件进行merge，合并分区，分区内数据进行排序。

2.在merge后只会有一个file.out文件和一个fiile.index文件，一个存放最终输出，一个存放最终索引。

3.在这里逐一将相同的partition的数据放到一个里面，一个一个partition进行合并，每个partition里面的数据按照key进行排序，每次取出最小的放到临时文件，最后输出到最终文件

三、shuffle

这里借用网图做一个整体流程梳理（注意：shuffle过程只是图的中间部分，准确描述为map方法结束后，reduce方法开始前，这里展示的图只是为了帮助更好的从全局理解整个过程）

1.每个map读取的数据进入环形缓冲区（kvbuffer，默认100M）后，索引和数据同向增加

2.当到达环形缓冲区内存的80%左右时，开始溢写（溢写前会对数据进行分区排序）

3.数据溢写的同时，索引和数据会以上次相遇的剩余空间的中间位置作为分界线，反向存放数据

4.每个map会溢写多次，在磁盘上生成多个文件。 Combiner（可选过程，会在map阶段先聚合一次，所以如果要取平均数这样的数据，这个过程不可以有的，因为平均数这个值不可以累加）存在的时候，这些文件会在各个map中独立进行merge（这里第二次会对数据文件进行分区排序）

5.最终每个map对应生成一个文件提供给reduce

6.reduce将数据copy到内存里面，如果内存不够，会直接溢写到磁盘里，这里需要注意：①当若干个map任务，只要有一个全部执行成，reduce就会去找对应的partition的数据进行copy，不是非要等到map全部执行完毕。②每个reduce的线程并行度是5，就是默认会有5个线程同时去map端拉去所对应的数据。③如果从某个map拉去数据失败，断开连接等情况，reduce会去其他的map下载数据，这个可以延长下载时间来避免数据不完整，公司一般都会增大这个时间mapreduce.reduce.shuffle.read.timeout，默认180000秒。

7.在reduce中进行merge，这次的区别是将来自多个map端输出的数据进行分区，排序，shuffle结束。然后进入自定义的reduce方法中进行逻辑处理