Sweaty Imposter

Reservoir Sampling

TechniqueApproximationSeniorStaffUpdated
Sample k items uniformly at random from a stream of unknown (and unboundedly large) length.

When to Use Reservoir Sampling

When the dataset is too large or unbounded to hold in memory, and you need a representative random subsample. Logs sampling, A/B testing of streaming events, telemetry.

In Practice

Distributed tracers (Jaeger, OpenTelemetry) use reservoir sampling to keep a representative slice of traces under a fixed memory budget.

Sketch

Python

def reservoir(stream, k):
    sample = []
    for i, item in enumerate(stream):
        if i < k:
            sample.append(item)
        else:
            j = random.randint(0, i)
            if j < k:
                sample[j] = item
    return sample

How Reservoir Sampling Comes Up in Interviews

Scenario

Your distributed tracer receives an unbounded firehose of spans and you must keep exactly 1,000 of them, uniformly at random, with a fixed memory budget, without knowing the total volume in advance. Which algorithm?

Reservoir sampling picks k items uniformly at random from a stream of unknown length using only O(k) memory, exactly what tracers like Jaeger use to keep a representative slice.

Reservoir sampling solves the surprisingly non-obvious problem of 'pick k uniformly at random from a stream of unknown length using O(k) memory.' The algorithm (Vitter's Algorithm R) keeps the first k items, then for item i (i >= k) replaces a random slot in the reservoir with probability k/i. The math works out so every item ever seen has equal probability k/n of being in the final reservoir, regardless of when it arrived. Jaeger, Zipkin, and OpenTelemetry SDKs use reservoir sampling (or rate-limited variants) to keep a representative slice of traces under a fixed memory budget. The pattern also shows up in MapReduce data sampling and SQL TABLESAMPLE.

Where It Comes Up