在MapReduce框架中，shuffle是连接Map和Reduce之间的桥梁，Map的输出要用到Reduce中必须经过shuffle这个环节，shuffle的性能高低直接影响了整个程序的性能和吞吐量。Spark作为MapReduce框架的一种实现，自然也实现了shuffle的逻辑。
Spark-Shuflle发展阶段
Spark-Shuflle1: HashShuflle阶段，生成MM*RR个中间小文件，MM为Map数量，RR为Reduce数量；
Spark-Shuffle2: 优化的HashShuflle，cosolidate机制，生成CC * RR个中间小文件，CC为core数量；
Spark-Shuffle3: SortShuffle阶段，生成MM*2个中间小文件#(数据文件 + 索引文件)。
什么是Shuffle？
Shuffle是MapReduce框架中的一个特定的phase，介于Map phase和Reduce phase之间，当Map的输出结果要被Reduce使用时，输出结果需要按key哈希，并且分发到每一个Reducer上去，这个过程就是shuffle。由于shuffle涉及到了磁盘的读写和网络的传输，因此shuffle性能的高低直接影响到了整个程序的运行效率。
下面这幅图清晰地描述了MapReduce算法的整个流程，其中shuffle phase是介于Map phase和Reduce phase之间。
概念上shuffle就是一个沟通数据连接的桥梁，那么实际上shuffle（partition）这一部分是如何实现的的呢，下面我们就以Spark为例讲一下shuffle在Spark中的实现。
Spark Shuffle进化史
先以图为例简单描述一下Spark中shuffle的整一个流程：
首先每一个Mapper会根据Reducer的数量创建出相应的bucket，bucket的数量是MM×RR，其中MM是Map的个数，RR是Reduce的个数。
其次Mapper产生的结果会根据设置的partition算法填充到每个bucket中去。这里的partition算法是可以自定义的，当然默认的算法是根据key哈希到不同的bucket中去。
当Reducer启动时，它会根据自己task的id和所依赖的Mapper的id从远端或是本地的block manager中取得相应的bucket作为Reducer的输入进行处理。
#补充说明：这里的bucket是一个抽象概念，在实现中每个bucket可以对应一个文件，可以对应文件的一部分或是其他等。
Apache Spark 的 Shuffle 过程与 Apache Hadoop中MR 的 Shuffle 过程有着诸多类似，一些概念可直接套用，例如，Shuffle 过程中，提供数据的一端，被称作 Map 端，Map 端每个生成数据的任务称为 Mapper，对应的接收数据的一端，被称作 Reduce 端，Reduce 端每个拉取数据的任务称为 Reducer，Shuffle 过程本质上都是将 Map 端获得的数据使用分区器进行划分，并将数据发送给对应的 Reducer 的过程。
#
