随机访问大型二进制文件

Question

我有一个大的二进制文件(12 GB),我想在其中动态组装一个较小的二进制文件(16 KB).假设文件在磁盘上,并且较小文件的字节在某种程度上随机分布在大型二进制文件中.什么是最好和最快的方法？到目前为止,我已经做不到三分钟了.

我尝试过的东西,或多或少具有相同的性能:

1. 将文件转换为HDF5格式并使用C接口(慢速).
2. 通过文件写一个小的C程序到fseek()(慢).

如何快速随机访问这些数据？

我希望查询时间不到几秒钟.

Answer 1

答案基本上是"不".

单个机械磁盘驱动器需要10毫秒左右才能执行搜索,因为它必须移动磁头.16000寻求每次搜寻10毫秒的时间等于160秒.你编写代码的方式完全没有区别; 例如,mmap()将没有任何区别.

欢迎来到物理世界,软件人:-).您必须改善操作的位置.

首先,对要访问的位置进行排序.文件中的附近位置可能在磁盘附近,并且在附近位置之间寻找比随机搜索更快.

接下来,您的磁盘可能会读取大约100兆字节/秒的顺序数据; 也就是说,它可以在执行搜索所需的大约相同的时间内按顺序读取1兆字节.因此,如果您的两个值相差小于1兆字节,那么最好读取它们之间的所有数据,而不是在它们之间执行搜索.(但要对此进行基准测试,以找到硬件上的最佳权衡.)

最后,RAID可以帮助提高吞吐量(但不是寻求时间).它还可以提供多个磁头,如果您想要多线程读取您的读取代码,它们可以同时寻找.

但一般来说,访问随机数据是您可以要求计算机执行的最糟糕的事情,无论是在内存中还是在磁盘上.顺序访问和随机访问之间的相对差异每年都在增加,因为物理是本地的.(好吧,无论如何,我们依赖的物理学.)

[编辑]

@ JeremyP建议使用SSD是一个很好的建议.如果它们是一种选择,它们的有效寻道时间约为0.1 ms.这意味着您可以期望您的代码在此类硬件上运行速度提高50-100倍.(我没有想到这一点,因为我通常使用1 TB范围内的SSD太昂贵的文件.)

[编辑2]

正如@FrankH在评论中提到的,我的一些建议认为该文件在磁盘上是连续的,这当然不能保证.您可以通过使用良好的文件系统(例如XFS)并在文件创建时提供"提示"来帮助改进这一点(例如,使用posix_fallocate通知内核您打算填充大文件).

Answer 2

好吧，您可以达到的速度在很大程度上取决于您执行的读取操作总数，以便提取构成新文件有效负载的96 kB。

为什么？因为从（旋转）磁盘的随机读取受到搜索限制；与重新放置磁头所需的时间相比，这样的读取（几乎）是无限快的。

由于您是说访问模式是随机的，因此您也不太可能从操作系统可能决定使用的任何预读中受益。您可以选择是否关闭fadvise(fd, 0, MAX_OFFSET, FADV_RANDOM);大文件的filedescriptor上的内容。或者，madvise()如果您选择了mmap()它。但这只会在您进行大量阅读时才有意义（并且您知道进行大量预读是胡说八道）。对于小读而言，将完全取决于搜寻时间。

假设您需要N随机读取并且M查找时间为毫秒，那么N * m执行数据提取将至少需要数毫秒（如果您拥有磁盘，则...）。没有办法打破这一障碍。

编辑：关于缓解策略的几件事：

正如一些人提到的，解决此问题的关键是最小化搜寻。有以下几种策略：

1. 如果可以的话，发出异步读取（即，如果读取操作N+1不取决于读取操作N所做的操作，则可以同时发出两者）。这允许操作系统/设备驱动程序将它们排队，并可能对其进行重新排序（或将它们与其他同时运行的进程进行的读取合并），以实现最有效的查找。
2. 如果您事先知道所有位置，请执行分散收集I / O（preadv()会想到UN * X ），以达到相同的效果。
3. 查询文件系统和/或块设备以获取最佳/最小块大小；如何执行此操作取决于系统，请参见例如statvfs（）或ioctl_list。如果您知道这一点，则可以使用Nemo提到的技术（将“最佳”块大小内的两个小读取合并为一个大读取，而无需查找）。
4. 甚至甚至可以使用查询接口（例如FIEMAP/）FIBMAP（Windows的大致等价点FSCTL_GET_RETRIEVAL_POINTERS）来确定文件数据的物理块在何处，并基于该接口执行读取合并的决定（如果实际的话，发出大的“非查找”读取是没有意义的）跨越物理块边界，文件系统将其分成两个）。
5. 如果您在相对较长的时间内建立了要读取的位置，则在仍计算未来的读取偏移量时（异步）进行读取，也将有助于隐藏查找延迟，因为您可以充分利用计算周期/等待时间。

通常，如果以上条件均不适用，则您必须硬着头皮接受接受等待时间。如果可以证明成本（和/或RAM的波动性）合理，请购买固态磁盘和/或使用支持RAM的文件系统。