1
$\begingroup$

In a web application, I use a map as a simple in-memory cache/lookup.

  • A key is a string, say A and maps to an integer value, say 50.
  • The app handles thousands of requests per minute. Requests need to look up keys.
  • If the key isn't found in the map, then the value is computed and stored under they key as map[A]=50
  • Next time a request comes in for the key A, the cache returns map[A], which is 50.

I'd like to keep track of the hit ratio of cache lookups. If the hit ratio is close to $0$, then the cache doesn't work, almost no items are found. If the hit ratio is close to $1$, we're happy, most lookups of keys are cached and avoid expensive computation.

I tried several approaches, with mixed results:

(1) Once the app starts, we initialize two counters hit=0 and total=0 and just count up: total always, hit if a key was found. If the app runs with high cache hit ratio for a long time (say, days) it takes very long to reflect a prolonged 100% cache miss rate.

(2) Initialize the counters as above, but every $t$ minutes, we

  • calculate there the ratio hit/total and log it.
  • reset hit and total to $0$ again.

This kind of works, but if the amount of cache lookups is irregular in the time frame (for example for a few minutes no lookup at all) then for that interval the rate can be $0$ or if there's one successful lookup then the hit rate will be $1$. Also results can be skewed, see (3).

(3) Keep a ring buffer with $n$ entries, each entry is a cache lookup that's either $1$ or $0$. It's a sample of the latest $n$ lookups and doesn't depend on time. But the sample can be skewed, say we have $1000$ entries in the ring buffer and the same key is requested $1000$ times and is never found (for example due to a software bug), then if another $1000$ lookups happen for a different key and they succeed, they overwrite all the previous data, skewing the result.


These are techniques I could come up with - but are there any standardized approaches for this? Some data structures or sampling algorithms that could accommodate for skewness but still provide a valid approximation of the true underlying lookup rate?

I'm not very well versed in this field and would be glad for any pointers/additional literature I should review.

$\endgroup$

1 Answer 1

1
$\begingroup$

What you're looking for is not so much a data structure as a problem statement. What is it that you're trying to learn from a metric such as a hit-count? The structures need to match what you're doing with the data.

From the sound of it, the data you wish to work with is a time history of hit ratios. You want to be able to look at a window and say "these time ranges went bad. Go look at what was happening then."

A common solution is to start from (2) and manipulate the data. Capture all activity within some short time period, and then log the result. Then manipulate the data to show you what you want to see. For example:

  • Keep a FIFO of these log datas (rather than individual hits), and output the hit ratio for the entire FIFO buffer (a longer period).
  • Keep a weighted average of the last score and the most recent score. This works like a FIFO except it weights the more recent entries heavier, and only requires O(1) space, rather than the O(n) where N is the length of the FIFO.
  • Output more than one number, or create a combined metric. Maybe you need to output both hit-ratio and total hits to identify when the total count was too low for the hit-ratio to be meaningful. Or maybe you scale the hit-count towards 1 when the ratio is low because you intend to ignore those times.
  • Determine what you really want to know about your cache and apply statistics. If you actually know what you want to learn from the metric, you may be able to apply Bayesian analysis to correctly weight the data where total-count is low.
  • If you're worried about high-volume times where you need to respond quickly, you might even be able to skip the hit/total counters and do the Bayesian analysis on the individual cache hits and cache misses.
$\endgroup$
1
  • $\begingroup$ Thanks for the ideas where to go from here, you are right, need to have a closer look which insights we actually want to gain. Two questions: 1) Do you have some example for the Bayesian approach? I learned briefly about Bayesian statistics in the past, but only a bit. 2) One idea I had is to sample requests regularly based on a random variable, non-uniformly distributed, maybe sth like a Gamma distribution can make sense? Thanks again for the discussion. $\endgroup$
    – BMBM
    Commented Feb 24 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.