sorting - 对云中的大量数据进行排序？

Question

给定一个包含 1PB 数据的云存储文件夹，对所有这些数据进行排序的最快方法是什么？对其中的一小部分进行排序很容易，但是将它们合并为更大的排序输出将需要更长的时间，因为在某些时候单个进程将不得不合并整个事物。我想避免这种情况，并有一个完全分布式的解决方案，有没有办法？如果是这样，是否有任何适合用于在 S3 中对数据进行排序的实现？

Answer 1

由于您需要排序的数据量超过 RAM（很多），唯一合理的方法（据我所知）是先对块进行排序，然后将它们合并在一起。

合并排序是完成此任务的最佳方式。您可以使用并行进程同时对单独的数据块进行排序，这应该会加快排序速度。

问题是，在完成对块的排序之后，您不必让一个进程完成所有合并，您可以让多个进程同时合并不同的块：

该算法采用并行合并算法，不仅可以并行化数组的递归除法，还可以并行化合并操作。当与快速稳定的顺序排序（例如插入排序）和快速顺序合并作为合并小数组的基本情况相结合时，它在实践中表现良好。

这是一个链接，提供了有关合并算法的更多信息（以防万一）。

Answer 2

坏消息——你无法避免多个排序文件的 k 合并。好消息是您可以并行执行一些操作。