Произвольный доступ к большому двоичному файлу

Question

У меня есть большой двоичный файл (12 ГБ), из которого я хочу на лету собрать меньший двоичный файл (16 КБ).Предположим, что файл находится на диске, и что байты для меньшего файла несколько случайно распределены в большом двоичном файле.Какой самый лучший и быстрый способ сделать это?До сих пор я не смог добиться большего успеха, чем около трех минут.

Вещи, которые я пробовал, с более или менее одинаковой производительностью:

1. Преобразование файла вформат HDF5 и использование интерфейса C (медленно).
2. Написание небольшой программы на C для fseek () через файл (медленно).

Как получить произвольный доступ к этим даннымдействительно быстро ?

Я хочу получить менее пары секунд для запроса.

Answer 1

Ответ в основном "нет".

Одному механическому дисковому накопителю потребуется около 10 мсек, чтобы выполнить поиск, потому что он должен переместить головку диска. 16000 раз поиска 10 миллисекунд на поиск равны 160 секундам. Не имеет абсолютно никакого значения, как вы пишете свой код; например mmap () ничего не изменит.

Добро пожаловать в физический мир, программист :-). Вы должны улучшить местность своих операций.

Сначала отсортируйте местоположения, к которым вы обращаетесь. Ближайшие местоположения в файле, скорее всего, будут рядом на диске, и поиск между соседними местоположениями быстрее, чем случайный поиск.

Затем ваш диск может считывать последовательные данные со скоростью около 100 мегабайт в секунду; то есть он может читать 1 мегабайт последовательно примерно за то же время, которое требуется для выполнения поиска. Поэтому, если два ваших значения находятся на расстоянии менее 1 мегабайта, вам лучше прочитать всех данных между ними , чем выполнять поиск между ними. (Но сравните это, чтобы найти оптимальный компромисс на вашем оборудовании.)

Наконец, RAID может помочь с пропускной способностью (но не время поиска). Он также может обеспечить несколько головок дисков, которые могут выполнять одновременный поиск, если вы хотите многопоточное чтение кода.

Но в целом доступ к случайным данным - это самое худшее, что вы можете попросить сделать у своего компьютера, будь то в памяти или на диске. И относительная разница между последовательным доступом и произвольным доступом увеличивается с каждым годом, потому что физика является локальной. (Ну, во всяком случае, физика, от которой мы здесь зависим.)

[править]

@ JeremyP советует использовать твердотельные накопители. Если они являются опцией, они имеют эффективное время поиска 0,1 мс или около того. Это означает, что вы могли ожидать, что ваш код будет работать в 50-100 раз быстрее на таком оборудовании. (Я не думал об этом, потому что я обычно работаю с файлами в диапазоне 1 ТБ, где твердотельные накопители будут слишком дорогими.)

[править 2]

Как @FrankH упоминает в комментарии, некоторые из моих предложений предполагают, что файл непрерывен на диске , что, конечно, не гарантируется. Вы можете помочь улучшить это, используя хорошую файловую систему (например, XFS) и давая «подсказки» во время создания файла (например, используйте posix_fallocate , чтобы сообщить ядру, что вы намереваетесь заполнить большой файл).

Answer 2

Ну, скорость, которую вы можете достичь для этого, во многом зависит от общего количества операций чтения, которые вы выполняете для извлечения 96 кБ, которые составляют полезную нагрузку для вашего нового файла.

Почему это так?Поскольку случайное чтение с (вращающихся) дисков ограничено поиском;чтение как таковое (почти) бесконечно быстро по сравнению со временем, которое требуется для изменения положения магнитных головок.

Поскольку вы говорите, что схема доступа случайная, вы также вряд ли выиграете отлюбое ожидание, которое операционная система может решить использовать;поэтому вы можете, если захотите, отключить это с помощью fadvise(fd, 0, MAX_OFFSET, FADV_RANDOM); в дескрипторе файла для большого файла.Или madvise(), если вы выбрали mmap().Но это только выиграет, если вы выполняете большие чтения (и вы знаете, что большое чтение впереди было бы бессмыслицей).Для небольших операций чтения общее время определяется исключительно временем поиска.

При условии, что вам нужно N случайное чтение, и у вас есть время поиска M мс, это займет как минимум N * m миллисекунд для извлечения данных (если у вас есть диск для себя ...).Нет никакого способа преодолеть этот барьер.

Редактировать: Несколько вещей по смягчающим стратегиям:

Как уже упоминалось несколькими людьми, ключ к решению этой проблемы заключается в том, чтобыминимизировать ищет.Для этого есть несколько стратегий:

1. Выполняйте асинхронное чтение, если можете (то есть, если операция чтения N+1 не зависит от того, что выполняла операция N, вы можете одновременно выполнять обе операции),Это позволяет операционной системе / драйверу устройства ставить их в очередь и, возможно, переупорядочивать их (или объединять их со считываниями, выполняемыми другими одновременно выполняющимися процессами) для наиболее эффективного поиска.
2. Если вы знаете позиции заранее.затем выполните ввод-вывод с разбросом (на ум придет UN * X preadv()), с тем же эффектом.
3. Запрос вашей файловой системы и / или блочного устройства на лучший / минимальный размер блока;как это сделать зависит от системы, см., например, statvfs () или даже ioctl_list .Если вы знаете это, вы можете использовать метод, упомянутый Nemo (объединить два небольших чтения с «оптимальным» размером блока в одно большое чтение, не требуя поиска).
4. Возможно, даже используйте интерфейсы запросов, такие как FIEMAP / FIBMAP (эквивалент Windows примерно равен FSCTL_GET_RETRIEVAL_POINTERS), чтобы определить, где находятся физические блоки для ваших файловых данных, и принять решение о слиянии чтения, основываясь на этом (нет смысла выдавать большое чтение "не для поиска"если на самом деле это пересекает границу физического блока, а файловая система превращает его в две части).
5. Если вы строите позиции для чтения за сравнительно большое время, то читаете (асинхронно), пока вы все еще вычисляете будущие смещения чтениятакже поможет скрыть задержку поиска, так как вы правильно используете циклы вычислений / время ожидания.

В общем, если ничего из вышеперечисленного не применимо, вам придется прикусить пулю ипринять задержку поиска.Купите твердотельный диск и / или используйте поддерживаемую ОЗУ файловую систему, если вы можете оправдать затраты (и / или изменчивость ОЗУ).

Answer 3

Если вам нужно прочитать весь файл, и вы используете механический жесткий диск, вы ввернуты. Предположим, что скорость передачи составляет около 1 Гигабит / с , это означает, что физически вы не можете получить все биты через шину менее чем за 12 x 8 = 96 секунд. Это предполагает отсутствие времени поиска, и процессор может обрабатывать данные по мере их поступления.

Поскольку скорость передачи данных ограничена скоростью вращения диска, как и всего остального, даже если вы точно знаете, где находится каждый байт данных, которые вы хотите прочитать, если они случайно распределены по файлу, это все равно займет примерно до тех пор, пока вам придется ждать вращения диска, пока следующий нужный байт не окажется под заголовком.

Если у вас есть твердотельный накопитель, вы, вероятно, сможете значительно улучшить его, поскольку не нужно ждать, пока байты закроются под головой ...

Answer 4

Вы пробовали mmaping файл?(в вашем случае mmap64).Это будет лениво считывать данные с диска при доступе к нему.

Если вам придется искать по всему файлу, чтобы найти искомые данные, вы сможете ускорить егоSSD, но он всегда будет медленным.Расположение данных, которые вы ищете, известно заранее?

Является ли файл текстовым файлом или двоичным файлом?

Answer 5

Используйте параллельное или асинхронное чтение.Выполняйте их из нескольких потоков, процессов и т. Д. По мере необходимости или используйте preadv, как сказал FrankH.

Это означает, что вам не придется ждать выполнения одного запроса ввода-вывода перед следующимможет прийти, что повысит производительность, если у вас есть умный RAID-контроллер и много шпинделей.

С другой стороны, если у вас действительно глупая подсистема ввода-вывода, это может сделать только незначительнуюразница.Подумайте, какой планировщик ввода-вывода использовать (вы можете изменить их на лету, без перезагрузки, что действительно здорово).Неподтвержденные данные свидетельствуют о том, что «noop» лучше всего, если у вас «умное» оборудование, cfq или дедлайн, если у вас тупое оборудование.

Answer 6

Некоторые подсказки, чтобы немного ускорить чтение файлов (помимо того, что уже было сказано): - читать куски, которые умножены на размер блока - в POSIX-совместимых системах используйте posix_fadvise (), который советует ОС по подкачке.

Answer 7

Полагаю, это зависит от того, сколько поисков вам нужно сделать.16 тысяч или меньшее количество?Можете ли вы сохранить файл 12 ГБ на твердотельном диске?Это сократит задержки поиска.

Можете ли вы разбить файл и сохранить фрагменты на отдельных жестких дисках?Это позволило бы асинхронный поиск параллельно.