Build an LRU + TTL Cache

Build an LRU + TTL Cache

"Just put a cache in front of it" is the most common system-design reflex — and the follow-up is always "how does the cache decide what to keep?" This project builds the workhorse answer: an LRU cache with per-entry TTL, with O(1) get and put. The O(1) part is the whole interview: it's why the answer is "a hash map plus a doubly-linked list," and being able to say why both is what separates a real answer from a memorized one.

Feel the policy first

Before coding, use the debugger below to see why LRU (not FIFO, not always LFU) is the default — and where it fails (a scan bigger than the cache). Step the workloads and predict each eviction.

The spec

• get(k): O(1). Returns the value if present and not expired, and marks it most-recently-used. Expired → miss (and lazily evicted).
• put(k,v): O(1). Inserts/updates as most-recently-used; if over capacity, evicts the least-recently-used entry.
• TTL: each entry expires after a fixed duration; expired entries never count as hits.
• Thread-safe under concurrent callers (one lock is fine to start).

Why a hash map and a linked list

Neither structure alone is O(1) for both operations. A hash map gives O(1) lookup but has no order. A doubly-linked list gives O(1) reorder/evict at the ends but O(n) lookup. Combine them: the map stores key → *node, the list keeps recency order (head = most-recent, tail = least-recent). get = map lookup + unlink/relink at head (O(1)); evict = drop the tail (O(1)). That pairing is the canonical answer.

Reference — LRU+TTL (Go)

type node struct{ key, val string; exp time.Time; prev, next *node }

type Cache struct {
    mu       sync.Mutex
    cap      int
    ttl      time.Duration
    m        map[string]*node
    head, tail *node        // sentinels: head.next = MRU, tail.prev = LRU
}

func New(cap int, ttl time.Duration) *Cache {
    h, t := &node{}, &node{}; h.next, t.prev = t, h
    return &Cache{cap: cap, ttl: ttl, m: map[string]*node{}, head: h, tail: t}
}
func (c *Cache) unlink(n *node){ n.prev.next = n.next; n.next.prev = n.prev }
func (c *Cache) toFront(n *node){ n.prev = c.head; n.next = c.head.next; c.head.next.prev = n; c.head.next = n }

func (c *Cache) Get(k string) (string, bool) {
    c.mu.Lock(); defer c.mu.Unlock()
    n, ok := c.m[k]
    if !ok { return "", false }
    if time.Now().After(n.exp) {            // expired → lazy evict
        c.unlink(n); delete(c.m, k); return "", false
    }
    c.unlink(n); c.toFront(n)               // mark most-recently-used
    return n.val, true
}
func (c *Cache) Put(k, v string) {
    c.mu.Lock(); defer c.mu.Unlock()
    if n, ok := c.m[k]; ok {
        n.val, n.exp = v, time.Now().Add(c.ttl); c.unlink(n); c.toFront(n); return
    }
    n := &node{key: k, val: v, exp: time.Now().Add(c.ttl)}
    c.m[k] = n; c.toFront(n)
    if len(c.m) > c.cap {                    // evict LRU (tail)
        lru := c.tail.prev; c.unlink(lru); delete(c.m, lru.key)
    }
}

Reference — LRU+TTL (Java)

// The pragmatic Java answer: LinkedHashMap in access-order mode is an LRU in ~10 lines.
public final class LruTtlCache<K, V> {
    private record Entry<V>(V val, long expiresAt) {}
    private final int cap; private final long ttlMs;
    private final LinkedHashMap<K, Entry<V>> map;

    public LruTtlCache(int cap, long ttlMs) {
        this.cap = cap; this.ttlMs = ttlMs;
        this.map = new LinkedHashMap<>(16, 0.75f, true) {   // true = access-order
            protected boolean removeEldestEntry(Map.Entry<K, Entry<V>> e) {
                return size() > LruTtlCache.this.cap;         // evict LRU automatically
            }
        };
    }
    public synchronized Optional<V> get(K k) {
        Entry<V> e = map.get(k);                              // access-order bumps recency
        if (e == null) return Optional.empty();
        if (System.currentTimeMillis() > e.expiresAt()) { map.remove(k); return Optional.empty(); }
        return Optional.of(e.val());
    }
    public synchronized void put(K k, V v) {
        map.put(k, new Entry<>(v, System.currentTimeMillis() + ttlMs));
    }
}

Interviewers love that you know LinkedHashMap(…, true) + removeEldestEntry is a ready-made LRU — and that you can also build it by hand from a map + DLL when asked to (the Go version), which is the real test.

Tests to write

• Eviction order: cap 2; put A,B, get A, put C → B is evicted (A was used more recently). This is the exact behaviour you predicted in the debugger.
• TTL expiry: put with short TTL, sleep past it, get → miss and the entry is gone.
• Recency on get: get must count as a use (move-to-front) — verify a gotten key survives an eviction its access saved it from.
• Concurrency: hammer get/put from many threads; assert no corruption and size never exceeds cap (run Go with -race).

Extensions

• Active expiry: a background sweeper (or a min-heap by expiry) so dead entries don't waste memory until they're touched.
• Sharded locks: split into N shards each with its own lock to cut contention (what Guava/Caffeine do).
• Switch the policy: make eviction pluggable and drop in LFU or W-TinyLFU (Caffeine's scan-resistant policy) — recall from the debugger when each wins.
• Distributed: this is the node-local tier; put Redis behind it and you have the classic two-tier cache — now reason about invalidation across tiers.

What you've mastered when this is done

• You can justify map + doubly-linked list for O(1) get/put and explain why neither alone suffices.
• You can build LRU both by hand (map+DLL) and via LinkedHashMap access-order, and add correct TTL semantics.
• You can pick the eviction policy for a workload (LRU vs LFU vs scan-resistant) and defend it — the judgment the debugger drilled.

I just read a lesson on **Build an LRU + TTL Cache** (Hands-On Builds) and want to truly understand it. Explain Build an LRU + TTL Cache from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Build an LRU + TTL Cache** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Build an LRU + TTL Cache** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Build an LRU + TTL Cache** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.