MapReduce的Shuffle过程介绍.docx

MapReduce 的 Shuffle 过程介绍 Shuffle 的本义是洗牌、混洗,把一组有一定规则的数据尽量转换成一组无规则的数据,越随机越好。 MapReduce 中的 Shuffle 更像是洗牌的逆过程,把一组无规则的数据尽量转换成一组具有一定规则的数据。为什么 MapReduce 计算模型需要 Shuffle 过程?我们都知道 MapReduce 计算模型一般包括两个重要的阶段: Map 是映射, 负责数据的过滤分发; Reduce 是规约, 负责数据的计算归并。 Reduce 的数据来源于 Map , Map 的输出即是 Reduce 的输入, Reduce 需要通过 Shuffle 来获取数据。从 Map 输出到 Reduce 输入的整个过程可以广义地称为 Shuffle 。 Shuffle 横跨 Map 端和 Reduce 端,在 Map 端包括 Spill 过程,在 Reduce 端包括 copy 和 sort 过程,如图所示: Spill 过程 Spill 过程包括输出、排序、溢写、合并等步骤,如图所示: Collect 每个 Map 任务不断地以对的形式把数据输出到在内存中构造的一个环形数据结构中。使用环形数据结构是为了更有效地使用内存空间,在内存中放置尽可能多的数据。这个数据结构其实就是个字节数组,叫 Kvbuffer ,名如其义,但是这里面不光放置了数据, 还放置了一些索引数据,给放置索引数据的区域起了一个 Kvmeta 的别名,在 Kvbuffer 的一块区域上穿了一个 IntBuffer ( 字节序采用的是平台自身的字节序) 的马甲。数据区域和索引数据区域在 Kvbuffer 中是相邻不重叠的两个区域,用一个分界点来划分两者,分界点不是亘古不变的,而是每次 Spill 之后都会更新一次。初始的分界点是 0 ,数据的存储方向是向上增长,索引数据的存储方向是向下增长,如图所示: Kvbuffer 的存放指针 bufindex 是一直闷着头地向上增长,比如 bufindex 初始值为 0 ,一个 Int 型的 key 写完之后, bufindex 增长为 4, 一个 Int 型的 value 写完之后, bufindex 增长为 8。索引是对在 kvbuffer 中的索引,是个四元组,包括: value 的起始位置、 key 的起始位置、 partition 值、 value 的长度, 占用四个 Int 长度, Kvmeta 的存放指针 Kvindex 每次都是向下跳四个“格子”, 然后再向上一个格子一个格子地填充四元组的数据。比如 Kvindex 初始位置是-4 ,当第一个写完之后, (Kvindex+0) 的位置存放 value 的起始位置、(Kvindex+1) 的位置存放 key 的起始位置、(Kvindex+2) 的位置存放 partition 的值、(Kvindex+3) 的位置存放 valu e 的长度,然后 Kvindex 跳到-8 位置,等第二个和索引写完之后, Kvindex 跳到-32 位置。 Kvbuffer 的大小虽然可以通过参数设置, 但是总共就那么大, 和索引不断地增加, 加着加着, Kvbuffer 总有不够用的那天, 那怎么办?把数据从内存刷到磁盘上再接着往内存写数据,把 Kvbuffer 中