skip to content

A clause classifier is getting a prediction cache; how do you estimate its hit rate from a day of request logs?

level: middleimportance: should knowfreq 47%

answer

  1. measure before you build
  2. two numbers out of the log
  3. one minus distinct over total
  4. rank the keys, read the falloff
  5. replay in time order at your TTL

basics

~20 s

Count requests and distinct keys in the log: the hit-rate ceiling is one minus distinct over total. Then replay the log in time order against the TTL you intend, because a repeat that arrives after expiry is a fill.

solid answer

~40 s

Take a day of production requests, derive the key you would actually use - the normalised clause-span hash plus the scorer version - and count two things: total requests and distinct keys. `1 - distinct/total` is the ceiling, so 2,000,000 requests over 600,000 distinct spans cannot exceed 70%. Then rank keys by frequency, because the falloff decides what you build: here the top 5,000 spans alone carry 900,000 requests, which is about 45 of those 70 points from a few thousand entries, while the remaining 25 points need 595,000 entries whose repeats are hours apart. Finally replay the log in timestamp order at the TTL you intend - the ceiling assumes an entry survives until its next request, and a real TTL usually does not.

code

pseudocode · 14 lines
pseudocode
lastSeen = empty map
hits = 0
fills = 0

for each request in traceSortedByTime:
    k = hash(normalise(request.clauseText)) + ":" + scorerVersion
    if lastSeen.has(k) and request.time - lastSeen[k] <= ttl:
        hits = hits + 1
    else:
        fills = fills + 1        // first sight, or the entry had expired
    lastSeen[k] = request.time

hitRate = hits / (hits + fills)
ceiling = 1 - countDistinctKeys(trace) / count(trace)

go deeper

for a junior

Know that a hit rate is measured rather than guessed: count how many of yesterday's requests would have repeated a key that was already stored.

for a middle

Be able to compute the ceiling as one minus distinct keys over total requests, and explain why a real TTL lands the measured rate below it.

for a senior

Show the ranking, not just the totals: state how many points the first few thousand keys buy and what chasing the tail costs in entries and memory.

for a principal

Weigh the estimate against what the cache costs to run and to reason about - 45 points from 5,000 entries and 70 points from 600,000 are different systems with different failure surfaces.

## The two numbers that bound everything A prediction cache is worth building only if the same key comes back, and that is measurable from traffic you already have, before any cache code is written. Take a day of production scoring requests and derive for each one the key you would actually use - the hash of the normalised clause span together with the version of the scoring function. Then count: - **total requests** - every call that would have consulted the cache; - **distinct keys** - how many different entries that traffic touches. Each distinct key must be computed once, so the **hit-rate ceiling** is `1 - distinct/total`. For a review workflow handling 2,000,000 clause scorings a day over 600,000 distinct spans the ceiling is 70%: 600,000 requests are unavoidable fills, and at most 1,400,000 can be served from the store. That ceiling holds under two assumptions the real cache will not honour - unlimited capacity, and an entry that survives until its next request. Everything below the ceiling is the gap those assumptions leave. ## The shape of the falloff, not the average The average of 3.3 requests per key hides the only thing that matters. Rank keys by request count and read the cumulative curve; in a template-driven corpus it falls off steeply, close to the straight line on log-log axes that **Zipf's law** describes. | Slice of the key ranking | Distinct keys | Requests | Contribution to the ceiling | |---|---|---|---| | top 5,000 spans | 5,000 | 900,000 | 44.75% | | the remaining tail | 595,000 | 1,100,000 | 25.25% | | all keys | 600,000 | 2,000,000 | 70.00% | Read that as a build decision rather than a statistic: - Nearly **45 points of hit rate come from 5,000 entries** - a cache small enough to be operationally boring. - The **remaining 25 points cost 595,000 entries**, each requested roughly twice, so they pay only if the entry outlives the gap between those two requests. - A proposal to cache everything is therefore a proposal to spend two orders of magnitude more storage for about a third of the benefit. ## Replay the trace; do not assume the ceiling The ceiling ignores time. A key requested at 09:00 and again at 22:00 counts as a repeat in the totals and is a fill in production if its entry expired at 14:00. So walk the same log **in timestamp order** and simulate: a request is a hit when the key was last seen within the TTL you intend, otherwise it is a fill. Sweeping a few candidate TTLs produces a curve of hit rate against freshness, which is the artefact to bring to a design discussion. Two details keep the simulation honest: 1. **Use the real key, version included.** If a release happened inside the window, traffic before and after it belongs to different keys; an estimate that ignores the version reports a hit rate no deployment can reproduce. 2. **Use a representative window.** A working-day peak over-represents bulk re-review jobs, which are the most repetitive traffic there is. A full day, or a week where the workflow has a weekly rhythm, is much harder to flatter. ## What the estimate deliberately leaves out The simulation assumes nothing is removed except by expiry. Capacity, eviction policy and how entries are spread across nodes belong to the caching tier and are sized separately; the point of this exercise is to find out whether the *workload* contains reuse at all. If the ceiling is 8%, no amount of capacity planning makes the cache worth the staleness it introduces. If the ceiling is 70% and 45 points of it live in 5,000 entries, the design almost writes itself. ## Turning a hit rate into a decision A hit rate is half a decision; the other half is what a hit is worth. A hit replaces a feature fetch and a forward pass with one lookup, so the expected saving per request is roughly `hitRate x scoringCost - lookupCost`. Ten per cent against a scorer that costs a millisecond is not worth the staleness; the same ten per cent against a heavy encoder can be decisive. After shipping, measure the same ratio per namespace - hits over hits plus fills - and compare it with the estimate. A large gap almost always means the key that shipped is not the key you measured: an extra field crept into it, or the normalisation differs between the estimator and the serving path.

  • Does a 55 percent hit rate cut the service's end-to-end p99 by about half?
    No. A hit is a key-value lookup of a millisecond or two; a miss still pays the feature fetch and the forward pass. Raising the hit rate pulls the median toward the lookup and leaves the tail roughly where it was, because the tail is made of misses. The deadline still has to be met on the miss path, so a cache never substitutes for a scorer that fits the budget.
  • Which requests would you leave out of the estimate entirely?
    The ones you would not cache. Spans short enough that scoring is already cheaper than a lookup, and any output whose inputs are customer-specific if the proposed key does not carry them. Filtering those before counting keeps the number honest - an estimate over all traffic flatters a cache you would not actually allow to serve that traffic.

saying these in an interview costs you the question

  • Quotes a hit rate without naming the key it was measured on.
  • Assumes the ceiling from distinct keys is reachable at any TTL.
  • Counts distinct documents when the cache keys on clause spans.
  • Treats a steep falloff as proof the long tail is worth caching too.
  • Estimates from a peak hour and extrapolates it across the day.