并行排序算法在分布式集群上的主要挑战是如何使各节点的工作负载相对均衡,因为负载不均衡容易导致数据倾斜问题,原始数据集倾斜的数据分布与大量的重复关键字是造成此问题的主要原因。对于基于分区的并行排序算法而言,解决数据倾斜问题的核心是分离器的划分策略能够尽可能均匀地划分原始数据集。在本文中,我们总结了一个高效的分离器在划分原始数据集时必须满足的6条标准。我们在Spark集群上针对Bucket Sort、Counting Sort、Pigeonhole Sort、Radix Sort以及Sample Sort设计了对应的基于分区的并行排序算法,并针对每种算法分析了其满足分离器划分策略6条标准的情况。对于样本排序我们设计了两种不同的分离器划分策略:百分位分离器划分策略与次优分离器划分策略。百分位分离器划分策略专注于均等地划分数据集,不考虑某一热key的分区中可能存在非热key的情况;而次优分离器划分策略通过一种等区与不等区的划分机制保证了热key与非热key不在同一分区之中,又通过等区切分、小分区合并以及分桶再平衡策略的手段尽可能保证了其能够均匀地划分数据集。分桶再平衡策略的工作原理是将热key数据通过Round-Robin的方式均匀地划分到多个分区之中。我们在一个具有32节点的总内存容量为768GB的Spark集群中对各算法进行了实验。实验证明,对于含有大量重复关键字的数据集,在已实现的6种并行排序算法以及Spark自带的sort By算子中,样本并行排序算法有着最小的排序时间开销以及最均衡的负载分布,并且使用百分位分离器划分策略的样本排序比使用次优分离器划分策略的样本排序有着相对更少的排序时间,但后者具备热key数据与非热key数据不在同一分区的特点。