Replacement in the Background
Next: Performance Evaluation
Up: Hybrid Adaptive Caching
Previous: Selection of Victims
Although our replacement overhead is low,
we also have designed
the system to allow replacement to be done in the background. HAC
always maintains a free frame, which is used to store the incoming
page.
Another frame must be freed before the next fetch, which can be done
while the client waits for the fetch response.
The client maintains usage information for each object to
differentiate between hot and cold objects. It periodically scans
frames in the cache, computes summary usage values for these frames,
and enters this information in the candidate set. The candidate set
maintains the summary usage information of frames that have been
scanned during the last few fetches. When a cache miss occurs, the
client fetches the missing page into a free frame, and frees a new
frame for the next fetch by compacting the least valuable frames from
the candidate set: it copies their hot objects into the current
target frame and evicts their cold objects.
Miguel Castro, Atul Adya, Barbara Liskov, and Andrew Myers
Copyright ©1997 by the Association for Computing Machinery