Concurrent file read approaches?

[Chris]

What's the best approach for heavily concurrent read access to a file?

I have a file that needs to be read by many threads. The file is much
too big to fit in memory. I'll do some caching, but access is mostly
random so there will be a large number of cache misses.

Unfortunately, RandomAccessFile is single threaded. To read data, you
much call seek() and then read(), and this can only be done one thread
at a time.

I see three possible approaches to the problem:
1. Wrap the calls to seek() and read() in a synchronized method. This
will be slow.
2. Have a pool of RandomAccessFile objects all pointing to the same
file. Have each thread grab and release objects from the pool as needed.
The downside here is that many file handles will be required.
3. Do something fancy with NIO and selectors. I haven't looked into this
deep enough to know if it's an option.

What's the best approach?

 

[Karl Uppiano]

What's the best approach for heavily concurrent read access to a file?

I have a file that needs to be read by many threads. The file is much too
big to fit in memory. I'll do some caching, but access is mostly random so
there will be a large number of cache misses.

Unfortunately, RandomAccessFile is single threaded. To read data, you much
call seek() and then read(), and this can only be done one thread at a
time.

I see three possible approaches to the problem:
1. Wrap the calls to seek() and read() in a synchronized method. This will
be slow.
2. Have a pool of RandomAccessFile objects all pointing to the same file.
Have each thread grab and release objects from the pool as needed. The
downside here is that many file handles will be required.
3. Do something fancy with NIO and selectors. I haven't looked into this
deep enough to know if it's an option.

What's the best approach?

I don't know the "best" approach, but NIO is very powerful and scalable. It
is about as close as you can get to overlapped I/O in the OS.

 

[Mark Thornton]

I don't know the "best" approach, but NIO is very powerful and scalable. It
is about as close as you can get to overlapped I/O in the OS.

Unfortunately the implementation of NIO doesn't allow concurrent read
(or write) on a single file channel. See the evaluation and comments on
bug 6371642.

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6371642

Mark Thornton

 

[Karl Uppiano]

Unfortunately the implementation of NIO doesn't allow concurrent read (or
write) on a single file channel. See the evaluation and comments on bug
6371642.

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6371642

Mark Thornton

Bummer.

 

[Furious George]

What's the best approach for heavily concurrent read access to a file?

I have a file that needs to be read by many threads. The file is much
too big to fit in memory. I'll do some caching, but access is mostly
random so there will be a large number of cache misses.

Unfortunately, RandomAccessFile is single threaded. To read data, you
much call seek() and then read(), and this can only be done one thread
at a time.

I see three possible approaches to the problem:
1. Wrap the calls to seek() and read() in a synchronized method. This
will be slow.
2. Have a pool of RandomAccessFile objects all pointing to the same
file. Have each thread grab and release objects from the pool as needed.
The downside here is that many file handles will be required.
3. Do something fancy with NIO and selectors. I haven't looked into this
deep enough to know if it's an option.

How about using a relational database?

 

[Chris Uppal]

What's the best approach for heavily concurrent read access to a file?

I question whether this is something worth aiming for. That's to say, I see no
reason why you shouldn't serialise all access to the file at the Java level.
Unless you know something about the filesystem and disk hardware that I don't,
you aren't really going to have "concurrent" access to the file anyway at the
hardware/OS level.

But, if you do want something closer to genuinely concurrent access, then split
the file up, and put each part onto a different physical disk.

-- chris

 

[Furious George]

I question whether this is something worth aiming for. That's to say, I see no
reason why you shouldn't serialise all access to the file at the Java level.
Unless you know something about the filesystem and disk hardware that I don't,
you aren't really going to have "concurrent" access to the file anyway at the
hardware/OS level.

But, if you do want something closer to genuinely concurrent access, then split
the file up, and put each part onto a different physical disk.

You are a genius. Putting the file on multiple physical disks would
probably be the only way to achieve the OP's desired effect.

However I question (as a humble student to a super genius) the wisdom
of splitting the file up. Since the OP said he is aiming for heavily
concurrent READ access, why not just copy the file. For example, the
OP could put a copy of the file on each physical drive. Then the OP
could create a pool of RandomAccessFile (like the OP's suggestion #2)
but instead of synchronizing on the same file, each RandomAccessFile
would point to a different copy of the same file.

I submit that this would allow for genuine concurrent access.

 

[Chris Uppal]

Since the OP said he is aiming for heavily
concurrent READ access, why not just copy the file.

Good point.

I had missed that part of the OP's requirements, thanks for pointing it out.
Yes, in that case you're right: it would be simpler and better to replicate the
whole file on different disks rather than split it up.

Although -- now I come to think of it -- it might be a good idea as well (at
some cost in complexity) to try to arrange that reads from the same part of the
file were /usually/ satisfied from the same copy. E.g. reads from the first
100MB would mostly come from the copy on drive 1, reads from the next 100MB
would mostly come from the copy on drive 2, and so on. That would allow the OS
and/or disk hardware to make best use of the caching that it will automatically
supply.

-- chris

 

[Patricia Shanahan]

I question whether this is something worth aiming for. That's to say, I see no
reason why you shouldn't serialise all access to the file at the Java level.
Unless you know something about the filesystem and disk hardware that I don't,
you aren't really going to have "concurrent" access to the file anyway at the
hardware/OS level.

But, if you do want something closer to genuinely concurrent access, then split
the file up, and put each part onto a different physical disk.

For random access to a large file, head movement is usually the
bottleneck, not data transfer.

Suppose block A is in an inner track, block B is on an outer track, and
block C halfway between. The block C request has a much reduced head
movement cost if they are done in the order A, C, B rather than A, B, C.

Almost certainly, somewhere in the chain from the operating system
through the physical disk, there is something that does head movement
optimization, but needs a pool of concurrent requests to do any good.

Of course, there are cases in which a single drive just cannot do the
job, even with optimized head movement.

Given that this is read access, any reason there can't be multiple
RandomAccessFile instances? I haven't tried it, so something horrible
might go wrong.

Patricia

 

[Mark Thornton]

Bummer.

Indeed, I was rather disappointed when I found out (that bug submission
is one of mine).

Note that this problem is (as far as I know) specific to Windows. You
may be able to obtain better concurrency on other platforms.


Mark Thornton

 

[Chris]

What's the best approach for heavily concurrent read access to a file?

I question whether this is something worth aiming for. That's to say, I see no
reason why you shouldn't serialise all access to the file at the Java level.
Unless you know something about the filesystem and disk hardware that I don't,
you aren't really going to have "concurrent" access to the file anyway at the
hardware/OS level.

But, if you do want something closer to genuinely concurrent access, then split
the file up, and put each part onto a different physical disk.

That's pretty much what RAID does. If you choose the right RAID level,
then you can have different disks working on requests from different
threads in a truly parallel way, and there's no need to rewrite the app
to handle a split file.

 

[Chris]

However I question (as a humble student to a super genius) the wisdom

of splitting the file up. Since the OP said he is aiming for heavily
concurrent READ access, why not just copy the file. For example, the
OP could put a copy of the file on each physical drive. Then the OP
could create a pool of RandomAccessFile (like the OP's suggestion #2)
but instead of synchronizing on the same file, each RandomAccessFile
would point to a different copy of the same file.

I submit that this would allow for genuine concurrent access.

A reasonable suggestion, but not for this app. I have terabytes of data
to deal with.

 

[Chris]

For random access to a large file, head movement is usually the

> bottleneck, not data transfer.
>
> Suppose block A is in an inner track, block B is on an outer track, and
> block C halfway between. The block C request has a much reduced head
> movement cost if they are done in the order A, C, B rather than A, B, C.
>
> Almost certainly, somewhere in the chain from the operating system
> through the physical disk, there is something that does head movement
> optimization, but needs a pool of concurrent requests to do any good.
>

Precisely -- this is why you want the OS to see all of the outstanding
requests, not just the next one in the queue. It is my understanding (I
could be wrong) that this is one of the advantages of SCSI over ATA.
It's somehow smarter in the way it schedules disk access.

> Given that this is read access, any reason there can't be multiple
> RandomAccessFile instances? I haven't tried it, so something horrible
> might go wrong.

A pool of RandomAccessFiles will work. The trouble, though, is that each
one requires its own file handle, and when you have a large number of
files this can be fatal. File handles are definitely a limited resource.

This is why I was thinking the NIO might be useful. It has something
called selectors which allow you to juggle multiple IO requests at once.
I just don't know much about it, and the articles I've read don't shed
much light.

 

[Patricia Shanahan]

Indeed, I was rather disappointed when I found out (that bug submission
is one of mine).

Note that this problem is (as far as I know) specific to Windows. You
may be able to obtain better concurrency on other platforms.


Mark Thornton

Even if the bug has to be fixed by adding synchronization, would it be
for the whole duration of the read, until the data comes back? Or,
assuming asynchronous I/O capability at the operating system interface
level, could the lock be released once the read has been issued?

If the latter, then NIO read with specified file position might be a
simple solution to this problem. It seems worth trying, anyway.

Patricia

 

[EJP]

That seems to be a severe overstatement. The bug concerns simultaneous
reading and writing while the length of the file is changed. The OP's
topic is about simultaneous reading *only*, and I don't see anything in
the bug report to suggest that that won't work with NIO. I have a large
body of code which suggests the contrary.

 

[EJP]

This is why I was thinking the NIO might be useful. It has something
called selectors which allow you to juggle multiple IO requests at once.
I just don't know much about it, and the articles I've read don't shed
much light.

You're half right. Selectors have nothing to do with it, but I would use
a MappedByteBuffer and slice() it for each thread that wants to access
it. The data isn't copied, the position/limit/capacity are unique to the
buffer instance: exactly what is wanted. especially when dealing with
terabytes. The only issue is releasing the memory if there are > 1 files
to be dealt with.

 

[Chris]

You're half right. Selectors have nothing to do with it, but I would use
a MappedByteBuffer and slice() it for each thread that wants to access
it. The data isn't copied, the position/limit/capacity are unique to the
buffer instance: exactly what is wanted. especially when dealing with
terabytes. The only issue is releasing the memory if there are > 1 files
to be dealt with.

I fooled with MappedByteBuffer some time ago, and discovered that you
couldn't map more than 2 gb. This limitation applied across all files,
not per-file.

I'd really been hoping that the OS would read data off disk on an
as-needed basis, and that I would be able to rely on the OS' caching to
do my caching for me.

Do you know if this limitation has been lifted? I think that last
version I tested was JDK 1.4.2.

 

[Mark Thornton]

That seems to be a severe overstatement. The bug concerns simultaneous
reading and writing while the length of the file is changed. The OP's
topic is about simultaneous reading *only*, and I don't see anything in
the bug report to suggest that that won't work with NIO. I have a large
body of code which suggests the contrary.

You can read with multiple threads, but their activity will be
serialised (only one reading at any time) due to synchronization around
the file position pointer.

Mark Thornton

 

[Mark Thornton]

I fooled with MappedByteBuffer some time ago, and discovered that you
couldn't map more than 2 gb. This limitation applied across all files,
not per-file.

Higher values are possible on 64 bit implementations. For 32 bit
Windows, the limit is often much lower. Another problem is there is no
way to ensure that mapped buffers are released in a timely fashion. The
JAM does not attempt to release unreachable buffers when an attempt to
map a new area fails.

Selectors currently only apply to SocketChannels.

Mark Thornton

 

[Chris Uppal]

A reasonable suggestion, but not for this app. I have terabytes of data
to deal with.

[Caveat: I have only worked on one system in the terabytes range, and I was
only peripherally involved in the design work]

If you have that much data, then I suspect you may be approaching this from the
wrong direction -- the question is not "how can I access it in Java", but "what
must I do in order to access it at all". Questions of what OS to use, and what
programming language to use are /very/ secondary to the physical architecture
that you will need in order to support your intended workload.

(BTW, do you mean that you have terabytes of data that you put in /one/ file ?
Seems very odd if true.)

Depending on what you want to do, it is perfectly plausible that you'd have to
split/replicate the data across hundreds of disks.

Of course, if all you want is a "transaction" rate which is comparable with
disk seek time, then the problem is not all that hard, and you may as well just
hack at it in Java without thinking about design. But, if your target work
rate scales anything like linearly with the quantity data, then you have to
build the entire system around that. (The fact that you are worried about
running out of file handles also suggests that you want to support a
significant work-rate).

Start with how many reads you want per second. That gives you an indication of
how many disks you'll need (forget RAID, that's just a question of how you
package the disks). Consider what kind of data-rate you'll need to sustain the
workload. Scatter-gather is mostly irrelevant here too. If you are designing
an OS, then the ability to merge uncorrelated requests is a useful feature, but
this isn't an OS, and you (the application designer) are in a position to
ensure that requests /are/ correlated.

Once you have settled on how many disks you want, then decide how many physical
machines you need. Say -- for the sake of argument -- that you need to split
this across 10 machines, and 100 disks. /Then/ you can consider what OSs will
provide the performance/reliability/etc your app needs. /Then/ you can think
about what programming language(s) to use.

That's how I see it, anyway. But do remember the opening caveat.

-- chris