Invalidation & Eviction

"There are only two hard things in Computer Science: cache invalidation and naming things." — Phil Karlton¹

Filling a cache is easy. The hard part is knowing when a copy stopped being true. The database changes; the copy in Redis, in twenty JVMs, in a CDN and in a million browsers does not know it. Every caching design is, at its core, an answer to two questions:

1. How stale may each piece of data be? (the staleness budget)
2. How does a change in the source reach every copy within that budget? (the invalidation mechanism)

And because memory is finite, a third question follows: when the cache is full, what do we throw away? (the eviction policy). This page covers the three.

The staleness budget

Before choosing a mechanism, decide — with the product team, not alone — how wrong each kind of data may be, and for how long. The answer is different for every entity.

Writing this table is half of the design: once each row has a budget, the mechanism follows.

TTL: the safety net

A TTL (time to live) makes every entry expire after a fixed time. It is the simplest mechanism and the one you should always have, even when you also invalidate explicitly — because explicit invalidation will eventually miss something (a bug, a manual SQL fix, a crashed process between the commit and the delete), and the TTL bounds how long the error lives.

Choosing the TTL is a trade-off between freshness and hit ratio:

• Too long: stale data lives long after a change.
• Too short: the long tail of keys always misses (a key read once every 10 minutes never hits with a 60 s TTL), and hot keys expire often, which risks a stampede.

Practical rules:

• Start from the staleness budget: TTL ≤ budget when there is no explicit invalidation; TTL = a few × budget when there is (the TTL then only bounds the damage of a missed invalidation).
• Add jitter — TTL = base ± 10% — so that keys written together do not expire together (cache avalanche).
• Absolute vs. sliding expiration: an absolute TTL expires a fixed time after the write; a sliding one is extended on every read (GETEX key EX 300 in Redis). Sliding expiration keeps hot keys forever — good for sessions, dangerous for data that changes, since a hot stale key may never be refreshed.

Explicit invalidation

To get freshness better than the TTL, the code that writes to the database also tells the cache that the value changed. Two decisions matter: delete or update, and in which order.

Delete, don't update

When the event changes, the writer can either update the cache with the new value or delete the key and let the next read fill it. Deleting is safer. Consider two organizers editing event 42 at the same time:

sequenceDiagram
    participant W1 as Writer 1
    participant W2 as Writer 2
    participant D as PostgreSQL
    participant R as Redis
    W1->>D: UPDATE price = 100
    W2->>D: UPDATE price = 120
    W2->>R: SET event:42 price 120
    W1->>R: SET event:42 price 100
    Note over D,R: DB says 120, cache says 100 until the TTL expires

The writes reached the database in one order and the cache in the other. With delete, both writers send DEL event:42: the operations are idempotent and their order does not matter; the next reader loads 120 from the database. Updating the cache is also wasteful when the value is written more often than it is read.

Write first, then delete

The cache-aside race

Even "write DB, then delete after commit" leaves one race. It needs a slow reader:

sequenceDiagram
    participant Rd as Reader
    participant R as Redis
    participant D as PostgreSQL
    participant W as Writer
    Rd->>R: GET event:42
    R-->>Rd: miss
    Rd->>D: SELECT event 42
    D-->>Rd: old row v1
    Note over Rd: reader pauses (GC, slow network)
    W->>D: UPDATE event 42 to v2 and COMMIT
    W->>R: DEL event:42
    Rd->>R: SET event:42 v1
    Note over R: stale v1 stays until the TTL expires

The reader read before the write and stored after the delete. It is rare — the reader must be slower than a whole write plus a delete — but at tens of thousands of reads per second, rare things happen every day. The fixes, from simplest to most robust:

1. A TTL as safety net — bounds the damage. For most data, this is enough.
2. Delayed double delete — the writer deletes, and deletes again a short time later (e.g. 500 ms, longer than a typical read). The second delete removes what a slow reader put back. Cheap, but probabilistic.
3. Versioned values — store the row version with the value and only write to the cache if the version is newer than what is there. Since versions come from the database (version column, or the commit LSN), a slow reader with v1 cannot overwrite v2. With versions, updating on write is safe too.
4. Leases — on a miss, the cache hands the reader a lease token; a delete invalidates outstanding tokens, and a SET with an invalid token is rejected. Facebook's memcache uses leases both for this race and to limit stampedes (only one lease per key every few seconds)².

-- KEYS[1] = cache key; ARGV[1] = version; ARGV[2] = value; ARGV[3] = TTL in seconds
local current = redis.call('HGET', KEYS[1], 'version')
if current and tonumber(current) >= tonumber(ARGV[1]) then
  return 0                       -- a newer (or equal) version is already cached
end
redis.call('HSET', KEYS[1], 'version', ARGV[1], 'data', ARGV[2])
redis.call('EXPIRE', KEYS[1], ARGV[3])
return 1

The script runs atomically inside Redis (Redis — atomicity), so the compare and the set cannot interleave with another writer.

Invalidation from the database log (CDC)

Invalidation in application code has a structural weakness: it only covers writes that go through that code. A batch job, another service, a migration or a DBA fixing a row by hand will change the database without deleting anything.

Change data capture (CDC) moves invalidation to the source: a connector reads the database's replication log (the PostgreSQL write-ahead log, WAL) and publishes every committed change as an event. An invalidator consumes the events and deletes the affected keys.

flowchart LR
    APP["catalog service"] -->|"UPDATE events"| DB[("PostgreSQL")]
    ADM["admin script"] -->|"UPDATE events"| DB
    DB -->|"WAL"| DBZ["Debezium<br/>CDC connector"]
    DBZ -->|"change event<br/>events id=42"| K[["Kafka topic<br/>catalog.events"]]
    K --> INV["cache invalidator"]
    INV -->|"DEL event:42"| R[("Redis")]
    INV -->|"publish invalidate 42"| PS(("pub/sub<br/>L1 caches"))

• Complete: every committed change is seen, whatever wrote it; uncommitted changes never are.
• Ordered per key: the log is in commit order, so invalidations cannot be reordered (with Kafka partitioned by key).
• Decoupled: the writer does not know which caches exist.
• Costs: an extra pipeline to run (Debezium, Kafka); invalidation lags the commit by milliseconds to seconds; still needs a TTL in case the pipeline stops.

CDC and the outbox pattern are covered in Messaging.

Invalidating many copies

A value may be cached in several places at once. Each needs its own mechanism:

Tag-based invalidation helps when one change affects many keys: tag every cached response that contains event 42 with event-42 and purge by tag. Some CDNs support it natively; in Redis you can keep a set of keys per tag (SADD tag:event-42 key1 key2) and delete them together.

Eviction policies

A cache has a memory limit. When it is full and a new value arrives, the eviction policy chooses a victim. A good policy keeps the items that will be read again soonest — which nobody knows, so every policy is a guess based on the past.

W-TinyLFU, used by Caffeine, combines both worlds: new items enter a small LRU window; to move into the main cache, an item must have a higher estimated frequency than the victim it would replace. Frequencies are kept in a compact probabilistic sketch (a Count-Min sketch) and periodically halved, so old popularity fades³.

The simulation below shows why the policy matters. A cache of 1,000 entries serves Zipf-distributed reads over 20,000 items; in the middle of the run, a reporting job scans 2,000 items that nobody else reads.

How to read it:

• During the scan, every policy misses — the scanned items were never cached. What matters is what the cache looks like afterwards.
• LRU and FIFO filled the whole cache with the 2,000 scanned items (more than its capacity), evicting every hot item; the hit ratio needs a while to climb back.
• LFU evicted scanned items among themselves (each had frequency 1) and kept the hot set: it recovers immediately and has a higher hit ratio overall, because with a stable Zipf workload frequency is a better predictor than recency.
• The weakness of plain LFU does not show here: if popularity changes (yesterday's sold-out show), it keeps old favourites too long. That is why real LFU implementations age their counters — and why W-TinyLFU exists.

Eviction in Redis

Redis applies a policy only when memory reaches maxmemory. Its LRU and LFU are approximated: instead of a global ordered list, Redis samples a few keys (maxmemory-samples, default 5) and evicts the best candidate among them; LFU uses a small logarithmic counter per key that decays over time⁴.

What consistency can a cache offer?

A cache-aside cache in front of a database is eventually consistent: after a write, readers may see the old value until the invalidation arrives or the TTL expires. You can strengthen specific guarantees, at a cost:

These are the same consistency models seen in Distributed Systems — a cache is just another replica, with weaker guarantees and no replication protocol.

How it connects

flowchart LR
    BUD["staleness budget<br/>per data item"] --> TTL["TTL: the safety net"]
    BUD --> EXP["explicit invalidation<br/>delete, don't update"]
    EXP --> RACE["write first, then delete<br/>the cache-aside race"]
    EXP --> CDC["CDC from the WAL<br/>Debezium → Kafka"]
    CDC --> MANY["many copies: L1 via pub/sub,<br/>CDN purge, versioned URLs"]
    CDC -.-> MSG["change streams<br/>→ Messaging patterns"]
    EV["eviction: LRU, LFU,<br/>W-TinyLFU"] --> MEM["maxmemory policy<br/>→ Redis"]
    TTL --> CONS["what consistency a cache offers<br/>→ Distributed consistency"]
    RACE --> CONS

Palette components: cache (TTLs, deletes, eviction policy) · app (deletes after the commit, keeps L1 copies) · sql (its write-ahead log is the source of invalidations) · kafka (Debezium change events, ordered per key) · pubsub (broadcast to in-process caches) · cdn (purge by URL or tag — or better, versioned URLs). Scenarios: read-heavy-cache, cdn-static, event-fanout. Continues in: Failure Modes, Distributed — consistency, Messaging — patterns (CDC, outbox), Edge — DNS & CDN, Hands-on 5.