Tech Report CS-90-29

Predictive Caching

Mark L. Palmer and Stanley B. Zdonik

November 1990

Abstract:

Prefetching data objects or program pages in advance of their use is a powerful means of improving performance which has proved difficult to realize. Current OODB systems that maintain object caches use policies for fetching and replacing referenced objects approximating those used for virtual memory demand paging. These policies usually assume no knowledge of the future. Object cache managers prefetch objects by using explicit representations of data structure, or employ demand fetching combined with data clustering to effect prefetching. The latter two methods can be awkward to implement and ineffective in systems where encapsulation is present, or where the usage patterns serviced are incompatible.

Recent work at Brown has introduced the notion of a black box, the {\em Estimating Prophet,} which assimilates access patterns of individual users over time and predicts access for each user. The Prophet samples an access sequence on-line and generates predictions which are used to prefetch data. This approach can be supplemental, and is in many instances preferable, to prefetching via data clustering, prefetching based on static representations of structure, and demand paging. We present a cache management model for use with prefetching and the design of a Prophet which learns to predict simple access sequences. We then discuss the potential of this approach.

(complete text in pdf)