FIFO, LRU, LFU: three guesses about the future.
Evict the oldest insert, the least recently used, or the least often used. The perfect policy evicts what’s needed farthest ahead, but that needs the future.
Does a one-year TTL keep it cached?
Bad: TTL means retention
Set max-age to a year, and it stays.
Good: TTL means freshness
Eviction drops valid entries for space; rarely read files go in days.
LRU in O(1) is a hash map plus a doubly linked list.
The map finds any node in one step. A hit relinks it at the front; a full cache drops the node at the back.
A nightly export reads every order once. Under LRU, each one enters at the front of the list.
The trick
The scan pushes every hot key out. Scan-resistant policies let one-time reads pass straight through.
72%
of keys between evictions are read once
The median across 6,594 production traces, in a window the size of a cache. LRU gives each one a full ride from front to back.
Let a newcomer in only if it earns the space.
S3-FIFO parks new keys in a small queue and promotes only those hit again. In the article’s simulation it served 18% more reads than LRU.
Redis at maxmemory: pick a policy
- allkeys-lru: the usual default for a cache
- allkeys-lfu: a stable hot set, like a catalogue
- allkeys-random: keys read in a repeating loop
- noeviction: writes fail once memory is full
Remember
A full cache guesses what won’t be read again. LRU is the default, but scans and one-hit wonders hurt it; admission policies like W-TinyLFU and S3-FIFO fix that. Measure on your own trace.