skip to content

Why does a frequency-based removal family keep a small decaying counter per entry rather than an exact access count?

level: seniorimportance: nice to knowfreq 38%

answer

  1. a total never forgets
  2. counter width costs capacity
  3. rises less each time
  4. decays so popularity ages
  5. one pass fools recency, not frequency

basics

~20 s

An exact count is wide and monotone: it never forgets, so an entry popular last week outranks one that is hot now. A small counter that rises sub-linearly and decays with age turns a total into an approximate current rate.

solid answer

~50 s

Ranking by frequency needs a number per entry, and the obvious number is wrong twice. It is wide - a full counter per entry is real memory on a tier of millions of small entries - and it is monotone, so yesterday's favourite accumulates a score a genuinely hot newcomer can never catch. The practical form is a small counter that rises **sub-linearly**, so each further access raises it less than the last and a few bits span the difference between accessed once and accessed constantly, and that **decays** with elapsed time, so the value approximates a recent rate rather than a lifetime total. The pay-off shows under a one-pass job touching every entry once: those entries reach a count of one and are not promoted, while a recency ranking sees them all as freshly wanted.

code

pseudocode · 11 lines
pseudocode
note_access(entry, now):
    elapsed = now - entry.last_examined
    entry.popularity = age_out(entry.popularity, elapsed)
    entry.last_examined = now

    raise_chance = 1.0 / (entry.popularity * rise_damping + 1.0)
    if random_fraction() < raise_chance and entry.popularity < popularity_ceiling:
        entry.popularity = entry.popularity + 1

age_out(popularity, elapsed):
    return largest_of(0, popularity - (elapsed / decay_interval))

go deeper

for a junior

Know the idea rather than the mechanism: a store can rank entries by how often they are used, and a count that never decreases would keep protecting things that were popular long ago.

for a middle

Explain the two properties - an increment that shrinks as the counter grows, and decay over elapsed time - and say what each one buys: a few bits of range, and a rate instead of a total.

for a senior

Bring the one-pass job. Describe how an export or migration makes every entry look freshly wanted to a recency ranking, and what that does to the working set on a tier already at its ceiling.

for a principal

Treat the decay rate as a policy with consequences: too slow and the tier protects yesterday's demand through a traffic shift, too fast and it collapses toward recency. Say how you would observe which is happening.

## Why the obvious counter fails Ranking entries by how often they are wanted requires a per-entry number. Taking that literally - a full-width integer incremented on every access - fails on two axes at once. - **Width.** On a tier holding millions of small entries, several bytes per entry of ranking state is a visible share of the ceiling. Ranking state competes with entries for the same memory, so a counter that is more precise than the decision needs has bought precision with capacity. - **Monotonicity.** A total never decreases. An entry that took a million accesses during a campaign last month outranks everything indefinitely, including the entries being read right now. The store ends up holding a museum of former favourites and removing current working-set entries to protect them. The second failure is the serious one. It is not inaccuracy, it is the wrong quantity: the ranking wants *how wanted is this entry now*, and a total answers *how wanted has this entry ever been*. ## The two properties that fix it 1. **A sub-linear rise.** Each additional access increases the counter by less than the previous one - by making the increment probabilistic, or by stepping through widening bands. A handful of bits then distinguishes an entry touched once from one touched a thousand times, because the counter measures something closer to an order of magnitude than a count. 2. **Decay with elapsed time.** The counter is reduced according to how long the entry has gone untouched, usually computed lazily when the entry is next examined rather than by sweeping the keyspace. Decay is what converts the stored total into an approximate current rate, and it is what allows a former favourite to fall. Together they give a ranking number that is small, that saturates instead of overflowing, and that forgets. ## Why frequency survives a one-pass scan The clearest case where the two ranked families diverge is a job that reads everything exactly once: an export, a migration, a backup-style walk, an analytics crawl over the keyspace. - To a **recency** ranking, every entry the job touched is now maximally recent. The entries the application actually depends on become the oldest things in the store, so the next removals take the real working set and keep entries the job will never look at again. - To a **frequency** ranking, each scanned entry has been seen once. A counter that rises sub-linearly barely moves for a single access, so the scanned entries never climb above the genuinely popular ones, and the working set survives the job. That is the strongest argument for paying for a frequency family at all. It is also not a universal law: some stores blunt the same scan inside their recency ranking instead, by refusing to treat a first touch as a full promotion, and stores that offer no frequency family at all handle the workload some other way or not at all. ## What the frequency family costs in return - **More per-entry state than recency**, both the counter and whatever timestamp the decay is computed against. - **Slower reaction.** A decaying counter deliberately resists sudden change, so when demand genuinely shifts, the store keeps protecting the old popular entries for a while. The decay rate is the tuning of that lag, and there is no universally right value. - **A cold-start disadvantage.** A newly written entry starts near the bottom, so under pressure it can be removed before it has had the chance to demonstrate demand. Designs compensate by starting new entries above the floor, which is another choice that differs between stores. - **It still gets approximated.** A frequency family gives the store a criterion, not a maintained order; the victim is normally still chosen by inspecting a small sample and taking the best candidate in it. ## Where implementations differ - Whether a frequency family exists at all: it is common to find stores in this class that offer only recency, only random, or no configurable family whatsoever. - Counter width, the shape of the rise, and the decay rate are all design or configuration choices, and none of them is a property of in-memory stores in general. - Whether the decay is applied lazily on access or by a background pass changes when the cost lands, not what the ranking means. ## What an interviewer is listening for That you can say why a total is the wrong quantity, name the two properties that repair it, and produce the one-pass job as the concrete workload where frequency and recency give opposite answers - while stopping short of claiming that one family wins in general.

  • Why does a sub-linear rise let a few bits carry a usable ranking?
    Because the decision needs relative magnitude, not an exact tally. If each further access raises the counter by less than the last, the stored value grows roughly with the order of magnitude of demand, so a small range separates accessed once from accessed constantly. A linear counter would spend most of its bits distinguishing numbers the ranking never compares.
  • What is the downside of a decaying frequency ranking when traffic shifts suddenly?
    It lags. The entries that were popular before the shift keep an elevated score until decay erodes it, so the store protects them while removing entries that are hot now. How long that lasts is the decay rate, which is a tuning decision with no universally correct value, and it is why a frequency family is not automatically the better ranking.

saying these in an interview costs you the question

  • Thinks an exact access count is the natural frequency ranking.
  • Believes a wider counter is strictly better.
  • Says decay exists to save memory rather than to age popularity.
  • Claims frequency ranking always beats recency ranking.
  • Forgets a new entry starts with no demonstrated demand.
  • Assumes every in-memory store offers a frequency family.