Feedback Control for Computer Systems

Chapter 13. Case Study: Cache Hit Rate

Maintaining the “hit rate” for a cache by adjusting its size is a perfect application of feedback principles. Caches are ubiquitous and important. Their basic function is familiar and so does not distract from the control architecture, which is our primary concern. This example will allow us to discuss some design decisions that arise in the application of control principles to computer systems.

This example also serves as an interesting “metaphor” for the application of feedback principles to any form of statistical process control. This identification may not be immediately obvious; we will revisit it after identifying the relevant components.

Defining Components

The controlled system is a cache, such as a web or database cache. We will assume that the cache can hold a fixed number n of items—this will be the control or input variable. For the sake of definiteness, we will consider a cache using a “most recently accessed” protocol: if the requested document or object is found in the cache then it is returned to the requestor; if it is not found then the object is fetched from the backing store and added to the cache. If the number of items held in the cache exceeds the maximally allowed number n, then the oldest item is removed from the cache. (The specifics of the caching policy are not important to the design of the feedback loop.)

During operation, we would like to maintain a specific hit rate or success rate of requests—for instance, we may ...