Predicting file system actions from prior events

Abstract

We have adapted a multi-order context modeling technique used in the data compression method Prediction by Partial Match (PPM) to track sequences of file access events. From this model, we are able to determine file system accesses that have a high probability of occurring as the next event. By prefetching the data for these events, we have transformed an LRU cache into a predictive cache that in our simulations averages 15% more cache hits than LRU. In fact, on average our fourmegabyte predictive cache has a higher cache hit rate than a 90 megabyte LRU cache. 1 Introduction With the rapid increase of processor speeds, file system latency is a critical issue in computer system performance [14]. Standard Least Recently Used (LRU) based caching techniques offer some assistance, but by ignoring any relationships that exist between file system events, they fail to make full use of the available information. We will show that many of the events in a file system are closely related. For exa...