ReservoirSampling
title: Reservoir Sampling radar_quadrant: Techniques radar_ring: Assess radar_position: inner created: 2026-05-26 last_updated: 2026-05-26 tags: [algorithms, sampling, streaming, telemetry, observability] source_url: https://samwho.dev/reservoir-sampling/
A randomised algorithm for drawing a representative sample from a data stream of unknown or unbounded size using O(k) memory, where k is the desired sample size. Described interactively on samwho.dev.
Standard random sampling requires knowing the population size in advance. When reading from a log stream, event queue, or any unbounded data source, the total count is unknown at read time. Buffering the entire stream to sample afterwards is impractical at scale.
Maintain a reservoir of size k. For the first k items, fill the reservoir directly. For each subsequent item at position n (n > k), generate a random integer r in the range [1, n]. If r ≤ k, replace the item at position r in the reservoir with the new item. When the stream ends, the reservoir contains a uniform random sample — every item in the stream has exactly k/n probability of being included, regardless of stream length.
- Telemetry downsampling: retain a statistically representative 1% of traces or log lines without buffering the full stream.
- Database random sampling: select k random rows from a table scan without COUNT(*) first.
- Streaming analytics: maintain a rolling random sample for approximate query answering.
- Testing with production data: sample a representative subset of live events for test fixture generation.
Weighted reservoir sampling (Algorithm A-Res) extends the basic algorithm to sample proportionally to item weights — useful when some events are more significant than others. Distributed reservoir sampling splits the reservoir across workers and merges the results.
Placed in Techniques / Assess / inner. Named, well-understood algorithm with direct applicability to observability pipelines, log processing, and streaming data workflows. Inner position reflects zero infrastructure cost (implementable in ~10 lines in any language) and broad applicability across data engineering and SRE contexts. Trial gate: reservoir sampling implemented in one real streaming or log-processing context, replacing either full buffering or a biased head/tail sampling approach, with sample representativeness verified.
