Design an LRU Cache (Low Level Design)

Problem Statement

Think of your study desk. It only fits three books. You have a whole shelf of books, but the desk is small. When you want a fourth book, something has to go back to the shelf. Which one? Most people pick the one they have not touched for the longest time. That is the whole idea of an LRU cache. LRU stands for "least recently used".

In software, the desk is memory and the shelf is something slow, like a database or a web call. We keep the answers we used lately in a small, fast place. When the place is full and we need room, we throw out the one nobody has asked for in the longest time.

The classic interview version: build a cache with a fixed capacity, where both get(key) and put(key, value) take constant time, O(1). That means the time does not grow when the cache grows.

Questions to Ask First

Requirements

• get(key) returns the value if present and marks the key as most recently used.
• put(key, value) stores the value. If the key exists, update it. If the cache is full, throw out the least recently used key first.
• Both are O(1).
• Works with any key type and value type.
• The "who should I throw out" rule can be swapped without rewriting the cache.
• A version that is safe when several threads use it at once.

Core Classes

Two jobs are kept apart on purpose. PolicyCache stores the values and knows the capacity. The policy only tracks the keys and their order, and answers one question: "who goes?".

How the Design Works

Why a map and a list together

Two simple ideas, and each one fails alone.

A hash map finds a key in O(1). But it has no idea which key is the oldest.

A list can keep keys in order of use: newest at the front, oldest at the back. Throwing out the oldest is easy, it is the last item. But finding a key inside a list means walking along it, which is O(n).

So we use both. The map says "key to node" and the list says "node order". With a map entry you jump straight to the node in the list. Then moving it to the front takes a few pointer changes. It does not matter if the list has ten items or ten million.

Why a doubly linked list, one with links in both directions? To take a node out of the middle, you need to tell its left neighbour "your next is now my next". With a single direction you do not know who the left neighbour is, and walking to find out costs O(n). Two directions fix that.

The node and the list

final class Node<K> {

    final K key;
    Node<K> prev;
    Node<K> next;

Notice the node stores the key. This feels redundant until you evict: you take the last node off the list, and now you must also remove that key from the map. Without the key in the node you would not know which one.

The list has two dummy nodes, one at each end. They hold nothing. Their job is to make sure every real node always has a neighbour on both sides, so the code never needs if (prev == null) checks.

void addFirst(Node<K> node) {
    node.prev = head;
    node.next = head.next;
    head.next.prev = node;
    head.next = node;
}

void remove(Node<K> node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null;
}

A good habit for interviews: draw four boxes and four arrows on paper, and do addFirst by hand once. Order of the four lines matters. If you change head.next first, you lose the old first node.

The policy interface

The cache does not decide who gets thrown out. It reports events and asks the policy:

public interface EvictionPolicy<K> {

    void onInsert(K key);

    void onAccess(K key);

    void onRemove(K key);

    /** Picks the key to throw out, forgets it, and returns it. */
    K evict();
}

LruPolicy is the list and the map from above, put together. Each event is two or three lines:

@Override
public void onAccess(K key) {
    Node<K> node = nodes.get(key);
    order.remove(node);
    order.addFirst(node);
}

@Override
public K evict() {
    Node<K> last = order.removeLast();
    nodes.remove(last.key);
    return last.key;
}

The honest cost of this split: there are now two hash maps, one in the cache (key to value) and one in LruPolicy (key to node). A one class LruCache could store key, value and links in the same node and use a single map. That would use less memory. I chose the split because it lets you plug in other policies, which interviewers love to ask about. If the question is only "implement LRU", the one class version is fine and shorter.

The cache

@Override
public void put(K key, V value) {
    Objects.requireNonNull(key, "key");
    Objects.requireNonNull(value, "value");
    if (values.containsKey(key)) {
        values.put(key, value);
        policy.onAccess(key);
        return;
    }
    if (values.size() == capacity) {
        K victim = policy.evict();
        values.remove(victim);
        onEvict.accept(victim);
    }
    values.put(key, value);
    policy.onInsert(key);
}

Three paths. The key already exists: update the value and count it as a use. The cache is full: evict first, then insert. Otherwise: just insert. Updating an existing key must never evict anything, and many first tries get that wrong.

get is short, and the one thing to remember is that it changes state, it does not just read:

V value = values.get(key);
if (value == null) {
    return Optional.empty();
}
policy.onAccess(key);
return Optional.of(value);

Null values are rejected in put, so a null from the map always means "not here". There is also an onEvict callback, which is handy for the demo and for real life too (closing a file, updating a counter).

FIFO shows that the policy really is swappable

FIFO means first in, first out: the oldest inserted key goes, even if you used it a minute ago. It is the same interface, and almost all methods are empty:

@Override
public void onAccess(K key) {
    // Nothing to do. That is the whole difference from LRU.
}

That is the strategy pattern at work. The cache has no idea which policy it got.

Thread safety

If two threads call put at the same moment on a plain PolicyCache, bad things happen. Each put is many small steps: check the size, evict, add to the map, move a node. When two threads mix their steps, the list can point at the wrong nodes and the map and list stop agreeing.

I tried it. I ran 8 threads with 20,000 random operations each on a capacity 100 cache with no lock. On every one of 5 runs it threw NullPointerException in several threads, and the final size was between 275 and 409 for a cache that should never go above 100. So this is not a theory.

The simplest fix is one lock around everything:

@Override
public synchronized Optional<V> get(K key) {
    return inner.get(key);
}

@Override
public synchronized void put(K key, V value) {
    inner.put(key, value);
}

LockedCache wraps any Cache, so the single threaded code stays clean and easy to test. It is a decorator: same interface on the outside, extra behaviour (the lock) added around it.

Here are the other two options, and why I would not start with them.

So which is easier to get right? The single lock, by a long way. With ConcurrentHashMap it looks safe and is not, which is worse than looking unsafe. Reach for it only if you are ready to also design how the order list gets updated safely. Real libraries that do this (Caffeine in Java is the well known one) write reads into a buffer and update the order later in batches. That is a lot of careful work.

If one lock becomes the bottleneck, the next step is not clever tricks. Split the cache into, say, 16 small caches, pick one by key.hashCode() % 16, and give each its own lock. Threads touching different parts no longer block each other. The price is that "least recently used" is now per part, not global.

TTL as a follow up

TTL means time to live: an entry dies after some seconds even if the cache is not full. I did not build it, but here is how I would, in a sketch (not in the repo):

record Entry<V>(V value, long expiresAtMillis) { }

// in get:
Entry<V> entry = values.get(key);
if (entry == null || clock.millis() >= entry.expiresAtMillis()) {
    remove(key);          // lazy: clean up only when somebody asks
    return Optional.empty();
}

Three points. First, check lazily on get, so no extra thread is needed for correctness. Second, expired entries that nobody asks for still sit in memory, so add a small cleanup that runs now and then (or checks the oldest few entries on each put). Third, do not call System.currentTimeMillis() directly. Pass in a Clock so a test can move time forward without waiting.

Patterns Used and Why

Strategy. EvictionPolicy is the strategy. LruPolicy and FifoPolicy are two versions. PolicyCache is the only user. A future LfuPolicy (least frequently used) is a new class and nothing else changes.

Decorator. LockedCache implements Cache and holds another Cache. It adds a lock and nothing else. Later you could add a StatsCache that counts hits and misses in the same way.

That is all. I did not add a Singleton, a Factory or a Builder, because nothing here asks for them.

Walk Through One Full Example

A cache with capacity 3. The list below shows the usage order from newest (left) to oldest (right).

put A         A
put B         B A
put C         C B A
get A         A C B        A moves to the front
put D         full! the last one, B, goes.   D A C

Real output of Main, first for LRU and then for FIFO with the same steps:

== LRU, capacity 3 ==
get A -> apple
put D
   evicted B
get A -> apple
get B -> miss
get C -> cherry
get D -> date

== FIFO, capacity 3, same steps ==
get A -> apple
put D
   evicted A
get A -> miss
get B -> banana
get C -> cherry
get D -> date

The only thing that changed is the policy object we passed in. In LRU, reading A saved it, and B (the quiet one) was thrown out. In FIFO, reading A did nothing, and A, the oldest insert, was thrown out.

Then updating and removing:

== Updating and removing ==
tea = 12, size = 1
after remove: tea = -1, size = 0

Putting tea twice leaves one entry with the newer price, and remove empties it.

Finally the thread test, 8 threads and 160,000 operations through the LockedCache:

== 8 threads share one LockedCache (capacity 100) ==
160000 operations done, size = 100, within capacity: true

To be fair, a test like this can show a bug but it cannot prove there is none. The no lock run above is the one that taught me something.

Edge Cases

• Capacity 1. Every new key evicts the previous one. Works.
• Capacity 0 or negative. Rejected in the constructor.
• put on an existing key. Updates the value and moves it to the front. No eviction.
• get on a missing key. Empty Optional, nothing changes.
• Null key or value. Rejected in put.
• Evicting from an empty list. Cannot happen through the cache (capacity is at least 1), and the list throws IllegalStateException if someone does it by mistake.
• The onEvict callback runs inside the lock in LockedCache. A slow callback blocks everyone. Keep it fast.

Follow Up Questions an Interviewer May Ask

"How would you add LFU?"

LFU evicts the key used the fewest times. The same EvictionPolicy interface works: onAccess adds one to the count, and evict picks the lowest count. For O(1), keep a map from count to a group of keys, plus the current lowest count. Ties are usually broken by LRU.

"Why not use LinkedHashMap?"

You can. LinkedHashMap with access order turned on and removeEldestEntry overridden is an LRU cache in about ten lines. In real work, use that. In an interview, the point is to show you know what is inside, so building the list yourself is the expected answer. I would mention it first, then say "but let me build it by hand".

"How do you make it faster for many threads?"

Shard it into several caches, each with its own lock (see above). Or use a library like Caffeine.

"How would you add expiry?"

See the TTL section: store the expiry time, check on get, clean up now and then, use a Clock.

"What if size should be in bytes, not items?"

Give each entry a weight. Keep a running total. On put, evict in a loop until the total fits. One put can now evict several keys.

"How would you build this as a distributed cache?"

That is a different problem: many machines, splitting keys between them (consistent hashing), what happens when a machine dies. Redis does the single machine version with the same ideas. I would say that and offer to go to the system design side.

Common Mistakes

Using a singly linked list. Removal from the middle becomes O(n), and the whole point is lost.

Forgetting to store the key in the node. You cannot remove the evicted entry from the map.

Evicting from the list but not from the map (or the reverse). The two drift apart and you get ghost entries or a cache that grows. Here the cache removes the victim from its own map right after policy.evict().

Not treating get as a use. Then it is not an LRU cache.

Evicting when updating an existing key.

Wrapping a ReadWriteLock around get and calling it concurrent. It mutates the list.

Saying "I used ConcurrentHashMap, so it is thread safe". Each call is safe. The sequence of calls is not.

Forgetting the dummy nodes and then writing null checks in six places.

Where This Is Simplified

• Capacity counts items, not memory.
• One lock, so threads wait in line. No sharding.
• The LruPolicy has its own map, so keys are stored twice.
• No TTL, no stats (hits, misses), no listener beyond the simple eviction callback.
• Null values are rejected, so you cannot cache "this key exists but has no value".
• No clear(), contains() or iteration.

How to Run

From the repo root (Java 17 or newer):

javac --release 17 -d /tmp/lrucache-out $(find src/LLD/LruCache/src -name '*.java')
java -cp /tmp/lrucache-out com.blueprint.lld.lrucache.Main

The code lives under src/LLD/LruCache/src/com/blueprint/lld/lrucache/.