Avoiding State-Space Explosion of Predictive Metadata with SESH

Appeared in Proceedings of the IEEE International Performance, Computing and Communications Conference (IPCCC).

Abstract

With growing storage capacities, the amount of required metadata for tracking 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. Our work utilizes structures similar to prior 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, that 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 GB to less than 150 MB.

Publication date:
December 2009

Authors:
David Essary
Ahmed Amer

Projects:
Prediction and Grouping

Available media

Full paper text: PDF

Bibtex entry

@inproceedings{essary-ipccc09,
  author       = {David Essary and Ahmed Amer},
  title        = {Avoiding State-Space Explosion of Predictive Metadata with {SESH}},
  booktitle    = {Proceedings of the IEEE International Performance,  Computing and Communications Conference (IPCCC)},
  month        = dec,
  year         = {2009},
}