Linux:对包含10 ^ 10条记录的500GB文本文件进行排序

Question

我有一个500GB的文本文件,大约有10亿行需要按字母顺序排序.什么是最好的算法？我的实施和设置能否得到改善？

现在,我正在使用coreutils sort命令:

LANG=C
sort -k2,2 --field-separator=',' --buffer-size=(80% RAM) --temporary-directory=/volatile BigFile

我在AWS EC2上运行120GB RAM和16核虚拟机.这需要一天的大部分时间.

/ volatile是10TB RAID0阵列.

'LANG = C'技巧提供x2速度增益(感谢1)

默认情况下,'sort'使用50%的可用RAM.上升到80-90%会有所改善.

我的理解是gnu'sort'是合并排序算法的变体,其中O(n log n)是最快的:见2和3.将转向QuickSort帮助(我对不稳定的排序感到满意)？

我注意到的一件事是只使用了8个核心.这与linux coreutils sort.c中default_max_threads设置为8有关(参见4).用16重新编译sort.c会有帮助吗？

谢谢!

---

跟进 :

@dariusz

我在下面使用了克里斯和你的建议.

由于数据已经批量生成:我分别对每个桶进行分类(在几台不同的机器上),然后使用'sort --merge'函数.像魅力一样工作得快得多:O(log N/K)vs O(log N).

我还从头开始重新考虑该项目:现在在生成数据时执行一些数据后处理,以便在排序之前可以丢弃一些不需要的数据(噪声).

总之,数据大小减少和排序/合并导致实现我的目标所需的计算资源的大量减少.

感谢您的所有有用的评论.

Answer 1

快速排序优于合并排序的好处是没有额外的内存开销。mergesort的好处是可以保证O（n log n）的运行时间，因为枢轴点采样不佳的情况下，quicksort可能会更加糟糕。如果您没有理由担心内存使用情况，请不要更改。如果这样做，则只需确保选择一个进行可靠数据透视采样的快速排序实施即可。

我认为重新编译sort.c不会产生明显的帮助。可能是在微观优化规模上。但是这里的瓶颈将是内存/磁盘速度，而不是可用的处理器数量。我的直觉是8个线程将已经使您的I / O吞吐量最大化，并且您不会看到性能上的改善，但这肯定取决于您的特定设置。

此外，通过利用数据分布，您可以显着提高性能。例如，可以通过一次存储桶排序过程非常快速地对均匀分布的数据进行排序，然后使用mergesort对存储桶进行排序。这还具有减少mergesort的总内存开销的额外好处。如果mergesort的内存复杂度为O（N），并且您可以将数据分为K个存储桶，则新的内存开销为O（N / K）。