Reservoir sampling: keep a uniform fixed-size sample

Last updated: 5 Oct 20269 min read

tutorial

Reservoir sampling keeps at most K incident IDs without knowing how long the feed will run. The first K arrivals fill the reservoir. On arrival number N greater than K, draw an integer uniformly from zero through N minus one; replace a stored slot only when the draw is below K. Each of the N observed positions then has inclusion probability K divided by N, assuming independent uniform random draws. The program uses a private seeded Python random generator so its example output is reproducible. This is a sample of event positions: if an incident ID appears repeatedly, it has multiple chances to appear. The sampler does not deduplicate IDs, weight recent events, or provide a cryptographic draw.

Operational case

An incident pipeline receives twenty event records numbered 47 through 66 and keeps four for manual review. Saving the first four would exclude every later event. A reservoir can replace earlier selections as later records arrive while using four stored IDs. The printed sample is one seeded outcome, not a guarantee that those IDs are special. If events are removed later, the original uniformity proof no longer applies. If the review policy requires one sample per unique customer rather than one sample per event, deduplicate upstream or choose a different sampling contract before using the output.

Working Python program

import random


class IncidentReservoir:
    def __init__(self, capacity, seed=None):
        if capacity < 0:
            raise ValueError("capacity cannot be negative")
        self.capacity = capacity
        self.seen = 0
        self.values = []
        self.random_source = random.Random(seed)

    def record(self, incident_id):
        self.seen += 1
        if len(self.values) < self.capacity:
            self.values.append(incident_id)
        elif self.capacity:
            slot = self.random_source.randrange(self.seen)
            if slot < self.capacity:
                self.values[slot] = incident_id

    def sample(self):
        return list(self.values)


sampler = IncidentReservoir(4, seed=47)
for incident_number in range(47, 67):
    sampler.record(f"incident-{incident_number}")
print("seen=", sampler.seen, "sample=", sampler.sample(), sep="")

Output

seen=20sample=['incident-65', 'incident-48', 'incident-51', 'incident-64']

Time, space, and tradeoff

For capacity K and N processed events, memory is O(K), and each arrival performs O(1) reservoir operations plus the cost of generating a random integer. Returning a sample copy takes O(K). Zero capacity stores nothing while still counting arrivals. Python's random generator is suitable for this reproducible teaching example but must not be used for security-sensitive draws. A single sample has no promise to represent every rare class; statistical guarantees concern repeated random runs. This implementation does not merge independently sampled streams, retract old events, or sample by weight. Those variants need extra counts or priorities and distinct proofs.

Common Mistakes

Do not keep only the first K arrivals and call them a stream-wide uniform sample.
Do not confuse uniform event positions with uniform unique IDs.
Do not claim one seeded output proves a distributional guarantee.
Do not use a non-cryptographic generator for security decisions.

Connected lessons

Compare its result with Misra–Gries: find frequent-item candidates in one pass, Space-Saving: ranked candidates with count bounds, HyperLogLog: estimate unique IDs with fixed registers, then complete the bounded-stream audit and contract quiz.

Alias tables: constant-work draws from fixed dispatch weights adds a related structure with a different operation boundary.

Exponential histograms: estimate failures in a recent event window adds a related structure with a different operation boundary.

data structures

array-data-structure-guide