↩ back to Probabilistic

Reservoir Sampling

The HyperLogLog page answers "roughly how many distinct items?" from a stream too long to hold in memory, in fixed space. Reservoir sampling answers a different question about the same kind of stream: give me k items, chosen uniformly at random from everything seen so far — without knowing in advance how long the stream is, without storing the whole thing, and without giving later items any better or worse odds than earlier ones. A log file being tailed forever, a firehose of events with no defined end, a database cursor too large to sort — all the same shape: you find out the stream is over only when it's over, and by then it's too late to go back and pick fairly from everything you've thrown away.

The classic solution, Algorithm R (Alan Waterman, popularized by Knuth), keeps a reservoir of exactly k slots. The first k items fill it outright. Every item after that — the i-th one seen (1-indexed) — gets one shot: draw a uniform random integer j in [1, i]; if j ≤ k, item i overwrites slot j, evicting whatever was there; otherwise item i is discarded for good. No item is ever revisited once its turn passes. That's the entire algorithm — and the surprising part, proved below and checked live further down, is that this simple rule gives every item that has ever passed through, from the 1st to the n-th, an exactly equal k/n probability of surviving to the end.

Try it

A fixed 12-item stream (labeled #0 through #11) feeding a 4-slot reservoir, using a seeded random generator so the trace is identical every time you replay it. Click Next to feed one item at a time. The first four auto-fill the reservoir; after that, watch the draw: #4 is admitted and evicts #3, #7 and #8 are both drawn and discarded, and the stream ends with #5, #1, #9, #6 sitting in the reservoir — a mix of very early and fairly late items, exactly as "every item equally likely" predicts, not "later items crowd out earlier ones" or vice versa.

Core operations

• feed(item) — the only operation. While the reservoir has room, append outright. Once full, draw j uniformly from [1, i] where i is this item's 1-indexed position in the stream so far; admit and evict slot j only if j ≤ k. Amortized O(1) per item — one random draw, one comparison, at most one write.
• sample() — read the current reservoir contents. Valid to call after any number of feed calls, not just at the "end" of the stream, because there's no such thing as a defined end the algorithm needs to wait for.
• There is no undo and no way to ask which items were rejected — once an item loses its draw, nothing about it survives, the same one-shot-per-item shape as HyperLogLog's per-register update.

Why every item ends up equally likely

Induction on the stream position. The claim: right after the i-th item is fed (i ≥ k), every one of those i items seen so far sits in the reservoir with probability exactly k/i. Base case i = k: all k items are in, trivially with probability 1 = k/k. Inductive step: assume it holds after item i. Item i+1 arrives and is admitted with probability k/(i+1) — if admitted, it evicts a uniformly random one of the k current occupants, so each of the first i items survives this one step with probability 1 − k/(i+1)·(1/k) = 1 − 1/(i+1) = i/(i+1). Combined with the inductive hypothesis, each of the first i items ends step i+1 with probability (k/i)·(i/(i+1)) = k/(i+1) — matching item i+1's own k/(i+1) admission probability exactly. Every item, old or brand new, lands at the same k/(i+1). The pattern holds all the way to i = n, giving the final k/n for every item — proved here algebraically, and checked numerically below with real trial counts, not just trusted from the derivation.

Reference implementation

class ReservoirSampler {
  #k;
  #reservoir = [];
  #seen = 0;

  constructor(k) {
    this.#k = k;
  }

  feed(item) {
    this.#seen++;
    if (this.#reservoir.length < this.#k) {
      this.#reservoir.push(item);
      return { admitted: true, slot: this.#reservoir.length - 1, replaced: null };
    }
    const j = Math.floor(Math.random() * this.#seen); // uniform in [0, seen-1]
    if (j < this.#k) {
      const replaced = this.#reservoir[j];
      this.#reservoir[j] = item;
      return { admitted: true, slot: j, replaced };
    }
    return { admitted: false, slot: -1, replaced: null };
  }

  sample() {
    return this.#reservoir.slice();
  }
}

Verified three ways, all in Node before any page prose was written. (1) The exact shipped demo trace — all twelve feed calls with the page's fixed seed reproduced standalone, step-by-step: auto-fill through #0..#3, then #4 admitted into slot 3 (evicting #3), #5 into slot 0 (evicting #0), #6 into slot 3 (evicting #4), #7 and #8 both drawn and discarded, #9 into slot 2 (evicting #2), #10 and #11 both discarded — final reservoir [5, 1, 9, 6], matching the page's prose exactly. (2) A 50,000-trial frequency sweep at this exact configuration (n=12, k=4) using real Math.random(), not the demo's fixed seed: every one of the 12 items landed in the final reservoir with observed frequency within 0.002 of the theoretical k/n = 0.3333 — the induction proof above isn't just algebra, it lands where measurement says it should. (3) Proved the check would catch a broken implementation: a sabotaged version that always evicts slot 0 instead of the drawn j pushed items #0-#3's survival frequency down near 0 and item #11's up near 1 on the same sweep — the "lands near 1/3" result means something. See /tmp/reservoir/final_check.js and /tmp/reservoir/sim.js, scratch, not committed.

Pitfalls

An off-by-one in the draw's range produces a real, exact, silent skew — not noise, not a crash. The correct draw is j uniform in [1, i] (equivalently, 0-indexed, Math.floor(Math.random() * seen) where seen = i). A tempting one-character mistake is drawing from [1, i-1] instead — "the current item can't evict itself, so why include it in the range?" The reasoning is backwards: the range's width sets how likely every earlier item is to survive this step, regardless of whether the current item's own index is a possible outcome. Shrinking the range makes every eviction more likely, not less, and the effect compounds across the whole stream:

Worked out exactly, not just measured: with the off-by-one bug, an item already in the reservoir (one of the first k) survives every later step with probability 1 − 1/i instead of the correct 1 − 1/(i+1), telescoping to (k−1)/(n−1) overall — for this page's n=12, k=4, exactly 3/11 ≈ 0.2727, noticeably under 1/3. A later item (arriving at position i ≥ k) is admitted with the inflated probability k/i instead of k/(i+1), but survives later steps with the same shrunk i/(n−1), and the two effects multiply out to exactly k/(n−1) — here 4/11 ≈ 0.3636, noticeably over 1/3. Both closed forms match the 50,000-trial button above to three decimal places. The bug doesn't throw, doesn't produce an empty or short reservoir, and every individual run still "looks like" 4 plausible items out of 12 — the only way to catch it is to run many trials and notice the frequencies aren't flat, exactly the check this page ships live instead of just describing.

The reservoir is a sample of what's been seen so far, not a snapshot frozen at some final size. If a caller reads sample() mid-stream and treats the result as final, it's a correct uniform sample of the i items seen up to that point — but it silently becomes stale and biased the moment more items arrive without a further read, since later items' admission draws happen whether or not anyone is still watching.

This is sampling without replacement within one pass, not sampling with replacement. Once an item is evicted, it cannot come back — the algorithm has no memory of discarded items at all, the same one-shot-per-item shape noted above. A different problem (draw k samples allowing repeats) doesn't need a reservoir at all; conflating the two leads to reaching for this algorithm when a much simpler with-replacement draw would do, or vice versa.

Where reservoir sampling shows up

• Log and event sampling. Tailing an access log or event stream that never technically ends, and needing a fair random sample of the last however-many-you-can-afford-to-keep entries for debugging or monitoring, without buffering the entire stream.
• Unix's shuf and database TABLESAMPLE-style row sampling over a cursor or generator whose total size either isn't known up front or is too expensive to compute first with a separate pass.
• Distributed tracing and telemetry. Systems like Twitter's and Google's production tracing pipelines use reservoir sampling to keep a fair sample of traces per time window without every service knowing the window's eventual total request count in advance.
• Interview-style "pick a random line from a huge file" problems — the canonical teaching example precisely because it's the shortest illustration of "you can be exactly fair without ever knowing how much data is coming."

Complexity

Time: O(n) — one pass, one random draw and at most one write per item, regardless of k. Space: O(k), fixed for the entire stream no matter how large n turns out to be — unlike sorting the whole stream and taking a random prefix, which needs O(n) space and a known endpoint before it can even begin. The trade for that fixed memory is exactly one random number generated per item after the first k, whether or not that item ends up surviving.

This site's guide, Choosing a Probabilistic Structure, compares this entry against HyperLogLog, Count-Min Sketch, and the site's other fixed-memory unbounded-stream structures side by side — including the one respect in which this entry, alone among them, is exact rather than approximate.