# LRU Cache — decision log

The Phase 5 answer key. Every entry is a question an interviewer actually asks ("why is eviction
its own interface?", "what exactly does the lock protect?") and the answer that earns the mark:
**what change or failure the decision anticipates, and what it would cost without it.**

Four classes, none of them big. `LruCache` is the biggest at under 120 lines and the only one with
a lock in it; `EvictionPolicy` is a three-method interface with no implementation of its own.

| File | One reason to change |
|---|---|
| `LruCache` | how storage, locking, or listener notification works changes |
| `EvictionPolicy` | the bookkeeping hooks an eviction rule needs change |
| `LruEvictionPolicy` | the default recency rule itself changes |
| `LruCacheApi`, `EvictionListener`, `Entry` | given by the contract, not ours to change |

---

## The seam this whole problem is about (B1, B7, C2)

`LruCacheApi`'s own javadoc says it outright: "which one is a policy, not a hardcoded behaviour."
`LruCache` never compares two keys by recency, frequency, or anything else — it calls
`policy.onInsert`, `policy.onAccess`, `policy.onRemove` at the moments the contract defines
standing changes, and asks `policy.victim()` exactly once, only when it is already at capacity and
a brand-new key needs room. `LruEvictionPolicy` is the only thing in this design that knows what
"recently" means, and it is fourteen lines wrapped around a `LinkedHashMap` used purely as an
ordered set.

**This is not a seam built on spec and then never exercised.** Three curveballs land on it three
different ways, and the measured cost is the honest evidence the seam is real rather than merely
named:

- **01, least-frequently-used** — a second, unrelated implementation of the same three-method
  interface. `reference_diff = 0`: not one line of `LruCache.java` changed. This is the curveball
  the corpus's own authoring brief calls out by name as the test of whether this seam is real, and
  it is why `LruCache` was written this way from the start rather than retrofitted.
- **02, per-entry ttl** — did not touch this seam at all, and that is itself informative: TTL is
  orthogonal to *which* key gets picked when the cache is full, so it composes as a decorator
  around the whole `LruCacheApi`, not as a fourth `EvictionPolicy`. Choosing the right seam for a
  requirement, not just building on the nearest one, is part of what this tag is testing.
- **03, write-through backing store** — landed on `EvictionListener` instead, `reference_diff = 0`
  again, and for the same reason 01 is zero: a seam that already exists for one purpose (letting a
  test observe what got evicted) turned out to be exactly the mechanism a real backing store needs
  (writing an evicted entry through before it is gone). Nobody designed `EvictionListener`
  anticipating a backing store; it just happened to already be the right shape.

---

## Concurrency first, because `get` mutating standing is the whole hazard (E1, E2)

### The shared mutable state, named out loud

Two pieces, told apart the same way `movie-booking` and `logger` both do it:

1. **`values` (the key→value map) and whatever `EvictionPolicy` tracks internally.** These move
   together — a key can never be added to one without the other knowing about it in the same
   instant — so they share exactly **one lock**, `LruCache`'s own monitor. Every method that reads
   or writes either one is `synchronized` on `this`, **including `get`**, which is the one a naive
   design gets wrong: `LruCacheApi` states directly that a read mutates standing, so a `get` that
   is not under the same lock `put` uses is not a slightly-riskier read, it is exactly as
   unsynchronized as `put` itself would be with no lock at all.
2. **`listeners`.** Read on every eviction, written only when a caller registers one — the same
   access pattern `logger`'s appender registry has, so it is a `CopyOnWriteArrayList` rather than
   a plain list guarded by the cache's own monitor (E4). Notification happens **after** the lock is
   released, so a slow or throwing listener can never make the cache's own lock the reason another
   thread stalls.

### The bug this design is built around, caught and measured

A variant of `get` with the `synchronized` keyword removed — nothing else changed — was built and
proven against `tests_concurrency/LruCacheStressTest`:

- **`aCrowdRefreshingOneKeyProtectsItFromTheNextEviction`** — the scenario the corpus's authoring
  brief asked for by name: a crowd hammers `get` on one already-present key, nothing else; then,
  back on one thread, a single new key forces exactly one eviction. Under the broken variant, the
  key the crowd had just refreshed was sometimes the one evicted anyway — the concurrent reads
  raced on `LruEvictionPolicy`'s internal `LinkedHashMap` and lost the refresh.
- **`concurrentGetsAndPutsNeverCorruptStandingBookkeeping`** — half the crowd reading existing
  keys, half inserting brand-new ones. This is the scenario that actually broke hardest: one
  observed failure read `capacity must still be the hard ceiling under a mixed read/write storm
  ==> expected: <20> but was: <119>` — a `HashMap` and a `LinkedHashMap` both being mutated by
  unsynchronized readers while a synchronized writer tries to maintain a 20-entry ceiling does not
  fail quietly.

**A read-only storm alone proves nothing, and an earlier draft of this suite said so the hard
way.** A first attempt at the crowd-reading scenario filled the cache to exactly capacity and then
hammered `get` on those same keys with no `put` anywhere in the storm, asserting nothing was
evicted. It passed against the broken variant every time — not because the bug wasn't there, but
because nothing in that scenario ever asked the cache to make an eviction decision, so a corrupted
recency structure never got the chance to produce a wrong answer. The fix was not a bigger crowd;
it was making the storm's aftermath actually ask the question the corrupted state could get wrong,
which is `aCrowdRefreshingOneKeyProtectsItFromTheNextEviction`'s whole design. A stress test that
cannot fail is not a weaker version of a real one — it is a different, useless test wearing the
same shape.

### The numbers, measured rather than guessed

`CROWD = 200`, `ROUNDS = 20`. Single-shot (repetitions pinned to 1) hit rates against the
unsynchronized-`get` variant, measured directly:

| CROWD | single-shot catch rate |
|---|---|
| 4 | 3 / 10 |
| 20 | 5 / 10 |
| 64 | 5 / 10 – 8 / 10 |
| 100 | 8 / 10 |
| 200 | 6 / 10 – 9 / 10 |

This bug is **wide**: even a small crowd catches it a meaningful fraction of the time, because
every concurrent `get` on the protected key touches the same unguarded structure. At the shipped
`ROUNDS = 20`, the full suite caught it on the very first repetition in every one of 3 consecutive
runs.

The **registry** bug — `listeners` changed from `CopyOnWriteArrayList` to a plain `ArrayList` —
is the opposite shape, **narrow**: an isolated single-shot measurement at `CROWD = 200` caught it
**0 times out of 15** independent attempts, and lowering `ROUNDS` from 20 to 5 (still `CROWD =
200`, still the full four-scenario suite) caught it only 6 times out of 8. At the shipped
`ROUNDS = 20`, six independent full-suite runs each caught it, five of them on the very first
repetition. This is the same story `logger`'s appender-registry test tells: a `ConcurrentModificationException`
needs a structural write to land inside one specific iterator's `hasNext`/`next` pair, which is a
narrow window that a small number of attempts can miss entirely. **Do not lower `ROUNDS` below 20,
and do not shrink `CROWD`** — both numbers were chosen because the narrower of the two bugs needs
them, not the wider one.

### Why the victim is chosen before the new key is registered, not after

`LruCache.put` computes the eviction victim, if any, **before** calling `policy.onInsert` for the
brand-new key — not after. For `LruEvictionPolicy` this ordering is invisible, because a
just-inserted key is by construction the most recently touched one and can never be the least
recently touched victim either way. It is not invisible for a frequency-based policy: a brand-new
key starts at a use count of one, which is usually the lowest count in the whole cache, so asking
`policy.victim()` after registering it let curveball 01's first draft nominate the very key it had
just been asked to make room for. This was found writing that curveball's tests, not designed in
advance, and fixed in this file rather than worked around in the curveball, because it is a fact
about the general contract between `LruCache` and any `EvictionPolicy`, not a fact about frequency
specifically. See `curveballs/01-least-frequently-used/reference-patch/PATCH.md` for the full
account, including the exact wrong output observed.

---

## The one ambiguity added to the contract, and why (rule 5 of the authoring brief)

`LruCacheApi.get` returns `Optional<Object>`, which cannot represent "present, holding `null`"
differently from "absent" on its own. The contract as first drafted did not say what happens to a
key stored with a `null` value, which is exactly the kind of unstated convention the deterministic-
contract spec calls a residual risk. One sentence was added to rule 2 pinning it down: a
`null`-valued key reads back as `Optional.empty()` too, and `containsKey` — unaffected by this —
is the one way to tell "present, holding null" apart from "not present at all." This is additive
documentation, not a behavioural change, and `nullValuedKeyIsPresentButUnreadableAsSuch` in the
base suite locks it in.

## Modelling notes

- **No custom exception hierarchy (A6).** The contract fixes `IllegalArgumentException` for a bad
  capacity and states no other thrown behaviour; a `CacheFullException` or similar would say
  nothing a plain eviction — which is not an error at all — needs said.
- **No `Entry`-like record for a stored value (A2, A7).** Values are `Object`, handed back exactly
  as given; wrapping them in a boundary type would invent structure the contract never asked for
  and this problem's single-value shape has no use for.
- **Iteration order is not exposed, on purpose (A7, C5).** `LruCacheApi` never hands back the key
  set in any order — rule 8 says so directly — because doing so would leak whichever
  `EvictionPolicy`'s internal representation the cache happens to be running, which is exactly what
  the policy seam exists to keep out of the contract.
- **No background sweep, here either.** Curveball 02's per-entry TTL is discovered lazily, the
  same convention `movie-booking`'s hold expiry and `rate-limiter`'s window both use: nothing ticks
  on its own, so there is nothing for the concurrency suite to race against beyond the design
  itself.

## What was deliberately not built

- **No `remove(key)` on the base contract.** Nothing in the base problem asks for explicit removal,
  only eviction as a side effect of `put`. Curveball 02's `TtlLruCache` feels this absence directly
  — an expired entry cannot be proactively purged from its delegate, only hidden from `get` and
  `containsKey` until the delegate's own eviction reclaims it — and that cost is stated honestly in
  that curveball's `PATCH.md` rather than solved by quietly inventing a method the base contract
  does not have.
- **No generic key or value type.** Every key in this problem is a `String` and every value is an
  `Object`, exactly as `LruCacheApi` declares; a generic `LruCache<K, V>` would be true to the
  textbook problem but false to the contract actually handed to a candidate, which fixes both types
  so the grader has something concrete to call.
