Identifying Stable File Access Patterns
Proceedings of the Twenty-first Symposium on Mass Storage Systems (MSS)
Introduction
Disk access times have not kept pace with the evolution of disk capacities, CPU speeds and main memory sizes. They have only improved by a factor of 3 to 4 in the last 25 years whereas other system components have almost doubled their performance every other year. As a result, disk latency has an increasingly negative impact on the overall performance of many computer applications.
Two main techniques can be used to mitigate this problem, namely caching and prefetching. Caching keeps in memory the data that are the most likely to be used again while prefetching attempts to bring data in memory before they are needed. Both techniques are widely implemented at the data block level. More recent work has focused on caching and prefetching entire files.
There are two ways to implement file prefetching. Predictive prefetching attempts to predict which files are likely to be accessed next in order to read them before they are needed. While being conceptually simple, the approach has two important shortcomings. First, the prefetching workload will get in the way of the regular disk workload. Second, it is difficult to predict file accesses sufficiently ahead of time to ensure that the predicted files can be brought into main memory before they are needed.
A more promising alternative is to group together on the disk drive files that are often accessed at the same time. This technique is known as implicit prefetching and suffers none of the shortcomings of predictive prefetching because each cluster of files can now be brought into main memory in a single I/O operation. The sole drawback of this new approach is the need to identify stable file access patterns in order to build long-lived clusters of related files.
We present here a new file predictor that identifies stable access patterns and can predict between 50 and 70 percent of next file accesses over a period of one year. Our First Stable Successor keeps track of the successor of each individual file. Once it has detected m successive accesses to file Y, each immediately following an access to file X, it predicts that file Y will always be the successor of file X and never alters this prediction.