Analysis of superposition of streams into a cache buffer

Abstract

We consider the superposition of address streams into a cache buffer which is managed according to a Least Recently Used (LRU) replacement policy. Each of the streams is characterized by a stack depth distribution, i.e., the cache hit ratio as a function of the cache size, if that individual stream were applied to a LRU cache. We seek the cache hit ratio for each stream, when the combined stream is applied to a shared LRU cache. This problem arises in a number of branches of computer science, particularly in database systems and processor architecture. We provide two techniques to solve this problem and demonstrate their effectiveness using database I/O request streams. The first technique is extremely simple and relies on an assumption that the buffer is "well-mixed". The second technique relaxes this assumption and provides more accurate results. We evaluate the performance of the two techniques on realistic data, both in a lab environment and a large database installation. We find that the first simple technique provides accuracy which is sufficient for most practical purposes. By investigating sources of error and trying various improvements in the model we obtain some insight into the nature of database I/O request streams.