Сокращение времени поиска при чтении многих небольших файлов

Мне нужно написать код (на любом языке) для обработки 10 000 файлов, которые находятся в локальной файловой системе Linux. Каждый файл имеет размер ~ 500 КБ и состоит из записей фиксированного размера по 4 КБ.

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

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

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

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

Я, конечно, открыт для любых других идей.

Файловая система - ext4, но такая оборотная.

Ответ 1

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

Ответ 2

Очень простой подход, хотя никаких результатов не гарантировано. Открывайте сразу столько файлов, сколько сможете, и сразу читайте их - либо используя потоки, либо асинхронный ввод-вывод. Таким образом, планировщик дисков знает, что вы читаете, и может самостоятельно уменьшить количество запросов. Изменить:, как замечает wildplasser, параллельный open(), вероятно, выполним только потоки, а не async I/O.

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

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

Ответ 3

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

Ответ 4

Поскольку операции аналогичны, а данные независимы, вы можете попробовать использовать пул потоков для отправки заданий, которые работают с несколькими файлами (может быть одним файлом). Затем вы можете пропустить нить, заполняющую одно задание. Это может помочь перекрывать операции ввода-вывода с выполнением.

Ответ 5

Простым способом было бы сохранить исходную программу, но переделать дополнительный процесс, у которого нет другой задачи, кроме предварительной выборки файлов и заполнения кэша дискового буфера. (система unix/linux использует всю "свободную" память в качестве дискового буфера).

Основная задача останется за несколькими файлами (скажем, десять). Жесткая часть - синхронизировать вещи. Труба кажется очевидным способом выполнить это.

UPDATE:

Псевдокод для основного процесса:

- fetch filename из рабочего списка
- если пустой goto 2.
- (возможно) fork рабочий процесс или поток
- добавить в очередь предварительной выборки
- добавить во внутреннюю очередь
- если меньше, чем XXX элементов во внутренней очереди goto 1
- получить имя файла из внутренней очереди
- обработать его
- goto 1

Для подчиненных процессов:

выборка из очереди
if empty: quit
файл предварительной выборки
цикл или выйти

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

Вам понадобятся примерные рабочие потоки/процессы seektime_per_file/processing_time_per_file.

В качестве упрощения: если поиск файлов не требуется (только последовательный доступ), подчиненные процессы могут состоять из эквивалента

dd if=name bs=500K

который можно обернуть в папку popen() или pipe + fork().