policybook / cache

cache

Policies for deciding which key to drop when a cache is full. A cache holds at most `capacity` keys, so when a new one arrives something has to go, and which one is the whole question. The difference between a good and a bad eviction rule on the same workload is routinely ten points of hit rate, for identical memory and near-identical cost per operation.

Run these side by side → Same trace, same seed, stepped in lockstep.

Choosing one

If you need	Use	Because
One good default	SIEVE	Scan-resistant, no lock on a hit, and the simplest thing here that is genuinely good.
The highest hit rate	W-TinyLFU	A frequency sketch turns admission into a contest the incumbent usually deserves to win.
Web or CDN traffic full of one-hit wonders	S3-FIFO	Most objects die in a small probation queue without ever touching the main cache.
To survive workload shifts without retuning	ARC	Adapts its own recency/frequency split as the workload moves, but check the patent history.
Scan resistance you can explain in a sentence	2Q	A key must come back after eviction to earn the main cache.
LRU without a write on every hit	CLOCK	One reference bit and a sweeping hand approximate the same order.
The default nobody will question	LRU	The baseline everything else here is measured against, and a scan flushes it.
Stable popularity, with scans passing through	LFU	Ranks by lifetime frequency. The price is that it cannot forget.
Predictable eviction, or hits that cost nothing	FIFO	Ignores reuse entirely. It is the floor everything else must beat.

Benchmarks

Hit rate on each trace, measured by this repository's benchmarks.

Policy	`zipf-1.0-100k`	`zipf-0.75-1m`	`scan-heavy`	`shifting-popularity`
W-TinyLFU	0.7339	0.4971	0.6746	0.6597
S3-FIFO	0.7300	0.4856	0.6734	0.6849
LFU	0.7273	0.4768	0.6686	0.3229
SIEVE	0.7273	0.4768	0.6686	0.6101
ARC	0.7248	0.4753	0.6687	0.6887
2Q	0.7147	0.4650	0.6587	0.6792
CLOCK	0.6850	0.4145	0.6222	0.6748
LRU	0.6746	0.4023	0.6139	0.6665
FIFO	0.6306	0.3655	0.5763	0.6261
Bélády OPT reference	0.8087	0.6399	0.7473	0.7939

Every policy

W-TinyLFU

Approximate frequencies in a four-bit sketch decide admission, so an unpopular newcomer never displaces a proven entry.

S3-FIFO

Three FIFO queues and two bits per entry. One-hit wonders die in a small admission queue. Proven keys graduate to the main one.

LFU

Evict the key used least often. Wins on stable skewed traffic, but holds yesterday's winners forever when popularity shifts.

SIEVE recommended

A FIFO queue with a moving hand that gives each entry one chance. Simpler than LRU, scan-resistant, and no reordering on a hit.

ARC

Balance recency against frequency and tune the balance from ghost hits. The standard against which adaptive policies are measured.

2Q

Admit to the main cache only on a second access. A ghost queue remembers evicted keys, so scans never reach the working set.

CLOCK recommended

Approximate LRU with one reference bit per entry. A hit sets a bit and writes nothing shared, so reads need no lock.

LRU

Evict the key used longest ago. The default baseline, and what most people mean when they say "cache".

FIFO

Evict the key that arrived first, ignoring how often it has been used. The baseline every other cache policy is measured against.

Bélády OPT

Evict whatever is needed furthest in the future. Not deployable, since it needs the whole trace, but it is the bound every other policy is read against.