The idea: a fair sample from a stream you cannot rewind
You want k random lines from a log file, k random requests from a live feed, or k random rows from a query result that does not fit in memory. You see each item once, and you do not know how many items will come. Reservoir sampling keeps a reservoir of k slots and decides for each new item, on the spot, whether it goes in. At every moment the reservoir is a uniform random sample of everything seen so far. The classic version is Algorithm R (Waterman, published by Knuth and analysed by Vitter in 1985).
On the canvas the stream runs across the top. Blue cells are items in the reservoir R, grey ones were dropped or pushed out, and the row under them shows each seen item's exact chance of being in R right now. The histogram at the bottom counts how often each item ended in the final sample over many streams.
Algorithm R
for i = 1, 2, 3, ... // item i arrives
if i <= k: R[i] = item i // fill the reservoir
else:
j = random integer in 1..i
if j <= k: R[j] = item i // keep it, replacing slot jSo the first k items always go in, and item i after that is kept with probability k/i. Item 5 has a 4/5 chance with k = 4, item 20 only 4/20. A kept item replaces a slot chosen uniformly at random, because j is uniform over 1..k once we know j ≤ k. The work is O(1) per item and the memory is O(k). (Demo 1: fill the reservoir, then keep item i with k/i; Demo 2: one whole stream of 20 items.)
| item i (k = 4) | chance item i gets in | chance each earlier item is still in R |
|---|---|---|
| 1–4 | 1 | 1 |
| 5 | 4/5 = 80% | 80% |
| 10 | 4/10 = 40% | 40% |
| 20 | 4/20 = 20% | 20% |
Why every item ends with k/N
The claim is an invariant: after i items, each of them is in R with probability k/i. It holds for i = k (all k are in). Suppose it holds after i items and item i + 1 arrives:
- The new item is kept with probability k/(i + 1), which is already the target.
- An old item in R leaves only if the new item is kept and picks its slot: k/(i + 1) · 1/k = 1/(i + 1). So it stays with probability i/(i + 1), and k/i · i/(i + 1) = k/(i + 1).
By induction, when the stream stops after N items, every item is in R with probability k/N, whatever N is. The algorithm never needed N. Following one item from arrival to the end gives the same answer as a product that telescopes:
(Demo 3: why k/i works (the proof) walks through these steps with the numbers on the canvas.)
Checking it: the histogram, and a rule that looks fair but is not
One sample proves nothing, so run many streams. With k = 4 and N = 20 each item should end in the sample 4/20 of the time: about 200 times in 1 000 streams, with random noise of about ±13 (one standard deviation). (Demo 4: 1 000 streams, every item lands 20% of the time.)
A tempting shortcut is to keep every new item with a fixed probability, say 1/2. It is not fair: the last item gets in half the time, while an early item must survive many later replacements. With k = 4 item 20 ends in the sample 50% of the time and item 5 only about 7%. The fraction must shrink as k/i, because the reservoir must stand for more and more items. (Demo 5: wrong rule, keep with a fixed 1/2.)
| rule | item 1 | item 5 | item 20 | fair? |
|---|---|---|---|---|
| keep with k/i (Algorithm R) | 20% | 20% | 20% | yes |
| keep with fixed 1/2 | 12% | 7% | 50% | no: recent items win |
Where it is used
- Sampling log lines, metrics or traces from a live stream with fixed memory.
- Picking k random rows in one pass instead of sorting by a random key (
ORDER BY random() LIMIT k). - Sampling a big file or a linked list whose length you would have to scan to learn.
- Distributed: each worker keeps a reservoir, and the reservoirs are merged with weights by stream size.
It sits next to other one-pass, small-memory stream summaries: the HyperLogLog counts distinct items and a Bloom filter answers "seen before?". Uniform randomness and its noise are the subject of Monte Carlo estimation of π and the birthday paradox.
What the page leaves out
Algorithm R draws one random number per item. Algorithm L (Li, 1994) instead computes how many items to skip before the next replacement, so it needs only O(k(1 + log(N/k))) random numbers. Weighted reservoir sampling (Efraimidis and Spirakis' A-Res: keep the k items with the largest u1/w) gives heavier items a larger chance. The page also leaves out sampling with replacement, sliding-window samples, and the random number generator's own quality.