Spark原理篇之Shuffle详解
1 Shuffle简介
Shuffle描述数据从Map Task输出到Reduce Task输入的这段过程。Shuffle是连接Map和Reduce之间的桥梁，Map的输出要用到Reduce中必须经过Shuffle这个环节，Shuffle的性能高低直接影响了整个程序的性能和吞吐量。因为在分布式情况下，Reduce Task需要跨节点去拉取其他节点上的Map Task结果。这一过程将会产生网络资源消耗和内存，次哦按IO的消耗。通常Shuffle分为两部分：Map阶段的数据准备和Reduce节点的数据拷贝处理。一般在Map端的Shuffle称之为Shuffle Write，在Reduce端的Shuffle成为Shuffle Read。
2 Spark Shuffle
在Spark 1.2以前，默认的Shuffle计算引擎是HashShuffleManager，它有着一个非常严重的弊端，就是会产生大量的中间磁盘文件，进而由大量的磁盘IO操作影响了性能。因此在Spark 1.2以后的版本中，计算引擎改成了SortShuffleManager，它的改进之处主要在于每个Task在进行Shuffle操作时，虽然产生较多的临时磁盘文件，但是最后会将所有的临时文件合并（merge）成一个磁盘文件，因此每个Task就只有一个磁盘文件。在下一个Stage的Shuffle Read Task拉取自己的数据时，只要根据索引读取每个磁盘文件中的部分数据即可。
2.1 Hash Shuffle
HashShuffleManager的运行机制主要分成两种，一种是普通运行机制，另一种是合并的运行机制。合并机制主要是通过复用Buffer来优化Shuffle过程中产生的小文件的数量。Hash Shuffle是不具有排序的Shuffle。
2.1.1 普通机制的Hash Shuffle 
（1）图解
这里我们先明确一个假设前提：每个Executor只有1个CPU Core，也就是说，无论这个Executor上分配多少个Task线程，同一时间都只能执行一个Task线程。
图中有3个Reducer，从Task开始将数据中的key进行Hash计算（分区器：hash/numreduce取模），分类出3个不同的类别，每个Task都分成3种类别的数据，想把不同的数据汇聚，然后计算出最终的结果，所以Reducer会在每个Task中把属于自己类别的数据收集过来，汇聚成一个同类别的大集合，每1个Task输出3份本地文件，这里有4个Mapper Tasks，所以总共输出了4个Tasks3个分类文件=12个本地小文件。
（2）Shuffle Write阶段
主要就是在一个Stage结束计算之后，为了下一个Stage可以执行Shuffle类的算子（比如reduceByKey，groupByKey），而将每个Task处理的数据按key进行分区。所谓分区，就是对相同的key执行Hash算法，从而将相同key都写入同一个磁盘文件中，而每一个磁盘文件都只属于Reduce端的Stage的一个Task。在将数据写入磁盘之前，会先将数据写入内存缓冲中，当内存缓冲填满之后，才会溢写到磁盘文件中去。
那么每个执行Shuffle Write的Task，要为下一个Stage创建多少个磁盘文件呢？很简单，下一个Stage的Task有多少个，当前Stage的每个Task就要创建多少份磁盘文件。比如下一个Stage总共有100个Task，那么当前Stage的每个Task都要创建100份磁盘文件。如果当前Stage有50个Task，总共有10个Executor，每个Executor执行5个Task，那么每个Executor上总共就要创建500个磁盘文件，所有Executor上会创建5000个磁盘文件。由此可见，未经优化的Shuffle Write操作所产生的的磁盘文件的数量时极其惊人的。
（3）Shuffle Read阶段
Shuffle Read通常就是一个Stage刚开始时要做的事情。此时该Stage的每一个Task就需要将上一个Stage的计算结果中所有相同key，从每个节点上通过网络拉取到自己所在的节点上，然后进行key的聚合或连接等操作。由于Shuffle Write的过程中，Task给Reduce端的Stage的每个Task都创建一个磁盘文件，因此Shuffle Read的过程中，每个Task只要从上游Stage的所有Task所在节点上，拉取属于自己的那一个磁盘文件即可。
Shuffle Read的拉取过程是一边拉取一边聚合的。每个Shuffle Read Task都会有一个自己的Buffer缓冲，每次都只能拉取与Buffer缓冲相同大小的数据，然后通过内存中的一个Map进行聚合等操作。聚合完一批数据后，再拉取下一批数据，并放到Buffer缓冲中进行聚合操作。以此类推，直到最后将所有数据拉取完，并得到最终的结果。
（4）注意
① Buffer起到的是缓存作用，缓存能够加速写磁盘，提高计算的效率，Buffer的默认大小32k。分区器：根据hash/numRedcue取模决定数据由几个Reduce处理，也决定了写入几个buffer中。Block File：磁盘小文件，从图中我们可以知道磁盘小文件的个数计算公式：Block File=MR。
② M为Map Task的数量，R为Reduce的数量，一般Reduce的数量等于Buffer的数量，都是由分区器决定的。
（5）Hash Shuffle普通机制的问题
① Shuffle前在磁盘上会产生海量的小文件，建立通信和拉取数据的次数变多，此时会产生大量耗时低效的IO操作（因为产生过多的小文件）；
② 可能导致OOM（out of memory，内存不够），大量耗时低效的IO操作，导致写磁盘时对象过多，这些对象存储在堆栈内存中，会导致内存不足，相应会导致频繁的GC，GC会导致OOM。由于内存中需要保存海量文件操作句柄和临时信息，如果数据处理的规模比较庞大的话，内存不可承受，会出现OOM等问题。
2.1.2 合并机制的Hash Shuffle
合并机制就是复用Buffer，开启合并机制的配置使spark.shuffle.consolidateFiles。该参数默认值为flase，将其设置为true即可开启优化机制。通常来说，如果我们使用HashShuffleManager，那么都建议开启这个选项。
这里还是有4个Tasks，数据类型还是分成3中类型，因为Hash算法会根据你的key进行分类，在同一个进程中，无论是有多少个Task，都会把同样的key放在同一Buffer里，然后把Buffer中数据写入以Core数量为单位的本地文件中（一个Core只有一种类型的key的数据），每1个Task所在的进程中，分别写入共同进程中的3份本地文件，这里有2个Mapper Tasks，所以总输出是2个Cores3个分类文件=6个本地小文件。
（1）图解：
开启consolidate机制之后，在Shuffle Write过程中，Task就不是为下游Stage的每个Task创建一个磁盘文件了。此时会出现ShuffleFileGroup的概念，每个ShuffleFileGroup会对应一批磁盘文件，磁盘文件的数量与下游Stage的Task数量是相同的。一个Executor上有多少个CPU Core，就可以并行执行多少个Task。而第一批并行执行的每个Task都会创建一个ShuffleFileGroup，并将数据写入对应的磁盘文件内。
Executor的CPU Core执行完一批Task，接着执行下一批Task时，下一批Task就会复用之前已有的ShuffleFileGroup，包括其中的磁盘文件。也就是说，此时Task会将数据写入已有的磁盘文件中，而不会写入到新的磁盘那文件中。因此，consolidate机制允许不同的Task复用同一批磁盘文件，这样就可以有效将多个Task的磁盘文件进行一定程度上的合并，从而大幅度减少磁盘文件的数量，进而提升Shuffle Write的性能。
假设第二个Stage有100个Task，第一个Stage有50个Task，总共还是有10个Executor，每个Executor执行5个Task。那么原本使用未经优化的HashShuffleManager时，每个Executor会产生500个磁盘文件，所有Executor会产生5000个磁盘文件的。但是此时经过优化之后，每个Executor创建的磁盘文件的数量的计算公式为：CPU Core的数量下一个Stage的Task数量。也就是说，每个Executor此时只会创建100个磁盘文件，所有Executor智慧创建1000个磁盘文件。
（2）注意：
① 启动HashShuffle的合并机制ConsolidatedShuffle的配置：spark.shuffle.consolidateFiles=true。
② Block File=CoreR：其中Core为CPU的核数，R为Reduce的数量。
（3）Hash Shuffle合并机制的问题
如果Reducer端的并行任务或者是数据分片过多的话则CoreReducer Task依旧过大，也会产生很多小文件。
2.2 Sort Shuffle
SortShuffleManager的运行机制主要分成两种，一种是普通运行机制，另一种是bypass运行机制。当Shuffle Read Task的数量小于等于spark.shuffle.sort.bypassMergeThreshold参数的值时（默认为200），就会启用bypass机制。
2.2.1 Sort Shuffle的普通机制
（1）写入内存数据结构
该图说明了普通的SortShuffleManager的原理。在该模式下，数据会先写入一个内存数据结构中（默认5M），此时根据不同的Shuffle算子，可能选用不同的数据结构。如果是reduceByKey这种聚合类的Shuffle算子，那么会选用Map数据结构，一边通过Map进行聚合，一边写入内存；如果是join这种普通的Shuffle算子，那么就会选用Array数据结构，直接写入内存。接着，每写一条数据进入内存数据结构之后，就会判断一下，是否达到了某个临界阈值。如果达到临界阈值的话，那么就会尝试将内存数据结构中的数据溢写到磁盘，然后清空内存数据结构。
（2）注意
Shuffle中的定时器：定时器会检查内存数据结构的大小，如果内存数据结构空间不够，那么会申请额外的内存，申请的大小满足如下的公式：applyMemory=nowMemory2-oldMemry（申请的内存=当前的内存情况2-上一次的内嵌情况）。意思就是说内存数据结构的大小的动态变化，如果存储的数据超出内存数据结构的大小，将申请内存数据结构存储的数据2-内存数据结构的设定值的内存大小空间。申请到了，内存数据结构的大小变大，内存不够，申请不到，则发生溢写。
（3）排序
在溢写到磁盘文件之前，会根据key对内存数据结构中已有的数据进行排序。
（4）溢写
排序过后，会分批将数据写入磁盘文件。默认的batch数量时10000条，也就是说，排序好的数据，会以每批1万条数据的形式分批写入磁盘文件。写入磁盘文件是通过Java的BufferedOutputStream实现的。BufferedOutputStream是Java的缓冲输出流，首先会将数据缓冲在内存中，当内存缓冲满溢之后再一次写入磁盘文件中，这样可以减少磁盘IO次数，提升性能。
（5）Merge
一个Task将所有数据写入将所有数据写入内存数据结构的过程中，会发生多次磁盘溢写操作，也就会产生多个临时文件。最后会将所有的临时磁盘文件都进行合并，这就是Merge过程，此时会将之前所有临时磁盘文件中的数据读取出来，然后依次写入最终的磁盘文件之中。此外，由于一个Task就只对应一个磁盘文件，也就意味着该Task为Reduce端的Stage的Task准备的数据都在这一个文件中，因此还会单独写一份索引文件，其中标识了下游各个Task的数据在文件中的Start Offset与End Offset。
SortShuffleManager由于有一个磁盘文件Merge的过程，因此大大减少了文件数量。比如第一个Stage有50个Task，总共有10个Executor，每个Executor执行5个Task，而第二个Stage有100个Task。由于每个Task最终只有一个磁盘文件，因此此时每个Executor上只有5个磁盘文件，所有Executor只有50个磁盘文件。
（6）注意
① Block File=2M：一个Map Task会产生一个索引文件和数据大文件。
② MR>2*M(R>2)：SortShuffle会使得磁盘小文件的个数再次减少。
2.2.2 Sort Shuffle的bypass机制
（1）bypass运行机制的触发条件如下
① Shuffle Map Task数量小于spark.shuffle.sort.bypassMergeThreshold参数的值。
② 不是聚合类的Shuffle算子（比如reduceByKey）。
此时Task会为每个Reduce端的Task都创建一个临时文件，并将数据按key进行Hash然后根据key的Hash值，将key写入到对应的磁盘文件之中。当然，写入磁盘文件也是先写入内存缓冲，缓冲写满之后再溢写到磁盘文件的。最后，同样将所有临时文件都合并成一个磁盘文件，并创建一个单独的索引文件。
该过程的磁盘写机制其实跟未经优化的HashShuffleManager是一模一样的，因为都要创建数量惊人的磁盘文件，只是在最后会做一个磁盘文件的合并而已。因此少量的最终磁盘文件，也让该机制相对于未经优化的HashShuffleManager来说，Shuffle Read的性能会更好。
而该机制与普通SortShuffleManager运行机制的不同在于：
① 磁盘写机制不同；
② 不会进行排序。也就是说，启用该机制的最大好处在于，Shuffle Write过程中，不需要进行数据的降序操作，也就节省掉了这部分的性能开销。
3 总结
Shuffle过程本质上都是将Map端获得的数据使用分区器进行划分，并将数据发送给对应的Reducer的过程。
Shuffle作为处理连接Map端和Reduce端的枢纽，其Shuffle的性能高低直接影响了整个程序的性能和吞吐量。Map端的Shuffle一般为Shuffle的Write阶段，Reduce端的Shuffle一般为Shuffle的Read阶段。Hadoop和Spark的Shuffle在实现上面存在很大的不同，Spark的Shuffle分为HashShuffle和SortShuffle。
HashShuffle又分为普通机制和合并机制，普通机制因为其会产生MR个数的巨量磁盘小文件而产生大量性能低下的Io操作，从而性能较低，因为其巨量的磁盘小文件还可能导致OOM，HashShuffle的合并机制通过重复利用Buffer从而将磁盘小文件的数量降低到CoreR个，但是当Reducer 端的并行任务或者是数据分片过多的时候，依然会产生大量的磁盘小文件。
SortShuffle也分为普通机制和bypass机制，普通机制在内存数据结构(默认为5M)完成排序，会产生2*M（Map Task的数量的2倍）个磁盘小文件。而当Shuffle Map Task数量小于spark.shuffle.sort.bypassMergeThreshold参数的值。或者算子不是聚合类的shuffle算子(比如reduceByKey)的时候会触发SortShuffle的bypass机制，SortShuffle的bypass机制不会进行排序，极大的提高了其性能。