What bookkeeping does each removal family - recency, frequency, remaining lifetime, random - charge an in-memory store?
answer
- ranking needs evidence, evidence costs
- recency turns reads into writes
- a raw count never ages
- random maintains nothing at all
basics
~20 sRecency needs per-entry metadata written on every read; frequency needs a counter plus an ageing rule; remaining lifetime needs the deadline the entry already stores; random needs nothing. Each family is priced by what it adds to the read path.
solid answer
~50 sA removal family is not free: each one names state the store must maintain so it has something to rank by. Ranking by **recency** means every read becomes a write of metadata, which costs memory per entry and, where the server is multi-threaded, a point of contention on the hottest path there is. Ranking by **frequency** costs a counter per entry plus a rule that ages it, otherwise the count is a lifetime total rather than a rate. Ranking by **remaining lifetime** is nearly free when the entry already stores a deadline, but it can only compare entries that carry one. **Random removal** maintains nothing at all: pick a resident entry and take it. That is why random is not absurd — it degrades gracefully, never pathologically, and under access with no locality it gives up much less than it looks like it should.
go deeper
Know that a store choosing what to drop needs some evidence about each entry, and that keeping evidence costs memory and time on every access, not only at the moment something is removed.
Be able to price all four families: what each maintains, when it is paid, and why random maintaining nothing makes it the cheapest rather than the silliest. Say that a frequency count must age.
Point at the read path. Explain that recency makes reads write metadata, what that does on a multi-threaded server, and why stores that ship a ranked family still refuse to maintain an exact order over it.
Treat bookkeeping as budget. Per-entry ranking state competes with entries for the same ceiling, so argue when a cheaper family that keeps more entries resident beats a better ranking over fewer.
## The families are priced, not free Every removal family is a promise to rank entries, and a ranking needs evidence. The evidence has to be produced somewhere, and the only place it can be produced is the access path — which is the busiest code in the store. So the honest way to compare the families is not *which removes the better entry*, but *what each one charges on every access, whether or not a removal ever happens*. | family | what it maintains | paid on | its weakness | |---|---|---|---| | recency | per-entry position or timestamp of last touch | every read and write | one pass over everything looks like fresh interest | | frequency | per-entry counter plus an ageing rule | every read and write | slow to react; a raw count pins old favourites | | remaining lifetime | the deadline the entry already carries | nothing extra | compares only entries that carry a lifetime | | random | nothing | nothing | no ranking at all; may take a hot entry | ## Recency: the read stops being a read To know which entry has gone untouched longest, the store has to record that a touch happened. That is a write on the read path. It costs bytes per entry, it dirties memory that would otherwise be read-only, and on stores where the server handles requests on more than one thread it creates a structure that concurrent readers must coordinate on. The deeper consequence is a behavioural one: **anything that touches every entry once looks, to a recency ranking, like interest in everything**. A one-pass job over the keyspace can therefore make the genuinely hot entries the oldest thing in the store. ## Frequency: a counter is not enough by itself A count per entry is more per-entry memory than a recency marker, and it only means something if it ages. An exact lifetime total is monotone: an entry that was hammered last week outranks a newcomer that is hot right now, forever. So a frequency family in practice keeps a small counter that rises sub-linearly and decays with elapsed time, which is what turns a total into an approximate rate. That ageing rule is bookkeeping too — it has to be applied somewhere, usually lazily on access. ## Remaining lifetime: cheap, and narrow If the store already keeps a deadline for entries that have one, ranking by which deadline is nearest costs no extra per-access work at all. The catch is scope, not cost: - Only entries carrying a lifetime can be compared, so the family is inseparable from the eligibility question of what happens to entries that carry none. - The ranking answers *which entry was going to leave soonest anyway*, which is a statement about the writer's intent rather than about demand. An entry with a long deadline and no traffic outranks a short-deadline entry being read constantly. - Exact ordering by deadline would need a structure kept in deadline order, so stores that offer this family typically approximate it the same way they approximate the others. ## Random: nothing maintained, and not absurd Random removal keeps no state, adds no bytes per entry, adds nothing to the read path and selects a victim in constant time. It is the floor of the price list. It is also a genuinely defensible posture in three situations: 1. **Access with no locality.** If every entry is about equally likely to be wanted next, no ranking has information to exploit, and the ranked families spend their bookkeeping for nothing. 2. **Extremely tight budgets.** When per-entry overhead is the problem you are solving, spending bytes per entry to choose a slightly better victim can cost more entries than it saves. 3. **Adversarial or unknown workloads.** Random has no worst case that an access pattern can steer it into; the ranked families do. Its weakness is equally plain: it can take the hottest entry in the store, and it will occasionally do so. ## What varies between stores - Which families exist at all: some stores offer several and a way to choose; some implement exactly one and expose no choice; some offer removal only over entries that carry a lifetime. - Whether the ranking is computed exactly or from a sample — almost every store that offers a ranked family declines to pay for exact order. - What the candidate set is: a store that allocates from fixed-size blocks looks for a victim among the entries in the block size it needs, so its ranking is local rather than global. A good answer prices the families and then says that the posture in front of you is a configured choice with a store-specific default, not a property of in-memory stores in general.
- Why does ranking by remaining lifetime cost almost nothing to maintain?Because the evidence already exists: a store that supports deadlines is keeping one per entry regardless, so the ranking reads state it did not have to add. The cost shows up as scope instead — only entries carrying a lifetime can be compared, and the ranking reflects the writer's stated intent rather than any observed demand.
- When is random removal a reasonable posture rather than a last resort?When access has little locality, so no ranking has information to exploit; when per-entry overhead is the binding constraint and ranking state would cost you resident entries; and when the workload is unknown or hostile, since random has no pattern an access sequence can steer into a worst case.
saying these in an interview costs you the question
- Calls random removal indefensible under any workload.
- Thinks recency costs nothing because it only reorders on eviction.
- Treats an exact access count as a usable frequency ranking.
- Assumes every store offers a choice of removal family.
- Ranks by remaining lifetime without noticing it excludes permanent entries.