Reservoir sampling a stream of unknown length: an interactive comparison

Systems often need a small random sample of something too big or too endless to store: log lines, requests to trace, events to show on a dashboard. When items arrive one at a time and nobody knows how many there will be, the obvious approaches are all biased. Reservoir sampling keeps exactly k items, uses memory for k items only, and gives every item seen so far the same chance of being in the sample.

The playground keeps 20 items from streams of 200, 1,000 and 5,000 items with four methods, repeated 1,500 times, and shows how likely each part of the stream is to end up in the sample.

Why the obvious approaches fail

• Keeping the first k is not a sample at all: everything after the first 20 items is ignored.
• A fixed probability per item is fair, but the sample size depends on the stream length, which you do not know: tuned for 1,000 items it keeps about 4 from a stream of 200 and 100 from a stream of 5,000, and even at 1,000 anywhere from 7 to 38.
• Replacing a kept item on a coin flip keeps the size right but heavily favours recent items: each later item has another chance to evict, so early items almost never survive.
• Reservoir sampling keeps item i with probability k / i. An item kept early is more likely to be evicted later, exactly enough that every item ends with the same chance, k / n, whatever n turns out to be.

The algorithm

def reservoir(stream, k):
    sample = []
    for i, item in enumerate(stream, start=1):
        if i <= k:
            sample.append(item)               # fill the reservoir first
        else:
            j = random.randint(1, i)          # uniform over 1..i
            if j <= k:
                sample[j - 1] = item          # kept with probability k / i
    return sample

# merging reservoirs from shards: pick from each in proportion to how many items it saw,
# or give every item a random key and keep the k smallest keys across all shards

Variants handle weights, where heavier items should be more likely, by keeping the items with the largest random key raised to the inverse of their weight, and distribution, where each shard keeps its own reservoir and a coordinator merges them. The same idea of a random key per item gives a fair sample across shards without any coordination during the stream.

In a system design interview

Sampling comes up in metrics, tracing and analytics: “Each collector keeps a reservoir of 1,000 example requests per endpoint per minute, so the dashboard can show representative slow requests without storing them all. Collectors attach a random key to each item and the aggregator keeps the 1,000 smallest keys across collectors, which is a uniform sample of the whole minute.” Expect the follow-ups: how to sample rare events such as errors, which uniform sampling mostly misses, and how sampling interacts with exact counts, which should be kept separately.

Read the guide to probabilistic data structures or batch and stream processing, see trace sampling and HyperLogLog, or watch a strong candidate design a metrics system.

Questions people ask