Space-Efficient Predictive Block Management

Appeared in Proceedings of the International Workshop on Software Support for Portable Storage (IWSSPS'09), Grenoble, France.


With growing storage capacities, the amount of required metadata for tracking predictive information for all blocks in a system becomes a daunting task. On mobile systems, the problem is compounded by a need to make the best use of available resources. Our previous work demonstrated a system software effort in the area of predictive data grouping for reducing power and latency on storage systems. Such efforts can reduce both power consumption and strain on underlying system hardware, while improving performance. Prior work utilizes structures similar to efforts in prefetching and predictive caching, keeping a fixed number of immediate successors per block. While providing powerful predictive capabilities and being more space efficient in the required metadata than previous strategies, there remains a growing concern of how much data is actually required. We present a novel method of storing equivalent information, SESH, a Space Efficient Storage of Heredity, which is resistant to state-space explosion of predictive metadata, utilizing block-level predictability to reduce the overall metadata storage by up to 99% without loss of information. As a result, we are able to provide a predictive tool that is adaptive, accurate, and robust in the face of workload noise, for a tiny fraction of the metadata cost previously anticipated; in some cases, reducing the required size from 12 gigabytes to less than 150 megabytes.

Publication date:
October 2009

David Essary
Ahmed Amer

Prediction and Grouping

Bibtex entry

  author       = {David Essary and Ahmed Amer},
  title        = {Space-Efficient Predictive Block Management},
  booktitle = {Proceedings of the International Workshop on Software Support for
Portable Storage (IWSSPS'09), Grenoble, France},
  month        = oct,
  year         = {2009},
Last modified 2 Nov 2009