Time-To-Live (TTL)

Caches, sessions, rate-limit counters, idempotency tokens — a huge share of real KV traffic is data that should clean itself up. TTL support means a key may carry an expiry deadline, after which the store treats it as gone.

Store the deadline, not the countdown

The idiom is to store an absolute expiry timestamp next to the value:

The trap is storing the remaining seconds and trying to tick them down: now every clock advance must visit every key. With an absolute deadline, expiry is one comparison at read time — a key is dead once now >= expires_at — and the remaining TTL is just expires_at - now.

Lazy vs active expiration

Lazy (passive): check the deadline only when the key is touched. A GET on an expired key removes it and reports a miss. Zero background cost — but keys nobody touches again leak memory forever.

Active: a sweeper hunts for corpses. Redis does this probabilistically: every ~100 ms it samples 20 random TTL keys, deletes the expired ones, and repeats immediately if more than 25% were expired — bounding CPU while keeping memory under control.

Production stores combine both, and so does this exercise: GET and LIST lazily purge whatever they find dead, and EXPIRE-COUNT runs an active sweep that reports how many entries the sweep itself removed. The interplay is observable: if GET and LIST already purged the corpses, a following EXPIRE-COUNT prints 0.

The simulated clock

Real time makes graders flaky, so the exercise simulates it: NOW <t> sets the clock — and prints OK like every other mutation. Semantics to honor exactly:

• PUT a 1 100 at NOW 0 expires at t=100 — the ttl argument is seconds from the current now, converted to an absolute deadline at write time.
• TTL k prints the remaining seconds (100 right after that PUT; 5 when a ttl-10 key is checked 5 seconds in), -1 for a live key with no TTL, and <nil> for a key that is missing or already expired.
• A plain re-PUT clears the TTL. PUT a 1 100 followed later by PUT a 2 (no ttl) makes a immortal. This mirrors Redis, where SET discards the old TTL unless you pass KEEPTTL — and yes, the grader tests it.

Your exercise

Implement NOW, PUT, GET, TTL, LIST, EXPIRE-COUNT. The grader-caught mistakes, from the real tests: (1) TTL overwrite — NOW 0, PUT a 1 100, NOW 50, PUT a 2, NOW 200, GET a must print 2; carrying the old deadline over kills the key at t=100 and prints <nil>; (2) expired vs no-TTL — a key stored at t=10 with ttl 5 answers <nil> to both GET and TTL at t=20, while a key stored with no ttl answers -1 to TTL, never <nil>; (3) sweep accounting — PUT a 1 5, PUT b 2 5, NOW 10, EXPIRE-COUNT prints 2, but in the visible test where GET b and two LISTs already lazily purged the dead keys, EXPIRE-COUNT prints 0 — count only what the sweep removes, not everything that ever expired.