Skip to content

CONCEPT Cited by 1 source

Time-aware LRU cache eviction

Definition

Time-aware LRU is LRU plus a per-entry TTL. Entries are evicted either when the cache is full (standard LRU) or when their expiration timer fires, whichever comes first. (Source: sources/2025-07-08-planetscale-caching.)

We can augment the LRU algorithm in a number of ways to be time-sensitive. How precisely we do this depends on our use case, but it often involves using LRU plus giving each element in the cache a timer. When time is up, we evict the element!

— sources/2025-07-08-planetscale-caching

Why add a timer to LRU

LRU alone only evicts on demand (new-entry needs a slot). A low-traffic entry can stale-sit in cache indefinitely if it's been touched once. A time-aware policy encodes an explicit "we know this is cold after N" signal rather than hoping it gets evicted organically.

Ben Dicken's worked examples (Source: sources/2025-07-08-planetscale-caching):

  • Social network — "automatically evicting posts from the cache after 48 hours." Recency bias says most traffic on a post is front-loaded; after 48h the hit probability collapses.
  • Weather app — "automatically evicting previous-days weather info from the cache when the clock turns to a new day." Yesterday's forecast is almost always stale / wrong.
  • Email app — "removing the email from the cache after a week, as it's unlikely to be read again after that." Inbox access has a short reaccess window.

We can leverage our user's viewing patterns to put automatic expirations on the elements.

Two orthogonal eviction triggers

Trigger Basis When it fires
LRU eviction Access order When cache is full and a new entry is inserted
TTL expiry Wall-clock age When now() > insert_time + ttl, regardless of access recency

In production, either trigger can remove an entry:

  • A popular but TTL'd entry — e.g., a short-TTL session token that's hit every request — will be evicted on its timer even though it's MRU.
  • An unpopular but long-TTL entry — e.g., a rarely-accessed user record — can still be evicted under memory pressure before its TTL fires.

Relationship to cache-aside TTL

Most production TTL usage is actually time-aware cache-aside rather than time-aware LRU:

  • Set-on-miss, TTL-to-auto-expire, no explicit eviction.
  • Memory pressure bounded by TTL budget + working-set size.

Strict time-aware LRU couples both mechanisms — works well for bounded-memory in-process caches (Guava, Caffeine, Redis maxmemory-policy).

TTL is workload-specific

The Dicken examples highlight that the right TTL depends on the actual reaccess distribution:

  • 48 hours for social posts.
  • 1 day for weather.
  • 1 week for email.

There is no universal TTL; measuring the reaccess decay curve for the specific workload and picking a TTL at the knee of the curve is the canonical procedure.

Sibling refinement: age-based TTL ladder

Some workloads have gradients rather than cliffs. A time- series dashboard (Netflix Druid interval cache, sources/2026-04-06-netflix-stop-answering-the-same-question-twice-interval-aware-caching-for-druid) uses age-based exponential TTL — short TTL for recent buckets (which might still change), long TTL for old buckets (which are late-arrival-safe). This is a generalisation of time-aware LRU where the TTL itself depends on the age of the underlying data, not just the age of the cache entry.

Known failure modes

  • Cache-miss spike at TTL expiry — if many entries were inserted at the same time and all expire at once, the backing store sees a synchronised miss storm. Mitigated by TTL jitter (each entry gets ttl ± random(jitter)) — see concepts/ttl-based-deletion-with-jitter.
  • Staleness under long TTLs — the cache TTL staleness dilemma — long TTL is a correctness risk for mutable data.
  • Clock-skew / wall-clock-dependence — TTL triggers depend on the cache node's clock being accurate; clock drift can make entries live much longer or shorter than intended.

Seen in

Last updated · 319 distilled / 1,201 read