Spark详解（十）：SparkShuffle机制原理分析

傷城~ 2022-03-17 12:22 222阅读 0赞

# 1. Spark Shuffle简介 #

在Hadoop的MapReduce框架中Shuffle是连接Map和Reduce的桥梁，Map的输出要用到Reduce中必须经过Shuffle这个环节。由于Shuffle阶段涉及到磁盘的读写和网络传输，因此Shuffle的性能高低直接影响到整个程序的性能和吞吐量。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70]

Spakr Shuffle定义：Shuffle在中文的意思是“洗牌、混洗”的意思，在MapReduce过程中需要各个节点上的同一个类型数据汇集到某一节点中进行计算，把这些分布在不同节点的数据按照一定的规则汇集到一起的过程称为Shuffle。

但是在Spark Shuffle中存在如下问题：

>  *  数据量非常大，达到TB甚至PB级别。这些数据分散到数百台甚至数千台的集群中运行，如果管理为后续的任务创建数据众多的文件，以及处理大小超过内存的数据量呢？
>  *  如果对结果进行序列化和反序列化，以及传输之前如何进行压缩呢？

# 2. Shuffle的写操作 #

Spark在Shuffle的处理方式是一个迭代的过程，从最开始避免Hadoop多余的排序（即在Reduce之前获取的数据经过排序），提供了基于哈希的Shuffle写操作，但是这种方式在Map和Reduce的数量较大的情况下写文件的数量大和缓存开销过大的问题。为了解决这个问题，在Spark1.2版本中默认的Shuffle写替换为基于排序的Shuffle写，该操作会把所有的结果写入到一个文件中，同时生成一个索引文件进行定位。

## 2.1 基于哈希的Shuffle写过程 ##

在Spark1.0之间实现的是基于哈希的Shuffle写过程。在该机制中每个Mapper会根据Reduce的数量创建相应的Bucket，bucket的数据是M\*R，其中M是Map的个数，R是Reduce的个数；Mapper生成的结果会根据设置地Partition算法填充到每个bucket中，这里的bucket是一个抽象的概念，在该机制中每一个bucket是一个文件；当Reduce启动时，会根据任务的编号和锁依赖的Mapper的编号从远程或者本地取得相应的bucket作为Reduce的输入进行处理，其处理流程如图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 1]

相比较于传统的MapReduce，Spark假定大多数情况下Shuffle的数据排序是没有必要的，比如WordCount，强制进行排序只能使得性能变差，因此Spark并不在Reduce端进行Merge Sort，而是使用聚合（Aggerator）。聚合实际上是一个HashMap，它以当前任务输出结果作为Key的键值，以任意要combine类型为值，当在Word Count的Reduce进行单词统计的时候，它会将Shuffle读到的每一个键值对更新或者插入到HashMap中。这样就不需要预先对所有的键值对进行mergeSort，而是来一个处理一个，省下了外部排序这个过程。

在HashShuffleWriter的writer方法中，通过ShuffleDependency是否定义了Aggregatror判断是否需要在Map端对数据进行聚合操作，如果需要对数据进行聚合处理。然后调用ShuffleWriterGroup的writers方法得到一个DiskBlockObjectWriter对象，调用该对象的writer方法写入。

## 2.2 基于排序的Shuffle写操作 ##

基于Hash的Shuffle写操作能够较好的完成Shuffle的数据写入，但是存在两大问题：

>  *  每个Shuffle Map Task作为后续的任务创建一个单独的文件，因此在运行过程中文件的数量是M\*R。这对于文件系统来说是一个很大的负担，同时shuffle数据量不大而文件非常多的情况，随机写入会严重降低I/O的性能。
>  *  虽然Shuffle写数据不需要存储在内存再写到磁盘，但是DiskBlockObjectWriter所带来的开销也是一个不容小视的内存开销。

为了缓解Shuffle过程中产生过多的文件和Writer Handler的缓存开销过大的问题，在SPark 1.1 版本中解决了Hadoop在Shuffle中的处理方式，引入了基于排序的Shuffle写操作机制。在该机制中，每个Shuffle Map Task不会为后续的每个任务创建单独的文件，而是会将所有的结果写入到同一个文件中，对应生成一个Index文件进行索引。通过这种机制避免了大量文件的产生，一方面可以降低文件系统管理众多文件的开销，另一方面可以减少Writer Handler缓存所占用的内存大小，节省了内存同时避免了GC的风险和频率。

前面我知道基于哈希的Shuffle写操作输出结果是放在HashMap中，没有经过排序，但是对于一些如groupbyKey操作，如果使用HashMap，则需要将所有的键值对放入HashMap中并且将值合并成一个数组。可以想象未来能够放下所欲数据，必须确保每一个Partition足够小，并且内存能够放下，这对于内存来说是一个很大的挑战。为了减少内存的使用，可以将Aggregator的操作从内存转移到磁盘中，在结束的时候再将这些不同的文件进行归并排序，从而减少内存的使用量。

对于Shuffle的写操作，主要是在SortShuffleWriter的write方法。在该方法中，首先判断输出结果在Map端是否需要合并(Combine), 如果需要合并，则外部排序中进行聚合并排序；如果不需要，则外部排序中不进行聚合和排序，例如sortByKey操作在Reduce端会进行聚合并排序。确认外部排序方式后，在外部排序中将使用PartitionedAppendOnlyMap来存放数据，当排序中的Map占用的内存已经超越了使用的阈值，则将Map中的内容溢写到磁盘中，每一次溢写产生一个不同的文件，当所有数据处理完毕后，在外部排序中有可能一部分计算结果在内存中，另一部分计算结果溢写到一或多个文件中，这时通过merge操作将内存和spill文件中的内容合并整到一个文件中。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 2]

SortShuffleWriter的write方法代码如下：

/** Write a bunch of records to this task's output */
      override def write(records: Iterator[Product2[K, V]]): Unit = { 
        // 获取Shuffle Map Task 的输出结果的排序方式
        sorter = if (dep.mapSideCombine) { 
          // 当输出结果需要Combine，那么外部排序算法进行聚合
          require(dep.aggregator.isDefined, "Map-side combine without Aggregator specified!")
          new ExternalSorter[K, V, C](
            context, dep.aggregator, Some(dep.partitioner), dep.keyOrdering, dep.serializer)
        } else { 
          // In this case we pass neither an aggregator nor an ordering to the sorter, because we don't
          // care whether the keys get sorted in each partition; that will be done on the reduce side
          // if the operation being run is sortByKey.
          // 在这种情况下，我们既没有将聚合器也没有传递给排序器，因为我们不关心Key是否在每个分区中排序;
          // 如果正在运行的操作是sortByKey，那么将排序阶段将在reduce端完成。
    
          // 其他情况下，当输出结果不需要进行Combine操作，那么Shuffle Write将不进行聚合排序操作
          new ExternalSorter[K, V, V](
            context, aggregator = None, Some(dep.partitioner), ordering = None, dep.serializer)
        }
    
        // 根据获取的排序方式，对数据进行排序并且写入到内存缓冲区中。如果排序中的Map占用的内存
        // 已经超越了阈值，则将Map中的内容溢写到磁盘中，每一次溢写都将产生一个不同的文件
        sorter.insertAll(records)
    
        // Don't bother including the time to open the merged output file in the shuffle write time,
        // because it just opens a single file, so is typically too fast to measure accurately
        // (see SPARK-3570).
        // 通过Shuffle编号和Map编号获取该数据文件
        val output = shuffleBlockResolver.getDataFile(dep.shuffleId, mapId)
        val tmp = Utils.tempFileWith(output)
    
        try { 
          // 通过Shuffle编号和Block编号获取ShuffleBlock编号
          val blockId = ShuffleBlockId(dep.shuffleId, mapId, IndexShuffleBlockResolver.NOOP_REDUCE_ID)
    
          // 外部排序中有可能一部分计算结果放在内存中，另一部分计算结果溢写产生一个或者多个文件之中，
          // 这个时候通过Merge Sort操作将内存和splil文件的内容整合到一个文件中
          val partitionLengths = sorter.writePartitionedFile(blockId, tmp)
    
          // 创建索引文件，将每个partitoon在数据文件中的起始位置和结束位置写入到索引文件中
          shuffleBlockResolver.writeIndexFileAndCommit(dep.shuffleId, mapId, partitionLengths, tmp)
    
          // 将元数据信息写入到MapStatus中，后续的任务可以通过该MapStatus得到处理结果信息
          mapStatus = MapStatus(blockManager.shuffleServerId, partitionLengths)
        } finally { 
          if (tmp.exists() && !tmp.delete()) { 
            logError(s"Error while deleting temp file ${tmp.getAbsolutePath}")
          }
        }
      }

在ExternalSorter的insterAll方法中，先判断是否需要进行聚合(Aggregation),如果需要，则根据键值进行合并(Combine), 然后把这些数据写入到内存缓冲区中，如果排序中Map占用的内存超过了阈值，则将Map中的内容溢写到磁盘中，每一次溢写产生一个不同的文件。如果不需要聚合，把数据排序写到内存缓冲区。

def insertAll(records: Iterator[Product2[K, V]]): Unit = { 
        // TODO: stop combining if we find that the reduction factor isn't high
        // 根据外部排序中是否需要进行聚合操作（Aggregator）
        val shouldCombine = aggregator.isDefined
    
        if (shouldCombine) { 
          // Combine values in-memory first using our AppendOnlyMap
          // 如果需要聚合，则使用PartitionedAppendOnlyMap根据键值进行合并
          val mergeValue = aggregator.get.mergeValue
          val createCombiner = aggregator.get.createCombiner
          var kv: Product2[K, V] = null
          val update = (hadValue: Boolean, oldValue: C) => { 
            if (hadValue) mergeValue(oldValue, kv._2) else createCombiner(kv._2)
          }
          // 对数据进行排序写入到内存缓冲区中，如果排序中的Map占用的内存以及超越了使用的阈值，
          // 则对Map中的内容溢写到磁盘中，每一次溢写产生一个不同的文件
          while (records.hasNext) { 
            addElementsRead()
            kv = records.next()
            map.changeValue((getPartition(kv._1), kv._1), update)
            maybeSpillCollection(usingMap = true)
          }
        } else { 
          // Stick values into our buffer
          // 外部排序中，不需要聚合操作
          // 对数据进行排序写入到内存缓冲区中
          while (records.hasNext) { 
            addElementsRead()
            val kv = records.next()
            buffer.insert(getPartition(kv._1), kv._1, kv._2.asInstanceOf[C])
            maybeSpillCollection(usingMap = false)
          }
        }
      }

# 3. Shuffle 读操作 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 3]

（1）在SparkEnv启动时，会对ShuffleManage、BlockManager和MapOutputTracker等实例化。ShuffleManager配置项有SortShuffleManager和自定义的ShuffleManager两种，  
SortShuffleManager实例化BlockStoreShuffleReader,持有的实例是IndexShuffleBlockResolver实例。

（2）在BlockStoreShuffleReader的read方法中，调用mapOutputTracker的getMapSizesByExecutorId方法，由Executor的MapOutputTrackerWorker发送获取结果状态的  
GetMapOutputStatuses消息给Driver端的MapOutputTrackerMaster，请求获取上游Shuffle输出结果对应的MapStatus，其中存放了结果数据信息，也就是我们之前在Spark作业执行中介绍的ShuffleMapTask执行结果元信息。

（3）知道Shuffle结果的位置信息后，对这些位置进行筛选，判断是从本地还是远程获取这些数据。如果是本地直接调用BlockManager的getBlockData方法，在读取数据的时候会根据写入方式的不同采取不同的ShuffleBlockResolver读取；如果是在远程节点上，需要通过Netty网络方式读取数据。  
在远程读取的时候会采用多线程的方式进行读取，一般来说，会启动5个线程到5个节点进行读取数据，每次请求的数据大小不回超过系统设置的1/5，该大小由spark.reducer.maxSizeInFlight配置项进行设置，默认情况该配置为48MB。

（6）读取数据后，判断ShuffleDependency是否定义聚合(Aggregation), 如果需要，则根据键值进行聚合。在上游ShuffleMapTask已经做了合并，则在合并数据的基础上做键值聚合。待数据处理完毕后，使用外部排序(ExternalSorter)对数据进行排序并放入存储中。

Shuffle Read 类调用关系图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 4]

**创建ShuffleBlockFetcherIterator，一个迭代器，它获取多个块，对于本地块，从本地读取对于远程块，通过远程方法读取**

**如果reduce端需要聚合：如果map端已经聚合过了，则对读取到的聚合结果进行聚合； 如果map端没有聚合，则针对未合并的<k,v>进行聚合**

**如果需要对key排序，则进行排序。基于sort的shuffle实现过程中，默认只是按照partitionId排序。在每一个partition内部并没有排序，因此添加了keyOrdering变量，提供是否需要对分区内部的key排序**

源码：

Shuffle读的起点是由ShuffledRDD.computer发起的，在该方法中会调用ShuffleManager的getReader方法，在前面我们已经知道Sort Based Shuffle使用的是BlockStoreShuffleReader的read方式。

// ResultTask或者ShuffleMapTask，在执行到ShuffledRDD时
      // 会调用compute方法来计算partition的数据
      override def compute(split: Partition, context: TaskContext): Iterator[(K, C)] = { 
        val dep = dependencies.head.asInstanceOf[ShuffleDependency[K, V, C]]
        // 获取Reader(BlockStoreShuffleReader)，拉取shuffleMapTask/ResultTask，需要聚合的数据
        SparkEnv.get.shuffleManager.getReader(dep.shuffleHandle, split.index, split.index + 1, context)
          .read()
          .asInstanceOf[Iterator[(K, C)]]
      }

（2）在BlockStoreShuffleReader的read方法里先实例化ShuffleBlockFetcherIterator，在该实例化过程中，通过MapOutputTracker的getMapSizeByExecutorId获取上游ShuffleMapTask输出的元数据。先尝试在本地的mapStatus获取，如果获取不到，则通过RPC通行框架，发送消息给MapOutputTrackerMaster，  
请求获取该ShuffleMapTask输出数据的元数据，获取这些元数据转换成Seq\[(BlockManagerId, Seq\[(BlockId, Long)\])\]的序列。在这个序列中的元素包括两部分信息，BlockManagerId可以定位数据所处的Executor，而Seq\[(BlockId,Long)\]可以定位Executor的数据块编号和获取数据的大小。

/** Read the combined key-values for this reduce task */
      override def read(): Iterator[Product2[K, C]] = { 
        // ShuffleBlockFetcherIterator根据得到的地理位置信息，通过BlockManager去远程的
        // ShuffleMapTask所在节点的blockManager去拉取数据
        val blockFetcherItr = new ShuffleBlockFetcherIterator(
          context,
          blockManager.shuffleClient,
          blockManager,
          // 通过MapOutputTracker获取上游的ShuffleMapTask输出数据的元数据，
          // 先尝试从本地获取，获取不到，通过RPC发送消息给MapOutputTrackerMaster,获取元数据
          mapOutputTracker.getMapSizesByExecutorId(handle.shuffleId, startPartition, endPartition),
          // Note: we use getSizeAsMb when no suffix is provided for backwards compatibility
          
          // 远程获取数据时，设置每次传输数据的大小
          SparkEnv.get.conf.getSizeAsMb("spark.reducer.maxSizeInFlight", "48m") * 1024 * 1024,
          SparkEnv.get.conf.getInt("spark.reducer.maxReqsInFlight", Int.MaxValue))
    
        // Wrap the streams for compression based on configuration
        val wrappedStreams = blockFetcherItr.map {  case (blockId, inputStream) =>
          serializerManager.wrapForCompression(blockId, inputStream)
        }

在MapOutputTracker的getMapSizesByExecutorId方法代码如下：

def getMapSizesByExecutorId(shuffleId: Int, startPartition: Int, endPartition: Int)
          : Seq[(BlockManagerId, Seq[(BlockId, Long)])] = { 
        logDebug(s"Fetching outputs for shuffle $shuffleId, partitions $startPartition-$endPartition")
        // 通过shuffleId获取上游ShuffleMapTask输出数据的元数据
        val statuses = getStatuses(shuffleId)
        // Synchronize on the returned array because, on the driver, it gets mutated in place
        // 使用同步的方式把获取到的MapStatuses转为Seq[(BlockManagerId, Seq[(BlockId, Long)])]格式
        statuses.synchronized { 
          return MapOutputTracker.convertMapStatuses(shuffleId, startPartition, endPartition, statuses)
        }
      }

获取上游的ShuffleMapTask输出数据的元数据是在getStatuses方法中，在该方法中通过同步的方式尝试在本地mapStatus中读取，如果成功获取，则返回这些信息；如果失败，则通过RPC通信框架发送请求到MapOutputTrackerMaster进行获取。

private def getStatuses(shuffleId: Int): Array[MapStatus] = { 
        // 根据ShuffleMapTask的编号尝试从本地获取输出结果的元数据MpaStatus，
        // 如果不能获取这些信息，则向MapOutPutTracekrMaster请求获取
        val statuses = mapStatuses.get(shuffleId).orNull
        if (statuses == null) { 
          logInfo("Don't have map outputs for shuffle " + shuffleId + ", fetching them")
          val startTime = System.currentTimeMillis
          var fetchedStatuses: Array[MapStatus] = null
          fetching.synchronized { 
            // Someone else is fetching it; wait for them to be done
            // 其他人在读取该信息，等待其他人读取完毕后再进行读取
            while (fetching.contains(shuffleId)) { 
              try { 
                fetching.wait()
              } catch { 
                case e: InterruptedException =>
              }
            }
    
            // Either while we waited the fetch happened successfully, or
            // someone fetched it in between the get and the fetching.synchronized.
            // 使用同步操作读取指定Shuffle编号的数据，该操作要么成功读取，要么其他人同时在读取，此时把读取Shuffle编号
            // 加入到fetching读取列表中，以便后续中读取。
            fetchedStatuses = mapStatuses.get(shuffleId).orNull
            if (fetchedStatuses == null) { 
              // We have to do the fetch, get others to wait for us.
              fetching += shuffleId
            }
          }
    
          if (fetchedStatuses == null) { 
            // We won the race to fetch the statuses; do so
            logInfo("Doing the fetch; tracker endpoint = " + trackerEndpoint)
            // This try-finally prevents hangs due to timeouts:
            try { 
              // 发送消息给MapOutputTrackerMaster，获取该ShuffleMapTask输出的元数据
              val fetchedBytes = askTracker[Array[Byte]](GetMapOutputStatuses(shuffleId))
    
              // 对获取的元数据进行反序列化
              fetchedStatuses = MapOutputTracker.deserializeMapStatuses(fetchedBytes)
              logInfo("Got the output locations")
              mapStatuses.put(shuffleId, fetchedStatuses)
            } finally { 
              fetching.synchronized { 
                fetching -= shuffleId
                fetching.notifyAll()
              }
            }
          }

（3）获取读取数据位置信息后，返回到ShuffleBlockFetcherIterator的initalize方法，该方法是Shuffle读的核心代码所在。在该方法中通过调用splitLocalRemoteBlocks方法对获取的数据位置信息进行区分，判断数据所处的位置是本地节点还是远程节点。如果是远程节点使用fetchUpToMaxBytes方法，从远程节点汇总获取数据；如果是本地节点使用fetchLocalBlock方法获取数据。

private[this] def initialize(): Unit = { 
        // Add a task completion callback (called in both success case and failure case) to cleanup.
        context.addTaskCompletionListener(_ => cleanup())
    
        // Split local and remote blocks. 切分本地和远程block
        // 对获取数据位置的元数据进行分区，区分为本地节点还是远程节点
        val remoteRequests = splitLocalRemoteBlocks()
        // Add the remote requests into our queue in a random order
        fetchRequests ++= Utils.randomize(remoteRequests)
        assert ((0 == reqsInFlight) == (0 == bytesInFlight),
          "expected reqsInFlight = 0 but found reqsInFlight = " + reqsInFlight +
          ", expected bytesInFlight = 0 but found bytesInFlight = " + bytesInFlight)
    
        // Send out initial requests for blocks, up to our maxBytesInFlight
        // 对于远程节点数据，使用Netty网络方式读取
        fetchUpToMaxBytes()
    
        val numFetches = remoteRequests.size - fetchRequests.size
        logInfo("Started " + numFetches + " remote fetches in" + Utils.getUsedTimeMs(startTime))
    
        // Get Local Blocks
        // 对于本地数据，sort Based Shuffle使用的是IndexShuffleBlockResolver的getBlockData方法获取数据
        fetchLocalBlocks()
        logDebug("Got local blocks in " + Utils.getUsedTimeMs(startTime))
      }

划分本地节点还是远程节点的splitLocalRemoteBlocks方法中划分数据读取方式：

private[this] def splitLocalRemoteBlocks(): ArrayBuffer[FetchRequest] = { 
        // Make remote requests at most maxBytesInFlight / 5 in length; the reason to keep them
        // smaller than maxBytesInFlight is to allow multiple, parallel fetches from up to 5
        // nodes, rather than blocking on reading output from one node.
    
        // 设置每次请求的大小不超过maxBytesInFlight的1/5，该阈值由spark.reducer.maxSizeInFlight配置，默认48MB
        val targetRequestSize = math.max(maxBytesInFlight / 5, 1L)
        logDebug("maxBytesInFlight: " + maxBytesInFlight + ", targetRequestSize: " + targetRequestSize)
    
        // Split local and remote blocks. Remote blocks are further split into FetchRequests of size
        // at most maxBytesInFlight in order to limit the amount of data in flight.
        val remoteRequests = new ArrayBuffer[FetchRequest]
    
        // Tracks total number of blocks (including zero sized blocks)
        var totalBlocks = 0
        for ((address, blockInfos) <- blocksByAddress) { 
          totalBlocks += blockInfos.size
          if (address.executorId == blockManager.blockManagerId.executorId) { 
            // Filter out zero-sized blocks
            // 当数据和所在BlockManager在一个节点时，把该信息加入到localBlocks列表中，
            // 需要过滤大小为0的数据块
            localBlocks ++= blockInfos.filter(_._2 != 0).map(_._1)
            numBlocksToFetch += localBlocks.size
          } else { 
            val iterator = blockInfos.iterator
            var curRequestSize = 0L
            var curBlocks = new ArrayBuffer[(BlockId, Long)]
            while (iterator.hasNext) { 
              val (blockId, size) = iterator.next()
              // Skip empty blocks
              if (size > 0) { 
                // 对于不空数据块，把其信息加入到列表中
                curBlocks += ((blockId, size))
                remoteBlocks += blockId
                numBlocksToFetch += 1
                curRequestSize += size
              } else if (size < 0) { 
                throw new BlockException(blockId, "Negative block size " + size)
              }
              // 按照不大于maxBytesInFlight的标准，把这些需要处理数据组合在一起
              if (curRequestSize >= targetRequestSize) { 
                // Add this FetchRequest
                remoteRequests += new FetchRequest(address, curBlocks)
                curBlocks = new ArrayBuffer[(BlockId, Long)]
                logDebug(s"Creating fetch request of $curRequestSize at $address")
                curRequestSize = 0
              }
            }
            // Add in the final request
            // 剩余的处理数据组成一次请求
            if (curBlocks.nonEmpty) { 
              remoteRequests += new FetchRequest(address, curBlocks)
            }
          }
        }
        logInfo(s"Getting $numBlocksToFetch non-empty blocks out of $totalBlocks blocks")
        remoteRequests
      }

（4）数据读取完毕后，回到BlockStoreShuffleReader的read方法，判断是否定义聚合，如果需要，则根据键值调用Aggregator的combineCombinersByKey  
方法进行聚合。聚合完毕，使用外部排序(ExternalSorter的insrtAll)对数据进行排序并放入内存中

val aggregatedIter: Iterator[Product2[K, C]] = if (dep.aggregator.isDefined) { 
          if (dep.mapSideCombine) { 
            // We are reading values that are already combined
            // 对于上游ShuffleMapTask已经合并的，对合并结果数据进行聚合
            val combinedKeyValuesIterator = interruptibleIter.asInstanceOf[Iterator[(K, C)]]
            dep.aggregator.get.combineCombinersByKey(combinedKeyValuesIterator, context)
          } else { 
            // We don't know the value type, but also don't care -- the dependency *should*
            // have made sure its compatible w/ this aggregator, which will convert the value
            // type to the combined type C
            // 对未合并的数据进行聚合处理，注意对比类型一个是C一个是Nothing
            val keyValuesIterator = interruptibleIter.asInstanceOf[Iterator[(K, Nothing)]]
            dep.aggregator.get.combineValuesByKey(keyValuesIterator, context)
          }
        } else { 
          require(!dep.mapSideCombine, "Map-side combine without Aggregator specified!")
          interruptibleIter.asInstanceOf[Iterator[Product2[K, C]]]
        }
    
        // Sort the output if there is a sort ordering defined.
        dep.keyOrdering match { 
          // 对于需要排序，使用ExternalSorter进行排序，根据获取的排序方式，对数据进行排序并写入到内存缓冲区中。
          // 如果排序中的Map占用的内存已经超越了使用的阈值，则将Map中的内容溢写到磁盘
          case Some(keyOrd: Ordering[K]) =>
            // Create an ExternalSorter to sort the data. Note that if spark.shuffle.spill is disabled,
            // the ExternalSorter won't spill to disk.
            val sorter =
              new ExternalSorter[K, C, C](context, ordering = Some(keyOrd), serializer = dep.serializer)
            sorter.insertAll(aggregatedIter)
            context.taskMetrics().incMemoryBytesSpilled(sorter.memoryBytesSpilled)
            context.taskMetrics().incDiskBytesSpilled(sorter.diskBytesSpilled)
            context.taskMetrics().incPeakExecutionMemory(sorter.peakMemoryUsedBytes)
            CompletionIterator[Product2[K, C], Iterator[Product2[K, C]]](sorter.iterator, sorter.stop())
          case None =>
            aggregatedIter
        }
      }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70]: /images/20220317/6cb48f3317644234828f12f9c3ebee02.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 1]: /images/20220317/af669f3e80634bb6834c7da8b7a6e86a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 2]: /images/20220317/117bf1fa042749c7892029b783a66c66.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 3]: /images/20220317/e1e81720cb144c5b9f2b93c8e33adbbd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 4]: /images/20220317/be547a74666749c6ad395d9aa017f136.png