Reservoir sampling
On the roadmap:Staff Engineer · step 2: Approximate answers at scale
Keep k uniformly random items from a stream of unknown length using only k slots, and check the fairness empirically.
In plain words
Pick k items at random from a stream you cannot store and do not know the length of, so that every item had the same chance of being picked.
Why it matters
You often cannot keep everything: logs, events, requests. This gives a fair sample using a fixed amount of memory, and you can prove it is fair by counting.
Where you meet it
- Sampling logs and traces
- Metrics and monitoring pipelines
- Random 'sample of users' from live traffic
You will be able to
- Run the algorithm with a fixed seed so results repeat
- Check fairness with a simple count
- Explain why no second pass is needed
In interviews
Shows up as a coding question and in 'sample from a huge stream' design problems.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- Algorithm R with an injectable random function
- A seeded generator for repeatable runs
- A statistical check that every item is equally likely
export function reservoir<T>(stream: Iterable<T>, k: number, rand: () => number = Math.random): T[] {
const sample: T[] = [];
let seen = 0;
for (const item of stream) {
seen++;
if (sample.length < k) sample.push(item);
else {
const j = Math.floor(rand() * seen); // 0 .. seen-1
if (j < k) sample[j] = item; // happens with probability k / seen
}
}
return sample;
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints reservoir-sampling ok when everything passes. You need Node.js installed.
mkdir reservoir-sampling && cd reservoir-sampling
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Production pipelines often need weighted sampling (keep important events more often) or time decay, so recent items count more.
- Samples are built on many machines and merged using each stream's count, so the result is still uniform.
- Tracing and logging systems usually sample at the source to cap cost; reservoir sampling is the fair way to do it when you do not know the volume.
Ways to sample a stream
| How it works | Memory | Fair to every item? | Pick it when | |
|---|---|---|---|---|
| Reservoir sampling | Keep k; later items replace one with a shrinking chance | Fixed: k items | Yes: every item has chance k/n | You do not know how long the stream is |
| Keep the first k | Stop after k items | Fixed: k items | No: it is biased to the earliest | Never, for a fair sample |
| Keep each item with probability p | Flip a coin per item | Varies with the stream | Yes, but the sample size varies | A flexible sample size is fine |
| Store everything, then pick | Pick at the end | The whole stream | Yes | The data is small |
| Weighted reservoir | Heavier items are more likely to stay | Fixed: k items | By weight | Some items matter more |
What it cannot do
The sample size is fixed
You choose k up front and cannot grow it without starting again.
It needs a random number per item
On a very fast stream that cost can matter.
All items are equal
If some events matter more, you need the weighted version.
A sample says little about rare items
A one-in-a-million event is unlikely to appear in a small sample.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Merge reservoirs from several streams using their counts
- Implement weighted sampling (A-Res)
- Sample a real log file line by line