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

Question

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

Answer 1

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

Merge Sort是完成此任务的最佳方式。您可以使用并行进程同时对不同的数据块进行排序，这可以加快排序速度。

的事情是，你做了排序块后，你不必有单过程完成所有合并的，你可以有多个进程同时合并不同的块：

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

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

Answer 2

坏消息 - 你不能避免多个排序文件的k合并。 好的是你可以并行地做一些操作。