10. Bounded State Cache for Concurrent Voice Contexts

Problem

Cartesia's WebSocket streaming API lets a single connection host many independent "contexts" at once, each a full-duplex continuous stream with its own running state. A production server juggling many simultaneous voice contexts can't keep every context's state resident forever — it needs to cap how many contexts stay "hot" in memory at once and evict the least-recently-touched one when a new context needs a slot.

Design a class, ContextStateCache, that holds state across calls: touch(context_id) marks a context as most-recently-used, creating a slot for it if it's new, and evicting the least-recently-used context if the cache is over capacity.

Source: src/10_state_cache_eviction.py

class ContextStateCache:
    def __init__(self, capacity: int): ...
    def touch(self, context_id: str) -> str | None: ...  # returns evicted id, or None
    def active_contexts(self) -> list[str]: ...  # most-recent -> least-recent

>>> cache = ContextStateCache(2)
>>> cache.touch("call-1")
>>> cache.touch("call-2")
>>> cache.touch("call-1")
>>> cache.touch("call-3")
'call-2'
>>> cache.active_contexts()
['call-3', 'call-1']

Step-by-Step Approach

1. Store resident contexts in an OrderedDict keyed by context_id, using its natural iteration order (oldest inserted/moved → newest) to track recency implicitly — no separate timestamp bookkeeping needed.
2. On touch(context_id), first check if the context is already resident. If so, call move_to_end(context_id) to refresh its recency and return None — no eviction is needed for a context that's already in the cache.
3. If the context is new and the cache is already at capacity, evict the least-recently-used entry with popitem(last=False), which pops from the front of the OrderedDict (the oldest, since fresh touches move things to the back).
4. Insert the new context at the end (most-recently-used position) and return the evicted id, or None if nothing had to be evicted.
5. For active_contexts(), remember the OrderedDict is stored oldest->newest but the spec wants most-recent->least-recent, so return list(reversed(self._contexts)).

The key insight is that an OrderedDict already gives you O(1) reordering (move_to_end) and O(1) pop-from-either-end (popitem), so you get a full LRU cache without hand-rolling a doubly linked list — the same idea as the classic LRU cache design problem, just applied to context ids instead of arbitrary key/value pairs.

Reference solution

from collections import OrderedDict


class ContextStateCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        # OrderedDict: front = least-recently-used, back = most-recently-used
        self._contexts: OrderedDict[str, bool] = OrderedDict()

    def touch(self, context_id: str):
        if context_id in self._contexts:
            # already resident: just refresh its recency, no eviction needed
            self._contexts.move_to_end(context_id)
            return None
        evicted = None
        if len(self._contexts) >= self.capacity:
            # popitem(last=False) removes the front == least-recently-used entry
            evicted, _ = self._contexts.popitem(last=False)
        self._contexts[context_id] = True
        return evicted

    def active_contexts(self):
        # stored oldest -> newest; spec wants most-recent -> least-recent
        return list(reversed(self._contexts))

Key Functions & Tricks

• collections.OrderedDict — dict subclass that remembers insertion order and supports O(1) reordering.
• move_to_end(key) — moves an existing key to the most-recently-used end in O(1).
• popitem(last=False) — pops from the front (oldest/least-recently-used) in O(1); last=True would pop from the back.
• list(reversed(od)) — iterates an OrderedDict back-to-front to present most-recent-first without mutating it.
• context_id in self._contexts — O(1) membership check to distinguish a refresh from a new insertion.

How to Recognize This Pattern