These are the notes for Low-Level Design (LLD) episode 65: the LRU cache, one of the most asked interview questions and a real part of almost every fast system. We start from what a cache is, watch "keep everything" and "evict the oldest" fail, invent the LRU eviction policy, build it with a list (correct but slow), then with a HashMap plus a doubly linked list and sentinel nodes for O(1) get and put, behind a generic cache interface. Then Java's shortcut, LinkedHashMap with accessOrder and removeEldestEntry, and a thread-safe LRU.
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 users, ids and the "slow database" are made up for teaching.
1. The problem: the kitchen counter
| In the kitchen | In software |
|---|---|
| The storeroom: every jar, but a walk away | The database: all the data, but slow to reach |
| The counter by the stove: room for 3 jars | The cache: small and fast |
| Needing a 4th jar: one must go back | Eviction: removing an item to make room |
| Putting back the jar untouched longest; salt never leaves | LRU: evict the least recently used item |
2. What a cache is
- Cache: a small, fast store that keeps copies of data that is slow to get. Example: user profiles kept in memory in front of a database.
- Hit: the answer is already in the cache. Fast.
- Miss: it isn't; go to the slow source, and keep a copy for next time.
- Capacity: the most items the cache may hold, like 3 jars on the counter.
- Hit rate: hits ÷ (hits + misses). Higher is better.
Our pretend database takes about 200 ms a call, so we count database calls: fewer is better.
3. Attempt 1 and 2: keep everything, or evict the oldest
import java.util.*;
public class Main {
static int dbCalls = 0;
static String slowDb(int id) { dbCalls++; return "user" + id; } // pretend: 200 ms each
public static void main(String[] args) {
Map<Integer, String> all = new HashMap<>(); // attempt 1: keep everything
for (int id = 0; id < 1_000_000; id++) all.computeIfAbsent(id, Main::slowDb);
System.out.println("no limit: " + all.size() + " entries in memory, and growing");
int capacity = 3; dbCalls = 0; int hits = 0; // attempt 2: 3 slots
Map<Integer, String> cache = new HashMap<>(); Deque<Integer> order = new ArrayDeque<>();
for (int id : new int[]{7, 1, 7, 2, 7, 3, 7, 4, 7, 5, 7}) { // user 7 is the hot one
if (cache.containsKey(id)) { hits++; continue; }
if (cache.size() == capacity) {
int old = order.pollFirst(); // evict the OLDEST put
cache.remove(old); System.out.println("evict " + old); }
cache.put(id, slowDb(id)); order.addLast(id);
}
System.out.println("oldest-first: hits " + hits + ", db calls " + dbCalls);
}
}
Real output:
no limit: 1000000 entries in memory, and growing
evict 7
evict 1
evict 2
evict 3
oldest-first: hits 4, db calls 7
- Keep everything: a million entries and growing. Memory is finite; a cache with no limit is just a slow copy of the database.
- Evict the oldest put (FIFO, first in, first out): the very first eviction is user 7, the hot one, requested every other time. 4 hits, 7 database calls.
Why it failed: an eviction policy is the rule that picks who leaves. FIFO looks only at when an item arrived, never at when it was last used.
4. LRU: least recently used
LRU (Least Recently Used): when the cache is full, evict the item that hasn't been used for the longest time. Every get or put makes that key the most recently used. It's a bet that what you used just now, you'll use again soon, which is true for many real workloads (a few hot users, a few hot pages).
Attempt 3: LRU with a plain list
The list keeps the order: front = least recently used, back = most recently used. We count every element walked past (indexOf) or shifted (remove in an ArrayList) as a step.
import java.util.*;
class ListLRU { // LRU with a plain list: front = least recently used
final int capacity; final Map<Integer, String> map = new HashMap<>();
final List<Integer> order = new ArrayList<>(); long steps = 0; int hits = 0, misses = 0;
ListLRU(int capacity) { this.capacity = capacity; }
void touch(int id) { int i = order.indexOf(id); steps += i + 1; // walk the list to find it
order.remove(i); steps += order.size() - i; order.add(id); } // shift the rest
String get(int id) {
if (map.containsKey(id)) { hits++; touch(id); return map.get(id); }
misses++;
if (map.size() == capacity) { int lru = order.remove(0); steps += order.size(); map.remove(lru);
if (capacity == 3) System.out.println("evict " + lru); }
map.put(id, "user" + id); order.add(id); return map.get(id); } }
public class Main { public static void main(String[] args) {
ListLRU small = new ListLRU(3);
for (int id : new int[]{7, 1, 7, 2, 7, 3, 7, 4, 7, 5, 7}) small.get(id);
System.out.println("LRU: hits " + small.hits + ", db calls " + small.misses);
ListLRU big = new ListLRU(10_000); Random r = new Random(42);
for (int i = 0; i < 200_000; i++) big.get(r.nextInt(12_000));
System.out.printf("200,000 gets: %,d hits, %,d list steps%n", big.hits, big.steps);
}}
Real output:
evict 1
evict 2
evict 3
LRU: hits 5, db calls 6
200,000 gets: 160,235 hits, 1,873,324,054 list steps
Correct: now 1, 2 and 3 are evicted and user 7 stays (5 hits, 6 database calls). But 1,873,324,054 steps for 200,000 gets: almost 10,000 steps per get.
5. Why the list is slow, and what we need
Big-O (episode 4) describes how the work grows with n, the number of items.
| Operation | ArrayList | What we need |
|---|---|---|
| Find a key's position | indexOf: walk the list, O(n) |
O(1): a HashMap |
| Remove from the middle | shift everything after it, O(n) | O(1): a doubly linked list |
| Add at the end | O(1) (amortised) | O(1) |
O(1) ("order one", constant time): the same small amount of work whether the cache holds 3 items or 3 million.
A doubly linked list is a chain of nodes where each node knows both its previous and its next node. A node can leave the chain by joining its two neighbours to each other: no walking, no shifting.
The idea: a HashMap from key to its node, and the nodes in a doubly linked list ordered from most to least recently used. The map finds; the list orders.
6. Sentinel nodes
A sentinel node is a dummy node that holds no data and is always there. We keep two: head (before the most recent) and tail (after the least recent). Because every real node always has a prev and a next, unlink and addFront never need if (x == null) checks, and the least recently used node is simply tail.prev.
head ⇄ [7] ⇄ [5] ⇄ [4] ⇄ tail get(4): unlink [4], addFront [4]
head ⇄ [4] ⇄ [7] ⇄ [5] ⇄ tail full? victim = tail.prev = [5]
7. HashMap + doubly linked list, behind a generic cache interface
A generic cache interface uses type parameters K and V (episode 3), so the same cache works for any key and value types: Cache<Integer, String>, Cache<String, byte[]>.
import java.util.*;
interface Cache<K, V> { Optional<V> get(K key); void put(K key, V value); int size(); }
class LRUCache<K, V> implements Cache<K, V> {
private class Node { K key; V val; Node prev, next; Node(K k, V v) { key = k; val = v; } }
private final int capacity; private final Map<K, Node> map = new HashMap<>();
private final Node head = new Node(null, null), tail = new Node(null, null); // sentinels
LRUCache(int capacity) { this.capacity = capacity; head.next = tail; tail.prev = head; }
private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
private void addFront(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
public Optional<V> get(K key) {
Node n = map.get(key); if (n == null) return Optional.empty();
unlink(n); addFront(n); return Optional.of(n.val); } // now the MOST recently used
public void put(K key, V value) { Node n = map.get(key);
if (n != null) { n.val = value; unlink(n); addFront(n); return; }
if (map.size() == capacity) { Node lru = tail.prev; unlink(lru); map.remove(lru.key);
if (capacity == 3) System.out.println("evict " + lru.key); }
n = new Node(key, value); map.put(key, n); addFront(n); }
public int size() { return map.size(); } }
public class Main { static int hits, misses;
static void load(Cache<Integer, String> c, int id) {
if (c.get(id).isPresent()) hits++; else { misses++; c.put(id, "user" + id); } }
public static void main(String[] args) {
Cache<Integer, String> small = new LRUCache<>(3);
for (int id : new int[]{7, 1, 7, 2, 7, 3, 7, 4, 7, 5, 7}) load(small, id);
System.out.println("LRU: hits " + hits + ", db calls " + misses);
Cache<Integer, String> big = new LRUCache<>(10_000); Random r = new Random(42); hits = 0;
for (int i = 0; i < 200_000; i++) load(big, r.nextInt(12_000));
System.out.printf("200,000 gets: %,d hits, size %,d, no list walking%n", hits, big.size()); } }
Real output:
evict 1
evict 2
evict 3
LRU: hits 5, db calls 6
200,000 gets: 160,235 hits, size 10,000, no list walking
The same answer as the list (5 hits, 6 database calls; and the very same 160,235 hits in the big test), but every get and put is a fixed handful of pointer changes: O(1).
| Method | Steps | Cost |
|---|---|---|
get(k) |
map.get → unlink → addFront |
O(1) |
put(k) existing |
update value → unlink → addFront |
O(1) |
put(k) new, full |
tail.prev → unlink → map.remove → new node → map.put → addFront |
O(1) |
8. Java's shortcut: LinkedHashMap with accessOrder and removeEldestEntry
LinkedHashMap (episode 4) is exactly a HashMap plus a doubly linked list inside.
new LinkedHashMap<>(16, 0.75f, accessOrder): initial size 16, load factor 0.75 (how full the table gets before it grows), and accessOrder.accessOrder = false(the default): the order keys were first inserted. That is FIFO.accessOrder = true: everygetorputmoves the key to the end: LRU order.- removeEldestEntry(eldest): a method LinkedHashMap calls after every
put, passing the eldest entry (the least recently used, in access order). Returntrueand it is removed.
import java.util.*;
class LRU<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
LRU(int capacity, boolean accessOrder) { super(16, 0.75f, accessOrder); this.capacity = capacity; }
@Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { // asked after every put
return size() > capacity; // true = remove the eldest entry
}
}
public class Main {
static void demo(String name, Map<Integer, String> c) {
c.put(1, "a"); c.put(2, "b"); c.put(3, "c");
c.get(1); // user 1 was just used
c.put(4, "d"); // one too many: who leaves?
System.out.println(name + ": " + c.keySet());
}
public static void main(String[] args) {
demo("accessOrder false", new LRU<>(3, false));
demo("accessOrder true ", new LRU<>(3, true));
}
}
Real output:
accessOrder false: [2, 3, 4]
accessOrder true : [3, 1, 4]
With false, user 1 was evicted although it was just used. With true, user 2 (untouched longest) left. One boolean changes the whole policy.
9. A thread-safe LRU
A thread is one path of work; a server runs many at once (episode 46). A race condition is when two threads change shared data at the same moment and their changes mix up. Thread-safe means it stays correct even when many threads call it.
The trap: in an LRU cache even get changes the list (it moves the key), so get is not a harmless read.
import java.util.*;
class LRU<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
LRU(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }
@Override protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > capacity; } }
public class Main {
static void hammer(String name, Map<Integer, Integer> cache) throws InterruptedException {
List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) threads.add(Thread.ofPlatform().start(() -> { // 4 threads at once
Random r = new Random();
for (int i = 0; i < 200_000; i++) { int k = r.nextInt(200); cache.get(k); cache.put(k, i); }
}));
for (Thread t : threads) t.join();
System.out.println(name + ": size " + cache.size() + ", capacity 100");
}
public static void main(String[] args) throws InterruptedException {
hammer("no lock ", new LRU<>(100));
hammer("synchronized", Collections.synchronizedMap(new LRU<>(100)));
}
}
One real run:
no lock : size 203, capacity 100
synchronized: size 100, capacity 100
With no lock the size runs far past the capacity (it changes every run: we saw 216, 202 and 199 in other runs; with only 200 distinct keys, 216 means the list was corrupted). With one lock (Collections.synchronizedMap wraps every call in synchronized), it is exactly 100.
A read lock on get is not enough. We also tried a ReentrantReadWriteLock with the read lock on get (many readers at once) and the write lock on put. Three real runs printed:
read lock on get: size 100, capacity 100
read lock on get: size 100, capacity 100
read lock on get: size 199, capacity 100
It passes sometimes and breaks sometimes: the worst kind of bug. Because get reorders the list, it needs the same exclusive lock as put. For more speed under many threads, split the cache into shards (several smaller caches, each with its own lock, chosen by the key's hash).
10. The class diagram
Cache<K, V> (interface: get, put, size)
└─implemented by─▶ LRUCache<K, V>
├─has──▶ HashMap<K, Node> key → its node, found in O(1)
└─has──▶ doubly linked list head ⇄ MRU ⇄ ... ⇄ LRU ⇄ tail (sentinels)
get(k): map → node → unlink → addFront O(1)
put(k): full? → remove tail.prev from list and map → addFront O(1)
shortcut: LinkedHashMap(16, 0.75f, true) + removeEldestEntry
threads: one lock around get AND put (get changes the order too)
11. Interview follow-ups
| Follow-up | Answer |
|---|---|
| Expire old entries | TTL (time to live): store expiresAt; an expired entry is a miss (practice 2) |
| Faster under many threads | Shards: N small LRUs, each with its own lock, picked by hash(key) % N |
| How good is the cache? | Cache statistics: hits, misses, evictions, hit rate (mini project) |
| Frequency matters more than recency | LFU: next episode |
| Limit in bytes, not items | Give each entry a weight; evict until the new one fits |
| Swap the policy | An EvictionPolicy interface: next episode |
| Two threads miss the same key at once | Both load it from the database; fix with a per-key "loading" future (computeIfAbsent on a ConcurrentHashMap<K, CompletableFuture<V>>) |
12. Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| No capacity | 1000000 entries in memory, and growing |
Memory is finite | A capacity and an eviction policy |
| Evict the oldest put | evict 7 (the hot user) |
FIFO ignores use | LRU: move on every get |
| ArrayList for the order | 1,873,324,054 list steps |
indexOf + shifting is O(n) |
Doubly linked list + HashMap |
accessOrder left false |
[2, 3, 4]: user 1 evicted |
Insertion order | new LinkedHashMap<>(16, 0.75f, true) |
| No lock | size 203, capacity 100 |
Race condition | One lock for get and put |
Read lock on get |
sometimes size 199, capacity 100 |
get changes the list |
Exclusive lock for get too |
| Capacity 0 or negative | (mini project) IllegalArgumentException: capacity must be positive |
No room for anything | Validate in the constructor |
Mini project: a thread-safe LRU cache with statistics in front of a slow service
The cache-aside pattern: the service checks the cache first; on a miss it loads from the database and stores the result.
import java.util.*;
import java.util.function.Function;
interface Cache<K, V> {
Optional<V> get(K key);
void put(K key, V value);
int size();
}
// HashMap + doubly linked list with sentinels; synchronized = thread-safe; counts hits and misses.
class LRUCache<K, V> implements Cache<K, V> {
private final class Node { K key; V val; Node prev, next; Node(K k, V v) { key = k; val = v; } }
private final int capacity;
private final Map<K, Node> map = new HashMap<>();
private final Node head = new Node(null, null), tail = new Node(null, null);
private long hits, misses, evictions;
LRUCache(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
this.capacity = capacity; head.next = tail; tail.prev = head;
}
private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
private void addFront(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
public synchronized Optional<V> get(K key) {
Node n = map.get(key);
if (n == null) { misses++; return Optional.empty(); }
hits++; unlink(n); addFront(n);
return Optional.of(n.val);
}
public synchronized void put(K key, V value) {
Node n = map.get(key);
if (n != null) { n.val = value; unlink(n); addFront(n); return; }
if (map.size() == capacity) { Node lru = tail.prev; unlink(lru); map.remove(lru.key); evictions++; }
n = new Node(key, value); map.put(key, n); addFront(n);
}
public synchronized int size() { return map.size(); }
public synchronized List<K> keysMostRecentFirst() {
List<K> out = new ArrayList<>();
for (Node n = head.next; n != tail; n = n.next) out.add(n.key);
return out;
}
public synchronized String stats() {
return String.format("hits %d, misses %d, evictions %d, hit rate %.1f%%", hits, misses, evictions,
100.0 * hits / Math.max(1, hits + misses));
}
}
// A slow "database" behind the cache: the cache-aside pattern (check the cache, else load and store).
class ProfileService {
private final Cache<Integer, String> cache; private final Function<Integer, String> db;
int dbCalls = 0;
ProfileService(Cache<Integer, String> cache, Function<Integer, String> db) { this.cache = cache; this.db = db; }
String profile(int id) {
return cache.get(id).orElseGet(() -> { dbCalls++; String p = db.apply(id); cache.put(id, p); return p; });
}
}
public class Main {
public static void main(String[] args) throws InterruptedException {
LRUCache<Integer, String> cache = new LRUCache<>(3);
ProfileService svc = new ProfileService(cache, id -> "profile of user " + id);
for (int id : new int[]{7, 1, 7, 2, 7, 3, 7, 4, 7, 5, 7}) svc.profile(id);
System.out.println("order (most recent first): " + cache.keysMostRecentFirst());
System.out.println(cache.stats() + ", db calls " + svc.dbCalls);
LRUCache<Integer, Integer> shared = new LRUCache<>(100);
List<Thread> ts = new ArrayList<>();
for (int t = 0; t < 4; t++) ts.add(Thread.ofPlatform().start(() -> {
Random r = new Random();
for (int i = 0; i < 200_000; i++) { int k = r.nextInt(200); if (shared.get(k).isEmpty()) shared.put(k, i); }
}));
for (Thread t : ts) t.join();
System.out.println("4 threads: size " + shared.size() + " (capacity 100)");
try { new LRUCache<String, String>(0); } catch (IllegalArgumentException e) { System.out.println(e); }
}
}
Real output:
order (most recent first): [7, 5, 4]
hits 5, misses 6, evictions 3, hit rate 45.5%, db calls 6
4 threads: size 100 (capacity 100)
java.lang.IllegalArgumentException: capacity must be positive
Note: profile() does get then put as two separate locked calls, so two threads that miss the same key at the same moment may both call the database. The cache stays correct; it just does a little extra work (see the last follow-up).
Practice
1. Add a hit-rate counter to LRUCache.
Answer
Count hits and misses in get, and report hits / (hits + misses): see stats() in the mini project. Real output: hits 5, misses 6, evictions 3, hit rate 45.5%, db calls 6.
2. Add a TTL to every entry, with an injected clock, and write get(key) that returns -1 on a miss.
Answer
import java.util.*;
import java.util.function.LongSupplier;
// Practice: LRU with a TTL per entry, an injected clock, and get() returning -1 on a miss.
class TtlLRU {
private record Entry(int value, long expiresAt) {}
private final int capacity; private final long ttl; private final LongSupplier clock;
private final LinkedHashMap<Integer, Entry> map;
TtlLRU(int capacity, long ttl, LongSupplier clock) {
this.capacity = capacity; this.ttl = ttl; this.clock = clock;
map = new LinkedHashMap<>(16, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry<Integer, Entry> e) { return size() > TtlLRU.this.capacity; }
};
}
synchronized int get(int key) {
Entry e = map.get(key);
if (e == null) return -1;
if (clock.getAsLong() >= e.expiresAt()) { map.remove(key); return -1; } // expired = a miss
return e.value();
}
synchronized void put(int key, int value) { map.put(key, new Entry(value, clock.getAsLong() + ttl)); }
synchronized Set<Integer> keys() { return map.keySet(); }
}
public class Main {
public static void main(String[] args) {
long[] now = {0};
TtlLRU c = new TtlLRU(2, 10, () -> now[0]);
c.put(1, 100); c.put(2, 200);
System.out.println("get(1) = " + c.get(1));
c.put(3, 300); // evicts 2, the least recently used
System.out.println("get(2) = " + c.get(2) + ", keys " + c.keys());
now[0] = 10;
System.out.println("at t=10: get(1) = " + c.get(1) + ", keys " + c.keys());
}
}
Real output:
get(1) = 100
get(2) = -1, keys [1, 3]
at t=10: get(1) = -1, keys [3]
An expired entry is removed and counted as a miss. The clock is a LongSupplier, so the test moves time by hand instead of sleeping.
3. Make LRUCache thread-safe with synchronized.
Answer
Mark get, put and size synchronized (the mini project does). Real output with 4 threads: 4 threads: size 100 (capacity 100).
4. In the list version, why is order.remove(0) also O(n)?
Answer
An ArrayList keeps its items in one block of memory; removing index 0 shifts every other item one place left. That's why our step counter adds order.size() there.
Quick quiz
LRU cache, capacity 2: put(1) put(2) get(1) put(3) put(4). Which keys are left? (a) [1, 4] (b) [3, 4] (c) [2, 4] (d) [1, 3]
Answer
(b) [3, 4]. After get(1), 2 is the least recent, so put(3) evicts 2; then 1 is the least recent, so put(4) evicts 1. Real LinkedHashMap run:
[3, 4]
Interview questions
- Design an LRU cache with O(1) get and put. HashMap from key to node + doubly linked list ordered by recency; get = lookup + move to front; put = insert at front, evicting
tail.prevwhen full. - Why a doubly linked list and not a singly linked one? To unlink a node in O(1) you need its previous node; a singly linked list would have to walk to find it.
- Why store the key inside the node? When you evict
tail.prev, you must also remove it from the map, and the map needs the key. - What are sentinel nodes for? Dummy head and tail so that every real node has neighbours: no null checks at the ends, and the LRU is always
tail.prev. - How does LinkedHashMap give you LRU?
accessOrder = truekeeps access order; overrideremoveEldestEntryto returnsize() > capacity. - Is LinkedHashMap thread-safe? No. Wrap it with
Collections.synchronizedMapor lock both get and put; a read lock on get is not enough because get reorders. - What is the eviction policy, and name others. The rule for who leaves: LRU, FIFO, LFU, random, TTL-based.
- When does LRU do badly? A one-time scan of many items pushes out the hot ones (next episode).
- How do you measure a cache? Hit rate, plus evictions and load time saved.
- What's the time and space complexity? O(1) per operation, O(capacity) space.
Glossary
| Term | Meaning, with an example |
|---|---|
| Cache | A small, fast store of copies of slow data: profiles in memory in front of a database |
| Hit | The item is in the cache: get(7) finds it |
| Miss | The item isn't: go to the database, then keep a copy |
| Hit rate | hits ÷ (hits + misses): 5 of 11 = 45.5% |
| Capacity | The most items the cache may hold: 3 |
| Evict | Remove an item to make room |
| Eviction policy | The rule that picks who leaves: FIFO, LRU, LFU |
| FIFO | First in, first out: evict the oldest put, even if it's hot |
| LRU | Least recently used: evict the item untouched longest |
| Most recently used | The key touched last: it goes to the front |
| Big-O | How work grows with n: O(n) grows with the size, O(1) doesn't |
| O(1) get and put | Each call costs the same small work at any size |
| Doubly linked list | Nodes that know both their previous and next node |
| Node | One link in a list: key, val, prev, next |
| HashMap plus doubly linked list | The map finds a key's node in O(1); the list keeps recency order |
| Sentinel nodes | Dummy head and tail nodes with no data, so there are no null checks |
| unlink / addFront | Remove a node by joining its neighbours / insert right after head |
| Generic cache interface | interface Cache<K, V>: works for any key and value types |
| Type parameter | A placeholder type like K filled in later: Cache<Integer, String> |
| LinkedHashMap | A HashMap with a linked list inside that remembers an order |
| Load factor | How full the table gets before it grows: 0.75 |
| LinkedHashMap with accessOrder | accessOrder = true orders by last access (LRU); false by insertion |
| removeEldestEntry | Called after every put with the eldest entry; return true to remove it |
| Thread | One path of work; servers run many at once |
| Race condition | Two threads change shared data at once and the result is wrong |
| Thread-safe LRU | An LRU that stays correct under many threads: one lock for get and put |
| synchronized | Only one thread at a time may run the method or block |
| Collections.synchronizedMap | Wraps a map so every call is synchronized |
| ReadWriteLock | Many readers or one writer at a time; wrong for LRU's get |
| Shards | Splitting one cache into several, each with its own lock |
| TTL | Time to live: an entry expires after a set time |
| Cache-aside | The caller checks the cache, else loads from the source and stores it |
Summary
- A cache keeps fast copies; a hit is fast, a miss goes to the slow source; capacity limits it.
- No limit: memory grows forever. FIFO evicted the hot user first.
- LRU evicts the least recently used; with a list it was correct but O(n) (1.87 billion steps).
- HashMap + doubly linked list + sentinel nodes: O(1) get and put, behind a generic
Cache<K, V>. - LinkedHashMap:
accessOrder = true+removeEldestEntryis an LRU in a few lines. - Thread-safe: one lock around get and put, because get changes the order.
Next episode: Design an LFU cache and a pluggable cache library: frequency counts, swappable eviction policies, write-through, write-back, TTL and statistics.