kv-par-merge-sort

键值并行归并排序

对不适合内存的 Pod (键，值) 数据集进行排序。

此软件包提供了 kv_par_merge_sort 库，允许用户通过 SortingPipeline 对 (键，值) 对（又称条目）的 Chunk 进行排序。排序后的输出存储在两个文件中：一个用于键，一个用于值。键文件已排序，而值文件与键文件并行。

更确切地说，我们表示输入流为 [(k[0], v[0]), (k[1], v[1]), ...]。最终的键和值文件分别布局为 [k[a], k[b], ...] 和 [v[a], v[b], ...]，这样键数组就是排序的。分开文件的原因是为了确保正确的数据类型对齐（用于零拷贝读取）而不会浪费空间进行填充。

对 ~17 GB 的数据集（约5亿条条目）进行排序

$ time RUST_LOG=debug cargo run --release --example large_data_set -- -o /ssd_data/bench_data/ -t /ssd_data/tmp/
[2022-05-28T08:24:56Z INFO  large_data_set] Random input data set will contain 18 unsorted chunks of at most 28071681 entries each
[2022-05-28T08:25:36Z INFO  large_data_set] Done generating random chunks
[2022-05-28T08:26:00Z INFO  kv_par_merge_sort] Running merge of 16 persisted chunks
[2022-05-28T08:26:01Z INFO  kv_par_merge_sort] All chunks sorted, only merge work remains
[2022-05-28T08:27:02Z INFO  kv_par_merge_sort] Running merge of 3 persisted chunks
[2022-05-28T08:28:30Z INFO  kv_par_merge_sort] Done merging! Performed 2 merge(s) total

real    3m33.830s
user    3m31.733s
sys     0m42.923s

实现

为了在不耗尽内存的情况下对任意大小的数据集进行排序，我们必须求助于使用文件系统作为临时空间的“外部”排序算法；我们使用并行归并排序。每个 Chunk 都单独进行排序，并行并流式传输到一对文件中。这些文件由合并线程消耗，该线程（也是并行地）迭代地合并最多包含 merge_k 个大小相似的块的一组。

文件句柄

警告：如果 Chunk 的大小太小，则可能会超出您系统对打开文件句柄的限制。

内存使用

警告：如果您内存不足，请确保您实际上可以在内存中容纳 max_sort_concurrency 个 Chunk。另外请注意，std::env::temp_dir 实际上可能是一个内存中的 tmpfs。

文件系统使用

此算法执行最终合并需要比输入数据大两倍的空闲文件系统空间。

许可协议：MIT OR Apache-2.0