Part 5 of 6 · 5 min read
Going further
Other eviction rules, loading on a miss, expiry.
Policies, loading and change requests
Other eviction rules. LRU is one rule among several. A policy interface makes the rule replaceable (the strategy pattern of Level 4, module 1). The cache tells the policy what happened and asks it who should go.
interface EvictionPolicy<K> {
void onInsert(K k); void onAccess(K k); void onRemove(K k);
K victim();
}
Three small classes implement it. LruPolicy and FifoPolicy keep a LinkedHashSet of keys in order. LRU moves a key to the end on access, and FIFO ignores access. LfuPolicy counts uses and picks the key with the lowest count. The cache itself, PolicyCache, holds the map and the policy and has no idea which rule is in use.
The same sequence, run through all three, shows the difference. Capacity 2: put a, put b, then get a twice, get b once, then put c. LRU removes a, since b was used after it. FIFO also removes a, since it was inserted first. LFU removes b, since a was used three times and b only twice. Each policy leaves a different cache, so the choice matters.
The cost of the choice: the policies above use a linked set for LRU and FIFO, which is constant time, and a scan for LFU victim, which is linear. A real LFU keeps buckets of keys per count to be constant time. Say this, and say that it is a next step and not required.
Loading on a miss. Often the cache sits in front of a slow source, such as a database. A caller wants "get this key, loading it if missing". A simple version holds the lock while loading, which blocks every other caller during the slow load. A version that loads outside the lock may load the same key twice if two threads miss together.
JCIP section 5.6 builds up to the answer. Store a Future of the value in a concurrent map, not the value itself. The first thread to miss puts a future in the map and starts the load. Any thread that arrives later finds the future and waits on it. The put uses putIfAbsent, which is atomic, so only one thread wins the right to load.
V get(K key) throws Exception {
Future<V> f = cache.get(key);
if (f == null) {
FutureTask<V> ft = new FutureTask<>(() -> load.apply(key));
f = cache.putIfAbsent(key, ft);
if (f == null) { f = ft; ft.run(); }
}
try { return f.get(); }
catch (ExecutionException e) { cache.remove(key, f); throw e; }
}
JCIP also warns of cache pollution: if the load fails and the failed future stays in the map, every later caller sees the same failure. The code removes it on failure. With eight threads asking for the same key and a slow load, the loader runs exactly once, and all eight get the answer. A loader that fails on its first call is retried on the next call and succeeds.
Change requests:
- "Entries expire after 60 seconds." Store an expiry time in each node, using an injected clock. A
getthat finds an expired node removes it and counts a miss. Add a background sweep if memory matters. - "Limit by memory, not by count." Give each value a size, track the total, and evict until the new entry fits.
- "Different policy per cache." Already supported by the policy interface.
- "Read-heavy workload." The single lock becomes a bottleneck. Options are to shard the cache into several smaller ones by hash of the key, or to use a library cache that has been tuned for this. Say the trade: sharding gives each shard its own LRU order, so the global order is only approximate.
- "Statistics." Hits and misses are already counted. An observer could publish them.
- "Persist across restarts." Save the entries in order, and reload them oldest first, so the order is rebuilt.
Common mistake
Using a HashMap for lookup and scanning for the oldest entry, or using a list and scanning for the key. Both are linear time, and the question exists to see that you can reach constant time with two structures.
Interview angle
Answer in your head first, then open it.
How do you get constant-time get and put?
A hash map from key to node plus a doubly linked list ordered by recent use. A hit unlinks the node and moves it to the front. An eviction removes the node at the back.
Why a doubly linked list?
A node found through the map must be unlinked in constant time, which needs its previous and next links.
Is it thread-safe?
Synchronized methods, and get needs the lock since it changes the order. For heavy reads, shard the cache.
How would you change the eviction rule?
A policy interface with LRU, FIFO and LFU classes.
Check yourself:
1. Which policy evicts b in the example, and why?
2. Why store a Future in the map and not the value?
3. What does sharding give up?
Words you will meet
| Word | Meaning |
|---|---|
| Cache | A small fast store of recent results |
| Hit and miss | A lookup that finds, or does not find, the key |
| Sentinel | A dummy node that removes special cases at the ends of a list |
| Eviction policy | The rule for choosing which entry to remove |
| Cache pollution | A failed or stale result kept in the cache |