LLD-014 · LOW LEVEL DESIGN

In-Memory Cache

Coordinate recency, expiry and in-flight loads without stale resurrection or lock-held I/O.

Local Java 21 reference verified: 321 checks. Learner drafts are not executed. Author self-review; independent review pending.

Existing introductory lesson · Version 1

Understand the problem

Build a generic local cache with count capacity, LRU eviction, expire-after-write TTL, invalidation and single-flight loading. Explain the difference between evicting entries, expiring values, cancelling callers and fencing old load completion.

Before you start

• Hash maps and access-order linked maps
• Monotonic elapsed time
• Futures and single-flight coordination
• Linearization and version/identity fencing

Scope and explicit decisions

• One JVM instance; no persistence, distributed coherence, write-through, refresh-ahead, weak references or byte-weighted eviction. Capacity counts retained entries, not total bytes. Values and keys must satisfy the caller ownership contract.
• Null keys/values are rejected; absence is Optional.empty. Keys must have stable equality/hash behavior. Values are returned by reference, so callers should use immutable V or provide a separate defensive-copy wrapper; the generic cache does not deep-copy arbitrary objects.
• TTL is positive expire-after-write duration in trusted elapsed units. get does not extend TTL. A value is expired when expiresAt<=current time; cached reads are authoritative for that expiry check.
• Explicit get/put/keys calls receive nonnegative nondecreasing time. getOrLoad samples an injected clock while holding the cache monitor at start and completion. This avoids callers sampling timestamps outside the serialization boundary.
• LRU uses LinkedHashMap access ordering under one monitor. get hits move to newest. Before put/store, expired entries are purged so a dead entry does not evict a live entry needlessly.
• One future per currently attached key shares load work. The loader runs outside the monitor. Same-thread recursive same-key load is rejected instead of joining its own future. Cross-thread cyclic loader dependencies are prohibited by contract, not detected by a full dependency graph.
• Max active owner loads is explicit (default max(1,entryCapacity)). Invalidating a load detaches its cache insertion right but does not free that active-load slot until it finishes. Followers do not consume an extra owner slot.
• invalidate and put detach any old attached future. Completion inserts only if the map still points to that same future identity. An old waiter may still receive the old loader result; this is write fencing, not cancellation or a guarantee that all readers see the new value.
• Load TTL starts at successful completion. A failed/null/overflowed load completes its future exceptionally and releases owner capacity. Owner and joined caller exception wrappers may differ. Capacity zero permits loading but stores no entries.

Worked examples

Try before revealing

Requirements and invariants

R1 — Retained live entries never exceed count capacity and hits update recency atomically. store protects I1.

R2 — Expired values are not returned as hits. get protects I2.

R3 — Only the attached future can publish its load result into the cache. getOrLoad protects I3.

R4 — Detached loads remain counted until completion, bounding active owner work. inFlight protects I4.

I1: The access-order map holds at most capacity entries; its oldest key is the next LRU eviction candidate after expiry cleanup.

I2: A hit is returned only when expiresAt>observed time; recency changes do not alter expiry.

I3: A completing loader stores only when flights.get(key) is exactly its own future identity.

I4: Active owner loaders, including detached ones, never exceed maxLoads; each releases its slot in finally.

Derive the design

A map plus LRU is only the starting point

A hash map with an access-order list can implement count-bounded LRU, but that does not define freshness or asynchronous loading. The reference uses Java’s LinkedHashMap for one consistent recency structure, adds deadline checks and a single-flight future map, then fences result publication by future identity. This keeps the most subtle state transitions explicit rather than pretending a concurrent map solves the whole cache.

Alternative: A handwritten hash-map+doubly-linked-list is useful for understanding LRU mechanics, as in the DSA lesson, but production component behavior also includes expiry, ownership and load failure. Sharding or a mature caching library may be practical after contracts and measurements are clear.

Responsibilities and ownership

Method contracts

What, when, why and how

Each concept is attached to the requirement it protects, its implementation, an alternative and a test.

Read and run the Java reference

1import java.util.*;
2import java.util.concurrent.*;
3import java.util.function.*;
4/** Local count-bounded LRU + expire-after-write cache with externally supplied trusted elapsed time. */
5public final class Solution {
6    private Solution() {}
7    private record Entry<V>(V value,long expiresAt){}
8    public static final class Cache<K,V> {
9        private final int capacity,maxLoads;
10        private int activeLoads;
11        private final ThreadLocal<Set<K>> loading=ThreadLocal.withInitial(HashSet::new);
12        private final LinkedHashMap<K,Entry<V>> entries=new LinkedHashMap<>(16,0.75f,true);
13        private final Map<K,CompletableFuture<V>> flights=new HashMap<>();
14        private long time;
15        public Cache(int capacity){this(capacity,Math.max(1,capacity));}
16        public Cache(int capacity,int maxLoads){if(capacity<0||maxLoads<1)throw new IllegalArgumentException("capacity");this.capacity=capacity;this.maxLoads=maxLoads;}
17        private void at(long now){if(now<time)throw new IllegalArgumentException("time");time=now;}
18        private void purge(){entries.entrySet().removeIf(e->e.getValue().expiresAt()<=time);}
19        private Optional<V> existing(K key){var e=entries.get(key);if(e==null)return Optional.empty();if(e.expiresAt()<=time){entries.remove(key);return Optional.empty();}return Optional.of(e.value());}
20        public synchronized Optional<V> get(K key,long now){Objects.requireNonNull(key);at(now);return existing(key);}
21        private void store(K key,V value,long expiry){if(capacity==0)return;purge();entries.put(key,new Entry<>(value,expiry));while(entries.size()>capacity)entries.remove(entries.keySet().iterator().next());}
22        public synchronized void put(K key,V value,long ttl,long now){Objects.requireNonNull(key);Objects.requireNonNull(value);if(ttl<1)throw new IllegalArgumentException("ttl");long expiry=Math.addExact(now,ttl);at(now);flights.remove(key);store(key,value,expiry);}
23        public synchronized void invalidate(K key){Objects.requireNonNull(key);entries.remove(key);flights.remove(key);}
24        public V getOrLoad(K key,long ttl,LongSupplier clock,Supplier<V> loader){
25            Objects.requireNonNull(key);Objects.requireNonNull(clock);Objects.requireNonNull(loader);if(ttl<1)throw new IllegalArgumentException("ttl");
26            final CompletableFuture<V> flight;final boolean owner;
27            synchronized(this){at(clock.getAsLong());var hit=existing(key);if(hit.isPresent())return hit.get();var current=flights.get(key);owner=current==null;if(owner){if(activeLoads>=maxLoads)throw new IllegalStateException("load capacity");flight=new CompletableFuture<>();flights.put(key,flight);activeLoads++;}else flight=current;}
28            if(!owner){if(loading.get().contains(key))throw new IllegalStateException("recursive same-key load");return flight.join();}
29            loading.get().add(key);
30            try{
31                V value=Objects.requireNonNull(loader.get());
32                synchronized(this){
33                    at(clock.getAsLong());long expiry=Math.addExact(time,ttl);
34                    // Identity fencing: invalidation/newer put or load detaches this old future.
35                    if(flights.get(key)==flight){flights.remove(key);store(key,value,expiry);}
36                }
37                flight.complete(value);return value;
38            }catch(Throwable error){
39                synchronized(this){flights.remove(key,flight);}flight.completeExceptionally(error);
40                if(error instanceof Error fatal)throw fatal;if(error instanceof RuntimeException runtime)throw runtime;throw new CompletionException(error);
41            }finally{synchronized(this){activeLoads--;}var owned=loading.get();owned.remove(key);if(owned.isEmpty())loading.remove();}
42        }
43        public synchronized List<K> keys(long now){at(now);purge();return List.copyOf(entries.keySet());}
44        public synchronized int inFlight(){return activeLoads;}
45    }
46}
47

Complexity and limits

• Expected O(1) get/invalidate over hash lookup and access ordering, with fixed-entry checks. Hash quality and key behavior remain assumptions.
• put and successful stored load perform an O(C) expiry purge for retained capacity C, plus O(1) expected recency/eviction operations. keys also scans/copies O(C). This is deliberately not advertised as universally O(1).
• Retained space is O(C×value size); active owner loads are bounded by maxLoads, with attached futures and thread-local recursion guards. Followers and payload bytes are not globally bounded by entry count.
• Loader runtime and blocking are external. Joined callers may wait indefinitely for a nonreturning loader; timeout/cancellation/backpressure policy is a separate extension.

Walk through the actual reference

These walkthrough fixtures are emitted only after the Java harness verifies their operations and expected state. Concurrency tests additionally exercise competing callers.

Mistakes and counterexamples

Engineer → Senior → Staff

Open focused practice →

Provenance and scope of evidence

Original teaching material. The local contract is implemented by Solution.java and tested by Test.java on Java 21. Distributed persistence, real provider/device adapters and deployment are not claimed.

Reference verification is not independent editorial review, production deployment verification or a claim that distributed adapters are implemented.