Take a random sample of 10,000 rows from a file of six million Wikipedia article titles, and if the whole file fits in memory the answer is one line: load it, shuffle, take the first 10,000. I had exactly this file, a plain text dump of titles, one per line, and for about thirty seconds I assumed the one-liner would do. Then I asked myself what happens if the file does not fit, or worse, if it is not a file at all but a live stream I cannot rewind, with no way to know in advance how many items are still coming. random.shuffle needs the whole collection in hand. A stream refuses to give you that.

Why “just sample randomly” breaks on a stream

The naive fix, sample each item with some fixed probability p as it arrives, looks reasonable until you ask what p should be. Pick p too high and the reservoir overflows before the stream ends. Pick p too low and you end up with far fewer samples than you wanted, because you fixed the probability before knowing the total count. Both failures come from the same root cause: a fair sample of size k drawn from a stream of unknown total length n needs every item, including ones that have not arrived yet, to have exactly probability k/n of ending up in the final sample. You cannot compute k/n until the stream is done, and by then it is too late to have sampled fairly along the way.

Reservoir sampling solves this without ever knowing n in advance, and the mechanism is small enough to write from memory once you have seen it worked through once.

The algorithm, one item at a time

Keep a reservoir of exactly k slots. Fill the first k slots with the first k items unconditionally, no decisions needed yet. From the (k+1)th item onward, for each new item at position i, generate a random integer j uniformly between 1 and i inclusive. If j falls within the reservoir’s range, 1 through k, overwrite reservoir slot j with the new item. Otherwise, discard the new item and move on.

import scala.util.Random

def reservoirSample[T](stream: Iterator[T], k: Int, seed: Long = 42L): Array[T] = {
  val rng = new Random(seed)
  val reservoir = new Array[Any](k)
  var i = 0

  while (stream.hasNext) {
    val item = stream.next()
    if (i < k) {
      reservoir(i) = item
    } else {
      val j = rng.nextInt(i + 1)  // uniform in [0, i]
      if (j < k) reservoir(j) = item
    }
    i += 1
  }
  reservoir.map(_.asInstanceOf[T])
}

Every item, whether it is item 4 or item 4,000,000, gets exactly one chance to enter the reservoir, decided the moment it arrives, using only information available up to that point. Past items are never revisited. The stream is consumed exactly once, left to right, and the algorithm never needs to know how many items remain.

Step by step reservoir sampling with k=3 and 8 items: first 3 items fill the reservoir directly, then each subsequent item generates a random index and either replaces a reservoir slot or is discarded, shown as a sequence of reservoir states

Why this is actually fair, not just plausible

The plausibility is easy to accept and the proof of correctness is the part worth sitting with, because it explains why the replace-with-probability-k/i step works rather than just asserting that it does.

For the first k items, each is in the reservoir with probability 1, trivially. Consider item i, for i > k. It enters the reservoir at the moment it arrives with probability k/i, by construction, since j is drawn uniformly from i values and k of those values land inside the reservoir. The harder question is whether item i is still in the reservoir once the stream ends at item n. For that, item i has to survive every later item’s chance to displace it. Item i+1 displaces slot j only if it lands on the specific slot item i occupies, probability 1/(i+1) of hitting that slot, times k/(i+1) of even attempting a replacement, though the cleaner way to see it is that the probability item i+1 does not evict item i works out to 1 minus 1/(i+1), i.e. i/(i+1). Multiply that survival probability across every item from i+1 through n, and the product telescopes:

P(survive) = i/(i+1) * (i+1)/(i+2) * ... * (n-1)/n = i/n

Combine the probability of entering, k/i, with the probability of surviving to the end, i/n, and the i cancels: k/i * i/n = k/n. Every item, regardless of when it arrived, ends up in the final reservoir with probability exactly k/n. That is the definition of a fair sample. The algorithm does not approximate fairness, it produces it exactly, using constant memory and a single pass.

Running it against six million titles

I ran this against a Wikipedia titles dump, one title per line, roughly six million lines, treating the file as a stream by reading it line by line rather than loading it whole, which defeats the entire point of the exercise.

import scala.io.Source

val source = Source.fromFile("enwiki-titles.txt")
val sample = reservoirSample(source.getLines(), k = 10000)
source.close()

println(sample.take(10).mkString("\n"))

Peak memory use tracked the reservoir size, not the file size, confirmed by watching the JVM heap while the file streamed past. A 400MB titles file produced the same memory footprint whether k was 1,000 or 100,000, because the only thing held in memory at any point is the reservoir itself and the current line being read. The file could have been forty times larger and the memory profile would not have moved.

The distribution check mattered more to me than the memory number. I bucketed the sampled titles by their position in the original file, in chunks of 100,000, and counted how many sampled titles fell in each chunk. A biased implementation, one where an off-by-one error in the random range let later items overwrite the reservoir more often than earlier items, shows up immediately as a skew toward the end of the file. Mine came out flat across all sixty chunks, give or take sampling noise consistent with a fair draw, which was the confirmation the maths above was not just correct on paper.

Where the reservoir idea shows up again

Once this clicked, I started noticing the same shape of problem elsewhere. Spark’s RDD.sample() without replacement uses a variant of this reasoning under the hood, particularly in the exact-count case. Any system that needs a representative subset from an unbounded or unknown-length source, log sampling in a monitoring pipeline, A/B test cohort selection from a live event stream, a database export tool sampling rows from a table it is scanning sequentially, runs into the same constraint: you cannot know the total until you have seen it all, and you often cannot afford to wait that long before making a decision about each item.

Data flowing left to right through a fixed-size reservoir window, with a crossed-out backward arrow showing the stream cannot be rewound, items arriving one at a time, and past items shown fading once they leave the window

What stayed with me from this exercise is how small the actual insight is. The code is twelve lines. The proof is four lines of algebra once you see the telescoping product. What takes the time is the mental shift from “I have all the data” to “I will never have all the data at once, and I still need an unbiased answer.” Most of the streaming work I have touched since, windowed aggregates, DStream batches, watermarking for late-arriving events, all sit on some version of that same shift. You give up the comfort of a complete dataset in memory. In exchange you get an algorithm that runs, correctly, on a stream with no end in sight.