An Analytical Approach to File Prefetching

Summary by Michael Stok

Prefetching data from a filesystem in anticipation of requests from user processes has been used as a technique for improving filesystem performance for some time now. Different environments offer various patterns of behavior that can be exploited by more sophisticated strategies.

This presentation described some of the features of a prefetching technique that has been developed in a UNIX environment and that prefetches entire files in groups that are determined by the system as it's used.

By recognizing patterns in file usage one can build a forest of access trees in memory and use it to see if a process (and the processes it might spawn) is close enough to a known pattern to make the other files in the access tree candidates for prefetching. As the system is used, it removes old access trees from memory or replaces those whose characteristics are changing.

Because each access tree can cover many files, both program and data, which make up a context, it is possible to generate large sets of files as prefetch candidates. This allows more chances for use of idle time to make larger prefetches than with some of the common block prefetch strategies.

The dynamics of access tree generation and replacement were one of the areas covered in the questions after the presentation.

The description of how the system generates access trees and how it recognizes whether a process or group of processes conforms to a known tree is discussed in detail in the paper published in the proceedings. The paper also discusses how the effectiveness of the strategy is affected by the speed of the network and presents results that indicate the stability and performance of the technique in a typical UNIX environment.

Originally published in ;login: Vol. 22, No.2, April 1997.