24. Terminal project: an LRU cache with TTL, two ways

Goal: a least-recently-used cache with a maximum size and per-entry expiry, the kind you put in front of a slow DNS resolver or model-metadata API. Build it twice: first on OrderedDict, then from scratch with a hash map and a doubly linked list, and compare with the Rust LRU and the Go LRU.

# labs/lru.py
import time
from collections import OrderedDict
from collections.abc import Callable, Hashable
from dataclasses import dataclass
from typing import Generic, TypeVar

K = TypeVar("K", bound=Hashable)
V = TypeVar("V")

class LRU(Generic[K, V]):
    """Version 1: OrderedDict keeps keys in use order; move_to_end is O(1)."""

    def __init__(self, maxsize: int, ttl: float, clock: Callable[[], float] = time.monotonic) -> None:
        self.maxsize, self.ttl, self.clock = maxsize, ttl, clock
        self._d: OrderedDict[K, tuple[float, V]] = OrderedDict()

    def get(self, key: K) -> V | None:
        item = self._d.get(key)
        if item is None:
            return None
        expires, value = item
        if self.clock() >= expires:
            del self._d[key]
            return None
        self._d.move_to_end(key)                 # mark as most recently used
        return value

    def put(self, key: K, value: V) -> None:
        self._d[key] = (self.clock() + self.ttl, value)
        self._d.move_to_end(key)
        while len(self._d) > self.maxsize:
            self._d.popitem(last=False)          # evict the least recently used

    def __len__(self) -> int:
        return len(self._d)

@dataclass(slots=True, eq=False)
class _Node(Generic[K, V]):
    key: K
    value: V
    expires: float
    prev: "_Node[K, V] | None" = None
    next: "_Node[K, V] | None" = None

class LRU2(Generic[K, V]):
    """Version 2: dict for O(1) lookup + a doubly linked list for O(1) reordering."""

    def __init__(self, maxsize: int, ttl: float, clock: Callable[[], float] = time.monotonic) -> None:
        self.maxsize, self.ttl, self.clock = maxsize, ttl, clock
        self._map: dict[K, _Node[K, V]] = {}
        self._head: _Node[K, V] | None = None    # most recent
        self._tail: _Node[K, V] | None = None    # least recent

    def _unlink(self, n: _Node[K, V]) -> None:
        if n.prev: n.prev.next = n.next
        else: self._head = n.next
        if n.next: n.next.prev = n.prev
        else: self._tail = n.prev
        n.prev = n.next = None

    def _push_front(self, n: _Node[K, V]) -> None:
        n.next, n.prev = self._head, None
        if self._head: self._head.prev = n
        self._head = n
        if self._tail is None: self._tail = n

    def get(self, key: K) -> V | None:
        n = self._map.get(key)
        if n is None:
            return None
        if self.clock() >= n.expires:
            self._unlink(n); del self._map[key]
            return None
        self._unlink(n); self._push_front(n)
        return n.value

    def put(self, key: K, value: V) -> None:
        if (old := self._map.pop(key, None)) is not None:
            self._unlink(old)
        n = _Node(key, value, self.clock() + self.ttl)
        self._map[key] = n
        self._push_front(n)
        while len(self._map) > self.maxsize and self._tail is not None:
            lru = self._tail
            self._unlink(lru); del self._map[lru.key]

    def __len__(self) -> int:
        return len(self._map)

if __name__ == "__main__":
    now = [0.0]
    for cls in (LRU, LRU2):
        c = cls(maxsize=2, ttl=10, clock=lambda: now[0])
        now[0] = 0
        c.put("a", 1); c.put("b", 2); c.get("a"); c.put("c", 3)   # evicts b
        assert (c.get("a"), c.get("b"), c.get("c")) == (1, None, 3)
        now[0] = 11                                             # everything expires
        assert c.get("a") is None and c.get("c") is None
        print(cls.__name__, "ok")

What to notice:

• The injected clock (clock=time.monotonic) makes expiry testable without sleep. Inject time, randomness, and I/O; it is the single best habit for testable code.
• The linked list that is famously hard in Rust is easy in Python: the garbage collector and reference counting handle the cycles of prev/next pointers. The price is memory and speed: each _Node is a full object. Version 1 is shorter and faster, because OrderedDict is implemented in C. In Python, the built-in, C-backed structure almost always beats the one you write.
• functools.lru_cache is the production version of this for function results. It has no TTL; for that, use cachetools.TTLCache.