Time, TTLs and expiry inside objects

01The intuition

The problem it solves

A school issues temporary hall passes. A pass is valid for 10 minutes. The first version of the pass register reads the wall clock directly and checks validity when asked.

import time

class PassRegister:
    def __init__(self) -> None:
        self.issued: dict[str, float] = {}      # student -> expiry time

    def issue(self, student: str) -> None:
        self.issued[student] = time.time() + 600

    def is_valid(self, student: str) -> bool:
        return self.issued.get(student, 0) > time.time()

Two problems hide here. First, the test for "a pass expires after 10 minutes" would have to sleep for 10 minutes, so nobody writes it. Second, expired entries never leave the dictionary; after a year it holds every pass ever issued. The same two problems appear in every cache, rate limiter and session store.

Build it one piece at a time

Step one: inject the clock. The register takes a function that returns the current time, defaulting to the real one. A test passes a fake clock it can move by hand, and the ten-minute test runs in a millisecond.

from typing import Callable

class PassRegister:
    def __init__(self, ttl: float = 600, clock: Callable[[], float] = time.time) -> None:
        self.ttl = ttl
        self.clock = clock
        self.issued: dict[str, float] = {}

    def issue(self, student: str) -> None:
        self.issued[student] = self.clock() + self.ttl

    def is_valid(self, student: str) -> bool:
        return self.issued.get(student, 0) > self.clock()

Step two: lazy expiry. When an entry is looked up and found expired, delete it on the spot. No background thread, no timers; the cost is paid by the caller who touched the entry anyway.

class PassRegister:   # continued
    def is_valid(self, student: str) -> bool:
        expiry = self.issued.get(student)
        if expiry is None:
            return False
        if expiry <= self.clock():
            del self.issued[student]        # lazy expiry
            return False
        return True

Step three: entries nobody looks up again still leak. Keep a second structure ordered by expiry time, a heap of (expiry, student), and sweep from its front whenever a write happens or when a size cap is hit. Each sweep removes only entries that are already past, so the work is proportional to what actually expired.

import heapq

class PassRegister:
    def __init__(self, ttl: float = 600, clock: Callable[[], float] = time.time) -> None:
        self.ttl, self.clock = ttl, clock
        self.issued: dict[str, float] = {}
        self.by_expiry: list[tuple[float, str]] = []

    def issue(self, student: str) -> None:
        self.sweep()
        expiry = self.clock() + self.ttl
        self.issued[student] = expiry
        heapq.heappush(self.by_expiry, (expiry, student))

    def sweep(self) -> None:
        now = self.clock()
        while self.by_expiry and self.by_expiry[0][0] <= now:
            expiry, student = heapq.heappop(self.by_expiry)
            if self.issued.get(student) == expiry:   # not re-issued since
                del self.issued[student]

With a fake clock starting at 0 and ttl 600, the state evolves like this:

Why it works

The invariant is: an entry is returned as valid only if its expiry is strictly in the future according to the injected clock, and nothing is ever removed before its expiry. Lazy expiry keeps the first half true at the point of use; the sweep keeps memory bounded by removing only entries whose expiry has passed. The check "stored expiry equals heap expiry" protects re-issued entries from being deleted by an old heap record.

Where it breaks: wall clocks jump. If the machine's clock is corrected backwards by a minute, passes live a minute longer. Use a monotonic clock for durations (Python's time.monotonic) and the wall clock only for timestamps shown to people. The second trap is the boundary: is a pass valid at exactly the expiry second? Decide, write it in the method name or docstring, and test that exact instant.

memory without sweep: all entries ever issued. With sweep: at most the entries issued in the last ttl, plus stale heap records until the next write

The trade-off you must say out loud

Lazy expiry is free but leaves garbage; a sweep costs a little on every write; a background thread with a timer wheel gives precise expiry at the price of concurrency and shutdown handling. For an in-process cache, lazy plus sweep is the usual answer. Say which you chose and why, and that the clock is injected so the behaviour is testable. The follow-up that usually comes next is "what if there are millions of entries with the same expiry", where a timer wheel of buckets per second replaces the heap.

Where it shows up in the 100 Google problems

• Key-value store with TTL: exactly this pattern, with the capacity cap added to the sweep.
• Rate limiter class: a token bucket refills by elapsed time read from the injected clock.
• Hit counter: hits older than 300 seconds expire from a ring of buckets.
• Movie ticket booking: seat holds expire so a user who abandons checkout frees the seat.
• Stopwatch: a monotonic clock injected, which is what makes pause and resume testable.

02Used in these problems

• Design a cache manager with pluggable eviction and TTL
• Design a key-value store with TTL
• Design a hit counter
• Design a logger rate limiter
• Design a rate limiter class
• Design a timer that supports many concurrent timers
• Design a stopwatch class
• Design a blocking connection pool
• Design a movie ticket booking system
• Design a URL shortener (class level)
• Design a traffic signal controller