Spark Shuffle

1. Shuffle相关

当Map的输出结果要被Reduce使用时，输出结果需要按key哈希，并且分发到每一个Reducer上去，这个过程就是shuffle。由于shuffle涉及到了磁盘的读写和网络的传输，因此shuffle性能的高低直接影响到了整个程序的运行效率。概念上shuffle就是一个沟通数据连接（map和reduce）的桥梁。每个ReduceTask从每个Map Task产生数的据中读取一片数据，极限情况下可能触发M*R个数据拷贝通道（M是MapTask数目，R是Reduce Task数目）。

在Spark1.1之前，其shuffle只存在一种模式，即hash base。在Spark1.1版本之后加入了sort base。Spark1.1默认采用的shuffle模式还是hash base。在Spark1.2中，sort base将作为默认模式。当然，你可以通过shuffle manager进行配置。

2. Spark shuffle流程

·        首先每一个Mapper会根据Reducer的数量创建出相应的bucket，bucket的数量是M×R，其中M是Map的个数，R是Reduce的个数。

·        其次Mapper产生的结果会根据设置的partition算法填充到每个bucket中去。这里的partition算法是可以自定义的，当然默认的算法是根据key哈希到不同的bucket中去。

·        当Reducer启动时，它会根据自己task的id和所依赖的Mapper的id从远端或是本地的block manager中取得相应的bucket作为Reducer的输入进行处理。

这里的bucket是一个抽象概念，在实现中每个bucket可以对应一个文件，可以对应文件的一部分或是其他等。

通常shuffle分为两部分：Map阶段的数据准备和Reduce阶段的数据拷贝。首先，Map阶段需根据Reduce阶段的Task数量决定每个MapTask输出的数据分片数目，有多种方式存放这些数据分片：

1） 保存在内存中或者磁盘上（Spark和MapReduce都存放在磁盘上）；

2） 每个分片一个文件（现在Spark采用的方式，若干年前MapReduce采用的方式），或者所有分片放到一个数据文件中，外加一个索引文件记录每个分片在数据文件中的偏移量（现在MapReduce采用的方式）。

在Map端，不同的数据存放方式各有优缺点和适用场景。一般而言，shuffle在Map端的数据要存储到磁盘上，以防止容错触发重算带来的庞大开销（如果保存到Reduce端内存中，一旦Reduce Task挂掉了，所有Map Task需要重算）。但数据在磁盘上存放方式有多种可选方案，在MapReduce前期设计中，采用了现在Spark的方案（目前一直在改进），每个Map Task为每个Reduce Task产生一个文件，该文件只保存特定Reduce Task需处理的数据，这样会产生M*R个文件，如果M和R非常庞大，比如均为1000，则会产生100w个文件，产生和读取这些文件会产生大量的随机IO，效率非常低下。解决这个问题的一种直观方法是减少文件数目，常用的方法有：1) 将一个节点上所有Map产生的文件合并成一个大文件（MapReduce现在采用的方案），2) 每个节点产生{(slot数目)*R}个文件（Spark优化后的方案）。对后面这种方案简单解释一下：不管是MapReduce 1.0还是Spark，每个节点的资源会被抽象成若干个slot，由于一个Task占用一个slot，因此slot数目可看成是最多同时运行的Task数目。如果一个Job的Task数目非常多，限于slot数目有限，可能需要运行若干轮。这样，只需要由第一轮产生{(slot数目)*R}个文件，后续几轮产生的数据追加到这些文件末尾即可。因此，后一种方案可减少大作业产生的文件数目。

在Reduce端，各个Task会并发启动多个线程同时从多个Map Task端拉取数据。由于Reduce阶段的主要任务是对数据进行按组规约。也就是说，需要将数据分成若干组，以便以组为单位进行处理。大家知道，分组的方式非常多，常见的有：Map/HashTable（key相同的，放到同一个value list中）和Sort（按key进行排序，key相同的一组，经排序后会挨在一起），这两种方式各有优缺点，第一种复杂度低，效率高，但是需要将数据全部放到内存中，第二种方案复杂度高，但能够借助磁盘（外部排序）处理庞大的数据集。Spark前期采用了第一种方案，而在最新的版本中加入了第二种方案， MapReduce则从一开始就选用了基于sort的方案。

3. shuffle分析

3.1 shuffle写

Spark中需要Shuffle输出的ShuffleMapTask会为每个ResultTask创建对应的Bucket,ShuffleMapTask产生的结果会根据设置的partitioner得到对应的BucketId,然后填充到相应的Bucket中区。每个ShuffleMapTask的输出结果可能包含所有的ResultTask所需要的数据，所以每个ShuffleMapTask创建Bucket的数目是和ResultTask的数目相等。

ShuffleMapTask创建的Bucket对应磁盘上的一个文件，用于存储结果，此文件也被称为BlockFile。通过属性spark.shuffle.file.buffer.kb配置的缓冲区就是用来创建FastBufferedOutputStream输出流的。如果在配置文件中设置了属性spark.shuffle.consolidateFiles为true的话，ShuffleMapTask所产生的Bucket就不一定单独对应一个文件了，而是对应文件的一部分，这样做会大量减少产生的BlockFile文件数量。

ShuffleMapTask在某个节点上第一次执行时，会被每个ResultTask创建一个输出文件，并把这些文件组织成ShuffleFileGroup,当这个ShuffleMapTask执行结束后，当前创建的ShuffleFileGroup可以被释放掉，进行循环使用，当又有ShuffleMapTask在这个节点执行时，不需要创建新的输出文件，而是在上次的ShuffleFileGroup中已经创建的文件里追加写一个Segment；如果当前的ShuffleMapTask还没执行完，此时又在此节点上启动了新的ShuffleMapTask,那么新的ShuffleMapTask只能又创建新的输出文件再组成一个ShuffleFileGroup来进行结果输出。

3.2 shuffle读

前面ShuffleMapTask写结果，现在轮到ResultTask去读那些数据了。Spark可以使用两种方式来读取数据，一种是普通的Socket方式，一种是使用Netty框架。使用Netty方式的话，可以通过配置属性spark.shuffle.use.netty为true来启动。

ResultTask读数据时，会通过BlockManager根据BlockID把相关的数据返回给ResultTask。如果使用是Netty框架，BlockManaget会创建ShuffleSender专门用于发送数据。如果ResultTask所需要的数据恰好在本节点，那就直接去磁盘上读即可，不在通过网络获取，这点比MapReduce做得更好，MapReduce取数据时，即使数据在本地还是要走一遍网络传输。

Spark默认的Shuffle过程中的数据都没有经过排序（Hash模式），这一点也要比MapReduce框架节省很多时间。ResultTask读取过来的数据首先存放到HashMap中，如果数据量比较小，占用内存空间不会太大，如果数据量比较大，那就需要较多内存，内存不足该如何解决？

Spark提供了两种方式，根据spark.shuffle.spill的设置，当内存不够时，直接就失败。如果设置了可以Spill到磁盘，那就把内存中的数据溢写到磁盘中。写到磁盘前，先把内存中的HashMap排序，并且把内存缓冲区中的数据排序之后和写到磁盘上文件数据组成一个最小堆，每次从最小堆中读取最小的数据。

4. sort与hash模式

用来配置所使用的shuffle manager，目前可用的有：

org.apache.spark.shuffle.sort.HashShuffleManager（配置参数值为hash）org.apache.spark.shuffle.sort.SortShuffleManager（配置参数值为sort）

可在spark-default.conf中加入如下内容使用SORT模式：

Spark.shuffle.maager SORT

这两个ShuffleManager如何选择呢，首先需要了解他们在实现方式上的区别。

HashShuffleManager，故名思义也就是在Shuffle的过程中写数据时不做排序操作，只是将数据根据Hash的结果，将各个Reduce分区的数据写到各自的磁盘文件中。带来的问题就是如果Reduce分区的数量比较大的话，将会产生大量的磁盘文件。如果文件数量特别巨大，对文件读写的性能会带来比较大的影响，此外由于同时打开的文件句柄数量众多，序列化，以及压缩等操作需要分配的临时内存空间也可能会迅速膨胀到无法接受的地步，对内存的使用和GC带来很大的压力，在Executor内存比较小的情况下尤为突出，例如Spark on Yarn模式。

SortShuffleManager，是1.1版本之后实现的一个试验性（也就是一些功能和接口还在开发演变中）的ShuffleManager，它在写入分区数据的时候，首先会根据实际情况对数据采用不同的方式进行排序操作，底线是至少按照Reduce分区Partition进行排序，这样来至于同一个Map任务Shuffle到不同的Reduce分区中去的所有数据都可以写入到同一个外部磁盘文件中去，用简单的Offset标志不同Reduce分区的数据在这个文件中的偏移量。这样一个Map任务就只需要生成一个shuffle文件，从而避免了上述HashShuffleManager可能遇到的文件数量巨大的问题

两者的性能比较，取决于内存，排序，文件操作等因素的综合影响。

对于不需要进行排序的Shuffle操作来说，如repartition等，如果文件数量不是特别巨大，HashShuffleManager面临的内存问题不大，而SortShuffleManager需要额外的根据Partition进行排序，显然HashShuffleManager的效率会更高。

而对于本来就需要在Map端进行排序的Shuffle操作来说，如ReduceByKey等，使用HashShuffleManager虽然在写数据时不排序，但在其它的步骤中仍然需要排序，而SortShuffleManager则可以将写数据和排序两个工作合并在一起执行，因此即使不考虑HashShuffleManager的内存使用问题，SortShuffleManager依旧可能更快。

5. Shuffle相关属性

可在conf/spark-defaults.conf中配置，或者是在spark-submit --conf中提供参数

（eg.spark-submit --conf spark.shuffle.spill=false）