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

Figure 4. The readahead windows

Sequentiality

ensures that random reads will be recognized
as the random pattern, while a random read
in between a sequential stream wont inter-
rupt the stream's readahead sequence.

Table 1 shows the common sequentiality criteria.
The most fundamental one among them is the
“consecutive criterion” in the last line, where page
access offsets are incremented one by one. The
legacy readahead algorithm enforces the sequen-
tiality criteria on each and every read request, so
one single seek will immediately shutdown the
readahead windows. Such rigid policy guarantees
high readahead hit ratio. However it was found to
be too conservative to be useful for many important
real life workloads.
Instead of demanding a rigorous sequentiality,
we propose to do readahead for reads that have
good probability to be sequential. In particular,
the following rules are adopted:

2. Assume sequentiality for the asynchronous

readahead triggered by a PG_readahead
page. Even if the page was hit by a true
random read, it indicates two random reads
that are close enough both spatially and
temporally. Hence it may well be a hot ac-
cessed area that deserves to be readahead.

concurrent Streams

The consecutive criterion in table 1 demands both
time and space continuity. However when multiple
threads do sequential reads on the same file in par-
allel, the read requests may appear interleaved in
time but still continuous in their respective access
spaces. Such kind of interleaved pattern used to

1. Check sequentiality only for synchronous

readahead triggered by a missing page. This

Table. 1. Common sequentiality criterions

criterion case

read_size > max_readahead oversize read, common in sendfile() calls

offset == 0 && prev_offset == -1 first read on start of file

offset == prev_offset unaligned consecutive reads

offset == prev_offset + 1 trivial consecutive reads