In a September post on The Old New Thing blog, Raymond Chen answered a question someone asked twenty years after Windows XP shipped: how did the system choose the startup picture for a new user? The answer turned out to be unexpectedly deep: not "picked a random picture," but a single-pass algorithm from random sampling theory — a special case of reservoir sampling, when the number of candidates is unknown in advance and you can't count them beforehand. Chen provides eight lines of pseudocode and notes that the code stops after the hundredth picture "in case someone puts a million files in the directory."
What caught me wasn't the algorithm description, but why it's built this way. In the naive solution everything's simple: count the files, roll the dice, take the right one. But such a two-pass algorithm traverses the filesystem twice (which is the bottleneck) and breaks if files appear or disappear during selection. Reservoir sampling solves both problems at once: one pass, zero foreknowledge, honest equal chances for every candidate — from the first to the one whose existence we learn at the last moment.
This turned out to be not a museum piece, but a living mechanism spinning inside PostgreSQL, Apache Spark, and machine learning replay buffers. I dug deeper — and it turned out the algorithm has its own 60-year history, its own proof in one induction, and an unexpectedly philosophical subtext: what does it mean to "fairly choose" when you don't know how much you're choosing from.
The formulation looks almost mocking: choose k items from a population you've never seen in full and don't see now. Items arrive one by one, you can't go back, you can't learn in advance how many there will be. At any moment the algorithm's state must be "the current fair sample" of everything that's already arrived.
Classic 1960s motivation — a magnetic tape of unknown length. A two-pass algorithm (first count the records, then choose) means an extra run through the tape, and that's hours of machine time and kilometers of film. Jeffrey Vitter formulates this drily in his 1985 paper: "determining N may be impractical or impossible." Machine translation of this phrase: the entire industry worked with data whose volume was unknowable by definition.
Today the same task sounds more contemporary: logs, event streams, clickstreams, Kafka topics. Volume is always unknown, memory is always finite. The solution idea is identical across all eras: keep only k slots in memory and decide on the fly what to remember and what to let go.
The heart of the algorithm is indecently small. We always take the first element. Element number k replaces the current winner with probability 1/k — that's it. Chen's eight lines from XP: a counter, a winner, the condition "if a random number from 1 to count matches count — replace."
Why this is fair is proven by induction in three lines. After the first element it's chosen with probability 1 — it is the entire sample. The second arrives, replaces with probability 1/2; both candidates now have 1/2 each. The third arrives: new elements are taken with probability 1/3, and the old winner holds his throne with probability 2/3 × 1/2 = 1/3. The math converges perfectly: the probability of the established throne-holder exactly compensates the newcomer's chance, and after n elements each has exactly 1/n. Wikipedia formulates the general step like this: an element from storage remains with probability (n/(n+1)) × (1/n) = 1/(n+1) — equality of chances is preserved at each step.
Most beautiful is that this fairness happens with zero knowledge of the future. At the moment the fifth element arrives, the algorithm has no idea there will be five million total. And still, by the time the last one arrives, each participant had an equal chance. This is a rare type of mathematical guarantee: fairness that doesn't require foreknowledge.
The algorithm also had a human shadow. In 2004 Chen told the story of a bug report: "Windows XP is racist — it gave me a kung fu picture because my last name is Chinese." Reality is prosaic: the random number generator landed on martial arts kick out of 21 available pictures. That same fair mechanism looked like a verdict in the user's eyes — first lesson about how randomness reads as malice.
The idea of sampling without knowing population size was first formalized by C. T. Fan, Mervin Muller, and Ivan Rezucha in June 1962 in the Journal of the American Statistical Association. Separately it was rediscovered by Alan Waterman — his version entered Knuth's TAOCP as Algorithm R: fill the reservoir from the first k elements, then each new one with probability k/n replaces a randomly chosen slot.
But Algorithm R has wastefulness: for every element in the stream a random number is spent, even if the element won't make it into the sample. Vitter in 1984–1985 showed you can skip chunks of the stream wholesale, computing skip-length from a distribution — and got sublinear time O(k(1+log(N/k))), proving its optimality. His Algorithm Z in the paper "Random Sampling with a Reservoir" (ACM TOMS, March 1985) works in one pass, with constant memory, and on a VAX 11/780 in FORTRAN 77 beat predecessors by orders of magnitude: 16·N microseconds for classic R versus 950·n·ln(N/n) for Z.
The "reservoir" metaphor is more precise than it seems. The stream is a river; the reservoir is a fixed container on the shore, in which exactly k portions of water mix. Each new sip has an equal chance to stay, regardless of how much water has already flowed past. Everything that didn't make it into the container vanishes irrevocably — just like data in a stream.
The names at the origins fold into a beautiful genealogy. Mervin Muller — the same one from Box-Muller transform (a way to generate normal random numbers) — stood at the origins of reservoir sampling: one person at the origins of both producing randomness and spending it economically. His PhD (UCLA, 1954) was about Monte Carlo for the Dirichlet problem — that same tradition of computation through randomness from which the entire approach grew.
Classic reservoir is fair to elements but blind to their quality: all candidates are equal, even if some are more important than others. The first extension — weighted reservoir. Efraimidis & Spirakis in 2006 (Information Processing Letters) came up with an elegant trick: each element with weight w_i is assigned a key r_i = u_i^(1/w_i), where u_i is a uniform random number, and elements with the largest keys enter the reservoir. The probability of entry becomes proportional to weight — without knowing the total stream. Earlier, in 1982, M. T. Chao published a similar scheme in Biometrika with accumulation of weight sums.
The second extension — distributed. In Spark the reservoir lives inside RangePartitioner: each partition holds its own local reservoir (SamplingUtils.reservoirSampleAndCount), then samples are merged. Elegant production code detail: the function returns not only the sample but also the input size — one pass gives both an honest sample and an exact count. And if the input turned out shorter than k, the array is simply trimmed: a partition in a distributed system can be anything.
Variations on the theme are already a whole family: sampling with replacement (Park et al., SIAM SDM 2004), jump optimizations, fresh 2026 work on weighted reservoir with replacement (Meligrana & Fazzone, ACM Web Conference 2026), KLRS for class balancing in continual learning through minimizing KL-divergence. The veteran algorithm continues spawning offspring.
The weightiest presence point — PostgreSQL. The query planner must know table statistics, for which ANALYZE collects random rows. The file sampling.c directly cites Vitter's paper and implements Algorithm Z with a threshold for switching at 22n. Tastiest — the comment in the same file about BlockSampler: "since we know the total number of blocks in advance, we can use the straightforward Algorithm S from Knuth 3.4.2 rather than Vitter's algorithm." Two sampling mechanisms side by side — and the choice between them is determined by exactly one question: do we know N.
In Apache Spark the reservoir works in RangePartitioner and in RDD sample paths. In ClickHouse — a separate story: the main sampling mechanism there is deterministic, hash-based (SAMPLE BY sipHash64), where rows are marked with a cryptographic hash in advance. But even there real reservoir exists — the aggregate function ReservoirSample. The contrast is useful: hash-based sampling is good when data has already been "marked" during insertion; reservoir is needed where the stream is live and you can't reorder. Fresh ClickHouse post from May 2026 with numbers: analytical query over 30.45 million rows in 687 ms, over 10% sample in 141 ms — 80% speedup with 2–8% error.
In machine learning reservoir occupied an unexpected niche: continual learning replay buffers. A model training on an infinite data stream can't store everything — it needs a "memory" buffer from which it rehearses the old. In the Avalanche framework the class ReservoirSamplingBuffer is the default policy: each sample is assigned a random key, top-N stays. The connection to iCaRL (CVPR 2017) is telling: there herding lives in parallel — purposeful selection of class prototypes. Two philosophies of "what to remember": honest randomness versus managed selection.
And Windows XP? That tiny variant with k=1 chose one picture from the stream with seed from GetTickCount() — and the limit "maximum 100 files" protected against pathology. Twenty years' age of the solution doesn't make it primitive: by the time of XP most systems still used two-pass counting.
Next to reservoir sampling stands the secretary problem — the classic optimal stopping problem. Candidates arrive in random order, decision on each is immediate, you can't take back a rejection. Optimal strategy: skip the first ~37% and stop at the first who's better than all seen; chance to pick the best — about 1/e ≈ 36.8%, regardless of whether there are 100 candidates or 100 million.
Both tasks are about a stream with unknown end and impossibility of going back, but they solve opposite things. The secretary problem sacrifices chance for quality — picks one, the best, with guaranteed (and modest) chance of success. Reservoir sacrifices "bestness" for fairness — picks k random ones with guaranteed uniformity, but without a hint of quality. Two answers to one question "how to choose from what you don't know in full."
And here a common layer emerges: this entire branch of algorithms grew from the philosophy "memory is more expensive than recalculation." Don't store everything — be able to compute from small state. From the same root grow HyperLogLog (cardinality in kilobytes), count-min sketch (frequencies in constant memory), streaming aggregates in ClickHouse and Spark. Reservoir sampling is not just a useful trick but one of the first examples of a class of algorithms that work honestly under conditions of fundamental unknowing of the world's volume.
My main sympathy is for the very type of guarantee that reservoir sampling gives. We're used to fairness requiring knowledge: to divide evenly, you need to know how much there is total. Reservoir breaks this dependency: equality of chances holds at every moment in time without any foreknowledge of volume. Mathematically it's trivial induction, but intuitively — a small miracle. Fairness without foreknowledge.
Second: the algorithm is a perfect example of how task conditions determine mechanism choice. The Postgres comment "know N — take Algorithm S; don't know — take Vitter" is an entire engineering culture in one sentence. Not "here's the best algorithm," but "here's the best algorithm for this amount of knowledge."
Third — and most unexpected: this 1962 veteran turned out to be the foundation of something its authors didn't think about. Continual learning replay buffers are literally "what to remember while learning forever." A model living in a data stream faces the same choice as the 1962 algorithm before a tape of unknown length. Reservoir is honest amnesia: every memory has an equal chance to remain. Sometimes fairness in memory is more important than smart selection: you never know what from the forgotten will come in handy.
Where I'd dig further: the connection of reservoir sampling with the distributed consensus problem — what happens when several reservoirs must agree on a common fair sample; and second track — reservoir in biology: doesn't evolution choose a "sample" of traits by a similar principle, when the fitness stream is infinite but the niche is a finite reservoir.