Filtering effects in cache hierarchies
A friend of mine was building a multi-tiered application with a cache fronting a database and was investigating why his database memory hit ratio was not as high as he expected it to be and how to optimize it. This matters only when you are paranoid about latency percentiles at TP99 or TP99.9s. One of the things, he found after a deeper investigation is what he called as “cherry picking” done by the caching tier that the next level did not see requests with high cache locality. A similar observation was made in Web cache research and was referred to filtering effects.
One of the important works done in this area is by Carey Williamson on “On Filter Effects in Web cache hierarchies”. This paper uses trace driven simulation to look into effects of what happens to workload locality when it travels through various cache hierarchies. Important results to call out:
– Proxy caches filter out the most popular documents from a workload. The filtering effect typically changes the Zipf-like document popularity profile of the input stream into a two-part piecewise-linear document popularity profile for the output stream. The upper leftmost part of the plot is significantly flattened.
– The percentage of unique documents referenced and the percentage of onetimer documents tend to increase as the request stream passes through a cache.
– Among the caches in a caching hierarchy, the first-level cache has the most pronounced filtering effect on the workload.
Even though this is a 10 year old work, highly recommended read for folks trying to understand the effects on caching on their systems.