I85PREP
⌘ K
HP JBT study materials
HP JBT study resources

Session Cache Evicting the Wrong Entry

HP JBT · Put your knowledge to work in context.

All case studies

Session Cache Evicting the Wrong Entry

The payments team ships a session cache used by an authorization service. The cache holds at most 10,000 entries and is written by hand: a HashMap<String, Node> keyed by session ID plus a doubly linked list that records recency, with the head as most-recently-used and the tail as the eviction candidate. During a load test that replays 5,000 distinct session IDs against a hot set of 20 IDs, the measured hit rate is 41% where the team's model predicted 96%. The same instance serves 4,000 requests per second from 16 worker threads. A capacity-3 reproduction shows the defect: put(A,1), put(B,2), put(A,3), put(C,4), then get(A) misses, even though A was the most recently written key. Review shows get() unlinks the node and re-links it at the head, but put() on a key that already exists overwrites node.value in place and returns early. The team wants a fix that does not regress read latency.

1. Trace both the current implementation and a correct LRU through put(A,1), put(B,2), put(A,3), put(C,4), get(A) with capacity 3. State exactly where the two diverge and what each one returns.

Read the worked answer

Write the list as head ... tail, head = most recently used, tail = eviction victim.

Correct LRU:

  1. put(A,1): [A].
  2. put(B,2): [B, A].
  3. put(A,3): existing key, so unlink A and re-link at head -> [A, B]. Value updated.
  4. put(C,4): size would be 3, no eviction yet -> [C, A, B].
  5. get(A): A is at position 2, so it is a HIT and A moves to head -> [A, C, B].

Buggy version (put on existing key does not touch the list):

  1. put(A,1): [A].
  2. put(B,2): [B, A].
  3. put(A,3): value overwritten, node stays at the tail -> [B, A].
  4. put(C,4): size would be 3, no eviction -> [C, B, A].
  5. get(A): A is still present, so this toy sequence still HITs; the divergence is visible only once an eviction happens.

So extend one more step, put(D,5), capacity 3:

  • Correct: [A, C, B] -> D evicts B -> [D, A, C].
  • Buggy: [C, B, A] -> D evicts A -> [D, C, B].

The divergence point is step 3. In the buggy version A keeps its old position even though it was just written, so it remains the eviction candidate. A subsequent put then throws away the hottest key instead of the coldest. That is precisely the 41% versus 96% gap: the hot set of 20 IDs is constantly re-written and then evicted by the next insertion.

2. Give the minimal correct fix and justify why an in-place value update breaks the eviction policy even though the stored data is correct.

Read the worked answer

The fix is one branch: when put() finds an existing key, unlink the node from its current position and re-link it at the head before (or after) assigning the new value. Nothing else in the structure needs to change.

The invariant the list must maintain is that positional order equals recency of last use, where a use is a successful get or a put that stores a value for that key. The eviction rule reads only the tail, so any operation that touches a key without moving it silently violates the invariant: the map says 'A exists, value 3' but the list says 'A is the oldest entry'. Both statements can be individually true, but they contradict each other.

Implementation details that matter:

  • Do the unlink/re-link exactly once, not twice. A common follow-up bug is to call moveToHead() in put() and also at the end of the method, corrupting the sentinel links.
  • Use sentinel head/tail nodes so unlink/insert need no null checks; the capacity-3 reproduction is much easier to reason about with sentinels.
  • Read latency does not regress: get() already performs the same unlink/insert, and put() on an existing key is the rarer path.
  • Add a regression test that asserts the eviction victim after a rewrite of an existing key, not just the hit rate. Hit-rate tests are statistical and will pass with a partially broken list under some workloads.

3. The cache is shared by 16 threads at 4,000 requests per second. What concurrency design do you recommend, and what would you measure before and after?

Read the worked answer

First note that this is not a read-mostly structure: get() mutates the linked list, so two concurrent gets on different keys race on the same head pointers. A plain synchronized get() is correct but serializes all 16 threads on one monitor, which will show up as a latency cliff long before 4,000 requests per second.

Options, in increasing order of engineering cost:

  1. One ReentrantLock around every operation. Correct, simplest, and worth measuring first - at 4,000 requests per second the lock is probably held for well under a microsecond, so this may already be enough. Do not assume contention without a measurement.
  2. Segmented cache: hash the session ID into N segments (say 16 or 32), each with its own HashMap and its own list and its own capacity slice. Locks are independent, so throughput scales. The cost is capacity accounting: a skewed key distribution gives one segment more pressure than its slice allows, slightly lowering the hit rate. Measure both hit rate and p99 latency, because segmentation trades a little hit rate for a lot of concurrency.
  3. Approximate policies: CLOCK or a sampled LRU (move to head only on every k-th access) reduce writes to the list and therefore contention, at the cost of exact LRU ordering. Mature libraries (for example Caffeine) use buffered, lossy recency plus frequency, which is usually a better trade than a hand-rolled exact LRU under concurrency.

Measure: p50/p99 get and put latency, lock wait time or contention count, achieved hit rate against the same replay trace, and throughput at 1, 4, 8 and 16 threads. A flat scaling curve with rising p99 points at the lock; a falling hit rate points at segmentation being too fine.