HP Labs Technical Reports

Disk Shuffling

Ruemmler, Chris; Wilkes, John

HPL-91-156

Keyword(s):

Abstract: Adapting disk layouts to observed, rather than predicted, access patterns can results in faster I/O operations. In particular, a technique called disk shuffling, which moves frequently-accessed data into the center of a disk, can substantially reduce mean seek distances. We report here on extensions to and (partial) validation of earlier work on this approach at the University of Maryland. Starting from disk access traces obtained during normal system use of 4.2BSD-based file systems, we established a repeatable simulation environment across a range of workloads and disk types for comparing different shuffling algorithms. We explored several of these, including how often to make layout changes, how large a unit of data to shuffle, and some mechanisms to exploit sequentiality of reference. Our conclusions: some of the originally identified benefits are real, but sometimes performance is worse rather than better unless access interdependencies are considered. Most of the benefit can be obtained from infrequent (weekly) shuffling. Smaller quanta generally produce better results, at the expense of needing more working storage. pp Overall, the benefits are small to moderate, but are likely to be much larger with file systems that do not do such a good job of initial data placement.

Back to Index