Reservoir sampling

What this chapter covers

Every data structure in this book so far assumed you could hold your data — or at least knew how much there was. This final chapter tackles the case where you can't and don't: a stream of items of unknown, possibly infinite length, seen once, in order, too big to store. How do you draw a uniform random sample from it — every item equally likely — when you can never see it all at once and don't know how long it is? Reservoir sampling is the elegant answer: a single pass, fixed memory (just enough to hold the k samples), and a provable guarantee that when the stream finally ends, every one of its n items — including the first, seen billions of items ago — had exactly the same k/n chance of being in your sample. This chapter builds it, watches items flow past a small reservoir being kept or rejected with a shrinking probability, and shows that its uniformity is real where the obvious alternatives are badly biased. It's a small, perfect algorithm, and a fitting close to a tier — and a book — about how the right idea makes the seemingly impossible routine.

A bit of history

Reservoir sampling's simplest form, "Algorithm R," was popularized by Jeffrey Vitter in a 1985 paper, "Random Sampling with a Reservoir," though the core idea circulated earlier (Alan Waterman is often credited, via Knuth's The Art of Computer Programming, where it appears as an exercise). Vitter's contribution was both the clean analysis and faster variants (Algorithm L and others that skip ahead over rejected items, turning the O(n) passes into O(k log(n/k)) by computing how many items to skip at once). The algorithm's importance grew enormously with big data and streaming systems: when datasets outgrew memory and data began arriving as unbounded streams — web logs, clickstreams, sensor telemetry, network packets — reservoir sampling became the standard way to take a fair sample without buffering everything. It's built into big-data frameworks (Spark, Flink), database engines (for approximate query processing and statistics), and monitoring systems. Its enduring appeal is that it makes a genuinely hard-sounding problem — fair sampling from something you can't hold or measure — fall to five lines of code and one exact probability, which is why it's a favorite in both practice and interviews.

The intuition

The naive attempts all fail, and seeing why sharpens the insight. Keep the first k items? Biased toward the beginning — later items never get a chance. Pick k random indices in advance? You can't, because you don't know n. Buffer everything and sample at the end? That needs O(n) memory you don't have, and never terminates for an infinite stream. The requirement is strict: one pass, O(k) memory, and uniformity — every item, whenever it arrived, equally likely.

Reservoir sampling meets it with a rule that seems almost too simple. Keep the first k items in a "reservoir." Then, for each subsequent item (the i-th, counting from 1), keep it with probability k/i; and when you keep it, have it replace a uniformly random one of the k items currently in the reservoir. Notice the acceptance probability shrinks as the stream grows: the 100th item is kept with probability k/100, the millionth with probability k/1,000,000 — later items are individually less likely to be accepted, which is exactly what balances the fact that early items have had more chances to be replaced. The magic is that these two effects cancel perfectly: at every moment, and at the very end, each item seen so far is in the reservoir with probability exactly k/(current count). An item that entered early has survived many rounds of possible replacement; an item that entered late was less likely to be accepted at all; and the arithmetic works out so that all of them, first to last, end at probability k/n. The face-off confirms it: reservoir sampling's selection probability is dead flat across all stream positions, while "keep the first k" selects only the start and "accept with a constant ½" over-selects the end.

Complexity: how it scales

Reservoir sampling is a single O(n) pass over the stream — one random number and a comparison per item — using O(k) memory, independent of the stream length n (which it never needs to know). Vitter's Algorithm L improves the time to O(k log(n/k)) by computing, after each acceptance, how many items to skip before the next acceptance (drawing that gap from the right distribution), avoiding a coin flip for every rejected item — useful when acceptances are rare in a very long stream. But the headline property isn't speed, it's correctness under constraints: uniformity with no buffering. The face-off measures that uniformity directly — the empirical probability that each stream position ends up in the sample, for reservoir sampling versus two plausible-but-wrong stream samplers:

Reservoir sampling's line is flat — every position sits at k/n = 0.2, the spread between the most- and least-likely position just 0.011, statistical noise. That flatness is uniformity: no position is favored, exactly as required. The two biased samplers show what happens when the probability is wrong. "Keep the first k" is a step function — probability 1 for the first six positions, 0 for all the rest, the most extreme bias possible (spread 1.0). "Accept with a constant ½" (instead of the shrinking k/i) rises steadily toward the end, because a fixed acceptance rate lets later items keep bumping earlier ones out, over-representing the tail (spread 0.43). Both are reasonable-looking stream samplers that are quietly, badly wrong — which is the whole point of the exact k/i rule. The difference between a fair sample and a biased one is a single correctly-chosen probability, and only reservoir sampling gets it right.

What it's good at, what it isn't

Reservoir sampling is the right tool whenever you must sample from data you can't fully hold or whose size you don't know in advance: streaming data (clickstreams, telemetry, network traffic, log lines), files or database tables too large for memory (a single scan samples them fairly), and online settings where you must maintain a representative sample as data arrives and be ready to report it at any moment. It's used in A/B testing and experiment sampling, approximate query processing in databases, load and performance sampling in monitoring systems, and anywhere a uniform sample of a big or unbounded dataset is needed in one pass. Its guarantees are exact (true uniformity, not approximate), its memory is minimal and fixed, and it needs no knowledge of the stream's length.

Where it's the wrong tool is when you can hold all the data and know its size — then random.sample is simpler and does the same thing without the streaming machinery. It gives an unweighted uniform sample by default; weighted sampling (items with different probabilities) needs the weighted variant (A-Res/A-ExpJ), which is more involved. It samples without replacement within the reservoir; sampling with replacement, or stratified/ grouped sampling, needs adaptations. And while it's exactly uniform, a single random sample is still just a sample — it has sampling variance, so for a fixed dataset where you need reproducibility or a specific subset, other methods may fit better. Reservoir sampling's niche is precise and important: fair, fixed-memory, single-pass sampling of streams and oversized data — the case nothing else handles as cleanly.

The data, or the inputs

The face-off empirically measures the probability that each stream position ends up in the sample — over tens of thousands of trials — for reservoir sampling against two biased stream samplers (keep-first-k and constant-½ acceptance), showing reservoir sampling's flat uniformity against their skew. Correctness is checked the same way at finer tolerance: across 40,000 trials, every item's empirical selection frequency must sit within 0.02 of the theoretical k/n, the sample must always have exactly k distinct items from the stream, and a stream shorter than k must return everything. The animation runs a size-3 reservoir over a ten-item stream, showing the first three items fill it, then each later item accepted (replacing a random slot) or rejected with the shrinking probability k/i.

Build it, one function at a time

Reservoir sampling — the whole algorithm in a single pass:

def reservoir_sample(stream, k, rng=random):
    """A uniform random k-sample of `stream` in one pass, O(k) memory, without knowing the stream's
    length. Fill the reservoir with the first k items. For each later item at index i (0-based), pick
    a random slot j in [0, i]; if j lands inside the reservoir (j < k), the new item replaces slot j —
    which happens with probability k/(i+1), exactly the acceptance rate that keeps the sample uniform.
    Returns the reservoir."""
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)                # the first k items fill the reservoir
        else:
            j = rng.randint(0, i)                 # uniform in [0, i]; accepts with prob k/(i+1)
            if j < k:
                reservoir[j] = item               # replace a uniformly random held item
    return reservoir


def reservoir_trace(stream, k, rng=random):
    """Same algorithm, but record each step (accepted?, which slot, the reservoir after) — for the
    animation. Returns (reservoir, steps)."""
    reservoir, steps = [], []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)
            steps.append({"i": i, "item": item, "action": "fill", "slot": i, "prob": 1.0,
                          "reservoir": reservoir[:]})
        else:
            j = rng.randint(0, i)
            prob = k / (i + 1)
            if j < k:
                reservoir[j] = item
                steps.append({"i": i, "item": item, "action": "accept", "slot": j, "prob": prob,
                              "reservoir": reservoir[:]})
            else:
                steps.append({"i": i, "item": item, "action": "reject", "slot": None, "prob": prob,
                              "reservoir": reservoir[:]})
    return reservoir, steps

Watch it work

Here's a size-3 reservoir sampling a ten-item stream, A through J. The leftmost cell (in) is the item currently arriving; the three cells to its right are the reservoir. The first three items — A, B, C — simply fill the empty reservoir. Then the interesting part: each new item is kept with probability k/i (shown in the caption, and shrinking as the stream grows — 3/4 for the 4th item, 3/5 for the 5th, and so on). When an item is accepted (green), it replaces a uniformly random one of the three held items, bumping it out; when rejected (red), the reservoir is unchanged. Watch how later items are individually less likely to get in — but if they do, they can evict an early survivor. When the stream ends, the three items left are a genuinely uniform sample: each of the ten had probability 3/10 of being among them, no matter how early or late it arrived, which the shrinking k/i acceptance is precisely engineered to guarantee:

The complete code

The from-scratch tab is reservoir sampling (and the traced version for the animation); the library tab is the store-everything-then-random.sample reference (exact but O(n) memory and needs the full data) plus the two biased samplers from the face-off. Flip between them — random.sample is what you'd use when you can hold the data; reservoir sampling is the five-line answer when you can't, and comparing them shows exactly what constraint the reservoir version is designed around.

"""Reservoir sampling — draw a uniform random sample of k items from a stream of UNKNOWN, possibly
infinite length, in a single pass, using only enough memory to hold the k samples. It answers a
question the earlier structures can't touch: how do you sample fairly from data too big to store, or
still arriving, when you can't hold it all and don't even know how much there is? Log files, sensor
streams, click events, database scans too large for memory — all of these you see once, in order, and
must sample without a second pass.

The naive approaches fail: keeping the first k biases toward the beginning; you can't pick k random
INDICES because you don't know n; storing everything to sample at the end needs O(n) memory you don't
have. Reservoir sampling (Algorithm R) solves it with a beautifully simple rule. Keep the first k
items. Then for the i-th item (counting from 1), keep it with probability k/i, and if you keep it,
have it REPLACE a uniformly random one of the k currently held. That's it — one pass, O(k) memory, and
a provable guarantee that at the end EVERY item the stream produced, no matter how long ago, has
exactly k/n probability of being in the sample.
"""
import random


# region: reservoir
def reservoir_sample(stream, k, rng=random):
    """A uniform random k-sample of `stream` in one pass, O(k) memory, without knowing the stream's
    length. Fill the reservoir with the first k items. For each later item at index i (0-based), pick
    a random slot j in [0, i]; if j lands inside the reservoir (j < k), the new item replaces slot j —
    which happens with probability k/(i+1), exactly the acceptance rate that keeps the sample uniform.
    Returns the reservoir."""
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)                # the first k items fill the reservoir
        else:
            j = rng.randint(0, i)                 # uniform in [0, i]; accepts with prob k/(i+1)
            if j < k:
                reservoir[j] = item               # replace a uniformly random held item
    return reservoir


def reservoir_trace(stream, k, rng=random):
    """Same algorithm, but record each step (accepted?, which slot, the reservoir after) — for the
    animation. Returns (reservoir, steps)."""
    reservoir, steps = [], []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)
            steps.append({"i": i, "item": item, "action": "fill", "slot": i, "prob": 1.0,
                          "reservoir": reservoir[:]})
        else:
            j = rng.randint(0, i)
            prob = k / (i + 1)
            if j < k:
                reservoir[j] = item
                steps.append({"i": i, "item": item, "action": "accept", "slot": j, "prob": prob,
                              "reservoir": reservoir[:]})
            else:
                steps.append({"i": i, "item": item, "action": "reject", "slot": None, "prob": prob,
                              "reservoir": reservoir[:]})
    return reservoir, steps
# endregion

"""The reference and the contrasts. Three ways to think about sampling k from a stream:

- `store_all_sample` is what you'd do if you COULD hold everything — buffer the whole stream, then
  `random.sample`. It's exact and uniform (the correctness reference for reservoir sampling's
  uniformity), but it needs O(n) memory and a known, finite length — exactly what reservoir sampling
  avoids.
- `keep_first_k` and `constant_half` are BIASED stream samplers, to show why the k/i acceptance
  probability is not arbitrary: keeping the first k over-weights the start, and accepting every item
  with a constant 1/2 over-weights the end. Comparing their per-position selection frequency against
  reservoir sampling's flat line is the face-off.

In production you'd use reservoir sampling directly (it's short) or a streaming framework's built-in;
`random.sample` is the reference for finite in-memory data.
"""
import random


# region: reference
def store_all_sample(stream, k):
    """Buffer the entire stream, then random.sample — exact and uniform, but O(n) memory and needs the
    full data in hand. The reference reservoir sampling matches without either requirement."""
    data = list(stream)
    if k >= len(data):
        return data[:]
    return random.sample(data, k)
# endregion


# region: biased
def keep_first_k(stream, k):
    """A biased sampler: just keep the first k items. Positions 0..k-1 are always selected, everything
    after is never selected — maximally biased toward the start."""
    out = []
    for item in stream:
        if len(out) < k:
            out.append(item)
        else:
            break
    return out


def constant_half(stream, k, rng=random):
    """A biased sampler: fill k, then accept every later item with a CONSTANT probability 1/2 (not
    k/i), replacing a random slot. Because the acceptance rate doesn't shrink as the stream grows,
    later items are over-represented — the sample skews toward the end."""
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)
        elif rng.random() < 0.5:
            reservoir[rng.randrange(k)] = item
    return reservoir
# endregion

Scratch vs library

Reservoir sampling is a perfect closing note because it distills the entire advanced tier's lesson into five lines: the right idea makes the impossible routine. Sampling fairly from an infinite stream you can't store sounds like it shouldn't be possible — and the naive attempts all fail — yet one exact probability, k/i, makes it fall out cleanly, with a proof that telescopes to k/n. That's the same spirit as the Bloom filter (represent a set without storing it), the skip list (balance without rebalancing), and the k-d tree (search space without scanning it): a clever structure or a clever probability buys you something that brute force can't. And the face-off drives home a theme from the whole book — that a plausible-looking algorithm can be quietly, badly wrong (constant-½ sampling looks fine and skews hard), so correctness must be reasoned about and verified, not assumed. In production you'd inline reservoir sampling (it's shorter than importing anything) or use a streaming framework's built-in; understanding it is understanding how big-data systems sample the unboundable, and why the exact probability, not a reasonable-seeming one, is what makes a sample fair.

Where you'll actually meet it

Reservoir sampling runs throughout big-data and streaming infrastructure. Data-processing frameworks (Spark's sample, Flink) use it to sample massive or streaming datasets in one pass. Databases use it for approximate query processing, statistics gathering, and sampling large tables that don't fit in memory. Monitoring and observability systems (metrics, tracing, log sampling) use it to keep a representative sample of high-volume events under fixed memory — distributed tracing systems sample spans this way. A/B testing and experimentation platforms sample users or events with it. Machine-learning pipelines use it to subsample huge or streaming training data. Network systems sample packets for analysis with it. And it's a classic interview and competitive-programming problem precisely because it tests whether you understand the exact probability. Anywhere a fair sample of a stream or an oversized dataset is needed in a single pass, reservoir sampling — or its weighted and skip-optimized variants — is very likely doing the work.

Takeaways

Reservoir sampling draws a uniform random k-sample from a stream of unknown length in a single pass and O(k) memory: keep the first k, then keep the i-th item with probability k/i, replacing a uniformly random held item. The shrinking acceptance probability exactly balances early items' greater exposure to replacement, so every item — first to last — ends with probability k/n, provable by a telescoping product. It needs neither the stream's length nor the full data, and its uniformity is exact where plausible alternatives (keep-first-k, constant acceptance) are badly biased. It's the clean answer to fair sampling from the unstorable.

With reservoir sampling the book closes. Fifty-six chapters have built the core of data structures and algorithms from the ground up — from how we measure cost, through the linear structures, hashing, recursion and sorting, trees, graphs, strings, the algorithm-design paradigms, and finally these advanced and probabilistic structures — each one built by hand, watched operating on real data, and measured against the library it competes with. The throughline has been that the right structure or the right idea is what separates the tractable from the intractable, the fair from the biased, the fast from the slow: a table instead of recomputation, an express lane instead of a walk, a heuristic instead of a flood, a probability instead of a guarantee. That judgment — knowing which idea a problem calls for, and why — is what the whole book has been for.