Reservoir Sampling: Random Sampling From a Stream

Reservoir sampling is an algorithm for picking a uniformly random sample of a fixed size from a stream of items when you don’t know — and may never know — how many items the stream will contain. It does this in a single pass, using memory proportional only to the sample size, not the stream’s length. That combination makes it the standard tool for random sampling from log files, unbounded event streams, or any dataset too large to hold in memory all at once.

The problem it solves

Picking a random sample from a fixed-size list is easy: count the items, generate a random index, and pick it. But that approach breaks down the moment you don’t know the total count ahead of time — which is the normal case for a stream of server logs, a Kafka topic, or rows read one at a time from a file too large to fit in memory. You can’t compute “one in N” odds for an N you don’t have yet, and you can’t buffer the whole stream just to count it.

Reservoir sampling solves this by maintaining a running sample — the “reservoir” — and deciding, as each new item arrives, whether it should replace something already in the reservoir. By the time the stream ends, whatever’s left in the reservoir is provably a uniform random sample of everything that passed through, regardless of how long the stream turned out to be.

Algorithm R: the classic version

The best-known version, Algorithm R, samples k items from a stream as follows:

1. Fill the reservoir with the first k items unconditionally.
2. For each subsequent item at position i (1-indexed, with i > k), generate a random integer j between 1 and i.
3. If j ≤ k, replace the reservoir’s j-th slot with the current item. Otherwise, discard the current item and move on.

That’s the entire algorithm — no sorting, no second pass, no need to know the stream’s length in advance. Memory usage stays fixed at k items no matter how long the stream runs, and each item is processed exactly once in constant time.

Why it stays uniform

The proof by induction is short but worth internalizing, because the intuition explains why the “replace with probability k/i” rule works. After processing the first i items, each item seen so far has exactly a k/i chance of being in the reservoir — true by construction for i = k (probability 1), and preserved at each step because a new item is accepted with probability k/i, and any item already in the reservoir survives that step with probability (i-1)/i × (k-1)/(i-1)… which simplifies back to the same k/i figure. The result: at the end of the stream, every item that ever appeared has had an equal chance of surviving into the final sample, whether it arrived first or last.

This is the same style of incremental, probability-preserving argument you’ll see in other streaming algorithms, like the approximate counting behind a HyperLogLog sketch — different guarantee, same instinct to trade an exact answer for a provably bounded approximate one computed in a single pass.

Weighted and multi-pass variants

The basic algorithm assumes every item has equal probability of selection. Weighted reservoir sampling extends this so items with a higher weight are proportionally more likely to end up in the sample — useful when, say, more recent log entries or higher-traffic requests should be over-represented. A common approach assigns each item a key derived from a random number raised to the power of 1/weight, then keeps the k items with the highest keys, which reduces to a partial-sort problem solvable with a min-heap of size k.

There are also faster variants — Algorithm L and Algorithm K among them — that skip ahead by computing how many items to discard before the next replacement, rather than generating a random number for every single item. They produce the same statistical guarantee with fewer random number generations, which matters when the stream is enormous.

Where it shows up

Reservoir sampling appears anywhere a system needs a representative sample without buffering the full dataset: sampling requests for distributed tracing, selecting a random subset of rows for a database’s query planner statistics, picking a small validation set from a training data stream, or choosing which log lines to retain when a full log would be too expensive to store. It pairs naturally with the kind of single-pass, constant-memory thinking behind the sliding window technique, even though the two solve different classes of problems.

Reservoir sampling vs simple random sampling

	Simple random sampling	Reservoir sampling
Requires knowing total size upfront	Yes	No
Memory usage	O(n) to buffer, or O(1) with an index list	O(k), independent of stream length
Passes over the data	One (with buffering)	Exactly one, streaming
Works on unbounded streams	No	Yes
Implementation complexity	Trivial	Moderate

The takeaway

Reservoir sampling produces a uniform random sample of size k from a stream of unknown or unbounded length, in a single pass and constant memory, by probabilistically swapping new items into a running reservoir as they arrive. Algorithm R is the simplest correct version; weighted and skip-ahead variants exist for biased sampling and better performance on very large streams. Whenever you need “pick a random N of these” and can’t afford to know N in advance or hold everything in memory, this is the algorithm to reach for.