如果数据不适合物理RAM内存，最快排序？

Question

我正在寻找在具有8-128核，RAM占10％的元素以及磁盘传输速度为100-1000 MB / s的系统上排序10亿到1000亿个元素的列表。

我已经测试了简单的合并排序，其中每个合并由CPU并行执行：

sorted_part_a:__
                \__[CPU.1]__
sorted_part_b:__/           \
                             \__[CPU.5]__
sorted_part_c:__             /           \
                \__[CPU.2]__/             \
sorted_part_d:__/                          \
                                            \__[CPU.7]
sorted_part_e:__                            /
                \__[CPU.3]__               /
sorted_part_f:__/           \             /
                             \__[CPU.6]__/
sorted_part_g:__             /
                \__[CPU.4]__/
sorted_part_h:__/

但是有一个问题，当合并最后两个输入时，最后的合并步骤[CPU.7]必须在单个内核上进行n个比较，并且比较可能很昂贵（请考虑必须遵守语言环境的字符串设置）。在我的测试中，[CPU.7]是瓶颈。

然后我看了红黑树。它们具有几个优点：

• 构建树时，得到排序列表的是O(n)，没有比较。这避免了我在合并排序测试中看到的瓶颈。
• 您可以build trees in parallel and merge them in parallel因此使用多个核心。
• 开始构建树之前，您不需要所有数据（因此，如果您正在从速度较慢的设备读取数据，则可以在读取数据时进行排序，因此不会浪费墙上的时钟时间。]]

将树保存到磁盘似乎也很容易（只需导出排序列表和树的高度），但是仅从磁盘取回树的一部分似乎比较棘手。

我已经读过Which parallel sorting algorithm has the best average case performance?，但似乎忽略了中型数据的常见情况：该数据适合服务器的磁盘，但不适合RAM。

考虑到硬件（8-128内核，RAM用于10％的元素，并且磁盘提供100-1000 MBytes / s的流，1000 iops），最快的方法是对10 ^ 9到100 * 10的列表进行排序^ 9个元素，每个元素10-100个字节？

用外行的话：

快速排序您将在一台服务器上排序的最大数据量的可靠方法是什么？

我正在寻找在具有8-128内核，RAM用于10％的元素以及磁盘传输速度为100-1000 MBytes / s的系统上排序10亿到1000亿个元素的列表的方法。我已经测试了一个简单的合并排序，...

Answer 1

[当我没有定制的软件来为我做繁重的工作时，我就不需要做这种事情。

但是我在Google时的标准解决方案是将您的初始数据存储在分布式文件系统中，进行分布式合并排序，然后将最终数据存储在分布式文件系统中。由于最终排序的数据结构存储在块中，这意味着即使在最后一次传递中，每个CPU也只需要在其块内进行比较，从而可以在整个过程中充分利用CPU。

Answer 2

在传统合并中，使用排序的子文件，最终合并为O（n log k），其中n是项目总数，k是子文件数。基本上，您将从每个已排序的子文件中建立第一项优先级队列，删除第一项，将其写出，然后从具有最小项的文件中插入下一项。