The Five-minute Rule
20 Years Later
and How Flash Memory Changes the Rules
written much more frequently (because of checkpoints)
than is optimal based on Gray and Putzolu’s formula.
In 1987, Gray and Putzolu speculated 20 years into
the future and anticipated a “five-hour rule” for RAM and
disks. For 1-KB records, prices and specifications typical
in 2007 suggest 20,978 seconds, or just under six hours.
Their prediction was amazingly accurate.
All break-even intervals are different for larger page
sizes (e.g., 64 KB or even 256 KB). Table 3 shows the
break-even intervals, including ones cited above, for a
variety of page sizes and combinations of storage technologies. “$400” stands for a 32-GB NAND flash drive available in the future for $400 rather than for $999 in 2007.
The old five-minute rule for RAM and disk now applies
to page sizes of 64 KB (334 seconds). Five minutes had
been the approximate break-even interval for 1 KB in
198716 and for 8 KB in 1997.17 This trend reflects the different rates of improvement in disk-access latency and
transfer bandwidth.
The five-minute break-even interval also applies to
RAM and the expensive flash memory of 2007 for page
sizes of 64 KB and above (365 seconds for 64 KB and
339 seconds for 256 KB). As the price premium for flash
memory decreases, so does the break-even interval (146
and 136 seconds, respectively).
The two new five-minute rules promised here are
indicated with values in bold italics in table 3. We will
come back to this table and these rules in the discussion
on optimal node sizes for B-tree indexes.
TABLE
3Break-even Intervals (seconds)
RAM-SATA
RAM-fl ash
Flash-SATA
RAM-$400
$400-SATA
20,978
2,513
32,253
1,006
80,553
5,248
876
8,070
351
20,155
1,316
467
2,024
187
5,056
PAGE MOVEMEN T
In addition to I/O to and from RAM, a three-level
memory hierarchy also requires data movement between
flash memory and disk storage. The pure mechanism for
moving pages can be realized in hardware (e.g., by DMA
transfer), or it might require an indirect transfer via RAM.
The former case promises better performance, whereas the
latter design can be realized entirely in software without
novel hardware. On the other hand, hybrid disk manufacturers might have cost-effective hardware implementations already available.
The policy for page movement is governed or derived
from demand-paging and LRU replacement. As already
discussed, replacement policies in both file systems and
database systems may rely on LRU and can be implemented with appropriate data structures in RAM. As with
buffer management in RAM, there may be differences
resulting from prefetch, read-ahead, and write-behind. In
database systems these may be directed by hints from the
query execution layer, whereas file systems must detect
page-access patterns and worthwhile read-ahead actions
without the benefit of such hints.
If flash memory is part of the persistent storage, page
movement between flash memory and disk is similar to
page movement during defragmentation, both in file
systems and in database systems. The most significant
difference is how page movement and current page locations are tracked in these two kinds of systems.
TRACKING PAGE LOCATIONS
The mechanisms for tracking page locations are quite
different in file systems and database systems. In file
systems, pointer pages keep track of data pages or runs of
contiguous data pages. Moving an individual page may
require breaking up a run. It always requires updating and
then writing a pointer page.
In database systems, most data is stored in B-tree
indexes, including clus-
tered (primary, nonredun-
dant) and nonclustered
(secondary, redundant)
indexes on tables, material-
ized views, and database
catalogs. Bitmap indexes,
columnar storage, and
master-detail clustering
can readily and efficiently
be represented in B-trees. 18
Tree structures derived
from B-trees are also used
334
365
513
146
1,281
88
339
135
136
