LRU Cache Concepts

A cache keeps copies of data that is expensive to fetch or compute in a smaller, faster place, so that the next request for the same data can be answered quickly. Because the fast place is small, a cache eventually fills up and has to decide what to throw away. The rule it uses is called an eviction policy, and LRU (least recently used) is the most widely taught and used one. This chapter introduces the vocabulary, compares LRU with other policies and explains when LRU is a good fit.

What a cache does

Every cache sits in front of something slower: a CPU cache in front of main memory, the OS page cache in front of the disk, Redis in front of a database, a CDN in front of an origin server. A lookup that finds the data is a hit; a lookup that has to go to the slow source is a miss. The fraction of lookups that hit is the hit ratio, and it is the number that decides whether a cache is worth having.

The simplest cache is a dictionary used for memoization. It never forgets anything, so it is only safe when the set of possible keys is small.

import time

slow_calls = 0

def slow_square(n):
    global slow_calls
    slow_calls += 1
    time.sleep(0.01)          # pretend this is a network call
    return n * n

memo = {}

def cached_square(n):
    if n in memo:             # hit
        return memo[n]
    memo[n] = slow_square(n)  # miss: compute and remember
    return memo[n]

for n in [3, 4, 3, 3, 4, 5]:
    cached_square(n)
print(slow_calls)             # 3 misses, 3 hits

Why a cache needs an eviction policy

Real caches have a capacity: a number of entries, a number of bytes or a number of memory pages. When a new item arrives and the cache is full, one existing item must be evicted. A good policy evicts the item that is least likely to be needed again soon. Nobody knows the future, so every policy is a guess based on the past.

TTL (time to live) answers a different question from the others: not "what do we drop when full?" but "how long may data stay before it is considered stale?". Real systems often combine TTL with LRU or LFU.

A FIFO cache is easy to build with an ordered dictionary: insertion order is the eviction order, and lookups do not change it.

from collections import OrderedDict

class FIFOCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        return self.data.get(key)        # reading does not change the order

    def put(self, key, value):
        if key not in self.data and len(self.data) >= self.capacity:
            self.data.popitem(last=False)  # drop the oldest insertion
        self.data[key] = value

fifo = FIFOCache(2)
fifo.put("a", 1); fifo.put("b", 2)
fifo.get("a")
fifo.put("c", 3)                         # evicts "a" even though it was just read
print(list(fifo.data))                   # ['b', 'c']

The LRU idea

LRU relies on temporal locality: data used recently is likely to be used again soon. It keeps entries ordered by recency. Every successful get or put moves the entry to the "most recently used" end; when space is needed, the entry at the "least recently used" end is removed. Compared with FIFO, the only difference is that a read refreshes an entry. That one change makes the cache follow the current working set of a program, a user or a service.

Python ships an LRU cache as a decorator, which is the quickest way to see the policy at work.

from functools import lru_cache

@lru_cache(maxsize=2)
def load(key):
    print("loading", key)
    return key.upper()

load("a"); load("b")
load("a")                 # hit: "a" becomes most recent
load("c")                 # full: evicts "b", the least recently used
load("b")                 # miss again: prints "loading b"
print(load.cache_info())  # CacheInfo(hits=1, misses=4, maxsize=2, currsize=2)

Vocabulary

• Capacity: the maximum number of entries (or bytes) the cache may hold.
• Hit / miss: whether a lookup was answered from the cache.
• Eviction: removing an entry to make room for a new one.
• Invalidation: removing or updating an entry because the source data changed.
• Working set: the set of keys a workload is actively using right now.
• Cache pollution: useful entries pushed out by data that will never be read again, typically by a one-time scan.

When LRU fits and when it does not

LRU works well when access is skewed toward a moving set of hot keys: user sessions, recently viewed pages, recently opened files. It does poorly in two situations. First, a sequential scan larger than the cache evicts everything and leaves only items that will not be reused. Second, if a few keys are popular over a long period but are touched less often than a stream of one-off keys, LFU or a hybrid such as 2Q, ARC or W-TinyLFU keeps them better. Many production systems therefore use LRU variants rather than textbook LRU.

Summary

• A cache trades a little fast memory for fewer slow operations; the hit ratio measures how well it works.
• When full, a cache needs an eviction policy: FIFO, LRU, LFU, random, often combined with TTL.
• LRU evicts the entry unused for the longest time and assumes temporal locality.
• Scans and long-term popularity are its weak spots, which is why real systems use LRU variants.