时间戳

首页 > 解决方案 > 如果数据不适合物理 RAM 内存，最快排序？

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

问题描述

我希望在具有 8-128 个内核、10% 元素的 RAM 以及提供 100-1000 MBytes/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] 是瓶颈。

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

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

我已阅读哪种并行排序算法具有最佳的平均案例性能？但它似乎忽略了中等大小数据的常见情况：该数据适合服务器的磁盘，但它不适合 RAM。

给定硬件（8-128 个内核，10% 的元素的 RAM，以及提供 100-1000 MBytes/s 流式传输的磁盘，1000 iops）什么是对 10^9 到 100 * 10^9 的列表进行排序的最快方法每个 10-100 字节的元素？

通俗地说：
在单个服务器上对最大数量的数据进行快速排序的可靠方法是什么？

标签： algorithmperformancesortingparallel-processinglow-latency

解决方案

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

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

对于大型数据集，基本上从来没有一个用例需要您在一个地方一次将它放在一个地方，您必须迭代整个事物。相反，施加这种任意限制只会造成不必要的瓶颈。

推荐阅读