Design an LRU cache

“Design an LRU cache with O(1) get and put.” Sometimes it’s a coding question with a size limit and two methods. Sometimes it’s “design a cache”, and LRU is where you’re expected to land.

A cache keeps a small number of values close at hand, so we don’t have to fetch them again from somewhere slow, like a database. It has a size limit. When it’s full and a new value arrives, something has to leave. LRU stands for “least recently used”: the value that leaves is the one nobody has asked for in the longest time.

Many people know the answer by heart: a hash map plus a doubly linked list. In the design version of this question, that’s only the start. Why does each part exist, and what breaks without it? How would a different eviction rule, or values that expire, fit without rewriting the cache? And the question that trips most people: why is a read-write lock wrong here?

The framework

1. 01Answer
2. 02Scope
3. 03Build
4. 04Full design
5. 05Stress
6. 06Wrap up

The answer in one minute

If you only have a minute, this is the design. The rest of the page explains how we get here.

1. A hash map finds each value, and a linked list remembers the order of use. The map points straight at a node in the list. So a read can move its node to the “most recent” end in a few steps, without searching. Get, put and eviction are all O(1), meaning they take the same time however big the cache is.
2. The eviction rule is a separate class. The cache stores values. A small policy object decides which key leaves. LRU is one policy; others can be swapped in.
3. Values expire lazily. Each value carries its expiry time. We check it when the value is read, using a clock we pass in, so tests don’t have to wait.
4. Listeners hear about every removal, and why. For example, “evicted” or “expired”. A listener that saves changed values back to the database needs to know the reason.
5. A read changes the cache. Moving a node is a write. So many threads need a real lock, not a read-write lock. For speed, we split the cache into independent parts (shards), each with its own lock.

We’ll build this in four stages, then deal with many threads at once.

Scope it

Before drawing anything, we ask a few questions. Each answer changes the structure or the locking. Anything that doesn’t, we assume and move on.

Interviewerminute 0

Design an LRU cache.

What they are testing

Whether you pin down the size limit (number of entries or bytes), threads and expiry in two or three minutes, since those change the structure and the locking. Jumping straight into the linked list looks like reciting a memorized answer.

Here are the questions that matter:

• Is the size limit a number of entries, or bytes? Entries. A limit in bytes needs the size of each value, and one put may have to evict several values.
• Do many threads share it? Yes, it’s a cache inside a server. With one thread, the whole concurrency section goes away.
• Do values expire? Yes, after a fixed time, called the TTL (“time to live”). Without it, there’s no clock and no expiry check.
• Is LRU the only rule? LRU now, but other rules may follow. If LRU were forever, the rule could stay inside the cache.
• Does anyone need to know when values leave? Yes: metrics, and saving changed values back to the database.

These answers give us one promise that matters more than the others: get, put and eviction are each O(1), all at once. The obvious designs give up one of the three. Three smaller promises come with it. The cache is safe and fast with many threads. A new eviction rule doesn’t change the cache. And time is passed in, so tests can check expiry without sleeping.

We leave out loading values on a miss (an extension), saving the cache to disk, and spreading it across several machines.

Go deeperThree more questions, and what each changes1 min

Question	We assume	If the answer were different
Who loads missing values?	The caller, after a miss	A loading cache calls a loader itself and must stop duplicate loads
Null values allowed?	No	Null needs a separate “present” flag, or get can’t tell a miss from null
Exact LRU, or “close to LRU”?	Close is fine at scale	Exact LRU across the whole cache limits how far concurrency can go

Build it

We’ll build the design in four stages. Each stage adds only what a new requirement needs. In each diagram, the new parts are outlined, and the colors show what each class does (the key is under every diagram).

Stage 1: A map and a queue

Interviewerminute 4

Start with something that works. What’s the simplest LRU you can write?

What they are testing

Whether you can produce a correct version quickly and say exactly where it’s slow. Pointing out the slow part yourself, before being asked, is the good sign. Defending it as “fine” is the bad one.

Start with the smallest thing that works. A map holds the values. A queue holds the keys in order of use, oldest at the front. A get moves its key to the back of the queue. A put into a full cache evicts the key at the front.

Stage 1: a map and a queue

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JLruCache.javaPylru_cache.pyC#LruCache.csGolru_cache.goTSlru-cache.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// The smallest cache that evicts the least recently used key: a map for the values,
// and a queue that keeps keys in the order they were last used (oldest first).
class LruCache<K, V> {
    private final int capacity;
    private final Map<K, V> values = new HashMap<>();
    private final ArrayDeque<K> order = new ArrayDeque<>();  // front = least recently used

    LruCache(int capacity) {
        if (capacity < 1) throw new IllegalArgumentException("capacity must be at least 1");
        this.capacity = capacity;
    }

    // A miss is normal for a cache, so it is an empty result, not an exception.
    Optional<V> get(K key) {
        if (!values.containsKey(key)) return Optional.empty();
        touch(key);  // reading counts as using: the key moves to the back
        return Optional.of(values.get(key));
    }

    void put(K key, V value) {
        if (values.containsKey(key)) {
            touch(key);  // an update is a use too, but never an eviction
        } else {
            if (values.size() == capacity) values.remove(order.pollFirst());  // evict the oldest
            order.addLast(key);
        }
        values.put(key, value);
    }

    // flaw: remove(key) walks the queue to find the key, so every get is O(n).
    // With a million entries, a cache hit costs more than the miss it saves. Stage 2.
    private void touch(K key) {
        order.remove(key);
        order.addLast(key);
    }
}

It’s correct, but one step is slow. To move a key to the back, the queue first has to find it, and that means checking up to n keys, one by one. We write that as O(n): the time grows with the number of entries. With a million entries, every hit could cost a million comparisons. That’s slower than the database call the cache was meant to save.

What would fix it? If each entry already knew where it sits in the order, we could take it out directly, without searching. That’s stage 2.

Stage 2: O(1) with a linked list

Interviewerminute 8

Make get and put O(1).

What they are testing

Whether you can explain why each part is needed: the map finds the node, the list keeps the order, the two links make removing a node quick, and the key in the node makes eviction quick. A correct structure without the reasons looks memorized.

The fix is to keep the order in a doubly linked list. Each entry is a node that holds its key, its value, and two links: one to the node before it and one to the node after it. The map no longer points at the value. It points at the node.

Now a get works like this. The map hands us the node right away. We take the node out of its place by joining its two neighbours to each other. Then we put it at the “most recent” end. That’s four pointer changes, whatever the size of the cache: O(1).

Each part has a job:

• The map finds a key’s node in O(1).
• The list keeps nodes in order of use. The front is the next to be evicted.
• Two links per node let a node remove itself. With only a “next” link, we’d need the node before it, and finding that means walking the list again.
• The key inside the node matters for eviction. We evict from the front of the list, and the key tells us which map entry to delete too.
• A sentinel is a dummy node that sits at both ends of the list. The list is never truly empty, so the code never has to check for “no node here”.

The recency list: one sentinel, least recent first

Scroll or pinch to zoom, drag to pan

Stage 2: the map points at list nodes

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JLruCache.javaPylru_cache.pyC#LruCache.csGolru_cache.goTSlru-cache.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// One entry in the recency list. It knows its neighbours, so it can unlink itself in O(1)
// without anyone searching for it. It also carries its key: on eviction we start from the
// node and need the key to remove it from the map.
class Node<K, V> {
    final K key;
    V value;
    Node<K, V> prev, next;

    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

class LruCache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> index = new HashMap<>();  // key -> its node, O(1)
    // Sentinels: a head and tail that are never removed, so linking and unlinking never have
    // to check for null or special-case an empty list.
    private final Node<K, V> head = new Node<>(null, null);    // head.next = least recent
    private final Node<K, V> tail = new Node<>(null, null);    // tail.prev = most recent

    LruCache(int capacity) {
        if (capacity < 1) throw new IllegalArgumentException("capacity must be at least 1");
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    Optional<V> get(K key) {
        Node<K, V> n = index.get(key);
        if (n == null) return Optional.empty();
        moveToBack(n);  // O(1): we already hold the node
        return Optional.of(n.value);
    }

    void put(K key, V value) {
        Node<K, V> n = index.get(key);
        if (n != null) {  // update in place; never evicts
            n.value = value;
            moveToBack(n);
            return;
        }
        if (index.size() == capacity) {
            Node<K, V> oldest = head.next;
            unlink(oldest);
            index.remove(oldest.key);  // why the node carries its key
        }
        n = new Node<>(key, value);
        linkAtBack(n);
        index.put(key, n);
    }

    int size() { return index.size(); }

    private void moveToBack(Node<K, V> n) {
        unlink(n);
        linkAtBack(n);
    }

    private void unlink(Node<K, V> n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void linkAtBack(Node<K, V> n) {
        n.prev = tail.prev;
        n.next = tail;
        tail.prev.next = n;
        tail.prev = n;
    }
}

Here is a put into a full cache, step by step. The new key isn’t in the map, so we evict first: the node right after the sentinel is the oldest. We take it out of the list, and use its key to delete it from the map. Then the new node goes in at the back, and into the map.

Sequence: a put that evicts

Scroll or pinch to zoom, drag to pan

• Color key
• Database
• Facade

Most languages already ship this structure. In Java, a LinkedHashMap in access order with removeEldestEntry is an LRU in five lines. Python’s OrderedDict has move_to_end and popitem(last=False). Say so in the interview, then build it anyway. The interviewer wants to see that you can.

What does it cost? Each entry now has a node on top of the map’s own entry, around 70 extra bytes on a 64-bit JVM. And every get changes four pointers. That second cost will matter a lot when many threads arrive.

Common mistake

A singly linked list, or a node without its key

With only “next” links, removing a node needs the node before it, which means walking from the head: O(n) again. And a node without its key can be removed from the list but not from the map. That leaks memory and leaves the map pointing at a dead node. Both mistakes compile and pass a small test.

Go deeperWhy not a timestamp on each entry?1 min

A common idea is to store “last used at” on each entry and evict the oldest. But finding the oldest means checking every entry (O(n)), or keeping entries sorted by time, in a heap or a sorted map. Then every get changes a timestamp and has to move the entry to its new sorted place, which is O(log n). The linked list keeps the order without comparing anything. Moving a node to the end is all it takes, and that’s why it’s O(1).

Stage 3: The eviction rule as a policy

Interviewerminute 15

We might want LFU instead of LRU for some caches. How would you support both?

What they are testing

Whether the eviction rule comes out as a small interface that the cache calls on each event, and whether you can name what the split costs. A subclass of the cache per rule, or a switch inside put, is the answer they mark down.

LFU means “least frequently used”: the key used the fewest times leaves first. FIFO means “first in, first out”: the oldest key leaves, however often it was used. LRU, LFU and FIFO differ in just one thing: which key leaves.

So we split the job in two. The cache keeps the values and the size limit. An EvictionPolicy keeps the order. The cache tells the policy about every access, insert and removal, and asks it one question when it’s full: “who’s next?” The linked list moves out of the cache and into LruPolicy, where it orders keys only. This is the Strategy pattern: one interface, and a class for each rule.

Stage 3: storage and policy, split

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JLruPolicy.javaPylru_policy.pyC#BoundedCache.csGobounded_cache.goTSbounded-cache.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// What callers depend on. They never learn which eviction rule is behind it.
interface Cache<K, V> {
    Optional<V> get(K key);
    void put(K key, V value);
    boolean remove(K key);
    int size();
}

// Decides who leaves when the cache is full. It sees keys and events, never values, so
// LRU, LFU and FIFO are each one class and the cache doesn't change.
interface EvictionPolicy<K> {
    void accessed(K key);  // a get hit or an update
    void added(K key);
    void removed(K key);   // removed by the caller, so the policy forgets it
    K victim();            // who to evict next; the cache then calls removed(victim)
}

// Least recently used, as a policy. A hash map finds a key's node in O(1), and a doubly linked
// list keeps the order: oldest at the front, newest at the back. The list holds keys only; the
// cache keeps the values.
class LruPolicy<K> implements EvictionPolicy<K> {
    private final Map<K, Node<K, Void>> nodes = new HashMap<>();
    private final Node<K, Void> head = new Node<>(null, null), tail = new Node<>(null, null);

    LruPolicy() {
        head.next = tail;
        tail.prev = head;
    }

    // A hit or an update: move the key to the back, the most recent end.
    public void accessed(K key) {
        Node<K, Void> n = nodes.get(key);
        unlink(n);
        linkAtBack(n);
    }

    // A new key starts at the back, as the most recent.
    public void added(K key) {
        Node<K, Void> n = new Node<>(key, null);
        nodes.put(key, n);
        linkAtBack(n);
    }

    public void removed(K key) { unlink(nodes.remove(key)); }

    public K victim() { return head.next.key; }  // least recently used

    private void unlink(Node<K, Void> n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void linkAtBack(Node<K, Void> n) {
        n.prev = tail.prev;
        n.next = tail;
        tail.prev.next = n;
        tail.prev = n;
    }
}

// Storage plus a policy. It owns the values and the capacity; the policy owns the order.
class BoundedCache<K, V> implements Cache<K, V> {
    private final int capacity;
    private final Map<K, V> values = new HashMap<>();
    private final EvictionPolicy<K> policy;

    BoundedCache(int capacity, EvictionPolicy<K> policy) {
        if (capacity < 1) throw new IllegalArgumentException("capacity must be at least 1");
        this.capacity = capacity;
        this.policy = policy;
    }

    public Optional<V> get(K key) {
        V v = values.get(key);
        if (v == null) return Optional.empty();  // null values aren't allowed, so null means a miss
        policy.accessed(key);
        return Optional.of(v);
    }

    public void put(K key, V value) {
        Objects.requireNonNull(value, "null values would be indistinguishable from a miss");
        if (values.containsKey(key)) {
            policy.accessed(key);
        } else {
            if (values.size() == capacity) {
                K victim = policy.victim();
                policy.removed(victim);
                values.remove(victim);
            }
            policy.added(key);
        }
        values.put(key, value);
    }

    public boolean remove(K key) {
        if (values.remove(key) == null) return false;
        policy.removed(key);
        return true;
    }

    public int size() { return values.size(); }
}

FIFO is LruPolicy with an empty accessed method. LFU is the same four methods over a different structure, and still O(1) (we’ll see how in the follow-up questions).

Notice that put evicts before adding the new key. For LRU it makes no difference. For LFU it does: a brand new key has the lowest count, so evicting after adding would throw out the key we just put in. Evicting first is safe for every rule.

What does the split cost? Two maps now hold the same keys: values in the cache, and nodes in the policy. That roughly doubles the map’s memory. Production caches like Caffeine merge them into one shared node. For an interview, the split is clearer. Just say what it costs.

Stage 4: Expiry and removal listeners

Interviewerminute 20

Entries should expire after five minutes. And the team wants to save changed entries back to the database when they leave the cache.

What they are testing

Whether expiry is checked lazily (and you can say what that costs), whether the clock is passed in, and whether listeners learn why an entry left. A background thread that checks every entry every second is the answer that doesn’t scale.

Each value is now stored in an Entry, together with the time it expires. That time comes from a clock that we pass into the cache. In tests, we pass a fake clock and move time forward by hand.

When do we check whether an entry has expired? The simplest place is when someone reads it. If it has expired, we remove it and report a miss. This is called lazy expiry. There’s no background thread and no timer per entry.

The second requirement is about values that leave the cache. A removal listener is told every time an entry leaves, together with the reason: evicted, expired, replaced by a new value, or removed by the caller. The reason matters. A listener that saves changed values to the database should save evicted and expired entries. But it must skip replaced ones, because the new value is already in the cache. This is the Observer pattern: the cache doesn’t know who is listening.

Stage 4: expiry and listeners

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JBoundedCache.javaPybounded_cache.pyC#BoundedCache.csGobounded_cache.goTSbounded-cache.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// Why an entry left. Listeners care: a write-back cache saves EVICTED and EXPIRED entries,
// but not REPLACED ones, because the new value is already in the cache.
enum RemovalCause { EVICTED, EXPIRED, REPLACED, EXPLICIT }

// Told about every removal, with the reason.
interface RemovalListener<K, V> {
    void removed(K key, V value, RemovalCause cause);
}

// A stored value and when it stops being valid.
record Entry<V>(V value, Instant expiresAt) {}

// The cache itself. It owns the values, the capacity and the expiry times; the policy only
// decides the order. Every way an entry can leave goes through evict, so the policy and the
// listeners are always told.
class BoundedCache<K, V> implements Cache<K, V> {
    private final int capacity;
    private final Duration ttl;
    private final Clock clock;  // injected, so a test can move time without sleeping
    private final Map<K, Entry<V>> entries = new HashMap<>();
    private final EvictionPolicy<K> policy;
    private final List<RemovalListener<K, V>> listeners = new ArrayList<>();

    BoundedCache(int capacity, Duration ttl, EvictionPolicy<K> policy, Clock clock) {
        if (capacity < 1) throw new IllegalArgumentException("capacity must be at least 1");
        this.capacity = capacity;
        this.ttl = ttl;
        this.policy = policy;
        this.clock = clock;
    }

    void subscribe(RemovalListener<K, V> l) { listeners.add(l); }

    public Optional<V> get(K key) {
        Entry<V> e = entries.get(key);
        if (e == null) return Optional.empty();
        // Expiry is lazy: checked when the key is read. An expired entry nobody reads still
        // takes a slot until LRU pushes it out, which is fine for a bounded cache.
        if (!clock.instant().isBefore(e.expiresAt())) {
            evict(key, RemovalCause.EXPIRED);
            return Optional.empty();
        }
        policy.accessed(key);
        return Optional.of(e.value());
    }

    public void put(K key, V value) {
        Objects.requireNonNull(value, "null values would be indistinguishable from a miss");
        Entry<V> old = entries.get(key);
        // Make room before adding, so a policy can never pick the newcomer as its own victim.
        if (old == null && entries.size() == capacity) evict(policy.victim(), RemovalCause.EVICTED);
        entries.put(key, new Entry<>(value, clock.instant().plus(ttl)));
        if (old != null) {
            policy.accessed(key);
            notify(key, old.value(), RemovalCause.REPLACED);
        } else {
            policy.added(key);
        }
    }

    public boolean remove(K key) {
        if (!entries.containsKey(key)) return false;
        evict(key, RemovalCause.EXPLICIT);
        return true;
    }

    public int size() { return entries.size(); }

    // The one exit: the entry goes, the policy forgets the key, and the listeners hear why.
    private void evict(K key, RemovalCause cause) {
        Entry<V> e = entries.remove(key);
        policy.removed(key);
        notify(key, e.value(), cause);
    }

    // A listener that throws must not break the cache: the entry is already gone.
    private void notify(K key, V value, RemovalCause cause) {
        for (RemovalListener<K, V> l : listeners) {
            try {
                l.removed(key, value, cause);
            } catch (RuntimeException ex) {
                System.err.println("removal listener failed: " + ex);
            }
        }
    }
}

What does lazy expiry cost? An expired entry that nobody reads still takes memory and a place in the cache. It does leave eventually, since nobody touches it and LRU pushes it out. But its listener is told late. When that matters, add a small sweep: on each put, remove a few expired entries from the old end of the list. Redis does something similar, checking a random sample of keys.

Common mistake

Expiry based on the wall clock

System.currentTimeMillis() and Date.now() can jump backwards when the computer corrects its clock. Then many entries look expired, or never expire, at once. For measuring durations, use a monotonic clock, one that only moves forward (System.nanoTime, time.monotonic, Go’s monotonic time readings). And pass it in, so tests control it.

This is enough for a mid-level answer. The map and list are correct, get, put and eviction are O(1), and updating a key doesn’t evict. The rest of the page is what makes it a senior answer.

The full design

Here is everything together. Each class is here because a requirement needed it.

LRU cache: full class diagram

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

</>lru-cache· read only

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

Explorer

• JAllInOne.java
• src
• JBoundedCache.java
• JCache.java
• JEntry.java
• JEvictionPolicy.java
• JLruPolicy.java
• JNode.java
• JRemovalCause.java
• JRemovalListener.java
• JShardedCache.java
• JSynchronizedCache.java

JAllInOne.java

AllInOne.javasrc/BoundedCache.javasrc/Cache.javasrc/Entry.javasrc/EvictionPolicy.javasrc/LruPolicy.javasrc/Node.javasrc/RemovalCause.javasrc/RemovalListener.javasrc/ShardedCache.javasrc/SynchronizedCache.java

AllInOne.java

// The complete design, built from every stage on this page.

import java.util.*;
import java.util.function.*;
import java.time.*;

// One entry in the recency list. It knows its neighbours, so it can unlink itself in O(1)
// without anyone searching for it. It also carries its key: on eviction we start from the
// node and need the key to remove it from the map.
class Node<K, V> {
    final K key;
    V value;
    Node<K, V> prev, next;

    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

// What callers depend on. They never learn which eviction rule is behind it.
interface Cache<K, V> {
    Optional<V> get(K key);
    void put(K key, V value);
    boolean remove(K key);
    int size();
}

// Decides who leaves when the cache is full. It sees keys and events, never values, so
// LRU, LFU and FIFO are each one class and the cache doesn't change.
interface EvictionPolicy<K> {
    void accessed(K key);  // a get hit or an update
    void added(K key);
    void removed(K key);   // removed by the caller, so the policy forgets it
    K victim();            // who to evict next; the cache then calls removed(victim)
}

// Least recently used, as a policy. A hash map finds a key's node in O(1), and a doubly linked
// list keeps the order: oldest at the front, newest at the back. The list holds keys only; the
// cache keeps the values.
class LruPolicy<K> implements EvictionPolicy<K> {
    private final Map<K, Node<K, Void>> nodes = new HashMap<>();
    private final Node<K, Void> head = new Node<>(null, null), tail = new Node<>(null, null);

    LruPolicy() {
        head.next = tail;
        tail.prev = head;
    }

    // A hit or an update: move the key to the back, the most recent end.
    public void accessed(K key) {
        Node<K, Void> n = nodes.get(key);
        unlink(n);
        linkAtBack(n);
    }

    // A new key starts at the back, as the most recent.
    public void added(K key) {
        Node<K, Void> n = new Node<>(key, null);
        nodes.put(key, n);
        linkAtBack(n);
    }

    public void removed(K key) { unlink(nodes.remove(key)); }

    public K victim() { return head.next.key; }  // least recently used

    private void unlink(Node<K, Void> n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void linkAtBack(Node<K, Void> n) {
        n.prev = tail.prev;
        n.next = tail;
        tail.prev.next = n;
        tail.prev = n;
    }
}

// The cache itself. It owns the values, the capacity and the expiry times; the policy only
// decides the order. Every way an entry can leave goes through evict, so the policy and the
// listeners are always told.
class BoundedCache<K, V> implements Cache<K, V> {
    private final int capacity;
    private final Duration ttl;
    private final Clock clock;  // injected, so a test can move time without sleeping
    private final Map<K, Entry<V>> entries = new HashMap<>();
    private final EvictionPolicy<K> policy;
    private final List<RemovalListener<K, V>> listeners = new ArrayList<>();

    BoundedCache(int capacity, Duration ttl, EvictionPolicy<K> policy, Clock clock) {
        if (capacity < 1) throw new IllegalArgumentException("capacity must be at least 1");
        this.capacity = capacity;
        this.ttl = ttl;
        this.policy = policy;
        this.clock = clock;
    }

    void subscribe(RemovalListener<K, V> l) { listeners.add(l); }

    public Optional<V> get(K key) {
        Entry<V> e = entries.get(key);
        if (e == null) return Optional.empty();
        // Expiry is lazy: checked when the key is read. An expired entry nobody reads still
        // takes a slot until LRU pushes it out, which is fine for a bounded cache.
        if (!clock.instant().isBefore(e.expiresAt())) {
            evict(key, RemovalCause.EXPIRED);
            return Optional.empty();
        }
        policy.accessed(key);
        return Optional.of(e.value());
    }

    public void put(K key, V value) {
        Objects.requireNonNull(value, "null values would be indistinguishable from a miss");
        Entry<V> old = entries.get(key);
        // Make room before adding, so a policy can never pick the newcomer as its own victim.
        if (old == null && entries.size() == capacity) evict(policy.victim(), RemovalCause.EVICTED);
        entries.put(key, new Entry<>(value, clock.instant().plus(ttl)));
        if (old != null) {
            policy.accessed(key);
            notify(key, old.value(), RemovalCause.REPLACED);
        } else {
            policy.added(key);
        }
    }

    public boolean remove(K key) {
        if (!entries.containsKey(key)) return false;
        evict(key, RemovalCause.EXPLICIT);
        return true;
    }

    public int size() { return entries.size(); }

    // The one exit: the entry goes, the policy forgets the key, and the listeners hear why.
    private void evict(K key, RemovalCause cause) {
        Entry<V> e = entries.remove(key);
        policy.removed(key);
        notify(key, e.value(), cause);
    }

    // A listener that throws must not break the cache: the entry is already gone.
    private void notify(K key, V value, RemovalCause cause) {
        for (RemovalListener<K, V> l : listeners) {
            try {
                l.removed(key, value, cause);
            } catch (RuntimeException ex) {
                System.err.println("removal listener failed: " + ex);
            }
        }
    }
}

// Why an entry left. Listeners care: a write-back cache saves EVICTED and EXPIRED entries,
// but not REPLACED ones, because the new value is already in the cache.
enum RemovalCause { EVICTED, EXPIRED, REPLACED, EXPLICIT }

// Told about every removal, with the reason.
interface RemovalListener<K, V> {
    void removed(K key, V value, RemovalCause cause);
}

// A stored value and when it stops being valid.
record Entry<V>(V value, Instant expiresAt) {}

// Thread safe by one lock. Note that get() needs the write side too: a hit moves the key in
// the recency list, so a read-write lock would let two "readers" corrupt the list.
class SynchronizedCache<K, V> implements Cache<K, V> {
    private final Cache<K, V> inner;
    private final Object lock = new Object();

    SynchronizedCache(Cache<K, V> inner) { this.inner = inner; }

    public Optional<V> get(K key) { synchronized (lock) { return inner.get(key); } }
    public void put(K key, V value) { synchronized (lock) { inner.put(key, value); } }
    public boolean remove(K key) { synchronized (lock) { return inner.remove(key); } }
    public int size() { synchronized (lock) { return inner.size(); } }
}

// N independent caches, each with its own lock. Threads only wait for each other when their
// keys hash to the same shard. The price: eviction is LRU within a shard, not across the
// whole cache, so the key evicted is "old in its shard", which is close enough for most uses.
class ShardedCache<K, V> implements Cache<K, V> {
    private final List<Cache<K, V>> shards = new ArrayList<>();

    ShardedCache(int capacity, int shardCount, Function<Integer, Cache<K, V>> newShard) {
        int perShard = (capacity + shardCount - 1) / shardCount;  // round up so total >= capacity
        for (int i = 0; i < shardCount; i++) shards.add(new SynchronizedCache<>(newShard.apply(perShard)));
    }

    // The same key always lands in the same shard. floorMod keeps negative hashes in range.
    private Cache<K, V> shard(K key) { return shards.get(Math.floorMod(key.hashCode(), shards.size())); }

    public Optional<V> get(K key) { return shard(key).get(key); }
    public void put(K key, V value) { shard(key).put(key, value); }
    public boolean remove(K key) { return shard(key).remove(key); }
    public int size() { return shards.stream().mapToInt(Cache::size).sum(); }  // a moment-in-time estimate
}

Read onlyJava 21Every file builds in CI11 files200 lines

Explorer

• Pyall_in_one.py
• lru_cache
• Pybounded_cache.py
• Pycache.py
• Pycommon.py
• Pyentry.py
• Pyeviction_policy.py
• Pylru_policy.py
• Pynode.py
• Pyremoval_cause.py
• Pysharded_cache.py
• Pysynchronized_cache.py

Pyall_in_one.py

all_in_one.pylru_cache/bounded_cache.pylru_cache/cache.pylru_cache/common.pylru_cache/entry.pylru_cache/eviction_policy.pylru_cache/lru_policy.pylru_cache/node.pylru_cache/removal_cause.pylru_cache/sharded_cache.pylru_cache/synchronized_cache.py

all_in_one.py

Read onlyPython 3.12Every file builds in CI11 files224 lines

Explorer

• C#AllInOne.cs
• src
• C#BoundedCache.cs
• C#Entry.cs
• C#ICache.cs
• C#IEvictionPolicy.cs
• C#LruPolicy.cs
• C#Node.cs
• C#RemovalCause.cs
• C#ShardedCache.cs
• C#SynchronizedCache.cs

C#AllInOne.cs

AllInOne.cssrc/BoundedCache.cssrc/Entry.cssrc/ICache.cssrc/IEvictionPolicy.cssrc/LruPolicy.cssrc/Node.cssrc/RemovalCause.cssrc/ShardedCache.cssrc/SynchronizedCache.cs

AllInOne.cs

Read onlyC# · .NET 10Every file builds in CI10 files206 lines

Explorer

• Goall_in_one.go
• Gobounded_cache.go
• Gocache.go
• Goentry.go
• Goeviction_policy.go
• Golru_policy.go
• Gonode.go
• Goremoval_cause.go
• Goremoval_listener.go
• Gosharded_cache.go
• Gosynchronized_cache.go

Goall_in_one.go

all_in_one.gobounded_cache.gocache.goentry.goeviction_policy.golru_policy.gonode.goremoval_cause.goremoval_listener.gosharded_cache.gosynchronized_cache.go

all_in_one.go

Read onlyGo 1.24Every file builds in CI11 files257 lines

Explorer

• TSall-in-one.ts
• src
• TSbounded-cache.ts
• TScache.ts
• TSentry.ts
• TSeviction-policy.ts
• TSlist-node.ts
• TSloading-cache.ts
• TSlru-policy.ts
• TSremoval-cause.ts
• TSremoval-listener.ts

TSall-in-one.ts

all-in-one.tssrc/bounded-cache.tssrc/cache.tssrc/entry.tssrc/eviction-policy.tssrc/list-node.tssrc/loading-cache.tssrc/lru-policy.tssrc/removal-cause.tssrc/removal-listener.ts

all-in-one.ts

Read onlyTypeScript, strictEvery file builds in CI10 files189 lines

Three ideas hold it together:

• Storing values and keeping order are separate jobs. BoundedCache never touches a list, and LruPolicy never sees a value. Each can be tested on its own. The policy is the Strategy pattern.
• Thread safety is a wrapper. The single-threaded cache stays simple. SynchronizedCache adds the lock around any Cache without changing it. That’s the Decorator pattern. Removal listeners are the Observer pattern.
• Callers only see the Cache interface. Sharded, locked or plain, the calling code is the same. To callers, the cache is a simple front door with four methods (a facade).

Stress it

The design works for one thread. But a cache usually lives inside a server, where many threads read and write it at once.

Many threads, and a read that writes

Interviewerminute 27

Many threads share this cache. Reads are 95% of the traffic. What do you do?

What they are testing

The classic trap: whether you notice that a get writes (it moves the node), so a read-write lock is wrong. Then whether you can trade exact LRU for speed, and say so.

The tempting answer is a read-write lock. It lets many readers in at once, but only one writer. Reads are 95% of the traffic, so this sounds perfect.

It’s wrong here, because a get is a write. A hit takes its node out of the list and puts it at the back: four pointer changes. Picture two threads doing that at the same moment, on neighbouring nodes. Each one reads the links, then changes them, and each overwrites part of the other’s work. A node ends up linked twice, or lost. The next eviction follows a broken link.

The clearly correct fix is one lock. Every method, including get, takes the same lock. This is safe, because only one thread at a time touches the map and the list. The cost: threads wait in line, even when they want different keys.

The better fix is sharding. We make, say, 16 independent caches, called shards, each with its own lock. A key’s hash picks its shard, so the same key always goes to the same shard. Two threads only wait for each other when their keys land in the same shard.

Option	How	Exact LRU?	Threads wait when
1. One lock	Every method holds the same lock	Yes	Always: one operation at a time
2. Read-write lock	Gets share a read lock	Breaks	Never, which is the problem
3. Sharding (our choice)	N caches, each with its own lock; the key’s hash picks one	Per shard	Only when keys share a shard
4. Buffered reads (Caffeine)	Gets write “accessed” into a buffer; one thread applies it later	Nearly	Rarely; reads don’t touch the list

JShardedCache.javaPysynchronized_cache.pyC#ShardedCache.csGosynchronized_cache.goTSloading-cache.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// Thread safe by one lock. Note that get() needs the write side too: a hit moves the key in
// the recency list, so a read-write lock would let two "readers" corrupt the list.
class SynchronizedCache<K, V> implements Cache<K, V> {
    private final Cache<K, V> inner;
    private final Object lock = new Object();

    SynchronizedCache(Cache<K, V> inner) { this.inner = inner; }

    public Optional<V> get(K key) { synchronized (lock) { return inner.get(key); } }
    public void put(K key, V value) { synchronized (lock) { inner.put(key, value); } }
    public boolean remove(K key) { synchronized (lock) { return inner.remove(key); } }
    public int size() { synchronized (lock) { return inner.size(); } }
}

// N independent caches, each with its own lock. Threads only wait for each other when their
// keys hash to the same shard. The price: eviction is LRU within a shard, not across the
// whole cache, so the key evicted is "old in its shard", which is close enough for most uses.
class ShardedCache<K, V> implements Cache<K, V> {
    private final List<Cache<K, V>> shards = new ArrayList<>();

    ShardedCache(int capacity, int shardCount, Function<Integer, Cache<K, V>> newShard) {
        int perShard = (capacity + shardCount - 1) / shardCount;  // round up so total >= capacity
        for (int i = 0; i < shardCount; i++) shards.add(new SynchronizedCache<>(newShard.apply(perShard)));
    }

    // The same key always lands in the same shard. floorMod keeps negative hashes in range.
    private Cache<K, V> shard(K key) { return shards.get(Math.floorMod(key.hashCode(), shards.size())); }

    public Optional<V> get(K key) { return shard(key).get(key); }
    public void put(K key, V value) { shard(key).put(key, value); }
    public boolean remove(K key) { return shard(key).remove(key); }
    public int size() { return shards.stream().mapToInt(Cache::size).sum(); }  // a moment-in-time estimate
}

Why is this correct? Each shard is the stage 4 cache behind one lock. So every operation on a shard, including the node moves inside a get, runs alone. A key always goes to the same shard, so all operations on one key meet the same lock. Shards share nothing, so there’s nothing to keep in step between them.

What does it cost? We lose the order across the whole cache. The evicted key is the least recently used in its shard, not overall. With a good hash and many keys per shard, that’s close to the overall answer. The size limit is also split: if many popular keys land in one shard, it evicts while other shards sit half empty. And size() across shards is only an estimate, since shards change while we add them up.

Common mistake

A concurrent map plus a separately locked list

Making the map thread-safe and the list thread-safe separately still lets a thread find a node in the map that another thread has just evicted from the list. The map and the list must change together, under one lock (per shard).

Go deeperHow each language does the lock1 min

Java uses a synchronized block on one lock object per shard. Python needs a lock too. The GIL makes single bytecode steps safe, not a four-pointer unlink. Go uses a sync.Mutex per shard (not RWMutex, for the same reason as above). C# 13’s Lock type does the same.

TypeScript in one Node process has no threads, so there’s no race on the list. Its stage 5 solves the problem Node does have: ten requests missing the same key at once would each call the slow backend. A single flight map makes the nine latecomers wait for the first load.

How many shards? A common start is a small multiple of the number of CPU cores, such as 16 or 64. More shards mean less waiting, but each shard gets a smaller share of the size limit, so the LRU order inside each one gets rougher. Use a power of two, so picking a shard is a quick bit mask of the hash. And spread the hash bits first: some hash codes differ only in their high bits, which would send every key to the same few shards.

Go deeperTen threads miss the same key at once1 min

Each thread calls the backend for the same key, so one slow value causes ten slow calls. This is called a thundering herd. The fix is single flight: the first miss registers “I’m loading this key”, and the other nine wait for that load instead of starting their own. Java’s ConcurrentHashMap.computeIfAbsent with a future as the value, Go’s singleflight package, and the TypeScript stage 5 above all do this.

One rule: never hold the cache’s lock while loading. One slow load would block every other key.

Go deeperHow Caffeine avoids a lock on every read1 min

In Caffeine, a popular Java cache, reads don’t touch the list at all. A get looks up a concurrent hash map (no lock) and writes “this key was used” into a small buffer. When the buffer fills, one thread takes the lock and applies all those uses to the list at once. If a buffer is full, the note is simply dropped. So the order is slightly approximate, and reads almost never wait.

Caffeine also uses a smarter rule than LRU, called Window TinyLFU. It keeps a compact count of how often keys are used, which protects popular keys from one-off reads.

How you’d prove it works

Each test protects one promise:

• The least recently used key is evicted, and a get changes which key that is.
• Updating an existing key never evicts, and makes it the most recent.
• A cache of size 1 works (the sentinel’s edge cases).
• An expired entry reads as a miss, and the listener hears “expired”. This uses a test clock.
• Many threads using a sharded cache never cause errors and never go over the size limit.

The thread test runs 16 threads over 5,000 keys with a 1,000-entry cache, so evictions happen all the time. It checks rules, not exact values: nothing threw, and the size never went over the limit. When we took the lock out, the symptom wasn’t an error but a hang: the broken links sent a thread around the list forever. So run the test with a time limit, and a hang shows up as a failure.

Go deeperThe tests in five languages2 min

JTestClock.javaPytest_clock.pyC#Program.csGotest_clock.goTSexample.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// A clock the test moves by hand, so expiry is tested without sleeping.
static class TestClock extends Clock {
    Instant now = Instant.parse("2026-01-01T00:00:00Z");
    public Instant instant() { return now; }
    public ZoneId getZone() { return ZoneOffset.UTC; }
    public Clock withZone(ZoneId zone) { return this; }
}

TestClock clock = new TestClock();

BoundedCache<String, Integer> lru(int capacity) {
    return new BoundedCache<>(capacity, Duration.ofMinutes(5), new LruPolicy<>(), clock);
}

@Test
void evictsTheLeastRecentlyUsedKey() {
    var c = lru(2);
    c.put("a", 1);
    c.put("b", 2);
    c.get("a");     // a is now more recent than b
    c.put("c", 3);  // full: b goes, not a
    assertTrue(c.get("b").isEmpty());
    assertEquals(Optional.of(1), c.get("a"));
}

@Test
void updatingAKeyNeverEvicts() {
    var c = lru(2);
    c.put("a", 1);
    c.put("b", 2);
    c.put("a", 10);  // same key: replace, and a becomes most recent
    assertEquals(2, c.size());
    assertEquals(Optional.of(10), c.get("a"));
    assertEquals(Optional.of(2), c.get("b"));
}

@Test
void expiredEntriesReadAsMissesAndSayWhy() {
    var c = lru(2);
    List<RemovalCause> causes = new ArrayList<>();
    c.subscribe((k, v, cause) -> causes.add(cause));
    c.put("a", 1);
    clock.now = clock.now.plus(Duration.ofMinutes(5));  // exactly the TTL: expired
    assertTrue(c.get("a").isEmpty());
    assertEquals(List.of(RemovalCause.EXPIRED), causes);
}

@Test
void concurrentUseNeverBreaksTheListOrOverfills() throws Exception {
    // 8 shards of 125: total capacity 1,000. 16 threads hammer 5,000 keys.
    Cache<Integer, Integer> c = new ShardedCache<>(1_000, 8,
            n -> new BoundedCache<>(n, Duration.ofHours(1), new LruPolicy<>(), clock));
    ExecutorService pool = Executors.newFixedThreadPool(16);
    List<Future<?>> work = new ArrayList<>();
    for (int t = 0; t < 16; t++) {
        int seed = t;
        work.add(pool.submit(() -> {
            Random r = new Random(seed);
            for (int i = 0; i < 50_000; i++) {
                int k = r.nextInt(5_000);
                if (c.get(k).isEmpty()) c.put(k, k);
            }
        }));
    }
    for (Future<?> f : work) f.get();  // rethrows if a corrupted list threw anywhere
    pool.shutdown();
    assertTrue(c.size() <= 1_000);
}

Go deeperEvery edge case, and where it is handled2 min

Case	What happens	Where
Size limit 0 or negative	Rejected when the cache is created	constructors
Size limit 1	Every new key evicts the previous one	eviction before insert
Put an existing key	Value replaced, key becomes most recent, no eviction	put, REPLACED
Get a key that expired	Miss; entry removed; listener told EXPIRED	get
Expired entry never read	Holds its place until evicted (lazy expiry)	by design
Null value	Rejected (Java, C#); a miss and a null would look the same	put
Listener throws	Logged; the cache is already consistent	notify
Listener calls back into the cache	Runs under the shard lock; must be quick and must not block	the listener’s job
Negative hash code	floorMod or an unsigned cast keeps the shard number in range	ShardedCache.shard
Clock moves backwards	Monotonic clock in production; a fake clock in tests	Clock

Wrap up

The decisions, and what each one costs

Decision	We chose	We gave up
Structure	Hash map to nodes of a doubly linked list, one sentinel	Around 70 bytes extra per entry
Eviction rule	An EvictionPolicy strategy	A second map of the same keys
When to evict	Before inserting the new key	Nothing; safe for every rule
Expiry	Lazy, checked on read, with a monotonic clock passed in	Expired entries stay until read or evicted
Removal events	Listeners told the reason	Listeners run under the lock and must be quick
Thread safety	A lock per shard, as a wrapper	Exact LRU across the whole cache
Read-write lock	Rejected	Nothing: a get writes

Go deeperGenuinely different designs, and when to pick them2 min

CLOCK (second chance). Entries sit in a circle, each with a “used recently” flag. A get only sets the flag, with no list changes, so reads are cheap and easy to share between threads. To evict, a pointer moves around the circle, clearing flags, until it finds one already clear. It’s close to LRU, and operating systems use it to decide which memory pages to drop.

Window TinyLFU (Caffeine). A small LRU area for new entries, a main area split into “on trial” and “protected” parts, and a compact frequency count that decides whether a newcomer deserves to replace a victim. It resists one-off scans that would empty a plain LRU, and gets clearly higher hit rates on real traffic.

Just use the library. LinkedHashMap for single-threaded Java, Caffeine for Java with threads, functools.lru_cache for Python functions. In production, building your own LRU is rarely right. The interview asks so it can see how you think about the structure.

How to spend 45 minutes

• 0 to 3. Entries or bytes, threads, expiry, other rules.
• 3 to 5. The promises. Name “O(1) for get, put and eviction together” as the hard one.
• 5 to 25. The queue version and its O(n). Then the map and list (code it fully). Then the policy split, then expiry and listeners.
• 25 to 27. Walk through the full diagram: storing versus ordering, thread safety as a wrapper.
• 27 to 36. Why a get is a write, one lock, then sharding, and single flight for misses.
• 36 to 45. One extension, usually size in bytes or LFU, then your own questions.

If time is short, describe the listener in a sentence. Always code stage 2 completely. It’s the part that gets checked line by line.

Follow-up questions

Interviewerminute 36

Some of our values are 1 KB and some are 5 MB. A limit by count doesn’t work.

What they are testing

Whether the change lands in one place (a weight per entry, and a loop in eviction), and whether you spot the new edge case: one entry bigger than the whole cache.

Most extensions fit into one place:

Extension	What changes	Touches BoundedCache?
LFU or FIFO	A new EvictionPolicy	No
Size in bytes	A weigher function; evict in a loop until the new entry fits; refuse oversize entries	Yes, eviction only
Loading on a miss	A LoadingCache wrapper with single flight	No
TTL per entry	put(key, value, ttl); Entry already stores its own expiry	One overload
Metrics	Counters in a wrapper; evictions from a removal listener	No
Across machines	A different system: consistent hashing across nodes (see the caching building block)	Not this class

Go deeperAdding a size limit in bytes, step by step2 min

Start with what changes. Today, the cache counts entries, and “full” means “count equals the limit”. With values from 1 KB to 5 MB, ten entries could be 10 KB or 50 MB. So we count bytes instead.

1. A weigher. The cache is given a small function that returns the size of a value, for example value.length. That’s the only new class, and the caller writes it, because only the caller knows how big their values are.
2. A running total. The cache keeps totalWeight. A put adds the new entry’s weight, and every removal (evicted, expired, replaced, removed) subtracts the old one. Replacing a value counts both: take away the old weight, add the new one.
3. Evict in a loop. One new 5 MB value may need several small values to leave. So instead of “evict one if full”, put says “while the total plus the new weight is over the limit, evict the policy’s victim”.
4. Refuse what can never fit. If one value is bigger than the whole cache, the loop would evict everything and still fail. So we check that first and refuse the value, leaving the cache as it was.

Notice what stayed the same. The policy still answers “who’s next?”, and doesn’t care about bytes. The listeners still hear “evicted” for each value the loop removes. Only the eviction step in BoundedCache changed.

Go deeperAdding loading on a miss, step by step2 min

Today, the caller handles a miss: it asks the cache, gets nothing, loads the value from the database, and puts it in. Every caller repeats those three steps, and every caller can get them slightly wrong. A loading cache does it for them: get(key) loads the value itself on a miss.

We don’t change BoundedCache for this. We wrap it, the same way SynchronizedCache wraps it for locking.

1. A loader. The wrapper is given one function, load(key), that fetches a value from the slow place. The caller writes it once, when the cache is built.
2. Get or load. get(key) first asks the inner cache. On a hit, it returns the value. On a miss, it calls the loader, puts the result in the inner cache, and returns it.
3. One load per key. This is where the thundering herd from earlier comes back. If ten threads miss the same key at once, they must not start ten loads. The wrapper keeps a map of loads in progress. The first thread adds “loading k” and starts the load. The other nine find that entry and wait for its result. When the load finishes, the entry is removed.
4. Failures. If the load fails, all ten waiting threads get the same error, and nothing goes into the cache. The next request tries again. Caching a failure by accident would hide the database for the whole TTL.

The rule from the concurrency section still holds: the wrapper never holds a shard’s lock while the loader runs. The map of loads in progress has its own small lock, held only for a moment.

Go deeperBuilding LFU in O(1), step by step3 min

LFU evicts the key used the fewest times. The obvious version sorts keys by count, which costs O(log n) per access. Here’s how to keep it O(1).

The idea is to group keys by their count. We keep three things:

1. A count for each key. For example, a has been used 3 times.
2. A list for each count. All keys used exactly once are in list 1, keys used twice are in list 2, and so on. Each list is a doubly linked list in order of use, just like our LRU list.
3. The smallest count in use. We call it minCount.

Now each policy method is a few pointer changes:

• accessed(key). The key’s count goes from c to c + 1. We take its node out of list c (O(1), since we have the node) and put it at the back of list c + 1. If list c is now empty and c was minCount, then minCount becomes c + 1.
• added(key). A new key has count 1. It goes to the back of list 1, and minCount becomes 1.
• victim(). The front of list minCount: among the keys used the fewest times, the one used longest ago.

Why does minCount only ever need to go up by one, or reset to 1? Because an access moves exactly one key up by exactly one count. And a new key always starts at 1. So we never search for the smallest count.

This is also why stage 3 evicts before adding. The newcomer would sit in list 1, as the most recent key there. If eviction ran after adding, and list 1 held only the newcomer, the victim would be the key we just added.

Go deeperTwo more follow-up questions1 min

Interviewer asksA batch job reads every key once and flushes the whole cache. Fix it.

That’s LRU’s known weakness: one pass over many keys evicts everything that was popular. Options: segmented LRU (new entries start in an “on trial” part and only move to the “protected” part on a second hit), or an admission filter like TinyLFU that refuses newcomers used less often than the victim. Or give the batch job its own cache.

Interviewer asksHow would you measure whether the cache is worth it?

Hit rate, but weighted by cost: a hit that saves a 200 ms database call matters more than one that saves 1 ms. Track hits, misses, evictions by reason, and load time. If most removals are evictions and the hit rate is low, the cache is too small for the keys people actually use.

Further reading

• Strategy pattern, Decorator pattern, Observer pattern
• Thread safety basics, Caching
• Design a rate limiter, which also keeps per-key state that must be evicted
• Caffeine: Design, buffered reads and Window TinyLFU
• Einziger, Friedman, Manes: TinyLFU, the admission policy behind Caffeine
• Redis: Key eviction, approximated LRU by sampling