Eviction policies and cache sizing

A 2 GB cache in front of 20 GB of product records can hold a tenth of them, so once it is full, every new entry pushes an old one out. Two decisions follow, and they belong together: which entry leaves, and how much memory the cache gets in the first place. Eviction policieseviction policy: The rule a full cache follows to choose which entry leaves when a new one needs room, such as LRU, LFU, FIFO or random eviction. make the first decision; cache sizing makes the second.

Why a cache has to forget

Memory is the cache’s whole budget. A catalogue of 20 million products cannot sit in a few gigabytes, so the cache keeps only part of it, and the part it keeps decides its hit ratiohit ratio: The share of lookups a cache answers itself: hits divided by hits plus misses over a period. At 95 % of 20,000 lookups a second, 1,000 a second still reach the layer behind it. More in “Where caches live, from browser to database”. That ratio grows with the cache’s size, but not evenly: the first entries hold the most popular items and add many hits each, while the last ones hold items that are rarely read.

This trace shows the flattening with real numbers. It replays 400,000 reads of 20,000 items, the popular ones read far more often, through LRULRU (least recently used): A cache policy that, when the cache is full, evicts the entry that has gone longest without being read. It keeps what was read recently, which is close to, but not the same as, keeping the most popular items. More in “Estimating storage, bandwidth and cache memory” caches of seven sizes:

"""Hit ratio of an LRU cache by size, on one seeded trace: 400,000 reads of 20,000 items whose popularity follows a
Zipf-like curve (the item of rank k is read in proportion to 1 / k**0.9). The same seed gives the same trace, so the
table is the same on every run."""
import random
from collections import OrderedDict
from itertools import accumulate

ITEMS, READS = 20_000, 400_000
rng = random.Random(11)
cumulative = list(accumulate(1 / k**0.9 for k in range(1, ITEMS + 1)))
trace = rng.choices(range(ITEMS), cum_weights=cumulative, k=READS)


def lru_hit_ratio(capacity):
    cache, hits = OrderedDict(), 0
    for key in trace:
        if key in cache:
            hits += 1
            cache.move_to_end(key)  # the most recently used goes to the end
        else:
            cache[key] = True
            if len(cache) > capacity:
                cache.popitem(last=False)  # forget the least recently used
    return hits / READS


print(f"{'entries':>8} {'of items':>9} {'hit ratio':>10} {'points per 1,000 more entries':>31}")
previous = None
for size in [200, 500, 1_000, 2_000, 4_000, 8_000, 16_000]:
    ratio = lru_hit_ratio(size)
    gain = "" if previous is None else f"{(ratio - previous[1]) * 100 / ((size - previous[0]) / 1_000):.1f}"
    print(f"{size:>8,} {size / ITEMS:>9.1%} {ratio:>10.1%} {gain:>31}")
    previous = (size, ratio)

 entries  of items  hit ratio   points per 1,000 more entries
     200      1.0%      28.9%                                
     500      2.5%      38.9%                            33.5
   1,000      5.0%      47.7%                            17.4
   2,000     10.0%      57.3%                             9.7
   4,000     20.0%      68.2%                             5.4
   8,000     40.0%      80.3%                             3.0
  16,000     80.0%      92.6%                             1.5

Holding 5 % of the items answers almost half the reads. Each further 1,000 entries then adds less: 33.5 points at first, 1.5 points near the end. So cache sizing is never “as big as possible”; it is the point where the next gigabyte stops paying for itself. The curve is not a law of nature either. It comes from the skew of your own reads, which is why the same memory can answer half the reads in one system and nearly all of them in another.

Eviction policies decide which entry leaves when a new one needs room. The common ones are short to state:

• LRU evicts the entry that has gone unused for the longest time.
• LFU evicts the entry that has been read least often.
• FIFO evicts the oldest entry, however often it is read.
• Random eviction drops an entry chosen at random, which costs no bookkeeping at all.
• TTL expiry removes an entry when its lifetime ends, whether or not memory is short.
• An admission filter such as W-TinyLFU decides whether a new item may enter at all, from an estimate of how often it is read.

On the same memory, eviction policies can differ by ten points of hit ratio or more, and the best one depends on how the reads behave over time. Cache sizing and the policy are therefore one decision: a better policy needs less memory for the same hit ratio.

How LRU, LFU, FIFO and random choose a victim Pro: opens with a Pro, Premium or Ultimate pass