CODEWITHSUNDEEP
linuxlanguage-agnosticfilesystems
NPE
NPE

Reputation: 500663

Reducing seek times when reading many small files

I need to write some code (in any language) to process 10,000 files that reside on a local Linux filesystem. Each file is ~500KB in size, and consists of fixed-size records of 4KB each.

The processing time per record is negligible, and the records can be processed in any order, both within and across different files.

A naïve implementation would read the files one by one, in some arbitrary order. However, since my disks are very fast to read but slow to seek, this will almost certainly produce code that's bound by disk seeks.

Is there any way to code the reading up so that it's bound by disk throughput rather than seek time?

One line of inquiry is to try and get an approximate idea of where the files reside on disk, and use that to sequence the reads. However, I am not sure what API could be used to do that.

I am of course open to any other ideas.

The filesystem is ext4, but that's negotiable.

Upvotes: 18

Views: 3777

Answers (5)

wildplasser
wildplasser

Reputation: 44250

A simple way would be to keep the original program, but fork an extra process which has no other task than to prefetch the files, and prime the disk buffer cache. ( a unix/linux system uses all "free" memory as disk buffer).

The main task will stay a few files behind (say ten). The hard part would be to keep things synchronised. A pipe seems the obvious way to accomplish this.

UPDATE:

Pseudo code for the main process:

    • fetch filename from worklist
    • if empty goto 2.
    • (maybe) fork a worker process or thread
    • add to prefetch queue
    • add to internal queue
    • if fewer than XXX items on internal queue goto 1
    • fetch filename from internal queue
    • process it
    • goto 1

For the slave processes:

  • fetch from queue
  • if empty: quit
  • prefetch file
  • loop or quit

For the queue, a message queue seems most appropiate, since it maintains message boundaries. Another way would be to have one pipe per child (in the fork() case) or use mutexes (when using threads).

You'll need approximate seektime_per_file / processing_time_per_file worker threads / processes.

As a simplification: if seeking the files is not required (only sequential access), the slave processes could consist of the equivalent of

dd if=name bs=500K

, which could be wrapped into a popen() or a pipe+fork().

Upvotes: 0

Rafał Dowgird
Rafał Dowgird

Reputation: 45131

A very simple approach, although no results guaranteed. Open as many of the files at once as you can and read all of them at once - either using threads or asynchronous I/O. This way the disk scheduler knows what you read and can reduce the seeks by itself. Edit: as wildplasser observes, parallel open() is probably only doable using threads, not async I/O.

The alternative is to try to do the heavy lifting yourself. Unfortunately this involves a difficult step - getting the mapping of the files to physical blocks. There is no standard interface to do that, you could probably extract the logic from something like ext2fsprogs or the kernel FS driver. And this involves reading the physical device underlying a mounted filesystem, which can be writing to it at the same time you're trying to get a consistent snapshot.

Once you get the physical blocks, just order them, reverse the mapping back to the file offsets and execute the reads in the physical block order.

Upvotes: 2

Wim Coenen
Wim Coenen

Reputation: 66753

Perhaps you could do the reads by scheduling all of them in quick succession with aio_read. That would put all reads in the filesystem read queue at once, and then the filesystem implementation is free to complete the reads in a way that minimizes seeks.

Upvotes: 6

savagepanda
savagepanda

Reputation: 877

could you recommend using a SSD for the file storage? that should reduce seek times greatly as there's no head to move.

Upvotes: 1

perreal
perreal

Reputation: 98048

Since operations are similar and data are independent you can try using a thread pool to submit jobs that work on a number of files (can be a single file). Then you can have an idle thread complete a single job. This might help overlapping IO operations with execution.

Upvotes: 0

Related Questions