Cache simulator

Hit-ratio curves. Pick a workload, the policies, and the largest cache (as a percentage of the distinct keys). Every policy is simulated at a dozen log-spaced cache sizes in a Web Worker, and the curves are drawn together with Belady’s OPT (dashed) as the ceiling. For Zipf workloads two dotted reference lines are added: Che’s approximation of LRU, and the best static cache (the c most popular keys), which bounds any policy in the long run under independent requests. Hover or tap the chart for values; Table lists them all (the best online policy per size in bold). The tiles above show how many keys are seen only once (no cache can hit those) and the largest hit ratio possible (1 − distinct ÷ requests).

Step through. Type a short trace (keys separated by spaces) and pick two policies and capacities to run side by side. Step sends one request; each pane explains what the policy just did (“candidate d (freq 1) does not beat victim a (freq 3) — d rejected”) and draws its internal structures: LRU order, FIFO queue, CLOCK frames with reference bits and the hand, LFU priorities, ARC’s T1/T2 lists, ghost lists B1/B2 and target p, 2Q’s A1in/A1out/Am, W-TinyLFU’s window, probation and protected segments with sketch frequencies, S3-FIFO’s small, main and ghost queues, and OPT’s next-use times. The strip of requests shows each pane’s hits (green) and misses (red); tap one to jump there. ← and → step, Space plays. Presets include Belady’s anomaly.

Write policies. An LRU cache under a Zipf read/write mix with write-through, write-back and write-around: read hit ratio, read and write latency, how many writes reach the store, how many writes write-back coalesces into each store write, and how much acknowledged data sits dirty in the cache (lost if the node dies).

Stampede. Keys filled together, Poisson traffic, a TTL and a recompute time δ; a database that slows once too many queries run at once. Compare no protection, request coalescing per server (singleflight), a global lock, probabilistic early expiration (XFetch) and stale-while-revalidate, each with TTL jitter. Charts show queries started per second and queries in flight; the table runs every strategy on the same traffic.

Hot keys & tiers. An in-process L1 in every app server in front of a sharded Redis L2 and a database: hit ratio per tier, mean latency, requests reaching Redis and the database, and the load on every shard — where the hottest key lands, whether it exceeds a shard’s capacity, and how an L1 or a few copies of the key fix it.

On Zipf traffic the modern policies (ARC, W-TinyLFU, S3-FIFO) recover a large part of the gap between LRU and OPT. At small cache sizes their hit ratio can be two or three times LRU’s; at larger sizes a few points of hit ratio are still a large cut in the miss ratio — the load on whatever is behind the cache.

Che’s approximation tracks simulated LRU to within a fraction of a percent on Zipf traffic: a quick way to size an LRU cache without simulating.

On the loop, LRU’s curve is a cliff (so are ARC’s, LFU’s and S3-FIFO’s), while W-TinyLFU’s admission filter keeps part of the loop and follows OPT closely; on scans, LRU and CLOCK drop while ARC, 2Q, W-TinyLFU and S3-FIFO hold up; on the shifting hot set, frequency without enough aging lags.

In the stampede, every expiry of an unprotected hot key sends about λδ requests to the database at once; once that exceeds the database’s concurrency the queries slow down, more requests pile in and the herd snowballs. Coalescing cuts it to one query per key per server (or one in all), XFetch to about one early recompute, stale-while-revalidate to one background refresh with no waiting at all. Mass expiry of many keys filled together is fixed by TTL jitter.

All objects have the same size, so hit ratio equals byte hit ratio. Size-aware policies (GDSF, AdaptSize, LHD) and Caffeine’s adaptive window sizing (hill climbing) and its random admission guard against hash flooding are not modelled.

OPT here is the offline optimum with bypass for unit-size objects. With variable sizes OPT is NP-hard and only bounds exist.

The Zipf generator draws independent requests (the independent reference model). Real traces have temporal locality, bursts and correlation — upload one to see its real curve.

The write-policy model is one LRU cache with no replication; write-backs happen off the request path. The stampede model is a simplified event simulation (one recompute time with ±20% noise, database slowdown linear beyond its limit). The tiers tab uses Che’s approximation, which assumes independent requests and LRU in every tier.

Up to 2 million requests per workload; very large uploaded traces may take a while in the worker.

L. A. Belady, “A study of replacement algorithms for a virtual-storage computer”, IBM Systems Journal 5(2), 1966 (OPT/MIN); L. A. Belady, R. A. Nelson, G. S. Shedler, “An anomaly in space-time characteristics of certain programs running in a paging machine”, CACM 12(6), 1969.

R. L. Mattson, J. Gecsei, D. R. Slutz, I. L. Traiger, “Evaluation techniques for storage hierarchies”, IBM Systems Journal 9(2), 1970 (stack distances).

N. Megiddo, D. S. Modha, “ARC: A Self-Tuning, Low Overhead Replacement Cache”, FAST 2003 (the algorithm in Figure 4 is implemented line for line).

T. Johnson, D. Shasha, “2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm”, VLDB 1994 (the full version with Kin = 25%, Kout = 50%).

G. Einziger, R. Friedman, B. Manes, “TinyLFU: A Highly Efficient Cache Admission Policy”, ACM Transactions on Storage 13(4), 2017;

J. Yang, Y. Zhang, Z. Qiu, Y. Yue, K. V. Rashmi, “FIFO queues are all you need for cache eviction”, SOSP 2023 (S3-FIFO).

M. Arlitt, L. Cherkasova, J. Dilley, R. Friedrich, T. Jin, “Evaluating content management techniques for Web proxy caches”, ACM SIGMETRICS PER 27(4), 2000 (LFU-DA).

F. J. Corbató, “A paging experiment with the Multics system”, MIT Project MAC, 1968 (CLOCK).

H. Che, Y. Tung, Z. Wang, “Hierarchical Web caching systems: modeling, design and experimental results”, IEEE JSAC 20(7), 2002; C. Fricker, P. Robert, J. Roberts, “A versatile and accurate approximation for LRU cache performance”, ITC 2012.

A. Vattani, F. Chierichetti, K. Lowenstein, “Optimal Probabilistic Cache Stampede Prevention”, PVLDB 8(8), 2015 (XFetch).

M. Nottingham, RFC 5861: HTTP Cache-Control Extensions for Stale Content (stale-while-revalidate).

Facebook’s “Scaling Memcache at Facebook” (NSDI 2013) for leases against thundering herds and stale sets, and the cache-aside “delete, don’t set” rule.