Lab L05 · Java + Go

Implementing a bounded TTL cache

Build an in-memory key-value cache with two limits. Size: at most capacity entries; inserting into a full cache evicts the least-recently-used entry. Time: every write gives the entry a lifetime of ttl, after which it is never returned again. Reads refresh recency but not lifetime. Time comes from an injected clock so tests can move it deterministically.

The task

A rider service caches user profiles in front of a slow profile service. Memory must stay bounded (hence LRU eviction) and stale data must not live forever (hence TTL). The TTL is counted from the last write, not the last read, so a profile that is read constantly still gets refreshed from the source of truth every ttl. This lab is the template for the rest of the bank: injected clock, inclusive deadline, and one lock around a small data structure.

Two independent limits: the recency order decides who is evicted when full, and the lifetime bars decide who is invisible. Reading a at t=1 moved it in the recency order but did not stretch its bar.

What you implement

public final class TtlCache<K, V> {
    public TtlCache(int capacity, Duration ttl);
    public TtlCache(int capacity, Duration ttl, LongSupplier nanoTime);  // fake clock for tests
    public Optional<V> get(K key);
    public void put(K key, V value);
    public boolean delete(K key);    // true if an entry was present (even if expired but not yet swept)
    public int size();               // number of unexpired entries
}

Rules

put at time now sets expiresAt = now + ttl. An entry is expired when now >= expiresAt: the deadline itself is already expired.
get of a live entry returns it and makes it most-recently used, but does not extend expiresAt. get of an expired entry removes it and returns empty.
put on an existing key replaces the value, resets expiresAt and makes it most-recently used.
put of a new key first drops expired entries; if the cache is still over capacity, it evicts the least-recently-used entry.
size() counts only unexpired entries.
capacity <= 0 or non-positive ttl → IllegalArgumentException; null key or value → NullPointerException. All methods are thread-safe.
Hint: new LinkedHashMap<>(cap, 0.75f, true) keeps entries in access order, so the first key is the LRU one.

Worked example

capacity = 2, ttl = 10 s. At t=0: put(a), put(b) — both expire at t=10.
t=1: get(a) → hit; a becomes most recent (still expires at 10).
t=2: put(c) → the cache is full, so b (least recent) is evicted. c expires at 12.
t=10: get(a) → empty (exactly at the deadline). get(c) → hit. size() → 1.

Files and commands

Read the tests first, then replace each TODO in the starter until they pass. Java starter: TtlCache.java · tests: TtlCacheTest.java. Go starter: cache.go · tests: cache_test.go.

cd java
./gradlew test --tests 'labs.ttlcache.*'

cd go
go test -race -count=1 ./ttlcache

Reveal the reference solutions

Java: TtlCache.java
Go: cache.go

When to use

Use this lab to revise a stateful in-memory component whose behavior depends on collection semantics, time, synchronization, and capacity. The shared contract is intentionally narrow: a positive fixed capacity, positive TTL, LRU eviction, and expiration at or after the deadline. A live read changes recency, not lifetime; updating a key refreshes its TTL and makes it most-recently used. Expired entries are removed when observed and swept on writes/size checks; the cache bounds entry count, not bytes or immediate reclamation.

Java rejects null keys and values. Go permits nil keys and values when their types allow them; a separate Boolean distinguishes a hit containing nil from a miss. Go rejects keys that cannot be compared at runtime or are not equal to themselves, including NaN, by panicking before mutation. Java keys must retain stable equality and hash codes while stored. Both delete operations report whether a resident entry was removed, even if that entry had expired but had not yet been swept.

This is an instructional local cache, not a distributed cache. It does not promise durable storage, cross-process coherence, loading de-duplication, eviction notifications, or protection of mutable objects stored as values.

Steps

Write the contract. get returns a value or miss. put inserts or replaces. Capacity and TTL must be positive. Expiry is inclusive at the deadline. A successful read updates LRU order. Operations are linearizable with respect to one cache instance.
Choose representations. Java uses an access-ordered LinkedHashMap; its iterator begins at the least-recently accessed entry. Go uses a map from key to list node plus a doubly linked list with the most-recent node at the front. Both representations keep all compound state behind one lock. Lookup and deletion are expected O(1), excluding key costs and contention; every write and live-size check sweeps all resident entries and is O(n), under the lock. Measure that trade-off before replacing the simple sweep.
Make time injectable. Java receives a LongSupplier returning monotonic nanoseconds and uses System.nanoTime() in normal construction. Go receives a func() time.Time; normal time.Now() values preserve a local monotonic reading for comparisons. Neither cache serializes deadlines. Tests advance a fake clock and assert immediately before and exactly at expiry.
Implement one atomic operation boundary. Lookup, expiry validation, recency promotion, insertion, stale-entry sweeping, and eviction all share the same monitor/mutex. This is easy to reason about and demonstrates the invariant. Do not replace it with a concurrent map without specifying how the recency list and expiry cleanup remain consistent.
Check the state invariants. Map size equals list/map-entry count, each key occurs once, capacity is never exceeded, and a hit promotes exactly one entry. Tests cover miss, hit, update, expiration, eviction order, invalid construction, and simultaneous operations.
Run and inspect both implementations. Reference sources are under solutions/. Go tests use go test -race; Java tests use Gradle. The shared behavior is more important than identical internal data structures.
Try variations from memory. Rebuild the LRU index without library ordering support, then add a maximum value-size estimate. For each variation, state which invariant changes and how the memory bound is defined.

Checklist

Recall and variation

Rebuild lookup and recency promotion before opening Go or Java. Variation: expire the least-recent entry exactly when inserting at capacity. Acceptance: expired state is reclaimed before a live victim is chosen, and every live key still has one recency position.

Expiration boundary is exactly now >= deadline in both languages
Reads update recency only for a live entry
Updating a key replaces value and deadline and promotes it
Writes sweep expired entries before capacity eviction
Capacity remains bounded for every operation sequence
Fake-clock tests contain no sleep
Coordinated concurrent tests check the capacity and representation invariants; race tools provide additional exercised-path evidence, not proof
Mutable values are documented as caller-owned aliases, not deep-copied snapshots
Complexity and the O(n) expiry sweep are explicit
The local-only and in-memory limitations are not described as durability guarantees

Signals

Working

A test can advance to the precise deadline and consistently observe a miss.
A hand-worked sequence of gets, puts, updates and expiry predicts the exact LRU victim.
The two implementations satisfy the shared expiration, capacity, and recency contract while documenting their different input rules.
Contention cost is measured before a more complex synchronization design is proposed.

Going wrong

A cache hit returns an expired value or fails to promote it.
The key map and recency structure disagree after update or eviction.
Capacity is exceeded because only the target key is checked for expiry.
Tests sleep and become slow or flaky.
A race-free implementation still loses recency updates because operations are split across locks.
The cache is presented as protecting mutable object graphs or as a persistent system of record.