Reservoir sampling

How do you keep a uniform sample of an endless stream, and what can a sample never tell you?

A reservoir sample keeps k items chosen uniformly at random from a stream of unknown length, in one pass and O(k) memory.

The algorithm and its proof, both short. Keep the first k items. For the i-th arrival (for i > k), keep it with probability k/i, and if kept, evict a uniformly chosen current member.

import random
def reservoir(stream, k):
    sample = []
    for i, x in enumerate(stream, start=1):
        if i <= k:
            sample.append(x)
        elif random.random() < k / i:
            sample[random.randrange(k)] = x
    return sample

Why it is uniform: item i enters with probability k/i. It then survives each later step j with probability (j − 1)/j. The product of these from j = i + 1 to n telescopes (the terms cancel in pairs) to i/n. So the total probability that item i is in the final sample is (k/i) · (i/n) = k/n, the same for every i.

Where it matters here: Spark's RangePartitioner boundaries (the sampling that chooses range cut points for a sort, as in Ordering structures), stratified training-set construction, approximate query processing, and debugging a stream you cannot store. The weighted variant (A-Res) is one line: give each item the key u^(1/w) (where u is a uniform random number and w the item's weight) and keep the k items with the largest keys.

Two things to understand about samples, as distinct from sketches

First, a sample answers questions you have not chosen yet, which no sketch does. That is its unique value, and the reason it belongs in the toolkit despite worse error than a purpose-built sketch.

Second, a uniform sample destroys exactly what most data engineering cares about. Rare events (errors, fraud, the one broken partition) are absent from a uniform sample almost by definition. That is why sampling a log stream to find failures finds nothing. And there is a much harder limitation: you cannot estimate cardinality from a uniform sample. Extrapolating a distinct count from a sample provably needs a sample of nearly linear size unless you make assumptions about the distribution. That single fact is why the whole HLL/KMV family had to be invented. The obvious approach does not merely perform badly; it cannot work.