大型二进制文件的随机访问

Question

大型二进制文件的随机访问

clinuxperformancefilebinary

5

我有一个大二进制文件（12GB），我想要实时组装一个较小的二进制文件（16KB）。假设文件已经在磁盘上，并且小文件的字节在大二进制文件中分布得比较随机。什么方法最快捷有效？到目前为止，我的最佳成绩是三分钟。

以下是我尝试过的一些方法，它们的表现几乎相同：

1. 将文件转换为HDF5格式并使用C接口（较慢）。 2. 编写一个小的C程序通过fseek()在文件中寻找（较慢）。

如何才能真正快速地随机访问这些数据？

我希望查询时间不到两秒钟。

- Genausactly

我怀疑在几秒钟内随机读取12G并将其写回可能在物理上不可能实现。 - Jacob

你能提供更多细节吗？你需要扫描全部12GB来定位较小文件的字节，还是有算法/头文件/链等可以告诉你它们在哪里？你慢的“fseek”程序会有所帮助，以便更好地解释。 - Roddy

一个16kb的文件需要3分钟，那么将整个12gb文件分割成16kb的块呢？ - Vinicius Kamakura

7个回答

6

好的，你能够实现的速度在很大程度上取决于为提取96kB新文件的负载所执行的读取操作总数。

为什么会这样呢？因为从（旋转）磁盘进行随机读取受到查找限制；相比重定位磁头所需时间，读取本身（几乎）是无限快的。

由于你说访问模式是随机的，所以也不太可能从操作系统中获得任何预读取的好处；如果你选择这样做，可以通过对大文件的文件描述符使用 fadvise(fd，0，MAX_OFFSET，FADV_RANDOM); 将其关闭。或者，如果你选择使用mmap()，则可以使用madvise()。但是，这只在你执行大型读取时才有用（并且你知道大量预读取是无意义的）。对于小型读取，只有查找时间确定总体时间。

假设您需要进行N个随机读取，并且您有M毫秒的寻道时间，至少需要N * m毫秒来执行数据提取（如果您独占磁盘...）。没有办法突破这个限制。

编辑：减轻策略的一些要点：

正如一些人所提到的，解决这个问题的关键是最小化寻道。有几种策略可以采用：

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

一般而言，如果以上情况均不适用，则必须接受查找延迟。如果您可以证明成本（和/或RAM的易失性），则购买固态硬盘和/或使用基于RAM的文件系统。

- FrankH.

1

你尝试过使用mmap映射文件吗？（在你的情况下，是mmap64）。这将在访问数据时从磁盘中惰性读取数据。

如果你必须遍历整个文件才能找到你要查找的数据，你可以通过使用SSD来加速它，但它始终会很慢。你是否提前知道要查找的数据的位置？

文件是文本文件还是二进制文件？

- Dave

不会行的。任何魔法都无法克服物理硬盘的限制。 - JeremyP

1

如果你必须读取整个文件并且使用机械硬盘，那么你就完了。假设传输速率约为 1 Gigabit/second，这意味着你物理上无法在少于12 x 8 = 96秒内将所有位通过总线传输。这假设不存在寻道时间，并且处理器可以随时处理数据。

由于传输速率受驱动器速度的限制，即使你确切知道要读取的每个字节数据的位置，如果它们随机散布在文件中，仍然需要大约相同的时间，因为你必须等待磁盘旋转，直到你想要的下一个字节位于磁头下方。

如果你有一个固态硬盘，那么你可能可以大大改善这种情况，因为不需要等待字节在磁头下出现。

- JeremyP

你读了问题吗？他试图通过在每次读取之前“寻找”来读取16k。因此，他并不是试图读取整个文件；他试图总共读取16k。因此，传输速率是无关紧要的，如果文件大小为12TB，则他的代码所需的时间完全相同。这里唯一相关的数字是寻道时间，而不是传输速率，因此你目前给出的答案是错误的。 - Nemo

@Nemo：你有没有读到我回答的第二段话，我说“由于传输速率受驱动器速度的限制，因此很大程度上取决于驱动器的速度”。你明白这是什么意思吗？这意味着，无论你是否读取中间所有字节，读取一个字节然后再读取另一个字节需要多长时间都没有区别。当磁盘不在读取时，它不会加速。 - JeremyP

好的，加上你的SSD建议很不错，所以我已经取消了我的反对票。但是你的第一段仍然是无意义的；他的问题非常明确，他不需要读取整个文件，所以那个数学计算是无关紧要的。而且随机读取所需的时间与读取整个文件的时间“大约相同”也是错误的。它们是完全不相关的数字。 - Nemo

PS：至少一半的随机访问时间是用于将磁盘头本身向/远离磁盘中心移动；另一半时间是等待磁盘旋转。因此，即使磁盘无限快地旋转（旋转延迟=零），寻道时间仍将以毫秒为单位测量。 - Nemo

@Nemo：感谢您取消了负评。第一段只是为了让人们了解他试图完成的任务的规模。从某种意义上说，这是相关的，因为他无论如何都在尝试遍历一个非常大的文件，并且他可能受到设备物理特性的限制。 - JeremyP

显示剩余3条评论

0

我想这取决于你需要做多少次搜索。一万六千次，还是更少？你能把12GB的文件存储在固态硬盘上吗？这将减少寻址延迟。

你能将文件分割并存储在不同的硬盘上吗？这将使异步并行寻址成为可能。

- Mike Dunlavey

0

一些加速读取文件的小技巧（除了已经提到的）： - 读取块大小的倍数块 - 在符合POSIX标准的系统上使用posix_fadvise()，向操作系统建议分页。

- Maciej

0

使用并行或异步读取。必要时从多个线程、进程等发出请求，或者像FrankH所说的那样使用preadv。

这意味着在下一个IO请求到来之前，您不必等待一个IO请求完成，如果您拥有聪明的RAID控制器和大量的磁盘，这将提高性能。

另一方面，如果您有一个非常愚蠢的IO子系统，它可能只会有很小的差别。考虑使用哪个I/O调度程序（您可以随时更改它们，而无需重新启动，这真的很酷）。据传"noop"是最好的选择，如果您有"聪明"的硬件，而cfq或deadline如果您有愚蠢的硬件。

- MarkR

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nemo · Accepted Answer

答案基本上是“不行”。单个机械硬盘需要大约10毫秒的时间来执行寻道操作，因为它必须移动磁盘头。16000次寻道乘以每次10毫秒等于160秒。你如何编写代码都没有任何区别；例如mmap()也不会有任何影响。

欢迎来到物理世界，软件人员 :-）。你必须改进你的操作局部性。

首先，对你正在访问的位置进行排序。文件中附近的位置很可能在磁盘上也是相邻的，并且在相邻位置之间进行寻道比随机寻道更快。

其次，你的磁盘可能以大约100兆字节/秒的速度读取连续数据；也就是说，它可以在大约执行一次寻道的时间内顺序读取1兆字节。因此，如果你的两个值相差不到1兆字节，你最好读取它们之间的所有数据，而不是在它们之间执行寻道。（但是在你的硬件上进行基准测试以找到最佳平衡点。）

最后，RAID可以帮助提高吞吐量（但不能改善寻道时间）。如果你想多线程读取代码，它还可以提供多个磁盘头并发寻道。

但是总的来说，访问随机数据是你可以要求计算机做的最糟糕的事情，无论是在内存中还是在磁盘上。而顺序访问和随机访问之间的相对差异每年都在增加，因为物理学是局部的。（好吧，在这里我们所依赖的物理学是局部的。）

@JeremyP的建议使用固态硬盘是一个好主意。如果有这个选项，它们的有效搜索时间约为0.1毫秒。这意味着您可以期望在此类硬件上运行代码的速度快50-100倍。(我没有考虑到这一点，因为我通常处理的文件大小为1TB，SSD会太昂贵。)

[编辑2]

正如@FrankH在评论中提到的那样，我的一些建议假定文件在磁盘上是连续的，这当然不能保证。您可以通过使用良好的文件系统(例如XFS)和在文件创建时提供"提示"(例如使用posix_fallocate来告知内核您打算填充大文件)来帮助改善此问题。