Sequential File Prefetching in Linux - Advanced Operating Systems and Kernel Applications - page 223

However, with the rapid evolvement of com-
puter hardware, we are now facing new constraints
and demands. The bandwidth and capacity of
memory and disk both improved greatly, while the
disk access times remain slow and become more
and more an I/O bottleneck. As a consequence,
the benefit of readahead hits goes up. It not only
adds importance to prefetching, but also favors
aggressive prefetching.
The cost of prefetching misses has been much
lowered, reducing the performance relevance of
prefetching hit ratio. There are two major costs of
prefetching miss: Firstly, wasted memory cache.
When more memory is taken by prefetching, less
is available for caching. This may lower the cache
hit ratio and increase number of I/O. However, in
the context of memory abundance, the impact of
cache size on cache hit ratio should be limited.
Secondly, wasted disk bandwidth. It is relatively
easy to estimate the impact of prefetching misses
on I/O bandwidth. For an I/O intensive applica-
tion, if a page being asynchronously prefetched
is accessed later, it typically means one less I/O
operation, assume that the saved disk seek time is
5ms; on the other hand, a prefetching miss page
costs about 4KB/80MBps=0.05ms extra disk
transfer time. From these two numbers alone, we
could say that a prefetching hit ratio larger than
1% would be beneficial if not optimal.
So it deserves to use more aggressive prefetch-
ing polices. It can improve overall I/O performance
even when sacrificing the hit ratio. The prefetching
hit ratio of a workload depends on its accuracy of
pattern recognition and pattern run length estima-
tion. For sequential workloads, loosing the pattern
recognition accuracy means that the strict page-
after-page pattern matching for read requests is no
longer necessary, which will allow the detection
of more interleaved and semi-sequential patterns;
loosing the run length estimation accuracy means
larger prefetching size.
It is argued in (Papathanasiou and Scott, 2005)
that more aggressive prefetching policies be em-
ployed to take advantage of new hardware and

fulfill increasing I/O demands. Our experiences
are backing it: there are risks of regression in
extending the sequential detection logic to cover
more semi-sequential access patterns, however
we received no single negative feedback since
the wide deployment of the new policies in Li-
nux 2.6.23. It's all about performance gains in
practice, including the tricky retry based AIO
reads(Bhattacharya, Tran, Sullivan, and Mason,
2004) and locally disordered NFS reads(Ellard,
Ledlie, Malkani, and Seltzer, 2003; Ellard and
Seltzer, 2003), which will be discussed in this
chapter.

readahead in linux

Linux 2.6 does autonomous file level prefetching
in two ways: read-around for memory mapped
file accesses, and read-ahead for general buffered
reads. The read-around logic is mainly designed
for executables and libraries, which are perhaps the
most prevalent mmap file users. They typically do
a lot of random reads that exhibit strong locality
of reference. So a simple read-around policy is
employed for mmap files: on every mmap cache
miss, try to pre-fault some more pages around the
faulting page. This policy also does a reasonable
good job for sequential accesses in either forward
or backward directions.
The readahead logic for buffered reads, includ-
ing read(), pread(), readv(), sendfile(), aio_read()
and the Linux specific splice() system calls, is
designed to be a general purpose one and hence
is more comprehensive. It watches those read
requests and tries to discover predictable patterns
in them, so that it can prefetch data in a more I/O
efficient way. Due to the highly diversity of access
patterns and wide range of system dynamics, it
has been hard to get right, and only the sequential
access patterns are supported for now.
The read-around and read-ahead algorithms are
either dumb or heuristic, in various cases these in-
kernel logics can be aided with some kind of user/