Part 2 of 6 · 2 min read
Two reasons an entry leaves
Eviction because the cache is full, and expiry because the entry is too old.
Think of a bookshelf beside a desk. The shelf holds 20 books. To add a 21st, a book must come off: that is a choice about space. Separately, a book that is an old edition should be thrown out even if the shelf has room: that is a choice about age. A cache has both rules.
The book "System Design Interview" explains eviction: once the cache is full, adding an item may cause existing items to be removed. The book "Understanding Distributed Systems" explains expiry: a cache has an expiration policy that says for how long to keep an entry.
Eviction
Eviction is the removal of an entry from a full cache to make room for a new one. A policy chooses which entry goes.
Example: a cache holds 1,000 entries. Entry number 1,001 arrives. The policy picks one old entry to remove.
Expiry (TTL)
Expiry removes an entry because it has been in the cache too long. The time to live (TTL) is the number of seconds an entry may stay.
Example: an entry with a TTL of 60 seconds is stored at 10:00:00. After 10:01:00 it counts as expired.
| Eviction | Expiry | |
|---|---|---|
| Trigger | The cache is full | Time has passed |
| Question answered | Which entry is least useful to keep? | Is this entry too old to trust? |
| Protects against | Running out of memory | Serving stale data for ever |
| Chosen by | Eviction policy (LRU, LFU...) | TTL |
An entry can leave for either reason. A cache with a long TTL but little memory evicts a lot. A cache with plenty of memory and a short TTL expires a lot.
Expiry does not have to happen at the exact second. The book "Understanding Distributed Systems" notes that expiry can be deferred to the next time the entry is requested. This is called lazy expiry. It can be better than removing at once: if the source is unavailable and the cache is inline, it may return the expired entry rather than an error.
A worked example of lazy expiry. A cache has 1,000,000 entries, each with a TTL. Scanning all of them every second to find expired ones would cost a million checks per second. With lazy expiry, an entry is checked only when read: 5,000 reads a second means 5,000 checks. A slow background sweep removes entries that are never read again, so memory does not fill with dead entries.
Check yourself:
- A cache has free memory, but one entry is 2 hours old with a TTL of 1 hour. Which rule applies?
- Why is lazy expiry cheaper than checking every entry every second?