概述

介绍Spark Shuffle的概念及三种实现，hash shuffle、sort shuffle、tungsten-sort shuffle。

Shuffle

Spark 官方文档Shuffle operations部分对Shuffle做了简要介绍。

背景

Spark是分布式计算系统，数据块在不同节点执行，但是一些操作，例如join，需要将不同节点上相同的Key对应的Value聚集到一起，Shuffle便应运而生。

影响

Shuffle是昂贵的操作，首先其涉及到网络IO，此外，Spark中Shuffle是一定落磁盘的，所以又涉及到磁盘IO。Spark默认使用32KB的memory buffer存储Shuffle的中间结果，如果buffer满了就会写入磁盘，生成一个小文件，每个Partition的多个小文件会在map端处理结束后合并为一个大文件，这些临时文件会在对应的application结束后被删除。

Hadoop MapReduce

提到Shuffle不得不提Mapreduce，其一，Mapreduce是我接触的第一个分布式计算模型，相信对很多人也是如此，其实现很经典。其二，学习了Spark的Shuffle之后，Spark sort shuffle的流程和MapReduce一模一样，细微不同之处在于sort shuffle中sort是可选的，因此，懂了MapReduce也就是懂了Spark sort shuffle。

上图描述了MapReduce的过程，大致如下

read、compute and buffer in memory map task读取数据，计算并将数据存储在内存。sort、spill to disk and merge 内存不足，数据溢写到磁盘，溢写的数据是已经sort的，最后对溢写的磁盘数据再进行一次merge sort。reduce fetch data and merge reduce task读取map的输出，并进行归并排序。compute and output 对归并后的数据进行计算并输出。

对于Mapreduce过程的理解并没有结合源码，定有纰漏之处，大致介绍这个过程是Spark Shuffle的铺垫。

触发Shuffle的操作

分为以下三类

repartition相关 repartition、coalesce*ByKey操作groupByKey、reduceByKey、combineByKey、aggregateByKey等join相关cogroup、join

实现

Spark中先后实现了三个Shuffle算法，如下 接下来分别介绍hash shuffle、sort shuffle、tungsten-sort shuffle的实现细节。

hash shuffle

Spark Shuffle之Hash Shuffle

sort shuffle

Spark Shuffle之SortShuffleWriter

tungsten-sort shuffle

Spark Shuffle之Tungsten-Sort

参考： Shuffle operations Spark Architecture: Shuffle