Exploiting Disk Layout and Block Access History for I/O Prefetch - Advanced Operating Systems and Kernel Applications - page 206

to represent disk layout sufficiently well. This is
because disk manufacturers usually attempt to
carefully map logical blocks to physical blocks
with minimal disk head positioning cost, so that
accessing blocks with consecutive LBNs has per-
formance close to that of accessing blocks physi-
cally contiguous on disk (Schlosser, Schindler,
Papadomanolakis, Shao, Ailamaki, Faloutsos, &
Ganger, 2005). Such a standard logic interface is
used by operating systems and upper-level com-
ponents to access disk data, thus it is available and
portable across various computing platforms. In
practice, we find that using this logical disk layout
is sufficient to exploit disk-side information in
prefetch policies.
In DiskSeen, the LBNs are used to track the
access times of recently accessed disk blocks for
analyzing the associations of access times among
adjacent blocks. In other words, we use LBNs as
abstraction of physical disk blocks and analyze
the access pattern of blocks.

Figure 2, the block table has three levels, Block
Global Directory (BGD), Block Middle Direc-
tory (BMD), and Block Table Entry (BTE). Each
level consists of multiple 4KB pages, each of
which is further divided into multiple entries. A
block's LBN is correspondingly broken into three
segments, each of which is used as an offset to
locate an entry in the page of the corresponding
level. The BTE entries in the block table are used
to maintain data access information (e.g. block
access times). Different from BTE entries, BGD
and BMD entries also maintain a pointer field,
which is the address of a memory page in the next
level. In this way, the block table is organized
as a tree structure with three levels. For a given
LBN, at most three memory accesses are needed
to reach the BTE entry. As an example shown in
Figure 2, suppose one page can hold 512 entries,
the access times of a block with LBN 2,631,710
(10 × 512 2 + 20 × 512 + 30) can be efficiently
reached via BGD entry (10), BMD entry (20),
and BTE entry (30).
In DiskSeen, block access times are needed
to identify the relationship between data blocks.
However, knowing the physical wall clock time
is unnecessary. Instead, we use the logic block
access time. Suppose the entire sequence of ac-
cessed disk blocks is referred to as a block access
stream . The n th block in the stream has access index
n . We maintain a global access counter, which
is incremented with each block reference. Upon
a data access, the value of the access counter is
read as the access index for the accessed block.
The access index is recorded in the corresponding
BTE entry to represent its logic access time. In
our prototype, each BTE entry can record up to
four access indices as its access history.
As time elapses, the block table may grow and
occupy an excessively large amount of memory
space, thus we need to remove the out-of-date
history information to reduce spatial overhead. To
facilitate an efficient removal of old BTEs, each
directory entry (BGD and BMD entry) records
the largest access index of all of the blocks under

the block table

In order to analyze workload access pattern, the ac-
cess history of all data blocks in the storage space,
which is often as large as multiple Terabytes, has
to be maintained. It is challenging to efficiently
manage such a huge amount of information with
low overhead. First, the data structure holding
this information must support efficient access of
block entries and their neighboring blocks via
LBNs. Second, addition, removal, and lookup
of block entries must be efficient to avoid high
runtime overhead. Finally, maintaining the history
information should require low memory space.
In DiskSeen, we use a data structure called block
table to achieve these requirements.
The block table is inspired by the multi-level
page table used for a process's memory address
translation, which is widely used in nearly all
operating systems. Different from the page table,
the block table is used to manage the storage
space, instead of memory space. As shown in