14. Jitter Buffer: Reorder Out-of-Order Real-Time Audio Packets

Problem

Cartesia's streaming API delivers synthesized audio to the client as a sequence of chunks, and the client is meant to start consuming and playing them incrementally rather than waiting for the whole utterance to finish. Over a real, lossy network path, those chunks can arrive out of send order. A jitter buffer sits in front of playback: it reorders incoming packets by sequence number, releasing only a contiguous in-order prefix at a time, and gives up waiting on a lost packet once too many later packets have piled up behind the gap.

Design a class, JitterBuffer, where max_wait bounds how many packets the buffer will hold behind a gap before giving up on it: once more than max_wait packets are buffered without having been able to release anything, the buffer force-skips forward to the earliest packet it has and releases the contiguous run from there.

Source: src/14_audio_packet_reorder_buffer.py

class JitterBuffer:
    def __init__(self, max_wait: int): ...
    def push(self, seq: int, payload: str) -> list[tuple[int, str]]: ...

>>> jb = JitterBuffer(max_wait=3)
>>> jb.push(1, "b")
[]
>>> jb.push(0, "a")
[(0, 'a'), (1, 'b')]
>>> jb.push(2, "c")
[(2, 'c')]

Step-by-Step Approach

1. Track a next_expected sequence number (starting at 0) and a dict[int, str] buffer of not-yet-released packets, keyed by sequence number.
2. On push(seq, payload), first drop the packet immediately (return []) if seq < next_expected — it's a late duplicate/straggler for something already released, and re-releasing it would corrupt playback order.
3. Otherwise store it in the buffer, then try to drain: while next_expected is a key in the buffer, pop it, append it to the result, and increment next_expected. This releases the longest contiguous in-order run starting from the current gap.
4. If the drain released nothing this call and the buffer now holds more than max_wait packets, the gap has been open too long — force-skip: jump next_expected straight to min(buffer) (the earliest packet actually held), then drain again from there.
5. Return whatever was released by the drain (possibly empty, if the gap is still open and under the wait limit).

The key insight is that "reorder" and "give up on a loss" are the same drain operation applied twice: a normal push tries to drain from the true next_expected, and a forced skip just relabels next_expected to the earliest available packet first, then reuses the identical drain loop — no separate code path is needed for the timeout case.

Reference solution

class JitterBuffer:
    def __init__(self, max_wait: int):
        self.max_wait = max_wait
        self.next_expected = 0
        self._buffer: dict[int, str] = {}

    def push(self, seq: int, payload: str) -> list[tuple[int, str]]:
        if seq < self.next_expected:
            # late duplicate/already-released packet: drop it
            return []
        self._buffer[seq] = payload
        released = self._drain()
        if not released and len(self._buffer) > self.max_wait:
            # waited too long for the gap at next_expected: give up on it and
            # jump straight to the earliest packet we do have
            self.next_expected = min(self._buffer)
            released = self._drain()
        return released

    def _drain(self) -> list[tuple[int, str]]:
        # release the contiguous in-order prefix starting at next_expected
        released = []
        while self.next_expected in self._buffer:
            released.append((self.next_expected, self._buffer.pop(self.next_expected)))
            self.next_expected += 1
        return released

Key Functions & Tricks

• dict[int, str] keyed by seq — O(1) insert and lookup for out-of-order arrivals, keyed by their sequence number.
• _drain() helper — shared release loop reused by both the normal path and the forced-skip path — avoids duplicating the contiguous-release logic.
• while next_expected in buffer: pop ... — releases exactly the contiguous in-order prefix, stopping the instant a real gap is hit.
• min(self._buffer) — finds the earliest still-buffered packet in O(k) to jump to when force-skipping past a lost packet.
• seq < next_expected check — guards against re-releasing or double-counting late duplicates of already-flushed packets.

How to Recognize This Pattern