需要高性能/bin/sort；有什么建议？

Question

我正在寻找高性能的 /bin/sort 替代品。我知道有 pbzip2 可以使用多核，但是 /bin/sort 有类似的产品吗？

我找到了 distsort.sh，但我想要一些不那么 IO 密集的东西。我正在寻找排序哦.. 60 演出数据非常频繁。

Answer 1

在四处搜索时，我发现了很多对学术论文的引用和一种名为Nsort 的商业产品。除了他们的网站声称：

Nsort 是一个排序/合并程序，可以并行使用大量处理器和磁盘，对大量数据进行快速排序。在 CPU 效率方面独一无二，Nsort 是唯一一个用于演示的商业排序程序：

• 1 TB 排序（33 分钟）
• 1 GB/秒的文件读写速率

Nsort 在排序海量生产数据集方面有着悠久的历史，例如：

• 高流量网站的网络日志
• 电话记录
• 政府机构数据

Answer 2

嗯。我想你会在这里遇到一些问题。首先，您的输入数据将对排序性能产生很大影响（不同算法的性能更好或更差取决于输入的分布）。然而，一个更大的问题是 60GB 是大量数据。

此外，排序不像压缩那样容易并行化，因为没有邻近性保证。换句话说，通过压缩/解压缩，您可以将输入分成离散的块，并分别独立地对它们进行操作。处理完每个块后，它们会简单地连接在一起。通过排序，您涉及多个步骤，因为您不能仅仅连接结果（除非您进行一些预处理），您必须合并结果（因为 60GB 开头的条目可能会与条目相邻在 60GB 的末尾，排序后）。

我基本上可以在这里想到一些通用的解决方案：

• 以易于排序和重组的方式对数据进行预分区。例如，如果您进行简单的字母排序，您可能将数据存储在 26 个桶中，每个桶对应一个字母。然后您可以单独对每个桶进行排序，并在最后重新组合它们。您如何对数据进行预分区的具体细节取决于数据本身、您当前的存储方法等。某些设置可能比其他设置更适用于此。
• 编写您自己的排序前端，它基本上可以完成我上面写的内容，但是是即时的。换句话说，您将有一个脚本来读取输入，并基于一些非常快速的操作（例如读取第一个字母，或任何适用于您的数据的操作），然后将该数据块分配到适当的排序桶。每种排序独立运行，直到处理完所有数据，然后将它们全部重新组合在一起。这实际上与使用 MapReduce 进行排序的特殊情况非常相似。
• 使用基于 MapReduce 的排序解决方案。有一个名为 Hadoop 的开源项目，它提供了一堆子项目，其中一个是开源 MapReduce 实现。我从来没有用过它，但是，只是阅读它。我不知道它是否实际上适用于您的特定问题。
• 您可以索引数据，然后对其进行排序吗？整个 60GB 是排序键的一部分吗？或者是否有您正在排序的较小部分，然后是每个部分的一堆附加数据？如果是后者，索引和排序只是某种键值，然后根据需要查找其他数据，可能是要走的路。
• 也许您可以完全预先排序您的数据，并将其保持在排序状态。每次添加或更新数据时，您都会从排序的角度更正它。该解决方案高度依赖于您存储数据的方式，以及排序更新对性能的影响是否可以接受。
• 最后，你可以押注整件事。将您的数据转储到 RDBMS（我自己喜欢 PostgresSQL），让数据库为您处理排序。

在不了解更多关于你的数据和你正在做的事情的细节的情况下，这是我能提供的最好的建议。

[注意：我不是排序方面的专家，所以比我更聪明的人可能会指出我逻辑中的错误，或改进这些错误的建议。]

Answer 3

GNUsort有 -m 可能可以帮助你。假设您有 200 个 .gz 文件需要排序和合并。然后你可以使用 GNU Parallel 来执行以下操作：

seq 1 200 | parallel mkfifo /tmp/{}
ls *.gz | nice parallel -j200 'zcat {} | sort >/tmp/$PARALLEL_SEQ' &
seq 1 200 | parallel -X sort -m /tmp/{} >/tmp/sorted

如果 I/O 是问题而内存不是问题，则首先使用 -Ssort以确保所有内容都保留在内存中。此外，您可能希望lzop每次写入磁盘时都使用 (--compress-program=lzop)：磁盘通常是限制因素，因此即时 lzopping 可以为您提供额外的速度。或者您可以制作一个 RAM 磁盘并将 -T 设置为该目录。

编辑2023

其中一些想法现在已经成为 的一部分parsort，也比上面的经过了更好的测试。