随机化超大文件内容顺序的有效方法是什么？

Question

对于我的神经网络训练项目，我有一个非常大的输入数据文件。文件格式为二进制，由大量固定大小的记录组成。该文件目前约为 13GB，但将来可能会变得更大；出于这个问题的目的，我们假设它太大而无法一次将所有内容保存在我计算机的 RAM 中。

今天的问题涉及我编写的一个小实用程序（用 C++ 编写，虽然我认为在这里选择语言并不重要，因为在任何语言中都可能遇到相同的问题），旨在阅读大文件和输出类似的大文件 -- 输出文件包含与输入文件相同的数据，只是记录被打乱成随机顺序。

为此，我mmap()将输入文件存入内存，然后生成一个从 1 到 N 的整数列表（其中 N 是输入文件中的记录数），随机打乱顺序该列表，然后遍历该列表，将 mmap 内存区域中的第 n 条记录写入输出文件。

就目前而言，一切正常；问题是它的扩展性不是很好；也就是说，随着输入文件的大小变大，进行此转换所需的时间增加得比 O(N) 更快。它已经到了成为我工作流程瓶颈的地步。我怀疑问题是 I/O 系统（对于 MacOS/X 10.13.4，使用我的 Mac Pro 垃圾桶的内部 SSD，以防万一）针对顺序读取进行了优化，并且就 caching/read-ahead/other I/O 优化而言，跳转到输入文件中完全随机的位置几乎是最坏的情况。（我想在旋转磁盘上它会由于寻头延迟而表现更差，但幸运的是我至少在这里使用 SSD）

所以我的问题是，是否有任何聪明的替代策略或优化我可以用来使这个文件随机化过程更有效——随着输入文件大小的增加，它可以更好地扩展？

Answer 1

如果问题与读取随机文件位置时的交换和随机磁盘访问有关，您至少可以按顺序读取输入文件吗？

当您访问 mmap-ed 文件中的某个块时，预取器会认为您很快就会需要相邻页面，因此它也会加载它们。但你不会，所以这些页面将被丢弃，加载时间将被浪费。

创建 N 个 toPositons 数组，因此 toPosition[i]=i;
随机化目的地（您使用的是 knuth 的随机播放吗？）；
然后 toPosition[i] = input[i] 的目的地。因此，从头开始依次读取输入数据，并将它们放入目标文件的相应位置。

也许，这样会更prefetcher-friendly。当然，随机写入数据也很慢，但至少，您不会浪费从输入文件中预取的页面。

额外的好处是，当您处理了数百万个输入数据页后，这些 GB 将从 RAM 中卸载，您将不再需要它们，因此您不会污染实际的磁盘缓存。请记住，实际内存页面大小至少为 4K，因此即使您随机访问 mmap-ed 文件的 1 字节，也应该至少从磁盘读取 4K 数据到缓存中。

Answer 2

我建议不要使用 mmap() - 内存压力根本没有任何帮助，而且 unless you're re-reading the same data multiple times, mmap() is often the worst-performing way to read data.

首先，生成 N 个随机偏移量，然后，根据这些偏移量，使用 pread() 读取数据 - 并使用 low-level C-style IO。

这对您的文件使用 fcntl() function to disable the page cache。因为你不是 re-reading 相同的数据，页面缓存可能对你没什么好处，但它确实会耗尽 RAM，减慢其他事情的速度。在禁用和不禁用页面缓存的情况下都尝试一下，看看哪个更快。另请注意，我省略了所有错误检查：

（我还假设 C-style IO 函数在 MAC 上的 namespace std 中，并且我使用 C-style 字符串和数组来匹配 C-style IO 功能，同时保持代码更简单。）

#include <sys/types.h>
#include <sys/uio.h>
#include <unistd.h>
#include <fcntl.h>

void sendRecords( const char *dataFile, off_t offsets, size_t numOffsets )
{
    int fd = std::open( dataFile, O_RDONLY );
    // try with and without this
    std::fcntl( fd, F_NOCACHE, 1 );

    // can also try using page-aligned memory here
    char data[ RECORD_LENGTH ];

    for ( size_t ii = 0; ii < numOffsets; ii++ )
    {
        ssize_t bytesRead = std::pread( fd, data, sizeof( data ), offsets[ ii ] );
        // process this record
        processRecord( data );
    }

    close( datafd );
}

假设您有一个包含预先计算的随机偏移量的文件：

#include <sys/types.h>
#include <sys/uio.h>
#include <unistd.h>
#include <fcntl.h>

void sendRecords( const char *dataFile, const char *offsetFile )
{
    int datafd = std::open( dataFile, O_RDONLY );
    // try with and without this
    std::fcntl( fd, F_NOCACHE, 1 );

    int offsetfd = std::open( offsetFile, O_RDONLY );

    // can also try using page-aligned memory here
    char data[ RECORD_LENGTH ];

    for ( ;; )
    {
        off_t offset;
        ssize_t bytesRead = std::read( offsetfd, &offset, sizeof( offset ) );
        if ( bytesRead != sizeof( offset ) )
        {
            break;
        }
        bytesRead = std::pread( fd, data, sizeof( data ), offset );
        // process this record
        processRecord( data );
    }

    std::close( datafd );
    std::close( offsetfd );
}

您也可以走得更快，因为该代码交替读取和处理，使用多个线程同时读取和处理可能会更快。使用一个或多个线程将数据读入预分配的缓冲区并不难，然后将这些缓冲区排队并发送到您的处理线程。

Answer 3

多亏了此线程中各个人的建议（特别是 Marc Glisse 和 Andrew Henle），我能够将我的程序在 13GB 输入文件上的执行时间从大约 16 分钟减少到大约 2 分钟。我将在这个答案中记录我是如何做到的，因为解决方案与上面的任何一个答案都不太相似（它更多地基于 Marc 的评论，所以我会给 Marc 他重申的复选框 if/when他的评论作为回答）。

我尝试用 pread() 替换 mmap() 策略，但这似乎没有太大区别；我尝试将 F_NOCACHE 和各种其他标志传递给 fcntl()，但它们似乎要么没有效果，要么让事情变得更慢，所以我决定尝试一种不同的方法。

新方法是以 2 层方式做事：我的程序现在不是一次读取单个记录，而是从输入文件加载 "blocks" 个连续记录（每个块包含大约 4MB 的数据）。

块以随机顺序加载，我加载块直到我有一定数量的 block-data 保存在 RAM 中（目前 ~4GB，因为那是我的 Mac RAM 可以轻松容纳）。然后我开始从随机 in-RAM 块中抓取随机记录，并将它们写入输出文件。当给定的块中不再有任何记录可供抓取时，我释放该块并从输入文件中加载另一个块。我重复此操作，直到加载了输入文件中的所有块并将它们的所有记录分发到输出文件。

这更快，因为我的所有输出都是严格顺序的，而且我的输入大部分是顺序的（即每次查找后读取 4MB 的数据，而不是仅约 2kB）。输出的顺序比以前稍微不那么随机了，但我认为这对我来说不是问题。

随机化超大文件内容顺序的有效方法是什么？

What's an efficient way to randomize the ordering of the contents of a very large file?

c++

io

mmap

random-access

large-files