LOW LEVEL DESIGN · MACHINE CODING · MEDIUM · 5 OF 42

Design an In-Memory Cache with TTL and LRU/LFU Eviction in Java

A bounded key-value cache designed and coded: the API, entries with expiry times, eviction as a Strategy with O(1) LRU (an access-ordered set) and O(1) LFU (frequency buckets and a minimum), lazy plus background TTL expiry, the put and get flows, why a read-write lock does not help, one lock versus striping, removal listeners, an injectable clock for tests and the follow-ups, with full Java 17 code.

Patterns usedObserverStrategyFactory methodIterator

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 19

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 280 lines, with a small main() demo. Save it as InMemoryCache.java, then run javac InMemoryCache.java && java InMemoryCache.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.LongAdder;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.LongSupplier;

/**
 * A bounded in-memory key-value cache with per-entry TTL and a pluggable eviction policy (LRU or LFU),
 * all operations O(1), safe to share between threads.
 */
public class InMemoryCache<K, V> {

    // ---------- eviction strategy ----------
    /** Tracks keys and picks the victim when the cache is full. Not thread-safe: the cache holds the lock. */
    interface EvictionPolicy<K> {
        void onPut(K key);

        void onGet(K key);

        void onRemove(K key);

        K victim();
    }

    /** Least recently used: a LinkedHashSet keeps keys in access order; the first one is the oldest. */
    static final class LruPolicy<K> implements EvictionPolicy<K> {
        private final LinkedHashSet<K> order = new LinkedHashSet<>();

        public void onPut(K key) { onGet(key); }

        public void onGet(K key) {
            order.remove(key);
            order.add(key); // move to the newest end
        }

        public void onRemove(K key) { order.remove(key); }

        public K victim() { return order.iterator().next(); }
    }

    /** Least frequently used, ties broken by least recent: frequency buckets plus the minimum frequency. */
    static final class LfuPolicy<K> implements EvictionPolicy<K> {
        private final Map<K, Integer> freq = new HashMap<>();
        private final Map<Integer, LinkedHashSet<K>> buckets = new HashMap<>();
        private int minFreq;

        public void onPut(K key) {
            if (freq.containsKey(key)) {
                onGet(key);
                return;
            }
            freq.put(key, 1);
            buckets.computeIfAbsent(1, f -> new LinkedHashSet<>()).add(key);
            minFreq = 1;
        }

        public void onGet(K key) {
            int f = freq.get(key);
            freq.put(key, f + 1);
            LinkedHashSet<K> b = buckets.get(f);
            b.remove(key);
            if (b.isEmpty()) {
                buckets.remove(f);
                if (minFreq == f) minFreq = f + 1;
            }
            buckets.computeIfAbsent(f + 1, x -> new LinkedHashSet<>()).add(key);
        }

        public void onRemove(K key) {
            Integer f = freq.remove(key);
            if (f == null) return;
            LinkedHashSet<K> b = buckets.get(f);
            b.remove(key);
            if (b.isEmpty()) buckets.remove(f);
            if (f == minFreq && !buckets.isEmpty() && !buckets.containsKey(f))
                minFreq = buckets.keySet().stream().min(Integer::compare).orElse(1); // rare: explicit delete
        }

        public K victim() { return buckets.get(minFreq).iterator().next(); }
    }

    enum Policy { LRU, LFU }

    /** Factory: callers name a policy, the cache gets a fresh instance. */
    static <K> EvictionPolicy<K> policyFor(Policy p) {
        return switch (p) {
            case LRU -> new LruPolicy<>();
            case LFU -> new LfuPolicy<>();
        };
    }

    /** Observer: metrics or a write-behind store can hear about evictions and expiries. */
    interface RemovalListener<K, V> { void onRemoval(K key, V value, String cause); }

    private record Entry<V>(V value, long expiresAt) {
        boolean expired(long now) { return expiresAt > 0 && now >= expiresAt; }
    }

    // ---------- the cache ----------
    private final int capacity;
    private final long defaultTtlMillis;
    private final Map<K, Entry<V>> map = new HashMap<>();
    private final EvictionPolicy<K> policy;
    private final LongSupplier clock;
    private final ReentrantLock lock = new ReentrantLock(); // a get changes recency, so reads need it too
    private final List<RemovalListener<K, V>> listeners = new CopyOnWriteArrayList<>();
    private final LongAdder hits = new LongAdder(), misses = new LongAdder();

    InMemoryCache(int capacity, long defaultTtlMillis, Policy policy, LongSupplier clock) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
        this.defaultTtlMillis = defaultTtlMillis;
        this.policy = policyFor(policy);
        this.clock = clock;
    }

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

    void put(K key, V value) { put(key, value, defaultTtlMillis); }

    /** ttlMillis = 0 means the entry never expires. */
    void put(K key, V value, long ttlMillis) {
        List<Runnable> events = new ArrayList<>();
        lock.lock();
        try {
            long now = clock.getAsLong();
            if (!map.containsKey(key) && map.size() >= capacity) {
                purgeExpired(now, events); // free expired space before evicting a live entry
                if (map.size() >= capacity) {
                    K victim = policy.victim();
                    removeLocked(victim, "evicted", events);
                }
            }
            map.put(key, new Entry<>(value, ttlMillis > 0 ? now + ttlMillis : 0));
            policy.onPut(key);
        } finally {
            lock.unlock();
        }
        events.forEach(Runnable::run); // call listeners outside the lock
    }

    Optional<V> get(K key) {
        List<Runnable> events = new ArrayList<>();
        Optional<V> out;
        lock.lock();
        try {
            Entry<V> e = map.get(key);
            if (e != null && e.expired(clock.getAsLong())) { // lazy expiry on read
                removeLocked(key, "expired", events);
                e = null;
            }
            if (e == null) {
                misses.increment();
                out = Optional.empty();
            } else {
                hits.increment();
                policy.onGet(key);
                out = Optional.of(e.value());
            }
        } finally {
            lock.unlock();
        }
        events.forEach(Runnable::run);
        return out;
    }

    boolean remove(K key) {
        lock.lock();
        try {
            if (!map.containsKey(key)) return false;
            map.remove(key);
            policy.onRemove(key);
            return true;
        } finally {
            lock.unlock();
        }
    }

    /** Active expiry: a background sweeper calls this so cold expired keys do not hold memory forever. */
    int sweep() {
        List<Runnable> events = new ArrayList<>();
        lock.lock();
        try {
            purgeExpired(clock.getAsLong(), events);
        } finally {
            lock.unlock();
        }
        events.forEach(Runnable::run);
        return events.size();
    }

    int size() {
        lock.lock();
        try {
            return map.size();
        } finally {
            lock.unlock();
        }
    }

    String stats() { return "hits=" + hits.sum() + " misses=" + misses.sum() + " size=" + size(); }

    private void purgeExpired(long now, List<Runnable> events) {
        List<K> dead = new ArrayList<>();
        map.forEach((k, e) -> { if (e.expired(now)) dead.add(k); });
        for (K k : dead) removeLocked(k, "expired", events);
    }

    private void removeLocked(K key, String cause, List<Runnable> events) {
        Entry<V> e = map.remove(key);
        policy.onRemove(key);
        if (e == null) return;
        for (RemovalListener<K, V> l : listeners) events.add(() -> l.onRemoval(key, e.value(), cause));
    }

    // ---------- demo ----------
    public static void main(String[] args) throws InterruptedException {
        AtomicLong now = new AtomicLong(0); // a fake clock makes TTL testable without sleeping

        InMemoryCache<String, String> lru = new InMemoryCache<>(3, 0, Policy.LRU, now::get);
        lru.addListener((k, v, cause) -> System.out.println("  [lru] " + cause + ": " + k));
        lru.put("a", "1");
        lru.put("b", "2");
        lru.put("c", "3");
        lru.get("a"); // a is now the most recent
        lru.put("d", "4"); // evicts b
        System.out.println("LRU has b? " + lru.get("b").isPresent() + ", has a? " + lru.get("a").isPresent());

        InMemoryCache<String, String> lfu = new InMemoryCache<>(3, 0, Policy.LFU, now::get);
        lfu.addListener((k, v, cause) -> System.out.println("  [lfu] " + cause + ": " + k));
        lfu.put("a", "1");
        lfu.put("b", "2");
        lfu.put("c", "3");
        lfu.get("a");
        lfu.get("a");
        lfu.get("b");
        lfu.put("d", "4"); // c was used least: evicted
        System.out.println("LFU has c? " + lfu.get("c").isPresent() + ", has a? " + lfu.get("a").isPresent());

        InMemoryCache<String, String> ttl = new InMemoryCache<>(10, 5_000, Policy.LRU, now::get);
        ttl.addListener((k, v, cause) -> System.out.println("  [ttl] " + cause + ": " + k));
        ttl.put("session:42", "token");
        ttl.put("config", "v7", 0); // never expires
        now.addAndGet(4_000);
        System.out.println("After 4 s: " + ttl.get("session:42").orElse("gone"));
        now.addAndGet(2_000);
        System.out.println("After 6 s: " + ttl.get("session:42").orElse("gone") + ", config "
                + ttl.get("config").orElse("gone"));

        // Eight threads hammer one cache: size never passes capacity and nothing throws.
        InMemoryCache<Integer, Integer> shared = new InMemoryCache<>(100, 0, Policy.LFU, now::get);
        ExecutorService pool = Executors.newFixedThreadPool(8);
        CountDownLatch done = new CountDownLatch(8);
        for (int t = 0; t < 8; t++) {
            int seed = t;
            pool.submit(() -> {
                for (int i = 0; i < 20_000; i++) {
                    int key = (i * 31 + seed * 7) % 500;
                    if (shared.get(key).isEmpty()) shared.put(key, key);
                }
                done.countDown();
            });
        }
        done.await();
        pool.shutdown();
        pool.awaitTermination(5, TimeUnit.SECONDS);
        System.out.println("Shared cache: " + shared.stats());
        if (shared.size() > 100) throw new AssertionError("over capacity");
    }
}

Notes

Requirements

The requirements. Get, put and remove by key. A put can carry its own time to live, or fall back to a default, and an expired entry must never be returned. The cache holds at most N entries; when it is full, a policy chosen at construction, LRU or LFU, picks the victim. Get and put must be constant time, the cache is shared by many threads, and we want hit and miss counts.

Pin down the edge cases. A time to live of zero means the entry never expires. Putting an existing key replaces the value and restarts its clock. If the cache is full but some entries have already expired, drop those before evicting a live one. When two keys tie in LFU, evict the least recently used of them. And capacity counts entries for now; sizing by bytes is a follow-up.

Requirements
  • get(key), put(key, value)
  • put with a TTL, or a default
  • remove(key)
  • capacity: at most N entries
  • full? evict by policy:
  • LRU or LFU, chosen at build
  • expired entries never returned
  • O(1) get and put
  • safe from many threads
  • hit and miss counts
Clarify first
  • TTL of 0?
  • never expires
  • put on an existing key?
  • replace value, reset TTL
  • full but some entries expired?
  • drop expired before evicting
  • LFU tie?
  • least recently used of them
  • capacity by count or bytes?
  • count, bytes later

Entities

Four collaborators do all the work. A hash map from key to entry gives constant-time lookups. An eviction policy tracks the order of keys and names the victim. A clock tells the cache what time it is, injected so tests can fake it. And a lock keeps the map and the policy consistent with each other. Separating the map from the policy is what lets us swap LRU for LFU without touching the cache.

Class diagram

Each map value is a small immutable entry: the value and an absolute expiry time in milliseconds, with zero meaning never. Storing the absolute time, not the duration, makes the expiry check a single comparison against the clock. A replaced value gets a brand new entry, so there is never a half-updated entry for another thread to see.

Entry and fields
record Entry<V>(V value, long expiresAt) {
  boolean expired(long now) {
    return expiresAt > 0
        && now >= expiresAt;
  }
}
Map<K, Entry<V>> map = new HashMap<>()
EvictionPolicy<K> policy
LongSupplier clock
ReentrantLock lock

Strategy: eviction

Eviction is a Strategy. The cache tells the policy about three events, a put, a get and a remove, and asks it one question: who is the victim? LRU, LFU, first in first out, or random eviction all fit the same four methods. The policy is not thread-safe on its own, deliberately, because the cache already holds its lock whenever it calls the policy.

EvictionPolicy<K>
interface EvictionPolicy<K> {
  void onPut(K key);
  void onGet(K key);
  void onRemove(K key);
  K victim();
}

LRU, LFU, FIFO, random:
  same four methods

LRU in O(1)

LRU in constant time is a hash map plus a doubly linked list: on every use, unlink the key and append it at the back; the front is always the least recently used. Java's linked hash set is exactly that pair, so on a get we remove and re-add the key, and the victim is the first element. In the demo, after putting a, b, c and reading a, putting d evicts b. In an interview, offer to write the linked list by hand too.

LruPolicy
LinkedHashSet<K> order

onGet(k): order.remove(k);
          order.add(k)  // to the back
onPut(k): same as onGet
victim(): order.iterator().next()

put a, b, c; get a; put d
  order: b, c, a -> evict b

LFU in O(1)

LFU in constant time is the clever one. Keep each key's use count, and a bucket of keys for each count, where each bucket is ordered by recency. Track the smallest count in use. A new key goes in bucket one and resets the minimum to one. A get moves the key up one bucket, and if it emptied the minimum bucket, the minimum goes up by one. The victim is the oldest key in the minimum bucket, which also breaks ties by recency.

LfuPolicy
Map<K, Integer> freq
Map<Integer, LinkedHashSet<K>> buckets
int minFreq

onPut new: freq 1, bucket 1, min = 1
onGet: move key from bucket f to f+1
  bucket f empty and f == min: min++
victim(): first of buckets[minFreq]
  (oldest in that bucket: LRU tie)

TTL expiry

Expiry happens in two ways. Lazy expiry checks the expiry time on every get and removes a dead entry before answering, so an expired value is never returned and it costs nothing extra. But a key nobody reads would sit in memory forever, so a background sweeper calls sweep every second or so. And when a put finds the cache full, it purges expired entries first, so a live entry is only evicted when it truly has to be.

Two kinds of expiry
  • lazy: get() checks expiresAt
  • and removes a dead entry
  • cost: nothing extra
  • active: a sweeper calls sweep()
  • every second or so
  • frees cold keys nobody reads
  • put when full: purge expired
  • before evicting a live entry
  • big caches: sample, not scan

Flow: put when full

The put flow. Take the lock. If the key is new and the cache is full, first purge expired entries, and if it is still full, ask the policy for a victim and remove it from both the map and the policy. Then store the new entry with its expiry time and tell the policy about the put. Release the lock, and only then call the removal listeners, so a slow listener never holds up other threads.

put(key, value, ttl)
lock
  if new key and size == capacity:
    purgeExpired(now)
    still full? remove(policy.victim())
  map.put(key, new Entry(v, now + ttl))
  policy.onPut(key)
unlock
run queued listener events

Flow: get

The get flow. Under the lock, look up the entry. If it has expired, remove it and treat it as missing. A miss increments the miss counter and returns an empty optional. A hit increments the hit counter and tells the policy, which moves the key to the back for LRU or up a bucket for LFU. Returning an optional instead of null makes the caller handle the miss on purpose.

get(key)
lock
  e = map.get(key)
  if e expired: remove it, e = null
  e == null: misses++, empty
  else: hits++, policy.onGet(key)
unlock
return Optional.of(value) or empty

Concurrency

Concurrency has a trap. It is tempting to use a read-write lock so many readers can get at once. But a get is not read-only: LRU moves the key, LFU bumps its count, and expiry may remove it. So every get needs the write lock, and a read-write lock buys nothing. One plain reentrant lock is correct and simple, and holds for well under a microsecond. Hit and miss counters use LongAdder, which needs no lock at all.

If one lock becomes the bottleneck at very high throughput, there are three standard moves. Stripe the cache into, say, sixteen segments, each with its own map, policy and lock, chosen by the key's hash; the cost is that LRU becomes per segment. Or record gets in a buffer and apply the reordering in batches, which is what production Java caches do. Or approximate: sample five random keys and evict the oldest, as some key-value stores do.

Why not a read-write lock?
  • get() is not read-only:
  • LRU moves the key, LFU bumps
  • its count, expiry may remove
  • so get needs the write lock
  • and a RW lock buys nothing
  • one ReentrantLock: correct,
  • simple, ~100 ns per call
  • LongAdder for stats: no lock
When one lock is not enough
  • striping: 16 segments, each
  • its own map, policy, lock;
  • segment = hash(key) % 16
  • LRU becomes per segment
  • buffer reads: record gets in a
  • queue, apply them in batches
  • sampled eviction: pick the
  • oldest of 5 random keys
  • (approximate, lock-free)

Observer

Removal listeners are the Observer pattern. When an entry is evicted or expires, the cache queues an event with the key, the value and the cause, and runs the listeners after releasing the lock. A metrics listener counts evictions, a write-behind listener saves dirty values to a database, and a debugging listener logs them. The cache never needs to know what any of them do.

Factory

Callers should not construct policy objects themselves, because a policy instance must never be shared between two caches. A small factory maps a policy enum to a fresh instance, so creating a cache reads like a sentence: capacity a hundred, default time to live five seconds, LFU, and the system clock. In a larger codebase this grows into a builder with optional settings like a maximum weight or a loader.

Factory for the policy
enum Policy { LRU, LFU }
static <K> EvictionPolicy<K>
    policyFor(Policy p) {
  return switch (p) {
    case LRU -> new LruPolicy<>();
    case LFU -> new LfuPolicy<>();
  };
}
new InMemoryCache<>(100, 5_000,
    Policy.LFU, System::currentTimeMillis)

Testing

The full code is below the player. The demo checks LRU evicts b, LFU evicts the least used key c, and that a five-second entry is still there after four seconds and gone after six, while a never-expiring key survives. The clock is a long supplier backed by an atomic counter, so the test moves time instantly. Finally eight threads hammer one cache, and it never grows past its capacity.

Run it
[lru] evicted: b
LRU has b? false, has a? true
[lfu] evicted: c
LFU has c? false, has a? true
After 4 s: token
[ttl] expired: session:42
After 6 s: gone, config v7
Shared cache: hits=.. misses=..
  size=100  (8 threads)

Follow-ups

Expect follow-ups. Write LRU without library classes: a hash map pointing into a doubly linked list with sentinel nodes. LRU or LFU? LFU keeps stable hot keys, LRU adapts faster when access patterns shift. Capacity in bytes? Add a weigher function. Many threads missing the same key at once? Keep one loading future per key so only one loads. And distributing it across machines is consistent hashing, covered in the system design track.

Follow-ups to expect
  • write LRU without libraries?
  • map + doubly linked list
  • LRU vs LFU: when?
  • LFU for stable hot keys,
  • LRU for shifting access
  • capacity in bytes? a weigher
  • thundering herd on a miss?
  • one loader per key (futures)
  • distributed? consistent hashing

Say it like this

The short version. A hash map of entries that carry an absolute expiry time, plus an eviction strategy: LRU as an access-ordered set, LFU as frequency buckets with a minimum. Expiry is lazy on get plus a background sweeper. One lock guards both, because even a get changes the order; stripe the cache if that lock gets hot, and run listeners outside it.

In the interview
  • "A hash map of entries with an
  • absolute expiry time, and an
  • eviction strategy: LRU as an
  • access-ordered set, LFU as
  • frequency buckets with a min.
  • Lazy expiry on get plus a
  • sweeper. One lock, because get
  • mutates order; stripe if hot."

Interview questions

How do you implement an LRU cache with O(1) get and put?

A hash map from key to a node in a doubly linked list. On each access unlink the node and move it to the tail; evict from the head. In Java a LinkedHashSet or an access-ordered LinkedHashMap provides the same pair of structures.

How do you implement LFU in O(1)?

Keep a count per key, a map from count to an insertion-ordered set of keys, and the minimum count in use. A get moves the key to the next bucket and bumps the minimum if its bucket emptied; a new key resets the minimum to 1; the victim is the oldest key in the minimum bucket.

How do you expire entries with a TTL?

Store an absolute expiry time on each entry. Check it on every get and remove expired entries (lazy expiry), and also run a periodic sweep so keys nobody reads are freed (active expiry). A full put purges expired entries before evicting a live one.

Why does a read-write lock not help here?

A get changes shared state: LRU moves the key, LFU increments its count, and expiry may delete it. Every get therefore needs exclusive access, so a read-write lock behaves like a plain lock with more overhead.

How would you scale the cache to many cores?

Stripe it into segments chosen by key hash, each with its own map, policy and lock; or buffer access events and apply reordering in batches; or use sampled, approximate eviction. Each trades exactness of the global eviction order for throughput.

Why make the eviction policy a Strategy?

The map and locking logic are the same for every policy; only the ordering differs. With an EvictionPolicy interface, LRU, LFU, FIFO or random are separate classes, and a factory gives each cache its own fresh instance.

How do you test TTL without sleeping?

Inject the clock as a LongSupplier. Tests use an AtomicLong they advance by hand, so a five-second expiry is checked by moving the fake clock forward, instantly and deterministically.

How do you avoid many threads loading the same missing key?

Keep one in-flight loading future per key, for example with computeIfAbsent on a concurrent map of futures. The first caller loads; the others wait on the same future, so the backing store sees one request instead of a stampede.