Tech Report CS-91-15

Fido: A Cache That Learns To Fetch

Mark Palmer and Stanley B. Zdonik

February 1991

Abstract:

Accurately fetching data objects or pages in advance of their use is a powerful means of improving performance, but this capability has been difficult to realize. Current OODBs maintain object caches that employ fetch and replacement policies derived from those used for virtual-memory demand paging. These policies usually assume no knowledge of the future. Object cache managers often employ demand fetching combined with data clustering to effect prefetching, but cluster prefetching can be ineffective when the access patterns serviced are incompatible.

This paper describes FIDO, an experimental {\em predictive cache} that predicts access for individuals during a session by employing an associative memory to assimilate regularities in the access pattern of an individual over time. By dint of continual training, the associative memory adapts to changes in the database and in the user's access pattern, enabling on-line access predictions for prefetching. We discuss two salient components of Fido:

\begin{enumerate} \item MLP, a replacement policy for managing pre-fetched objects. \item Estimating Prophet, an associative memory that recognizes patterns in access sequences adaptively over time and provides on-line predictions used for prefetching. \end{enumerate}

We then present some early simulation thatts which suggest that predictive caching works well, especially for sequential access patterns, and conclude that predictive caching holds great promise.

(complete text in pdf)