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

Question

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

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

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

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

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

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

Файловая система - ext4, но по договоренности.

Answer 1

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

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

UPDATE:

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

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

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

• выборка из очереди
• если пусто: выйти
• файл предварительной выборки
• цикл или выход

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

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

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

dd if=name bs=500K

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

Answer 5

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