The Cache Assignment Problem and Its Application to Database Buffer Management

Copyright [©] (1996) by IEEE. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distrubuted for profit. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

Given N request streams and L &le. N LRU caches, the cache assignment problem asks to which cache each stream should be assigned in order to minimize the overall miss rate. An efficient solution to this problem is provided, based on characterizing each stream using the stack reference model and characterizing the interaction of the streams using a bursty stream model. It is shown that for Bernoulli (purely random) mixing of streams, the optimal cache assignment is to have one cache per stream. But in practice, streams are mixed in a way that is much burstier than can be represented by the Bernoulli model. Therefore a method is presented for superposition of bursty streams. The performance of the methods developed for bursty stream superposition and cache assignment are tested using trace data obtained from the database system DB2. The resulting cache assignment recommendations are then applied to the DB2 system, and considerable performance improvement is found to result.

By: Hanoch Levy (Rutgers Univ.), Ted G. Messinger and Robert J. T. Morris

Published in: IEEE Transactions on Software Engineering, volume 22, (no 11), pages 827-38 in 1996

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .