[SPARK][CORE] 面试问题之UnsafeShuffleWriter流程解析（下）

欢迎关注微信公众号“Tim在路上”
Unsafe Shuffle的实现在一定程度上是Tungsten内存管理优化的的主要应用场景。其实现过程实际上和SortShuffleWriter是类似的，但是其中维护和执行的数据结构是不一样的。

UnsafeShuffleWriter 源码解析

@Override
public void write(scala.collection.Iterator<Product2<K, V>> records) throws IOException {
  // Keep track of success so we know if we encountered an exception
  // We do this rather than a standard try/catch/re-throw to handle
  // generic throwables.
  // [1] 使用success记录write是否成功，判断是write阶段的异常还是clean阶段
  boolean success = false;
  try {
    // [2] 遍历所有的数据插入ShuffleExternalSorter
    while (records.hasNext()) {
      insertRecordIntoSorter(records.next());
    }
    // [3] close排序器使所有数据写出到磁盘，并将多个溢写文件合并到一起
    closeAndWriteOutput();
    success = true;
  } finally {
    if (sorter != null) {
      try {
        // [4] 清除并释放资源
        sorter.cleanupResources();
      } catch (Exception e) {
        // Only throw this error if we won't be masking another
        // error.
        if (success) {
          throw e;
        } else {
logger.error("In addition to a failure during writing, we failed during " +
                       "cleanup.", e);
        }
      }
    }
  }
}

从上面的代码可以看出，UnsafeShuffleWriter的write过程如下：

[1] 使用success记录write是否成功，判断是write阶段的异常还是clean阶段
[2] 遍历所有的数据插入ShuffleExternalSorter
[3] close排序器使所有数据写出到磁盘，并将多个溢写文件合并到一起
[4] 清除并释放资源

// open()方法是在初始化UnsafeShuffleWriter调用的，其中会创建sorter， 并创建一个字节输出流，同时封装序列化流
private void open() throws SparkException {
  assert (sorter == null);
  sorter = new ShuffleExternalSorter(
    memoryManager,
    blockManager,
    taskContext,
    initialSortBufferSize,
    partitioner.numPartitions(),
    sparkConf,
    writeMetrics);
    // MyByteArrayOutputStream类是ByteArrayOutputStream的简单封装，只是将内部byte[]数组暴露出来】
    //【DEFAULT_INITIAL_SER_BUFFER_SIZE常量值是1024 * 1024，即缓冲区初始1MB大】
  serBuffer = new MyByteArrayOutputStream(DEFAULT_INITIAL_SER_BUFFER_SIZE);
  serOutputStream = serializer.serializeStream(serBuffer);
}

void insertRecordIntoSorter(Product2<K, V> record) throws IOException {
    assert(sorter != null);
    // [1] 获取record的key和partitionId
    final K key = record._1();
    final int partitionId = partitioner.getPartition(key);
    // [2] 将record序列化为二进制，并写的字节数组输出流serBuffer中
    serBuffer.reset();
    serOutputStream.writeKey(key, OBJECT_CLASS_TAG);
    serOutputStream.writeValue(record._2(), OBJECT_CLASS_TAG);
    serOutputStream.flush();

    final int serializedRecordSize = serBuffer.size();
    assert (serializedRecordSize > 0);
    // [3] 将其插入到ShuffleExternalSorter中
    sorter.insertRecord(
      serBuffer.getBuf(), Platform.BYTE_ARRAY_OFFSET, serializedRecordSize, partitionId);
  }

这一步是将record插入前的准备，现将序列化为二进制存储在内存中。

[1] 获取record的key和partitionId
[2] 将record序列化为二进制，并写的字节数组输出流serBuffer中
[3] 将序列化的二进制数组，分区id, length 作为参数插入到ShuffleExternalSorter中

那么数据在ShuffleExternalSorter中写入过程是怎么样呢？

public void insertRecord(Object recordBase, long recordOffset, int length, int partitionId)
  throws IOException {

  // [1] 判断inMemSorter中的记录是否到达了溢写阈值(默认是整数最大值)，如果满足就先进行spill
  // for tests
  assert(inMemSorter != null);
  if (inMemSorter.numRecords() >= numElementsForSpillThreshold) {
logger.info("Spilling data because number of spilledRecords crossed the threshold " +
      numElementsForSpillThreshold);
    spill();
  }
  // [2] 检查inMemSorter是否有额外的空间插入，如果可以获取就扩充空间，否则进行溢写
  growPointerArrayIfNecessary();
  final int uaoSize = UnsafeAlignedOffset.getUaoSize();
  // Need 4 or 8 bytes to store the record length.
  final int required = length + uaoSize;
  // [3] 判断当前内存空间currentPage是否有足够的内存，如果不够就申请，申请不下来就需要spill
  acquireNewPageIfNecessary(required);

  assert(currentPage != null);
  // [4] 获取currentPage的base Object和recordAddress
  final Object base = currentPage.getBaseObject();
  final long recordAddress = taskMemoryManager.encodePageNumberAndOffset(currentPage, pageCursor);
  // [5] 根据base, pageCursor, 先向当前内存空间写长度值，并移动指针
  UnsafeAlignedOffset.putSize(base, pageCursor, length);
  pageCursor += uaoSize;
  // [6] 再写序列化之后的数据， 并移动指指
  Platform.copyMemory(recordBase, recordOffset, base, pageCursor, length);
  pageCursor += length;
  // [7] 将recordAddress和partitionId插入inMemSorter进行排序
  inMemSorter.insertRecord(recordAddress, partitionId);
}

从上面分析，数据插入ShuffleExternalSorter总共需要7步：

[1] 判断inMemSorter中的记录是否到达了溢写阈值(默认是整数最大值)，如果满足就先进行spill
[2] 检查inMemSorter是否有额外的空间插入，如果可以获取就扩充空间，否则进行溢写
[3] 判断当前内存空间currentPage是否有足够的内存，如果不够就申请，申请不下来就需要spill
[4] 获取currentPage的base Object和recordAddress
[5] 先向当前内存空间写长度值，并移动指针
[6] 再写序列化之后的数据，并移动指指
[7] 将recordAddress和partitionId插入inMemSorter进行排序

从上面的介绍可以看出在整个插入过程中，主要涉及ShuffleExternalSorter 和 ShuffleInMemorySorter 两个数据结构。我们来简单看了ShuffleExternalSorter 类。

final class ShuffleExternalSorter extends MemoryConsumer implements ShuffleChecksumSupport {

  private final int numPartitions;
  private final TaskMemoryManager taskMemoryManager;
  private final BlockManager blockManager;
  private final TaskContext taskContext;
  private final ShuffleWriteMetricsReporter writeMetrics;
  private final LinkedList<MemoryBlock> allocatedPages = new LinkedList<>();

  private final LinkedList<SpillInfo> spills = new LinkedList<>();

  /** Peak memory used by this sorter so far, in bytes. **/
  private long peakMemoryUsedBytes;

  // These variables are reset after spilling:
  @Nullable private ShuffleInMemorySorter inMemSorter;
  @Nullable private MemoryBlock currentPage = null;
  private long pageCursor = -1;
  ...
}

可见每个ShuffleExternalSorter 中封装着ShuffleInMemorySorter类。同时封装allocatedPages

、spills和currentPage。也就是说ShuffleExternalSorter使用MemoryBlock存储数据，每条记录包括长度信息和K-V Pair。

另外在 ShuffleInMemorySorter 中，通过LongArray 来存储数据，并实现了SortComparator

排序方法。其中LongArray 存储的record的位置信息，主要有分区id, page id 和offset。

ShuffleExternalSorter	使用MemoryBlock存储数据，每条记录包括长度信息和K-V Pair
ShuffleInMemorySorter	使用long数组存储每条记录对应的位置信息(page number + offset)，以及其对应的PartitionId，共8 bytes

d.png

从上面的关于ShuffleExternalSorter 和ShuffleInMemorySorter 可以看出，这里其实质上是使用Tungsten实现了类似于BytesToBytesMap的数据结构，不过将其数组部分LongArray用ShuffleInMemorySorter 进行了封装，其余拆分为ShuffleExternalSorter 。

ShuffleExternalSorter 将数据写入了当前的内存空间，将数据的recordAddress和partitionId写入了ShuffleInMemorySorter ，那么其具体是如何实现排序和数据的溢写的？

private void writeSortedFile(boolean isLastFile) {

  // [1] 将inMemSorter的数据排序，并返回ShuffleSorterIterator
  // This call performs the actual sort.
  final ShuffleInMemorySorter.ShuffleSorterIterator sortedRecords =
    inMemSorter.getSortedIterator();

  // If there are no sorted records, so we don't need to create an empty spill file.
  if (!sortedRecords.hasNext()) {
    return;
  }

  final ShuffleWriteMetricsReporter writeMetricsToUse;

  ...

  // [2] 创建缓存数据writeBuffer数组，为了避免DiskBlockObjectWriter的低效的写
  // Small writes to DiskBlockObjectWriter will be fairly inefficient. Since there doesn't seem to
  // be an API to directly transfer bytes from managed memory to the disk writer, we buffer
  // data through a byte array. This array does not need to be large enough to hold a single
  // record;
  final byte[] writeBuffer = new byte[diskWriteBufferSize];

  // Because this output will be read during shuffle, its compression codec must be controlled by
  // spark.shuffle.compress instead of spark.shuffle.spill.compress, so we need to use
  // createTempShuffleBlock here; see SPARK-3426 for more details.
  final Tuple2<TempShuffleBlockId, File> spilledFileInfo =
    blockManager.diskBlockManager().createTempShuffleBlock();
  final File file = spilledFileInfo._2();
  final TempShuffleBlockId blockId = spilledFileInfo._1();
  final SpillInfo spillInfo = new SpillInfo(numPartitions, file, blockId);

  // Unfortunately, we need a serializer instance in order to construct a DiskBlockObjectWriter.
  // Our write path doesn't actually use this serializer (since we end up calling the `write()`
  // OutputStream methods), but DiskBlockObjectWriter still calls some methods on it. To work
  // around this, we pass a dummy no-op serializer.
  final SerializerInstance ser = DummySerializerInstance.INSTANCE;

  int currentPartition = -1;
  final FileSegment committedSegment;
  try (DiskBlockObjectWriter writer =
      blockManager.getDiskWriter(blockId, file, ser, fileBufferSizeBytes, writeMetricsToUse)) {

    final int uaoSize = UnsafeAlignedOffset.getUaoSize();
    // [3] 按分区遍历已经排好序的指针数据， 并未每个分区提交一个FileSegment,并记录分区的大小
    while (sortedRecords.hasNext()) {
      sortedRecords.loadNext();
      final int partition = sortedRecords.packedRecordPointer.getPartitionId();
      assert (partition >= currentPartition);
      if (partition != currentPartition) {
        // Switch to the new partition
        if (currentPartition != -1) {
          final FileSegment fileSegment = writer.commitAndGet();
          spillInfo.partitionLengths[currentPartition] = fileSegment.length();
        }
        currentPartition = partition;
        if (partitionChecksums.length > 0) {
          writer.setChecksum(partitionChecksums[currentPartition]);
        }
      }
      // [4] 取得数据的指针，再通过指针取得页号与偏移量
      final long recordPointer = sortedRecords.packedRecordPointer.getRecordPointer();
      final Object recordPage = taskMemoryManager.getPage(recordPointer);
      final long recordOffsetInPage = taskMemoryManager.getOffsetInPage(recordPointer);
      // [5] 取得数据前面存储的长度，然后让指针跳过它
      int dataRemaining = UnsafeAlignedOffset.getSize(recordPage, recordOffsetInPage);
      long recordReadPosition = recordOffsetInPage + uaoSize; // skip over record length
     // [6] 数据拷贝到上面创建的缓存中，通过缓存转到DiskBlockObjectWriter, 并写入数据，移动指针
      while (dataRemaining > 0) {
        final int toTransfer = Math.min(diskWriteBufferSize, dataRemaining);
        Platform.copyMemory(
          recordPage, recordReadPosition, writeBuffer, Platform.BYTE_ARRAY_OFFSET, toTransfer);
        writer.write(writeBuffer, 0, toTransfer);
        recordReadPosition += toTransfer;
        dataRemaining -= toTransfer;
      }
      writer.recordWritten();
    }

    committedSegment = writer.commitAndGet();
  }
  // If `writeSortedFile()` was called from `closeAndGetSpills()` and no records were inserted,
  // then the file might be empty. Note that it might be better to avoid calling
  // writeSortedFile() in that case.
  if (currentPartition != -1) {
    spillInfo.partitionLengths[currentPartition] = committedSegment.length();
    spills.add(spillInfo);
  }

  if (!isLastFile) {  // i.e. this is a spill file
    writeMetrics.incRecordsWritten(
      ((ShuffleWriteMetrics)writeMetricsToUse).recordsWritten());
    taskContext.taskMetrics().incDiskBytesSpilled(
      ((ShuffleWriteMetrics)writeMetricsToUse).bytesWritten());
  }
}

溢写排序文件总的来说分为两步：

首先是通过ShuffleInMemorySorter排序，获取对应分区的FileSegment和长度。写文件或溢写前根据数据的PartitionId信息，使用TimSort对ShuffleInMemorySorter的long数组排序，排序的结果为，PartitionId相同的聚集在一起，且PartitionId较小的排在前面，然后按分区写出FileSegment, 并记录每个分区的长度。

Unled.png

其次是基于排好序的指针执行数据的溢写操作。依次读取ShuffleInMemorySorter中long数组的元素，再根据page number和offset信息去ShuffleExternalSorter中读取K-V Pair写入文件, 溢写前先写入writeBuffer，然后在写入DiskBlockObjectWriter中。

itled.png

具体的步骤见下：

[1] 将inMemSorter的数据排序，并返回ShuffleSorterIterator
[2] 创建缓存数据writeBuffer数组，为了避免DiskBlockObjectWriter的低效的写
[3] 按分区遍历已经排好序的指针数据，并未每个分区提交一个FileSegment,并记录分区的大小
[4] 取得数据的指针，再通过指针取得页号与偏移量
[5] 取得数据前面存储的长度，然后让指针跳过它
[6] 数据拷贝到上面创建的缓存writeBuffer中，通过缓存转到DiskBlockObjectWriter, 并写入数据，移动指针

最后我们看下，UnsafeShuffleWriter是如何将最后溢写的文件进行合并的？

// UnsafeShuffleWriter
void closeAndWriteOutput() throws IOException {
  assert(sorter != null);
  updatePeakMemoryUsed();
  serBuffer = null;
  serOutputStream = null;
  // [1] 关闭排序器，并将排序器中的数据全部溢写到磁盘，返回SpillInfo数组
  final SpillInfo[] spills = sorter.closeAndGetSpills();
  try {
    // [2] 将多个溢出文件合并在一起，根据溢出次数和 IO 压缩编解码器选择最快的合并策略
    partitionLengths = mergeSpills(spills);
  } finally {
    sorter = null;
    for (SpillInfo spill : spills) {
      if (spill.file.exists() && !spill.file.delete()) {
logger.error("Error while deleting spill file {}", spill.file.getPath());
      }
    }
  }
  mapStatus = MapStatus$.MODULE$.apply(
    blockManager.shuffleServerId(), partitionLengths, mapId);
}

private long[] mergeSpills(SpillInfo[] spills) throws IOException {
    long[] partitionLengths;
    // [1] 如果根本没有溢写文件，写一个空文件
    if (spills.length == 0) {
      final ShuffleMapOutputWriter mapWriter = shuffleExecutorComponents
          .createMapOutputWriter(shuffleId, mapId, partitioner.numPartitions());
      return mapWriter.commitAllPartitions(
        ShuffleChecksumHelper.EMPTY_CHECKSUM_VALUE).getPartitionLengths();
    // [2] 如果只有一个溢写文件，就直接将它写入输出文件中
    } else if (spills.length == 1) {
      // [2.1] 创建单个file的map output writer
      Optional<SingleSpillShuffleMapOutputWriter> maybeSingleFileWriter =
          shuffleExecutorComponents.createSingleFileMapOutputWriter(shuffleId, mapId);
      if (maybeSingleFileWriter.isPresent()) {
        // Here, we don't need to perform any metrics updates because the bytes written to this
        // output file would have already been counted as shuffle bytes written.
        partitionLengths = spills[0].partitionLengths;
        logger.debug("Merge shuffle spills for mapId {} with length {}", mapId,
            partitionLengths.length);
        maybeSingleFileWriter.get()
          .transferMapSpillFile(spills[0].file, partitionLengths, sorter.getChecksums());
      } else {
        partitionLengths = mergeSpillsUsingStandardWriter(spills);
      }
    // [3] 如果有多个溢写文件,如果启用并支持快速合并，并且启用了transferTo机制，还没有加密,        就使用NIO zero-copy来合并到输出文件, 不启用transferTo或不支持快速合并，就使用压缩的BIO FileStream来合并到输出文件
    } else {
      partitionLengths = mergeSpillsUsingStandardWriter(spills);
    }
    return partitionLengths;
  }

多个spills的合并的具体的实现在mergeSpillsWithFileStream 方法中，为了减少篇幅的冗长这里就不再展开了。

溢写的文件进行合并，有如下几个步骤：

[1] 关闭排序器，并将排序器中的数据全部溢写到磁盘，返回SpillInfo数组

[2] 将多个溢出文件合并在一起，根据溢出次数和 IO 压缩编解码器选择最快的合并策略

 - [2.1] 如果根本没有溢写文件，写一个空文件

 - [2.2] 如果只有一个溢写文件，就直接将它写入输出文件中

 - [2.3] 如果有多个溢写文件,如果启用并支持快速合并，并且启用了transferTo机制，还没有加密,        就使用NIO zero-copy来合并到输出文件, 不启用transferTo或不支持快速合并，就使用压缩的BIO FileStream来合并到输出文件

至此，UnsafeShuffleWriter的实现就介绍完了。

下面我们谈下UnsafeShuffleWriter的优势：

ShuffleExternalSorter使用UnSafe API操作序列化数据，而不是Java对象，减少了内存占用及因此导致的GC耗时，这个优化需要Serializer支持relocation。 ShuffleExternalSorter存原始数据，ShuffleInMemorySorter使用压缩指针存储元数据，每条记录仅占8 bytes，并且排序时不需要处理原始数据，效率高。
溢写 & 合并这一步操作的是同一Partition的数据，因为使用UnSafe API直接操作序列化数据，合并时不需要反序列化数据。
溢写 & 合并可以使用fastMerge提升效率(调用NIO的transferTo方法)，设置spark.shuffle.unsafe.fastMergeEnabled为true，并且如果使用了压缩，需要压缩算法支持SerializedStreams的连接。
排序时并非将数据进行排序，而是将数据的地址指针进行排序

总结，UnsafeShuffleWriter是Tungsten最重要的应用，他的实现原理类似于SortShuffleWriter, 但是基于UnSafe API使用了定义的ShuffleExternalSorter和ShuffleInMemorySorter来存储和维护数据。

其整体流程为，所有的数据在插入前都需要序列化为二进制数组，然后再将其插入到数据结构ShuffleExternalSorter中。在ShuffleExternalSorter定义了ShuffleInMemorySorter主要用于存储数据的partitionId和recordAddress，另外定义了MemoryBlock页空间数组。

在ShuffleExternalSorter的insertRecord时会先，判断ShuffleInMemorySorter和当前内存空间是否足够新数据的插入，不够需要申请，申请失败则需要spill。

插入数据时会先写入占用内存空间的长度，再写入数据值，最后将recordAddress和partitionId插入ShuffleInMemorySorter中。在进行spill时会将ShuffleInMemorySorter中的数据进行排序，并按照分区生成FileSegment并统计分区的大小，然后遍历指针数组根据地址将对应的数据进行写出。在进行合并时可以直接使用UnSafe API直接操作序列化数据，返回汇总的文件。

通过UnsafeShuffleWriter只会产生两个文件，一个分区的数据文件，一个索引文件。整个UnsafeShuffleWriter过程只会产生2 * M 个中间文件。

今天就先到这里，通过上面的介绍，我们也留下些面试题：

为什么UnsafeShuffleWriter无法支持无法支持map端的aggregation？
为什么UnsafeShuffleWriter分区数的最大值为 (1 << 24) ？
ShuffleExternalSorter实现是基于JVM的吗？以及其在排序上有什么优化？

欢迎关注微信公众号“Tim在路上”