Cache eviction policies simulator

Pick a workload and a cache size. The simulator generates 10,000 requests, runs every policy on exactly the same requests, and shows each one’s hit ratio, the share of requests found in the cache. The optimal policy is computed too, so you can see how much room each policy leaves. The chart below the table shows the hit ratio over the last 500 requests as the trace goes on, which is where changes in the workload show up.

The second part takes a short trace of letters that you can edit. Each row is a policy and each column a request: a shaded cell is a hit, and a letter is the key that the miss pushed out. Click a column to see what every cache holds at that moment. Things to try:

• Choose Loop. LRU, FIFO and CLOCK score zero: the loop is a little longer than the cache, so every key is evicted just before it comes back.
• Choose Changing popularity and compare LFU with LRU. LFU keeps the old favourites long after nobody asks for them.
• In the short trace, watch what LRU does to A and B during the run of single-use letters D to J, and what SIEVE and ARC do.

The policies are written from their papers and checked: LRU and FIFO give the same hit counts as the Python cachetools library on every trace used here, no policy ever holds more keys than the cache size, and no policy beats the optimum on any trace.

A cache keeps copies of data in a faster, smaller store so that repeated requests do not go back to the slower source. Because it is smaller, it fills up. A cache eviction policy, also called a replacement policy, decides which item to remove to make room for a new one.

The same question comes up at every level of a computer: CPU caches choosing which line to drop, an operating system choosing which page of memory to write out (there the policy is called page replacement), a database choosing which page to drop from its buffer pool, and application caches such as Redis, Memcached or a CDN choosing which object to forget.

Every policy is a guess about the future. A request is a hit if the item is in the cache and a miss if it is not. The policy cannot know which items will be asked for next, so it uses the past as a guide: how recently an item was used, how often, or both. Workloads where the guide is right get high hit ratios; workloads that break the guess can drop any policy close to zero.

The hit ratio is hits divided by requests. Small differences matter more than they look: going from a 90% to a 95% hit ratio halves the number of misses, and so halves the load on whatever sits behind the cache.

Some misses cannot be avoided. The first request for any key is a miss whatever the policy does (a compulsory miss), which is why the simulator lists the highest possible hit ratio for each trace. Misses caused by the cache being too small are capacity misses, and those are what the policy can reduce.

In 1966 László Bélády, at IBM, described the best possible policy: when space is needed, evict the item whose next request is furthest in the future, or that will never be requested again. It is known as Bélády’s algorithm, MIN or OPT, and it produces the fewest possible misses. No real cache can run it, because it needs to know the future. It is computed offline on a recorded trace and used as the ceiling, as in the simulator, where it is calculated by looking ahead in the generated requests.

Bélády is also known for an anomaly. With FIFO, giving the cache more space can produce more misses. On the classic reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO misses 9 times with 3 slots and 10 times with 4. LRU and OPT never do this: a bigger cache always holds everything a smaller one would, so they miss 10 and 8 times. Policies with that property are called stack algorithms.

FIFO (first in, first out) evicts the item that entered the cache first, whether or not it has been used since. It is a plain queue and costs almost nothing per request, since a hit changes nothing.

LRU (least recently used) evicts the item that has gone longest without a request. Each hit moves the item to the front of the queue, so items in use keep their place. It is the most widely taught policy because it captures a real property of programs and users, temporal locality: what was used recently is likely to be used again soon. An LRU cache is usually built from a hash map and a doubly linked list, which makes every operation constant time; the LRU cache simulator walks through that structure.

LRU has two weak points that the simulator shows. A scan, a run of keys each requested once, pushes the whole working set out, because every scanned key becomes the most recent. And a loop over slightly more keys than the cache holds gives zero hits: each key is evicted just before its turn comes again. On the loop workload with a cache of 100, LRU and FIFO both score 0.0%, while the optimal policy reaches 79.0%.

On a multi-threaded server, LRU has a cost beyond the hit ratio: every hit rearranges the list, so every read is also a write to shared state and needs a lock. FIFO-like policies, which only set a bit on a hit, scale better, and this is one reason the newer policies below are built on FIFO.

LFU (least frequently used) counts requests per item and evicts the item with the lowest count; in this simulator ties go to the least recently used. When popularity is stable and skewed, LFU does well, because the most popular items build up high counts and are never evicted by a scan.

Its weakness is change. An item that was popular yesterday keeps its high count today, and new items start at one, so they are evicted first. In the changing-popularity workload, where the set of popular keys switches halfway, LFU scores 34.4% against LRU’s 47.3% at a cache of 100. Practical LFU implementations therefore age their counts. Redis, for example, stores a probabilistic logarithmic counter of 0 to 255 per key and decrements it as time passes (lfu-decay-time, one minute by default).

Counting every request in full is also expensive in memory. TinyLFU (Gil Einziger, Roy Friedman and Ben Manes) estimates frequencies with a compact sketch, similar to a count-min sketch, and uses it as an admission filter: a new item only enters the cache if it has been requested more often than the item it would replace. Its variant W-TinyLFU, with a small LRU window in front, is the policy of the Java library Caffeine.

CLOCK approximates LRU at FIFO cost. Items sit in a circle with one reference bit each, and a hit only sets the bit. To evict, a hand sweeps around the circle: an item with its bit set has the bit cleared and is spared once (its second chance), and the first item found with a clear bit is evicted. Fernando Corbató described the idea in 1968 for the paging system of Multics.

Operating systems use CLOCK and its variants because hardware sets the reference bit for free: the memory management unit marks a page table entry as accessed when the page is used, and the kernel only needs to read and clear the bits. Exact LRU would need work on every memory access. In the simulator, CLOCK scores close to LRU on most workloads, and like LRU it is helpless against the loop.

PostgreSQL’s buffer manager uses a clock sweep with a small usage count per buffer instead of a single bit: a hit raises the count up to a limit of 5, and the sweep decrements it, evicting a buffer when it reaches zero. Frequently used pages therefore survive several sweeps.

The cure for scans is to make a new item prove itself before it can push out the working set. 2Q, by Theodore Johnson and Dennis Shasha (VLDB 1994), puts new items in a small FIFO called A1in. When an item leaves A1in, the cache forgets its data but remembers its key in a ghost list, A1out. Only an item requested again while its key is in A1out is admitted to the main LRU list, Am. A scan therefore passes through A1in without touching Am. The paper suggests sizing A1in at 25% of the cache and A1out to remember keys for 50% of it, which is what the simulator uses.

2Q is the only online policy here that scores on the loop workload (64.2% at a cache of 100). Keys entering for the first time only push each other out of the small A1in, so most of the main list survives each pass of the loop.

ARC (adaptive replacement cache), by Nimrod Megiddo and Dharmendra Modha (FAST 2003), removes the fixed split. It keeps two LRU lists, T1 for items seen once recently and T2 for items seen at least twice, and two ghost lists, B1 and B2, holding the keys recently evicted from each. A request for a key in B1 means T1 was too small, so ARC raises its target size for T1; a request for a key in B2 lowers it. The cache keeps adjusting between recency and frequency as the workload changes, with no parameter to tune. In the simulator, ARC is at or near the top on every workload except the loop.

OpenZFS uses ARC for its in-memory cache. PostgreSQL 8.0 also shipped ARC, but concerns about IBM’s patent on it led the project to replace it, and PostgreSQL has used the clock sweep since version 8.1.

The same idea of a probationary area appears in many systems under other names. LRU-K (Elizabeth O’Neil, Patrick O’Neil and Gerhard Weikum, SIGMOD 1993) ranks pages by the time of their K-th most recent request. The Linux page cache keeps an active and an inactive list, and a page must be used again while on the inactive list to be promoted. MySQL’s InnoDB inserts new pages at the midpoint of its LRU list rather than the head.

SIEVE, by Yazhuo Zhang, Juncheng Yang, Yao Yue, Ymir Vigfusson and K. V. Rashmi (NSDI 2024), looks like CLOCK but differs in one detail that matters. Items are kept in a FIFO queue, newest at the head, with a visited bit each, and a hit only sets the bit. To evict, a hand moves from the tail towards the head, clearing set bits, and removes the first item whose bit is clear. New items are inserted at the head, not where the hand is, and items that survive keep their place instead of moving to the head.

The effect is that new items, inserted at the head, must be requested again before the hand reaches them, while popular old items stay near the tail where the hand passes them over. Items read only once are sifted out quickly. On 1,559 traces from seven sources, the paper reports that SIEVE had a lower miss ratio than nine state-of-the-art algorithms on more than 45% of the traces, and twice the throughput of an optimized LRU at 16 threads, since a hit takes no lock. In this simulator it is among the best on the skewed workloads.

SIEVE came out of a line of work by the same group arguing that FIFO-based designs are enough. S3-FIFO (Juncheng Yang and others, SOSP 2023) uses three FIFO queues: a small one for new items, a main one, and a ghost queue of keys, so items requested once are removed quickly from the small queue, the same insight as 2Q.

Hit ratios on each workload with a cache of 100 keys, 10,000 requests and the first random seed, computed by the simulator above. Bold marks the best policy that does not see the future.

• Redis evicts according to maxmemory-policy, whose options include noeviction, allkeys-lru, volatile-lru, allkeys-lfu, volatile-lfu, allkeys-random, volatile-random or volatile-ttl. Its LRU and LFU are sampled approximations: it picks a few keys (maxmemory-samples, 5 by default) and evicts the best candidate among them, which avoids keeping a global list.
• Memcached keeps a separate LRU per slab class and, by default since version 1.5, splits it into hot, warm and cold segments, so an item must be hit again to move out of the cold segment.
• Linux manages the page cache with active and inactive lists, a two-list scheme close to 2Q. Linux 6.1 added the multi-generational LRU (MGLRU), which sorts pages into several generations by age.
• PostgreSQL uses a clock sweep over its shared buffers, and gives large sequential scans a small ring of buffers of their own so they cannot flush the cache.
• MySQL InnoDB inserts new pages into its buffer pool LRU at a midpoint, by default 3/8 from the tail (innodb_old_blocks_pct = 37), and only moves a page to the young part if it is accessed again at least innodb_old_blocks_time after its first access, 1,000 ms by default.
• OpenZFS caches file data in memory with ARC, and can extend it to an SSD with L2ARC.
• Caffeine, the Java caching library, uses W-TinyLFU.

In most applications the policy comes with the tool, and the real choices are the cache size and what to cache. When you do choose:

• LRU is a reasonable default for small in-process caches where requests are skewed and scans are rare.
• If anything reads large amounts of data once (batch jobs, backups, reports, crawlers), use a scan-resistant policy, or keep that traffic out of the cache.
• If popularity is stable over long periods, an LFU with aging, or W-TinyLFU, will usually beat LRU.
• If the cache is hit by many threads, prefer a policy whose hits only set a bit (CLOCK, SIEVE, S3-FIFO) or a sampled approximation like Redis’s.
• Measure. Record a sample of real keys and replay it against candidate policies and sizes, as the simulator does with synthetic ones. A miss ratio curve, the miss ratio for every cache size, shows how much each extra gigabyte buys.

A bigger cache often helps more than a cleverer policy. Compare the two in the simulator: on the skewed workload, going from 100 to 200 keys raises LRU from 39.6% to 50.3%.

The most common coding question is “implement an LRU cache” with get and put in O(1): a hash map from key to node plus a doubly linked list in recency order. A follow-up is LFU in O(1), usually built from a map of counts to lists of keys and a pointer to the minimum count.

In system design interviews, eviction comes up as part of a caching layer: which policy, how big, what happens to the database when the hit ratio drops, and how to avoid a stampede when a popular key expires. A strong answer names the workload pattern (skew, scans, change) and picks a policy that suits it, and knows that Redis and Memcached approximate LRU instead of implementing it exactly.