依据Spark1.4版
Spark中的shuffle大概是这么个过程：map端把map输出写成本地文件，reduce端去读取这些文件，然后执行reduce操作。
那么，问题来了：
reducer是怎么知道它的输入在哪呢？
首先，mapper在写完文件之后，肯定能提供与它的输出相关的信息。这个信息，在Spark中由MapStatus表示
private[spark] sealed trait MapStatus { def location: BlockManagerId def getSizeForBlock(reduceId: Int): Long }
在ShuffleMapTask执行完毕时，MapStatus会被作为执行结果传递给driver。ShuffleMapTasks的runTask方法的声明是这样的
override def runTask(context: TaskContext): MapStatus
reducer如果从driver端获取了跟自己相关的MapStatus, 它就知道哪些BlockManager存储了自己所需要的map输出。
但是，还存在以下问题：
1. driver拿到MapStatus是如何处理的？
2. reducer是如何获取到MapStatus的？
3. reducer是如何根据MapStatus获取map输出的？
driver拿到MapStatus是如何处理的？
首先，executor会把MapStatus作为任务执行的结果，通过statusUpdate方法传给driver
override def statusUpdate(taskId: Long, state: TaskState, data: ByteBuffer) { val msg = StatusUpdate(executorId, taskId, state, data) driver match { case Some(driverRef) => driverRef.send(msg) case None => logWarning(s"Drop $msg because has not yet connected to driver") } }
DriverEndpoint收到StatusUpdate后，会调用TaskScheduler的statusUpdate方法
case StatusUpdate(executorId, taskId, state, data) => scheduler.statusUpdate(taskId, state, data.value)
然后经过一个很长的调用链……会调用到DAGScheduler的handleTaskCompletion方法，这个方法会对task的类型进行匹配
case smt: ShuffleMapTask =>
匹配后执行了很多操作，与shuffle有关的有以下一些
val shuffleStage = stage.asInstanceOf[ShuffleMapStage] updateAccumulators(event) val status = event.result.asInstanceOf[MapStatus] val execId = status.location.executorId if (failedEpoch.contains(execId) && smt.epoch <= failedEpoch(execId)) { logInfo("Ignoring possibly bogus ShuffleMapTask completion from " + execId) } else { shuffleStage.addOutputLoc(smt.partitionId, status) }
重点在于，会把output location加到ShuffleMapStage的OutputLoc里，这个OutputLoc是ShuffleMapStage持有的一个MapStatus的数组。当这个Stage的所有任务都完成了，这个Stage里所有任务的MapStatus会被告知给MapOutputTracker
mapOutputTracker.registerMapOutputs( shuffleStage.shuffleDep.shuffleId, shuffleStage.outputLocs.map(list => if (list.isEmpty) null else list.head).toArray, changeEpoch = true)
MapOutputTracker和BlockManager一样，都是master-worker的结构，worker通过RPC请求master，来提供信息。
由此，MapStatus的信息被从executor传递给driver，最终注册给了MapOutputTracker。
reducer是如何获取到MapStatus的？
首先，引发shuffle的transformation会生成特殊的RDD，ShuffledRDD和CoGroupedRDD，这些RDD的compute方法被调用时，会触发reduce的过程。
下面还是以ShuffledRDD为例。
override def compute(split: Partition, context: TaskContext): Iterator[(K, C)] = { val dep = dependencies.head.asInstanceOf[ShuffleDependency[K, V, C]] SparkEnv.get.shuffleManager.getReader(dep.shuffleHandle, split.index, split.index + 1, context) .read() .asInstanceOf[Iterator[(K, C)]] }
目前，shuffleManager的getReader方法，只会返回HashShuffleReader类型的reader，它是ShuffleReader的唯一子类。
它的read方法，会调用BlockStoreShuffleFetcher的fetch方法去获取map的输出
val iter = BlockStoreShuffleFetcher.fetch(handle.shuffleId, startPartition, context, ser)
这个fetch方法会请求MapOutputTracker来获取map输出的位置和大小，MapOutputTracker的getServerStatus方法会获取这个reducer对应的MapStatus。
//statuses: Array[(BlockManagerId, Long)] 获取这个shuffleId， reduceId对应的map输出的位置和大小 val statuses = SparkEnv.get.mapOutputTracker.getServerStatuses(shuffleId, reduceId)
reducer是如何根据MapStatus获取map输出的呢
statuses的类型是Array[(BlockManagerId, Long)]，这也就是MapStatus能提供的两个信息。
fetch方法会用获取到的MapStatus里的信息组装ShuffleBlockId
val splitsByAddress = new HashMap[BlockManagerId, ArrayBuffer[(Int, Long)]] for (((address, size), index) <- statuses.zipWithIndex) { splitsByAddress.getOrElseUpdate(address, ArrayBuffer()) += ((index, size)) } val blocksByAddress: Seq[(BlockManagerId, Seq[(BlockId, Long)])] = splitsByAddress.toSeq.map { case (address, splits) => (address, splits.map(s => (ShuffleBlockId(shuffleId, s._1, reduceId), s._2))) }
注意，statuses这个数组里的信息包括了每个map的输出，即使有map没有对应于此reduce的输出，也会有。这个数组i索引处的信息，即是mapId为i的map的输出信息。因此， splitsByAddress在生成时，使用了statues.zipWithIndex来获取mapId。而组装blocksByAddress的过程就由此生成ShuffleBlockId
case class ShuffleBlockId(shuffleId: Int, mapId: Int, reduceId: Int) extends BlockId { override def name: String = "shuffle_" + shuffleId + "_" + mapId + "_" + reduceId }
这个blocksByAddress会被用来构造ShuffleBlockFetcherIterator，它会去请求BlockManager获取对应的ShuffleBlock。下面是fetch方法中构造ShuffleBlockFetcherIterator的代码
val blockFetcherItr = new ShuffleBlockFetcherIterator( context, SparkEnv.get.blockManager.shuffleClient, blockManager, blocksByAddress, serializer, // Note: we use getSizeAsMb when no suffix is provided for backwards compatibility SparkEnv.get.conf.getSizeAsMb("spark.reducer.maxSizeInFlight", "48m") * 1024 * 1024)
ShuffleBlockFetcherIterator是一个迭代器，它的主构造器会调用initialize方法进行初始化。这个initialize的主要功能是生成对ShuffleBlock的fetch请求，并发送这些请求。
因此在ShuffleBlockFetcherIterator对象建立后，它就发送了很多FetchRequest. 又因为请求的发送和获得结果是异步的，而它需要把这些异步获取的结果封装于一个迭代器中，其实现还是有些复杂的。
private[this] def initialize(): Unit = { // Add a task completion callback (called in both success case and failure case) to cleanup. context.addTaskCompletionListener(_ => cleanup()) // 区分开本地的和远端的block val remoteRequests = splitLocalRemoteBlocks() // 把远端的block随机排列，加到队列里 fetchRequests ++= Utils.randomize(remoteRequests) // 发送对远端的block的请求 while (fetchRequests.nonEmpty && (bytesInFlight == 0 || bytesInFlight + fetchRequests.front.size <= maxBytesInFlight)) { sendRequest(fetchRequests.dequeue()) } val numFetches = remoteRequests.size - fetchRequests.size logInfo("Started " + numFetches + " remote fetches in" + Utils.getUsedTimeMs(startTime)) // 获取本地的block fetchLocalBlocks() logDebug("Got local blocks in " + Utils.getUsedTimeMs(startTime)) }
它会区分远端的还是本地的block，本地的block就是当前这个executor的BlockManager所管理的block，它可以通过block所在BlockManagerId是否等于本地的BlockManagerId来判断。
fetchLocalBlocks的过程很简单，只要请求本地的BlockManager就行了
val buf = blockManager.getBlockData(blockId)
获取远端的block麻烦一点, 需要ShuffleClient提供帮助
shuffleClient.fetchBlocks(address.host, address.port, address.executorId, blockIds.toArray, new BlockFetchingListener { ... } )
这个shuffleClient是由BlockManager提供的, 它是BlockTransferService的父类，ShuffleClient有两种
private[spark] val shuffleClient = if (externalShuffleServiceEnabled) { val transConf = SparkTransportConf.fromSparkConf(conf, numUsableCores) new ExternalShuffleClient(transConf, securityManager, securityManager.isAuthenticationEnabled(), securityManager.isSaslEncryptionEnabled()) } else { blockTransferService }
默认情况下会使用BlockTransferService这种ShuffleClient。这个东西有两种
val blockTransferService = conf.get("spark.shuffle.blockTransferService", "netty").toLowerCase match { case "netty" => new NettyBlockTransferService(conf, securityManager, numUsableCores) case "nio" => new NioBlockTransferService(conf, securityManager) }
默认使用NettyBlockTransferService。这个东西会启动一个NettyBlockRpcServer，提供block的传输服务。ShuffleClient会通过host和port联系上它。
经过一串的调用，这个server会收到OpenBlocks类型的消息，然后它会这么处理
message match { case openBlocks: OpenBlocks => val blocks: Seq[ManagedBuffer] = openBlocks.blockIds.map(BlockId.apply).map(blockManager.getBlockData) val streamId = streamManager.registerStream(blocks.iterator) logTrace(s"Registered streamId $streamId with ${blocks.size} buffers") responseContext.onSuccess(new StreamHandle(streamId, blocks.size).toByteArray)
在这里，它会调用BlockDataManager的getBlockData方法获取block。BlockManager继承了BlockDataManager，它会把自己注册给BlockTransferService
这个注册，发生在BlockManager的intialize方法中
def initialize(appId: String): Unit = { blockTransferService.init(this) //把自己注册给BlockTransferService，让BlockTransferService能通过自己存取block
所以，最终会调用到BlockManager的getBlockData方法
override def getBlockData(blockId: BlockId): ManagedBuffer = { if (blockId.isShuffle) { shuffleManager.shuffleBlockResolver.getBlockData(blockId.asInstanceOf[ShuffleBlockId]) } else { val blockBytesOpt = doGetLocal(blockId, asBlockResult = false) .asInstanceOf[Option[ByteBuffer]] if (blockBytesOpt.isDefined) { val buffer = blockBytesOpt.get new NioManagedBuffer(buffer) } else { throw new BlockNotFoundException(blockId.toString) } } }
所以对于ShuffleBlockId，它会调用ShuffleBlockResover来获取block的数据。
这个ShuffleBlockResolver是个神奇的东西。它是作为ShuffleManager和BlockManager之间的翻译用的，对于不同的shuffle方式，使用不同的ShuffleBlockResolver。
Spark的shuffle有两种， sort和hash, 分别使用HashShuffleManager和SortShuffleManager，而它们分别使用FileShuffleBlockResolver和IndexShuffleBlockResolver。
hash的方式会把每个map为每个reduce的输出写一个文件，但是sort是每个map只写一个文件。这种不同的写文件的方式是使用不同的ShuffleWriter实现的，而不同的ShuffleWriter使用不同的ShuffleBlockResolver确定文件的结构和命名。
这种对应关系是:
HashShuffleManager -> HashShuffleWriter, 它们都使用FileShuffleBlockResolver。HashShuffleManager的getWriter方法和相关代码为：
private val fileShuffleBlockResolver = new FileShuffleBlockResolver(conf)
override def getWriter[K, V](handle: ShuffleHandle, mapId: Int, context: TaskContext) : ShuffleWriter[K, V] = { new HashShuffleWriter( shuffleBlockResolver, handle.asInstanceOf[BaseShuffleHandle[K, V, _]], mapId, context)
SortShuffleManager -> SortShuffleWriter, 它们都使用IndexShuffleBlockResolver。SortShuffleManager的getWriter方法和相关代码为：
private val indexShuffleBlockResolver = new IndexShuffleBlockResolver(conf) override def getWriter[K, V](handle: ShuffleHandle, mapId: Int, context: TaskContext) : ShuffleWriter[K, V] = { val baseShuffleHandle = handle.asInstanceOf[BaseShuffleHandle[K, V, _]] shuffleMapNumber.putIfAbsent(baseShuffleHandle.shuffleId, baseShuffleHandle.numMaps) new SortShuffleWriter( shuffleBlockResolver, baseShuffleHandle, mapId, context) }
这两个ShuffleBlockResolver的区别集中体现了hash和sort两种shuffle方式里reducer读取map输出文件时的差别。
和Sort两种shuffle方式读取map输出文件时的差别
HashShuffleManager使用的是FileShuffleBlockResolver，它的getBlockData方法依据是否启用了consolidate shuffle有不同的执行方式，consolidate shuffle默认是不启用的，此时执行的是
override def getBlockData(blockId: ShuffleBlockId): ManagedBuffer = { if (consolidateShuffleFiles) { ... } else { val file = blockManager.diskBlockManager.getFile(blockId) new FileSegmentManagedBuffer(transportConf, file, 0, file.length) } }
会直接根据blockId去DiskBlockManager获取相应的文件，然后生成一个FileSegmentManagedBuffer对象，这个buffer的offset从0开始，长度为file.length，也就是整个文件。
SortShuffleManager使用IndexShuffleBlockResolver。由于sort方式的shuffle里的每个map会写一个数据文件和一个索引文件，这个数据文件里会有对应于多个reducer的数据，因此需要先读索引文件来确定对于哪个reducer该从何处读起。
override def getBlockData(blockId: ShuffleBlockId): ManagedBuffer = { // The block is actually going to be a range of a single map output file for this map, so // find out the consolidated file, then the offset within that from our index val indexFile = getIndexFile(blockId.shuffleId, blockId.mapId) val in = new DataInputStream(new FileInputStream(indexFile)) try { ByteStreams.skipFully(in, blockId.reduceId * 8) val offset = in.readLong() val nextOffset = in.readLong() new FileSegmentManagedBuffer( transportConf, getDataFile(blockId.shuffleId, blockId.mapId), offset, nextOffset - offset) } finally { in.close() } }
这个索引文件记得是一系列的long型的值，第i个值代表第i个reducer的数据在数据文件中的偏移。因此，它返回的FileSegmentManagedBuffer不像hash方式时的一样包括整个文件，而是这个文件中的一个片段。
总结：
关于map输出的信息会封装在MapStatus对象中，它会由DAGScheduler相关的任务结果收回的系统带给driver，然后进行driver端的MapOutputTrackerMaster，进行MapOutputTracker系统。reducer可以通过MapOutputTracker系统获取map输出的位置和大小。然后它会使用BlockTransferService来获取自己需要的block。而根据BlockId获取map输出数据的功能由ShuffleManager使用不同的ShuffleBlockResolver完成，ShuffleBlockResolver会访问BlockManager，确切地说是DiskBlockManager最终获取文件或者文件的segment。
为了实现shuffle系统，Spark使用了两套master-slave结构的系统:调度系统和MapOutputTracker系统，也使用了一个专门用于Block传输的BlockTransferService系统，它由一系列的server组成，其中的调用关系还是有点复杂的。