SortShuffle之SortShuffleWriter

SortShuffleWriter 对应SortShuffle的sort方式

通过SortShuffleWriter源码可以看出SortShuffleWriter使用ExternalSorter处理map端输出，因此，接下来的分析围绕ExternalSorter展开，在Spark Shuffle之Hash Shuffle这篇文章中简单讨论过reduce端使用ExternalSorter实现排序的原理。

ExternalSorter实现

#存储
ExternalSorter内部维护了两个集合PartitionedAppendOnlyMap、PartitionedPairBuffer 

两者底层均使用数组，完全一致，如下图所示：

每条K-V Pair记录占两个位置，2i位置存储的是元组，内容为PartitionId + K，2i + 1存储V，两者的区别在于功能上。

SortShuffleWriter会根据是否有aggregation操作，灵活选择PartitionedAppendOnlyMap或PartitionedPairBuffer，可以查看源代码。

#排序之TimSort

使用TimSort对PartitionedAppendOnlyMap、PartitionedPairBuffer底层的Array进行排序， 排序的逻辑是，先根据PartitionId，再根据K的hashCode进行排序。

SortShuffle的Map端处理后Partition内K是有序的，顺序由K的hashCode决定，但是和MapReduce实现不同，这个Partition内的顺序并不会被reduce端直接使用，Reduce端不会进行merge-sort，而是当做无序进行处理，更多信息请参考Add MR-style (merge-sort) SortShuffleReader for sort-based shuffle。

#总结

本文介绍ExternalSorter的实现原理，SortShuffleWriter使用其存储数据及进行排序。

#