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

Figure 2. Prefetching helps achieve I/O asynchrony and parallelism

Linux VFS (Virtual File System) mount options
noatime and relatime for eliminating undesirable
writes triggered by mtime updates.
Sequentiality . Sequential accesses enable se-
quential prefetching and maximize disk utilization.
For concurrent sequential accesses, prefetching
plays an essential role in aggregating interleaved
tiny I/Os into larger ones. For non-sequential
accesses, it still benefits to minimize seek and
rotational delays by employing techniques such as
smart disk layout management, informed prefetch-
ing, I/O queuing and scheduling. To name a few
real world examples: the deadline, anticipatory and
CFQ (Complete Fairness Queuing) I/O elevators
in Linux; the TCQ (Tagged Command Queuing)
for SCSI disks and NCQ (Native Command Queu-
ing) for SATA disks; the delayed allocation and
pre-allocation features of ext4/xfs; the writeback
clustering in xfs; etc.
Asynchrony . Asynchronous accesses improve
I/O computing efficiency by pipelining processor
and disk activities, and hiding I/O latencies to the
application. AIO, non-blocking I/O, writeback
and readahead are common facilities for asyn-
chronous I/O.
Parallelism . Disk arrays have been a standard
practice for aggregating multiple disks' capacity as
well as bandwidth. Beyond the traditional RAID
layer, the emerging file systems exemplified by
zfs and btrfs target to manage large pool of disks
on their own. For large scale cloud computing and

high performance computing, large pools of stor-
age servers can be organized with the Google file
system, Lustre, pNFS or other cluster file systems.
On the other hand, device level parallelism are
being employed inside SSD. For example, Intel (R)
pioneered 10 parallel NAND flash channels in its
SATA solid-state drives to deliver up to 250MB/s
read bandwidth and 35,000 IOPS. Concurrent I/O
requesting and parallel data transfer are the keys
to I/O throughput of the above parallel systems.
Aggressive prefetching plays a vital role in this
arena: they typically need large and asynchronous
prefetching I/O to fill the parallel data channels.
It is obvious that prefetching plays an important
role in each of the four I/O optimization strate-
gies. Prefetching brings benefits to applications,
storage devices and storage pools, and even
processing resources(Shriver, Small, and Smith,
1999). Applications can run smoother and faster
by masking the low level I/O delays. Disks can
be better utilized by large I/O size. Storage pools
can be better parallelized. The larger I/O unit
also helps amortize processing overheads in the
whole I/O path.

basic approaches to prefetching

Prefetching algorithms can be either heuristic or
informed. The heuristic algorithms try to predict
I/O blocks to be accessed in the near future
based on the past ones. The most successful one