These are the notes for Low-Level Design (LLD) episode 66. Last episode's LRU cache has one weak spot: a scan. Today we watch one reader empty an LRU cache, invent the LFU (least frequently used) cache with a frequency map and minimum frequency tracking, see the crash you get when you forget one line, and settle ties with tie-breaking by recency. Then we turn it into a small cache library: an EvictionPolicy interface and a Storage interface so policies are pluggable, cache statistics, write-through vs write-back, and TTL support.
How the code was run: every program was saved as Main.java in a fresh folder and run with javac Main.java && java -cp . Main on OpenJDK 21. Every output below is the real output, pasted exactly. The news app, pages and numbers are made up for teaching.
1. The problem: one reader empties the cache
A news app caches 3 pages. All day thousands of readers open the same three: home, cricket, weather. Then one reader opens three old pages from the archive, each once. A scan means going through many items one time each.
import java.util.*;
public class Main {
static Map<String, String> lru = new LinkedHashMap<>(16, 0.75f, true) { // last episode's LRU
protected boolean removeEldestEntry(Map.Entry<String, String> e) { return size() > 3; } };
static int misses = 0;
static void visit(List<String> pages) {
for (String page : pages)
if (lru.get(page) == null) { misses++; lru.put(page, "<html of " + page + ">"); }
}
public static void main(String[] args) {
List<String> favourites = List.of("home", "cricket", "weather");
for (int i = 0; i < 5; i++) visit(favourites); // read all day, 5 times each
visit(List.of("old1", "old2", "old3")); // ONE reader scans the archive, once
System.out.println("after the scan: " + lru.keySet());
misses = 0; visit(favourites);
System.out.println("favourites again: " + misses + " misses out of 3");
}
}
Real output:
after the scan: [old1, old2, old3]
favourites again: 3 misses out of 3
Why it failed: LRU remembers only when each page was used, never how often. The scan made three one-off pages the most recent, so they pushed out every favourite. The next readers all missed.
2. LFU: least frequently used
- Frequency: how many times a key has been used (each
gethit orputadds one). - LFU (Least Frequently Used): when full, evict the key with the smallest frequency.
- Tie-breaking by recency: when several keys share the smallest frequency, evict the least recently used of them.
The obvious LFU walks all keys to find the smallest count: O(n) per eviction. We want O(1).
3. LFU in O(1): the frequency map, buckets and minFreq
Three maps and one number:
| Structure | Holds | Example |
|---|---|---|
vals |
key → value | home → <html> |
freq (the frequency map) |
key → uses | home → 5 |
byFreq (buckets) |
uses → keys with that many uses, oldest first (LinkedHashSet) |
5 → [home, cricket, weather] |
minFreq |
the smallest frequency present | 5 |
capacity 3, after the favourites (5 uses each):
vals {home, cricket, weather}
freq {home=5, cricket=5, weather=5}
byFreq 5 → [home, cricket, weather] oldest first
minFreq 5
put(old1): full → victim = byFreq[minFreq].first() = home
old1 is new → freq 1, byFreq 1 → [old1]
minFreq = 1 ← a new key is ALWAYS the least used
Minimum frequency tracking:
- Evict: the victim is the first key in
byFreq[minFreq]: no search, O(1). Because each bucket keeps insertion order, the first key is the one that reached this frequency earliest: that's the tie-break by recency. - Use (
bump): move the key from bucketftof + 1; if bucketfwas the minimum and is now empty,minFreq++. - Insert a new key: frequency 1, so
minFreq = 1(nothing can be smaller).
4. The forgotten line
The same LFUCache without minFreq = 1 on insert:
import java.util.*;
class LFUCache<K, V> {
private final int capacity; private int minFreq = 0;
private final Map<K, V> vals = new HashMap<>();
private final Map<K, Integer> freq = new HashMap<>(); // key → how many uses
private final Map<Integer, LinkedHashSet<K>> byFreq = new HashMap<>(); // uses → keys, oldest first
LFUCache(int capacity) { this.capacity = capacity; }
private void bump(K key) { // one more use
int f = freq.get(key); freq.put(key, f + 1); byFreq.get(f).remove(key);
if (f == minFreq && byFreq.get(f).isEmpty()) minFreq++;
byFreq.computeIfAbsent(f + 1, x -> new LinkedHashSet<>()).add(key); }
V get(K key) { if (!vals.containsKey(key)) return null; bump(key); return vals.get(key); }
void put(K key, V val) {
if (vals.containsKey(key)) { vals.put(key, val); bump(key); return; }
if (vals.size() == capacity) {
K victim = byFreq.get(minFreq).iterator().next(); // least used; tie → oldest
byFreq.get(minFreq).remove(victim); vals.remove(victim); freq.remove(victim);
System.out.println(" evict " + victim + " (used " + minFreq + "x)"); }
vals.put(key, val); freq.put(key, 1); // a new key: used once
byFreq.computeIfAbsent(1, x -> new LinkedHashSet<>()).add(key); }
public String toString() { return "uses " + freq; } }
public class Main { public static void main(String[] args) {
LFUCache<String, String> c = new LFUCache<>(3); int misses = 0;
List<String> fav = List.of("home", "cricket", "weather");
for (int i = 0; i < 5; i++) for (String p : fav) if (c.get(p) == null) c.put(p, p);
for (String p : List.of("old1", "old2", "old3")) if (c.get(p) == null) c.put(p, p);
for (String p : fav) if (c.get(p) == null) misses++;
System.out.println(c + "\nfavourites again: " + misses + " misses out of 3"); }}
Real output:
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.util.LinkedHashSet.iterator()" because the return value of "java.util.Map.get(Object)" is null
at LFUCache.put(Main.java:16)
at Main.main(Main.java:26)
minFreq was still 0, there is no bucket 0, so byFreq.get(0) returned null and .iterator() threw a NullPointerException on the first eviction.
5. LFU fixed
import java.util.*;
class LFUCache<K, V> {
private final int capacity; private int minFreq = 0;
private final Map<K, V> vals = new HashMap<>();
private final Map<K, Integer> freq = new HashMap<>(); // key → how many uses
private final Map<Integer, LinkedHashSet<K>> byFreq = new HashMap<>(); // uses → keys, oldest first
LFUCache(int capacity) { this.capacity = capacity; }
private void bump(K key) { // one more use
int f = freq.get(key); freq.put(key, f + 1); byFreq.get(f).remove(key);
if (f == minFreq && byFreq.get(f).isEmpty()) minFreq++;
byFreq.computeIfAbsent(f + 1, x -> new LinkedHashSet<>()).add(key); }
V get(K key) { if (!vals.containsKey(key)) return null; bump(key); return vals.get(key); }
void put(K key, V val) {
if (vals.containsKey(key)) { vals.put(key, val); bump(key); return; }
if (vals.size() == capacity) {
K victim = byFreq.get(minFreq).iterator().next(); // least used; tie → oldest
byFreq.get(minFreq).remove(victim); vals.remove(victim); freq.remove(victim);
System.out.println(" evict " + victim + " (used " + minFreq + "x)"); }
vals.put(key, val); freq.put(key, 1); minFreq = 1; // a new key: used once
byFreq.computeIfAbsent(1, x -> new LinkedHashSet<>()).add(key); }
public String toString() { return "uses " + freq; } }
public class Main { public static void main(String[] args) {
LFUCache<String, String> c = new LFUCache<>(3); int misses = 0;
List<String> fav = List.of("home", "cricket", "weather");
for (int i = 0; i < 5; i++) for (String p : fav) if (c.get(p) == null) c.put(p, p);
for (String p : List.of("old1", "old2", "old3")) if (c.get(p) == null) c.put(p, p);
for (String p : fav) if (c.get(p) == null) misses++;
System.out.println(c + "\nfavourites again: " + misses + " misses out of 3"); }}
Real output:
evict home (used 5x)
evict old1 (used 1x)
evict old2 (used 1x)
uses {cricket=6, weather=6, old3=1}
favourites again: 1 misses out of 3
evict home (used 5x): all three favourites had 5 uses (a tie);homereached 5 first, so it is the least recent of them.old1andold2(1 use each) then evict each other: the one-off pages fight among themselves.- Favourites again: 1 miss out of 3 instead of 3 out of 3.
| Operation | Steps | Cost |
|---|---|---|
get |
vals lookup + bump |
O(1) |
put existing |
update + bump |
O(1) |
put new, full |
first of byFreq[minFreq] → remove from 3 maps → insert with freq 1, minFreq = 1 |
O(1) |
6. A pluggable cache library
Two caches (LRU, LFU) meant two copies of almost the same get/put. So we pull out what changes:
- EvictionPolicy interface:
used(k)on every use,removed(k), andvictim(): who leaves? - Storage interface: where values live:
get,put,remove,size. AHashMaptoday; a file, or a remote server tomorrow. - Pluggable policies: the cache is given a policy (and a storage) from outside; swapping one never changes the cache. This is the Strategy pattern (episode 34) plus dependency injection (episode 16).
- Cache statistics: counters for hits, misses and evictions; hit rate = hits ÷ (hits + misses).
import java.util.*;
interface Storage<K, V> { V get(K k); void put(K k, V v); void remove(K k); int size(); }
class MapStorage<K, V> implements Storage<K, V> { private final Map<K, V> m = new HashMap<>();
public V get(K k) { return m.get(k); } public void put(K k, V v) { m.put(k, v); }
public void remove(K k) { m.remove(k); } public int size() { return m.size(); } }
interface EvictionPolicy<K> { void used(K k); void removed(K k); K victim(); }
class LRUPolicy<K> implements EvictionPolicy<K> { private final LinkedHashSet<K> order = new LinkedHashSet<>();
public void used(K k) { order.remove(k); order.add(k); } public void removed(K k) { order.remove(k); }
public K victim() { return order.iterator().next(); } } // least recently used
class LFUPolicy<K> implements EvictionPolicy<K> { private final Map<K, Integer> uses = new LinkedHashMap<>();
public void used(K k) { uses.merge(k, 1, Integer::sum); } public void removed(K k) { uses.remove(k); }
public K victim() { return Collections.min(uses.entrySet(), Map.Entry.comparingByValue()).getKey(); } }
class Cache<K, V> { final Storage<K, V> store; final EvictionPolicy<K> policy; final int cap; // library
int hits, misses, evictions;
Cache(int c, Storage<K, V> s, EvictionPolicy<K> e) { cap = c; store = s; policy = e; }
V get(K k) { V v = store.get(k); if (v == null) misses++; else { hits++; policy.used(k); } return v; }
void put(K k, V v) {
if (store.get(k) == null && store.size() == cap) {
K out = policy.victim(); store.remove(out); policy.removed(out); evictions++; }
store.put(k, v); policy.used(k); }
String stats() { return "hits " + hits + ", misses " + misses + ", evictions " + evictions; } }
public class Main { public static void main(String[] args) {
String fav = "home cricket weather "; // same day as before
List<String> day = List.of((fav.repeat(5) + "old1 old2 old3 " + fav).split(" "));
for (EvictionPolicy<String> p : List.<EvictionPolicy<String>>of(new LRUPolicy<>(), new LFUPolicy<>())) {
Cache<String, String> c = new Cache<>(3, new MapStorage<>(), p); // plug in a policy
for (String page : day) if (c.get(page) == null) c.put(page, "<" + page + ">");
System.out.println(p.getClass().getSimpleName() + ": " + c.stats()); } }}
Real output:
LRUPolicy: hits 12, misses 9, evictions 6
LFUPolicy: hits 14, misses 7, evictions 4
Same Cache class, one argument changed. The statistics show LFU fits this workload better. (This simple LFUPolicy finds its victim with Collections.min, which is O(n); the mini project plugs in the O(1) bucket version.)
7. Write-through vs write-back, and TTL support
- Write-through: every write goes to the cache and the database at once. Always safe; every write pays the slow database.
- Write-back (also "write-behind"): write only the cache and mark the key dirty (changed but not yet saved). A flush later writes all dirty keys. Fast, and five quick updates become one database write, but a crash before the flush loses the dirty data.
- TTL (time to live): each entry gets
expiresAt = now + ttl; at or after that time,gettreats it as a miss. - Clock injection: the cache asks a
LongSupplier(a function returning along) for the time, so a test can move time by hand instead of sleeping.
| Write-through | Write-back | |
|---|---|---|
| Database writes for 5 quick updates | 5 | 1 (at flush) |
| Speed of a write | Slow (waits for the DB) | Fast (memory only) |
| Crash before flush | Nothing lost | Dirty data lost |
| Good for | Money, orders | Counters, likes, views |
import java.util.*;
import java.util.function.LongSupplier;
class Db { final Map<String, Integer> rows = new HashMap<>(); int writes = 0;
void save(String k, int v) { rows.put(k, v); writes++; } }
class WriteCache { record Entry(int value, long expiresAt) {} // a cache that also takes WRITES
final Map<String, Entry> map = new HashMap<>(); final Set<String> dirty = new HashSet<>();
final Db db; final boolean writeBack; final long ttl; final LongSupplier clock;
WriteCache(Db db, boolean writeBack, long ttl, LongSupplier clock) {
this.db = db; this.writeBack = writeBack; this.ttl = ttl; this.clock = clock; }
void put(String k, int v) {
map.put(k, new Entry(v, clock.getAsLong() + ttl));
if (writeBack) dirty.add(k); // write-back: the database later
else db.save(k, v); } // write-through: the database now
void flush() { for (String k : dirty) db.save(k, map.get(k).value()); dirty.clear(); }
Integer get(String k) { Entry e = map.get(k);
if (e == null || clock.getAsLong() >= e.expiresAt()) return null; // TTL: too old = a miss
return e.value(); } }
public class Main { public static void main(String[] args) {
long[] now = {0}; Db a = new Db(), b = new Db(); // a fake clock we can move by hand
WriteCache through = new WriteCache(a, false, 60, () -> now[0]); // TTL 60 seconds
WriteCache back = new WriteCache(b, true, 60, () -> now[0]);
for (int i = 1; i <= 5; i++) { through.put("likes", i); back.put("likes", i); } // 5 quick updates
System.out.println("write-through: " + a.writes + " db writes, db " + a.rows);
System.out.println("write-back: " + b.writes + " db writes, db " + b.rows + " <- crash now = lost");
back.flush(); System.out.println("after flush: " + b.writes + " db write, db " + b.rows);
through.put("score", 42);
now[0] = 59; System.out.println("at 59 s: score " + through.get("score"));
now[0] = 60; System.out.println("at 60 s: score " + through.get("score") + " (TTL 60 s: expired)"); }}
Real output:
write-through: 5 db writes, db {likes=5}
write-back: 0 db writes, db {} <- crash now = lost
after flush: 1 db write, db {likes=5}
at 59 s: score 42
at 60 s: score null (TTL 60 s: expired)
8. The class diagram
Cache<K, V> (the library)
├─has──▶ Storage<K, V> get · put · remove · size (MapStorage, a file, Redis-like...)
├─has──▶ EvictionPolicy<K> used · removed · victim (LRUPolicy, LFUPolicy, FIFO...)
├─has──▶ stats hits · misses · evictions → hit rate
├─has──▶ TTL + clock expiresAt = now + ttl; too old = a miss
└─has──▶ write mode write-through (db now) · write-back (dirty → flush)
LFUCache: vals + freq + byFreq (freq → LinkedHashSet) + minFreq O(1)
9. Interview follow-ups
| Follow-up | Answer |
|---|---|
| A page popular last year keeps a huge count forever | Aging: halve every count now and then, so old popularity fades |
| Keep LRU but survive scans | Two lists: a new item must be used twice before it joins the main list (the idea behind "2Q" / segmented LRU) |
| Thread safety | One lock for get and put, or shards with a lock each |
| Write-back durability | Flush on a timer and on shutdown (practice 4); for critical data use write-through |
| Expired entries nobody reads again | A background sweep removes them |
| Code wants to know when items leave | An eviction listener: the Observer pattern (episode 35) |
10. Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| LRU for scan-heavy traffic | favourites again: 3 misses out of 3 |
Recency only | LFU, or a scan-resistant LRU |
minFreq not reset on a new key |
NullPointerException: Cannot invoke "java.util.LinkedHashSet.iterator()" because the return value of "java.util.Map.get(Object)" is null |
Bucket 0 doesn't exist | minFreq = 1 on insert |
| Scanning all keys for the minimum | O(n) on every eviction | No buckets | freq → LinkedHashSet + minFreq |
| Policy code written inside the cache | A copy of get/put per policy | No interface | EvictionPolicy plugged in |
| Write-back with no flush | 0 db writes, db {} |
Dirty data only in memory | Flush on a timer and on shutdown |
| Reading the real clock in tests | Tests must sleep 60 s | Hidden dependency on time | Inject a LongSupplier clock |
Mini project: the complete cache library
Three policies (FIFO, LRU, and the O(1) LFU as a plug-in), storage behind an interface, statistics, TTL and an injected clock, thread-safe methods.
import java.util.*;
import java.util.function.LongSupplier;
// ---------- Storage: where values live ----------
interface Storage<K, V> { V get(K k); void put(K k, V v); void remove(K k); int size(); }
class MapStorage<K, V> implements Storage<K, V> {
private final Map<K, V> m = new HashMap<>();
public V get(K k) { return m.get(k); } public void put(K k, V v) { m.put(k, v); }
public void remove(K k) { m.remove(k); } public int size() { return m.size(); }
}
// ---------- Eviction policies: who leaves ----------
interface EvictionPolicy<K> { void used(K k); void removed(K k); K victim(); }
class FIFOPolicy<K> implements EvictionPolicy<K> { // order of first arrival
private final LinkedHashSet<K> order = new LinkedHashSet<>();
public void used(K k) { order.add(k); } // add() keeps the old position
public void removed(K k) { order.remove(k); }
public K victim() { return order.iterator().next(); }
}
class LRUPolicy<K> implements EvictionPolicy<K> {
private final LinkedHashSet<K> order = new LinkedHashSet<>();
public void used(K k) { order.remove(k); order.add(k); }
public void removed(K k) { order.remove(k); }
public K victim() { return order.iterator().next(); }
}
class LFUPolicy<K> implements EvictionPolicy<K> { // O(1): buckets + minFreq
private final Map<K, Integer> freq = new HashMap<>();
private final Map<Integer, LinkedHashSet<K>> byFreq = new HashMap<>();
private int minFreq = 0;
public void used(K k) {
Integer f = freq.get(k);
if (f == null) { freq.put(k, 1); bucket(1).add(k); minFreq = 1; return; }
freq.put(k, f + 1); bucket(f).remove(k);
if (f == minFreq && bucket(f).isEmpty()) minFreq++;
bucket(f + 1).add(k);
}
public void removed(K k) {
Integer f = freq.remove(k);
if (f != null) bucket(f).remove(k);
}
public K victim() {
while (bucket(minFreq).isEmpty()) minFreq++; // after removals the min may move up
return bucket(minFreq).iterator().next();
}
private LinkedHashSet<K> bucket(int f) { return byFreq.computeIfAbsent(f, x -> new LinkedHashSet<>()); }
}
// ---------- The library ----------
class Cache<K, V> {
private record Entry<V>(V value, long expiresAt) {}
private final Storage<K, Entry<V>> store; private final EvictionPolicy<K> policy;
private final int capacity; private final long ttl; private final LongSupplier clock;
private long hits, misses, evictions, expired;
Cache(int capacity, Storage<K, Entry<V>> store, EvictionPolicy<K> policy, long ttl, LongSupplier clock) {
this.capacity = capacity; this.store = store; this.policy = policy; this.ttl = ttl; this.clock = clock;
}
static <K, V> Cache<K, V> of(int capacity, EvictionPolicy<K> policy, long ttl, LongSupplier clock) {
return new Cache<>(capacity, new MapStorage<>(), policy, ttl, clock);
}
synchronized Optional<V> get(K k) {
Entry<V> e = store.get(k);
if (e != null && clock.getAsLong() >= e.expiresAt()) { store.remove(k); policy.removed(k); expired++; e = null; }
if (e == null) { misses++; return Optional.empty(); }
hits++; policy.used(k);
return Optional.of(e.value());
}
synchronized void put(K k, V v) {
if (store.get(k) == null && store.size() == capacity) {
K out = policy.victim(); store.remove(out); policy.removed(out); evictions++;
}
store.put(k, new Entry<>(v, clock.getAsLong() + ttl)); policy.used(k);
}
synchronized String stats() {
return String.format("hits %d, misses %d, evictions %d, expired %d, hit rate %.0f%%",
hits, misses, evictions, expired, 100.0 * hits / Math.max(1, hits + misses));
}
}
public class Main {
public static void main(String[] args) {
long[] now = {0};
String fav = "home cricket weather ";
List<String> day = List.of((fav.repeat(5) + "old1 old2 old3 " + fav).split(" "));
List<EvictionPolicy<String>> policies = List.of(new FIFOPolicy<>(), new LRUPolicy<>(), new LFUPolicy<>());
for (EvictionPolicy<String> p : policies) {
Cache<String, String> c = Cache.of(3, p, 1_000, () -> now[0]);
for (String page : day) if (c.get(page).isEmpty()) c.put(page, "<" + page + ">");
System.out.printf("%-10s %s%n", p.getClass().getSimpleName(), c.stats());
}
Cache<String, String> c = Cache.of(3, new LFUPolicy<>(), 60, () -> now[0]);
c.put("score", "42");
now[0] = 30; System.out.println("t=30 " + c.get("score"));
now[0] = 90; System.out.println("t=90 " + c.get("score") + " " + c.stats());
}
}
Real output:
FIFOPolicy hits 12, misses 9, evictions 6, expired 0, hit rate 57%
LRUPolicy hits 12, misses 9, evictions 6, expired 0, hit rate 57%
LFUPolicy hits 14, misses 7, evictions 4, expired 0, hit rate 67%
t=30 Optional[42]
t=90 Optional.empty hits 1, misses 1, evictions 0, expired 1, hit rate 50%
On this workload FIFO and LRU behave the same (the favourites are always the oldest and least recent before the scan), and LFU wins. The TTL entry is a hit at t = 30 and expired at t = 90.
Practice
1. Plug the O(1) LFU in as a policy. 2. Add a FIFO policy. 3. Add TTL to the library Cache.
Answer (1, 2 and 3)
All three are in the mini project: LFUPolicy with buckets and minFreq (note victim() moves minFreq up past buckets emptied by removals), FIFOPolicy where used() is just add() (a LinkedHashSet keeps the first position), and Entry(value, expiresAt) with the injected clock. Real output above.
4. Make a write-back cache flush every 200 ms, and once more on shutdown.
Answer
import java.util.*;
import java.util.concurrent.*;
// Practice: a write-back cache that flushes every 200 ms and once more on shutdown.
class WriteBackCache {
private final Map<String, Integer> map = new HashMap<>(), db = new HashMap<>();
private final Set<String> dirty = new HashSet<>();
private int dbWrites = 0;
private final ScheduledExecutorService timer = Executors.newSingleThreadScheduledExecutor();
WriteBackCache() { timer.scheduleAtFixedRate(this::flush, 200, 200, TimeUnit.MILLISECONDS); }
synchronized void put(String k, int v) { map.put(k, v); dirty.add(k); }
synchronized void flush() { for (String k : dirty) { db.put(k, map.get(k)); dbWrites++; } dirty.clear(); }
synchronized String db() { return dbWrites + " db writes, db " + db; }
void shutdown() { timer.shutdown(); flush(); } // never lose the last changes
}
public class Main {
public static void main(String[] args) throws InterruptedException {
WriteBackCache c = new WriteBackCache();
for (int i = 1; i <= 1000; i++) c.put("likes", i); // 1000 quick updates
System.out.println("right away: " + c.db());
Thread.sleep(300); // the timer flushed once
System.out.println("after 300 ms: " + c.db());
c.put("likes", 1001); c.put("views", 7);
c.shutdown();
System.out.println("after shutdown: " + c.db());
}
}
Real output:
right away: 0 db writes, db {}
after 300 ms: 1 db writes, db {likes=1000}
after shutdown: 3 db writes, db {views=7, likes=1001}
1000 updates became one database write. The shutdown flush saved the last two changes, which would otherwise be lost.
5. Why does LFU need LinkedHashSet buckets, not HashSet?
Answer
To break ties by recency. A LinkedHashSet remembers insertion order, so the first key in a bucket is the one that reached that frequency earliest. A HashSet has no order, so the "victim" would be arbitrary.
Quick quiz
LFU cache, capacity 2: put(a) put(b) get(a) get(b) put(c). Which key is evicted? (a) a (b) b (c) c (d) nobody
Answer
(a) a. Both have 2 uses, a tie; a reached 2 first, so it's first in bucket 2. Real LFUCache run:
evict a (used 2x)
uses {b=2, c=1}
Interview questions
- Design an LFU cache with O(1) get and put.
vals,freq,byFreq(frequency →LinkedHashSet), andminFreq; victim = first ofbyFreq[minFreq]; new key → freq 1,minFreq = 1. - How are ties broken? By recency within the same frequency: the bucket keeps insertion order.
- When is LFU better than LRU, and when worse? Better with stable popular items and scans; worse when popularity shifts, because old counts linger (fix: aging).
- How would you make the eviction policy pluggable? An
EvictionPolicyinterface (used,removed,victim) injected into the cache: the Strategy pattern. - Why a Storage interface? So the same cache logic can sit on memory, disk or a remote store, and tests can use a fake.
- Write-through or write-back? Write-through for data you can't lose; write-back for high write rates where losing a few updates is acceptable, with regular flushes.
- How do you implement TTL? Store
expiresAtper entry; check onget(lazy expiry), plus an optional background sweep. - How do you test TTL without waiting? Inject the clock.
- What statistics would you expose? Hits, misses, evictions, expirations, hit rate, load time.
- How do you make the library thread-safe? Synchronize get/put (policies change state on every use), or shard.
Glossary
| Term | Meaning, with an example |
|---|---|
| Scan | Going through many items once each: three archive pages read one time |
| Frequency | How many times a key was used: home → 5 |
| LFU | Least frequently used: evict the key with the fewest uses |
| Frequency map | key → use count: freq |
| Frequency bucket | All keys with the same count: byFreq[5] = [home, cricket, weather] |
| Minimum frequency tracking | Keeping minFreq, the smallest count present, so the victim is found in O(1) |
| minFreq | The smallest frequency in the cache; reset to 1 on every new key |
| Tie-breaking by recency | Among equal counts, evict the least recently used |
| LinkedHashSet | A set that remembers insertion order |
| NullPointerException | Calling a method on null: byFreq.get(0).iterator() |
| Eviction policy | The rule that picks who leaves |
| EvictionPolicy interface | used(k), removed(k), victim(): one class per policy |
| Storage interface | get, put, remove, size: where values live |
| Pluggable policies | Passing a policy object in, so swapping it never changes the cache |
| Strategy pattern | A family of interchangeable algorithms behind one interface (episode 34) |
| Dependency injection | Giving an object its collaborators from outside (episode 16) |
| Cache statistics | Counters: hits, misses, evictions, expirations |
| Hit rate | hits ÷ (hits + misses): 14 of 21 = 67% |
| Write-through | Write the cache and the database at once |
| Write-back | Write the cache, mark dirty, save to the database later |
| Write-through vs write-back | Safe and slow vs fast with a risk of losing dirty data |
| Dirty | Changed in the cache but not yet saved to the database |
| Flush | Write all dirty entries to the database |
| TTL | Time to live: an entry expires ttl after it was written |
| TTL support | expiresAt = now + ttl; expired entries are misses |
| Clock injection | Passing in the time source (LongSupplier) so tests can move time |
| LongSupplier | A function that takes nothing and returns a long: () -> now[0] |
| Aging | Periodically shrinking counts so old popularity fades |
| Eviction listener | A callback told whenever an item leaves (Observer) |
Summary
- One scan emptied the LRU cache:
[old1, old2, old3], 3 misses out of 3. - LFU evicts the least frequently used; ties go to the least recent.
- O(1) LFU:
vals+ frequency map + buckets (LinkedHashSet) +minFreq; a new key setsminFreq = 1, or the first eviction throws aNullPointerException. - A library: EvictionPolicy and Storage interfaces make policies pluggable; statistics compare them (LRU 12 hits vs LFU 14).
- Write-through (safe) vs write-back (fast, flush or lose); TTL with an injected clock.
Next episode: Design a logging framework: loggers, log levels, appenders, formatters and asynchronous logging.