FAST '04 Abstract
Pp. 173-186 of the Proceedings
C-Miner: Mining Block Correlations in Storage
Zhenmin Li, Zhifeng Chen, Sudarshan M. Srinivasan, and Yuanyuan Zhou, University of Illinois at Urbana-Champaign
Block correlations are common semantic patterns in storage systems. These
correlations can be exploited for improving the effectiveness of storage
caching, prefetching, data layout and disk scheduling. Unfortunately,
information about block correlations is not available at the storage system
level. Previous approaches for discovering file correlations in file systems do
not scale well enough to be used for discovering block correlations in storage
systems. In this paper, we propose C-Miner, an algorithm which uses a
data mining technique called frequent sequence mining to discover block
correlations in storage systems. C-Miner runs reasonably fast with
feasible space requirement, indicating that it is a practical tool for
dynamically inferring correlations in a storage system. Moreover, we have also
evaluated the benefits of block correlation-directed prefetching and data layout
through experiments. Our results using real system workloads show that
correlation-directed prefetching and data layout can reduce average I/O response
time by 12-25% compared to the base case, and 7-20% compared to the commonly
used sequential prefetching scheme.
- View the full text of this paper in HTML and
Until March 2005, you will need your USENIX membership identification in order to access the full papers. The Proceedings are published as a collective work, © 2004 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.