Expiring key-value store

THE PROBLEM

“A single-process service caches temporary verification results. Each write has a time to live. Reads must never return an expired result, including at the exact expiry instant. Tests must run instantly and deterministically. How would you make time an explicit dependency?”

Constructed practice question. Prerequisites: maps and LRU contracts. TTL is a duration; a deadline is the clock reading at write plus TTL. A monotonic clock advances without wall-clock corrections.

Contract	Required behavior
Input	Hashable key, arbitrary value, finite nonnegative TTL; injected monotonic clock
Output	`get` returns live value or raises `KeyError`; delete reports live removal
Expiration	Live exactly while `now < deadline`; TTL=0 immediately removes key
Cleanup	`purge()` removes all entries expired at one sampled instant and returns count
Failure/scope	Invalid TTL raises `ValueError` without overwriting; no persistence/concurrency

Optional refresher · the underlying tool

A TTL entry needs both a value and an expiry instant from a chosen clock. Compare the clock on read; background cleanup alone cannot promise expired data stays hidden:

value, expires_at = "hello", 105.0
now = 105.0
print(now >= expires_at)  # True: expired at the boundary

If an old expiry event runs after a new value replaces the key, it must not delete the replacement. Track a generation or compare the stored expiry before deleting.

A design choice worth saying aloud

Store expires_at from a specified clock and compare it on every read; cleanup runs can lag. An expiry task should carry a generation/version so an old task cannot delete a new value under the same key. State whether the clock is monotonic process time or persisted wall time before promising survival across restarts.

What the interviewer expects

The interviewer gives you the scenario and the contract above. Explain what a successful call returns, walk through one example below, and name what your state means before choosing a data structure.

Done means: get returns live value or raises KeyError; delete reports live removal.

Now predict each output before looking at the reference; invalid input should leave any existing state unchanged unless the contract says otherwise.

Test-case scenarios to settle before coding

01 · Before boundary

Input / starting state: deadline 105; get at 104.999
Expected result: stored value

What it is testing: Liveness is strict now < deadline.

02 · Exact boundary

Input / starting state: get at 105
Expected result: KeyError

What it is testing: Expiration does not wait for cleanup.

03 · Stored None

Input / starting state: live key maps to None
Expected result: get returns None

What it is testing: A miss needs an exception, not a sentinel.

04 · Zero TTL

Input / starting state: put with TTL 0
Expected result: key is immediately absent

What it is testing: No transient live interval exists.

05 · Overwrite invalid

Input / starting state: live key then put invalid TTL
Expected result: ValueError; old value/deadline remain

What it is testing: Validation is atomic.

06 · Purge sample

Input / starting state: a expires at 104, b at 105, c at 106; injected now=105
Expected result: purge() returns 2; c remains

What it is testing: The boundary is expired, and one clock sample decides all entries.

For each case, show which branch or state change produces that result.

At clock 100, set(a,'ok',5) yields 'ok' at 104.999 and KeyError at 105. Overwrite a at 103 with TTL 10 and it remains live at 105 until deadline 113. Storing None remains distinguishable from absence. Clarify whether reads extend expiry (they do not) and whether deletion of an expired key returns true (false).

Diagram: Test-case scenarios to settle before coding

Implement without sleeping. Write the exact-boundary test before deciding whether to use < or <= in the liveness check.

Solution, logical expiry, and follow-ups

One timer per key is an attractive baseline but creates scheduling/resource costs, and a timer callback may run after the deadline. A read that trusts “the timer has not fired yet” can return stale data. Periodically deleting expired keys also cannot replace checking expiry on the read path.

Store (value,deadline) in a dictionary. A get samples the injected clock and checks now >= deadline; if true, remove that entry and raise KeyError. An overwrite replaces both value and deadline. purge samples once, collects expired keys, and deletes them after iteration to avoid modifying the dictionary during traversal. TTL validation happens before changing existing state.

a successful get returns only a value whose stored deadline is strictly greater than that operation's clock sample. Logical absence at expiry does not require physical deletion at that instant. This separation permits lazy cleanup while preserving read correctness. It does not bound retained memory: expired keys never accessed again remain until purge.

01 · Try this input

Input / starting state: 100
Expected result: live

Action: set a, TTL 5

Stored deadline: 105

02 · Try this input

Input / starting state: 103
Expected result: new value

Action: overwrite a, TTL 10

Stored deadline: 113

03 · Try this input

Input / starting state: 105
Expected result: new value survives old deadline

Action: get a

Stored deadline: 113

04 · Try this input

Input / starting state: 113
Expected result: missing

Action: get a

Stored deadline: removed

Get/set/delete cost expected O(1) time and O(1) auxiliary space. N stored entries use O(N) state, counting expired entries awaiting cleanup. Purge costs O(N) time and O(X) temporary keys for X expired entries. These are process-local operations; clock advancement and caller scheduling are outside the data-structure cost.

Follow-up 1 — background heap cleanup. Predict the danger of an old expiry record after overwrite. A heap item must carry a generation or match the current deadline; otherwise the old timer deletes a newer value. Stale heap entries also need a compaction policy to keep memory proportional to current keys.

Follow-up 2 — persist across restarts. A process monotonic deadline cannot be serialized as a portable wall-clock expiry. Choose a persisted timestamp and clock-skew policy, or expire everything on restart. Multiple replicas additionally need a defined authority for writes and expiry decisions.

Senior depth tests equality, overwrite-before-expiry, invalid-write atomicity, and cleanup with a fake clock. Lead depth explains retention and time authority rather than promising that local TTL implies a distributed revocation guarantee.

Reference: solution.py (download file, source below); test_solution.py (download file, source below) supplies the fake clock and never uses timing sleeps.

solution.py · solution.py

"""Single-process TTL dictionary with injected monotonic clock and explicit purge."""
import math
import time


class ExpiringStore:
    def __init__(self, clock=time.monotonic):
        self.clock = clock
        self._entries = {}

    def set(self, key, value, ttl):
        if not isinstance(ttl, (int, float)) or not math.isfinite(ttl) or ttl < 0:
            raise ValueError("finite nonnegative TTL required")
        if ttl == 0:
            self._entries.pop(key, None)
            return
        deadline = self.clock() + ttl
        if not math.isfinite(deadline):
            raise ValueError("expiration must be finite")
        self._entries[key] = value, deadline

    def get(self, key):
        value, deadline = self._entries[key]
        if self.clock() >= deadline:
            del self._entries[key]
            raise KeyError(key)
        return value

    def delete(self, key):
        try:
            self.get(key)
        except KeyError:
            return False
        del self._entries[key]
        return True

    def purge(self):
        """Remove all entries expired at one clock reading; return removed count."""
        now = self.clock()
        expired = [key for key, (_, deadline) in self._entries.items() if now >= deadline]
        for key in expired:
            del self._entries[key]
        return len(expired)

test_solution.py · test_solution.py

import math
import unittest
from solution import ExpiringStore


class Clock:
    def __init__(self):
        self.now = 100

    def __call__(self):
        return self.now


class Tests(unittest.TestCase):
    def setUp(self):
        self.clock = Clock()
        self.store = ExpiringStore(self.clock)

    def test_exact_boundary_and_none_value(self):
        self.store.set('a', None, 5)
        self.clock.now = 104.999
        self.assertIsNone(self.store.get('a'))
        self.clock.now = 105
        with self.assertRaises(KeyError):
            self.store.get('a')
        self.assertNotIn('a', self.store._entries)

    def test_overwrite_zero_and_invalid_atomicity(self):
        self.store.set('a', 'old', 5)
        self.clock.now = 103
        self.store.set('a', 'new', 10)
        self.clock.now = 105
        self.assertEqual(self.store.get('a'), 'new')
        for ttl in [-1, math.inf, math.nan]:
            with self.assertRaises(ValueError):
                self.store.set('a', 'bad', ttl)
            self.assertEqual(self.store.get('a'), 'new')
        self.store.set('a', 'zero', 0)
        with self.assertRaises(KeyError):
            self.store.get('a')

    def test_purge_and_delete(self):
        self.store.set('a', 1, 2)
        self.store.set('b', 2, 3)
        self.store.set('c', 3, 5)
        self.clock.now = 103
        self.assertEqual(self.store.purge(), 2)
        self.assertEqual(self.store.purge(), 0)
        self.assertFalse(self.store.delete('missing'))
        self.assertTrue(self.store.delete('c'))
        self.assertFalse(self.store.delete('c'))

    def test_delete_expired_is_false(self):
        self.store.set('a', 1, 1)
        self.clock.now = 101
        self.assertFalse(self.store.delete('a'))


if __name__ == '__main__':
    unittest.main()

python -m unittest discover -s curriculum/04-scale-and-evolution/01-data-at-scale/problems/29-expiring-key-value-store -p 'test_*.py'