heyrian.dev
← Applied algorithms
Chance and live data From a stream of unknown length to a fair sample

Reservoir sampling

Keep k. Give every item the same chance.

Run ANALYZE on a large PostgreSQL table and it doesn’t read every row. Its documentation says it “takes a random sample of the table contents, rather than examining every row.” The source says how: the first rows go into a reservoir, later rows replace randomly chosen ones, and “At all times the reservoir is a true random sample of the tuples we've passed over so far, so when we fall off the end of the relation we're done.”

That is reservoir sampling: a sample of fixed size from a stream you can’t count until it ends. We’ll use it at a support desk that reviews five closed tickets a day without knowing how many tickets the day will bring.

TypeScriptGoOne support desk in each language

01 / The idea

Pick five tickets from a day nobody can count yet.

Every evening the support lead reviews five tickets closed that day. The review is only fair if any ticket could be picked: the quick morning fixes as much as the long afternoon escalations. Tickets arrive one at a time, and the desk can’t know until closing time whether there will be twelve or two hundred.

The obvious answers each break something. Keeping every ticket and picking five at the end stores the whole day. Keeping every tenth ticket isn’t random, and on a quiet day it keeps nothing. Keeping each ticket with a 5 in n chance needs n, the one number nobody has.

Algorithm R keeps the first five tickets. After that, ticket i draws a whole number from 0 to i − 1: a number below 5 names a slot, and the ticket replaces whoever is in it; any other number and it passes by. Watch Tuesday’s twelve tickets go through five slots.

Reservoir sampling

Keep five. Give every ticket the same chance.

SUPPORT DESK · 5 REVIEW SLOTS 1 ticket closed so far
  1. 4101
  2. 4102
  3. 4103
  4. 4104
  5. 4105
  6. 4106
  7. 4107
  8. 4108
  9. 4109
  10. 4110
  11. 4111
  12. 4112
  1. slot 0 T-4101
  2. slot 1 empty
  3. slot 2 empty
  4. slot 3 empty
  5. slot 4 empty

T-4101, ticket 1, takes empty slot 0.

01/ 03
Fill the slots

The first five tickets take the slots.

T-4101 to T-4105 close first and fill slots 0 to 4. Nobody at the desk knows yet how many tickets today will bring.

Reduced motion: choose a scene to see its completed state.

Read this scene

T-4101 to T-4105 close first and fill slots 0 to 4. Nobody at the desk knows yet how many tickets today will bring.

Tickets offered: 1 of the day. Slots: slot 0 T-4101.

Watch and Step through replay Tuesday with five slots and seed 2026. Try it runs the same TypeScript on other days, slot counts, and seeds, beside the off-by-one, and starts fresh each time you open it.

T-4108 replaced T-4106, which had come in only two tickets earlier, and the last four tickets all passed by. Neither is a pattern. Each of Tuesday’s twelve tickets had a 5 in 12 chance to end in the review, whether it closed at 08:12 or 16:55.

02 / Name the rule

Fill the slots, then draw below the ticket’s number.

A reservoir starts with k empty slots and a count of 0. Each ticket does one thing:

Fill

While a slot is empty

Tickets 1 to k take slots 0 to k − 1. No draw.

Draw

A number from 0 to i − 1

Every number equally likely. Ticket i is the i-th ticket seen, counting from 1.

Replace or pass

Below k names a slot

Replace whoever holds that slot. At k or above, the ticket passes by for good.

Why every ticket ends with k in n. Ticket i gets in with a k in i chance: k of its i numbers name a slot. After that, a later ticket j pushes it out only by drawing exactly its slot, a 1 in j chance, so it stays with chance (j − 1)/j. Staying through every ticket up to n multiplies to i/(i + 1) × (i + 1)/(i + 2) × … × (n − 1)/n, and everything cancels but i/n. Getting in times staying: k/i × i/n = k/n. The first k tickets are in from the start and stay with the same product from k + 1, which is k/n too.

Counting every way, instead of trusting the algebra. Like the Fisher–Yates lesson, the tests run every sequence of draws once. With five tickets and two slots, tickets 3, 4, and 5 draw from 3, 4, and 5 numbers: 60 equally likely sequences. Every ticket ends in the sample in exactly 24 of them, 2 in 5, and each of the 10 possible pairs in exactly 6. Both languages check that for every stream of up to eight tickets and every number of slots.

The draw has to be fair too. drawBelow is the Fisher–Yates lesson’s: a remainder of a 32-bit number favors small results, so values from the uneven slice at the top are thrown away and drawn again.

What if the draw is one short?The off-by-one, counted

Count tickets from 0 and draw below that count, and ticket i draws from 0 to i − 2. It looks harmless. Ticket k + 1 now draws below k and gets in every time, and every later ticket gets in a little more often than it should.

sample.ts
// The tempting off-by-one: count items from 0 and draw below that count. Item i then draws below
// i − 1, so the first item after the slots are full always gets in, and every later item gets
// slightly more than its share, at the expense of the items already kept.
export function offerOffByOne<T>(r: Reservoir<T>, item: T, draw: Draw): Offer<T> {
	if (r.seen >= MAX_SEEN)
		throw new SampleError('too-many', `A reservoir counts up to ${MAX_SEEN} items.`);
	const position = r.seen + 1;
	if (position <= r.size) {
		r.seen = position;
		r.slots.push(item);
		return { kind: 'filled', position, slot: position - 1 };
	}
	const j = pick(draw, position - 1); // one too few positions
	r.seen = position;
	if (j >= r.size) return { kind: 'passed', position, pick: j };
	const dropped = r.slots[j];
	r.slots[j] = item;
	return { kind: 'replaced', position, pick: j, slot: j, dropped };
}

Counting every sequence again: with five tickets and two slots the off-by-one makes 24 sequences, and the tickets end in the sample 6, 6, 12, 12, and 12 times. With one slot and four tickets, the first ticket is never kept. The tests check, for every stream of up to eight tickets, that the first k tickets end with (k − 1)/(n − 1) and every later one with k/(n − 1). On Tuesday that is 4 in 11 for the first five and 5 in 11 for the rest, and the lab’s replay shows it.

03 / Read the shape

A draw, a reservoir, and an offer.

Basic form is the draw and the whole method: reservoir makes the slots, offer handles one item and says what happened, and sample reads a copy. In the wild reads the day’s tickets from a stream and shuffles the picks. At the call site runs Tuesday twice with the same seed and counts every sequence for both versions. Both languages print the same four lines.

The whole method: the first size items fill the slots; item i draws a position below i, replaces the item in that slot if the position is a slot, and otherwise passes by. The draw is the Fisher–Yates lesson’s seeded xorshift with a rejected top slice, so TypeScript and Go draw the same numbers.

TypeScriptReading
sample.ts
// The same 32-bit xorshift generator as the Fisher–Yates lesson: identical numbers in TypeScript
// and Go, so a seed repeats a sample exactly. For repeatable examples and tests, not for secrets.
export function xorshift32(seed: number): () => number {
	if (!Number.isInteger(seed) || seed < 1 || seed >= UINT32)
		throw new SampleError('bad-seed', 'The seed must be a whole number from 1 to 4294967295.');
	let state = seed;
	return () => {
		state ^= state << 13;
		state ^= state >>> 17;
		state ^= state << 5;
		state >>>= 0;
		return state;
	};
}

// A remainder alone favors small values whenever 2³² isn't a multiple of bound,
// so a value from the uneven slice at the top is thrown away and drawn again.
export function drawBelow(next: () => number, bound: number): number {
	const limit = UINT32 - (UINT32 % bound);
	let value = next();
	while (value >= limit) value = next();
	return value % bound;
}

export function seededDraw(seed: number): Draw {
	const next = xorshift32(seed);
	return (bound) => drawBelow(next, bound);
}

// Algorithm R. The first `size` items fill the slots. After that, item i (counting from 1) draws
// a position below i. If the position is one of the slots, the item replaces whatever is there;
// otherwise it passes by. Item i gets in with chance size/i.
export type Reservoir<T> = { readonly size: number; seen: number; slots: T[] };

export type Offer<T> =
	| { kind: 'filled'; position: number; slot: number }
	| { kind: 'replaced'; position: number; pick: number; slot: number; dropped: T }
	| { kind: 'passed'; position: number; pick: number };

export function reservoir<T>(size: number): Reservoir<T> {
	if (!Number.isInteger(size) || size < 1 || size > MAX_SLOTS)
		throw new SampleError('bad-size', `A reservoir has 1 to ${MAX_SLOTS} slots.`);
	return { size, seen: 0, slots: [] };
}

export function offer<T>(r: Reservoir<T>, item: T, draw: Draw): Offer<T> {
	if (r.seen >= MAX_SEEN)
		throw new SampleError('too-many', `A reservoir counts up to ${MAX_SEEN} items.`);
	const position = r.seen + 1;
	if (position <= r.size) {
		r.seen = position;
		r.slots.push(item);
		return { kind: 'filled', position, slot: position - 1 };
	}
	const j = pick(draw, position); // 0 to position − 1, each equally likely
	r.seen = position;
	if (j >= r.size) return { kind: 'passed', position, pick: j };
	const dropped = r.slots[j];
	r.slots[j] = item;
	return { kind: 'replaced', position, pick: j, slot: j, dropped };
}

export const sample = <T>(r: Reservoir<T>): T[] => [...r.slots];
GoAlongside
sample.go
// The same 32-bit xorshift generator as the Fisher–Yates lesson: identical numbers in TypeScript
// and Go, so a seed repeats a sample exactly. For repeatable examples and tests, not for secrets.
func Xorshift32(seed int64) (func() uint32, error) {
	if seed < 1 || seed > 4294967295 {
		return nil, &SampleError{"bad-seed", "The seed must be a whole number from 1 to 4294967295."}
	}
	state := uint32(seed)
	return func() uint32 {
		state ^= state << 13
		state ^= state >> 17
		state ^= state << 5
		return state
	}, nil
}

// A remainder alone favors small values whenever 2³² isn't a multiple of bound,
// so a value from the uneven slice at the top is thrown away and drawn again.
func DrawBelow(next func() uint32, bound int) int {
	span := uint64(1) << 32
	limit := span - span%uint64(bound)
	value := uint64(next())
	for value >= limit {
		value = uint64(next())
	}
	return int(value % uint64(bound))
}

func SeededDraw(seed int64) (Draw, error) {
	next, err := Xorshift32(seed)
	if err != nil {
		return nil, err
	}
	return func(bound int) int { return DrawBelow(next, bound) }, nil
}

// Algorithm R. The first Size items fill the slots. After that, item i (counting from 1) draws
// a position below i. If the position is one of the slots, the item replaces whatever is there;
// otherwise it passes by. Item i gets in with chance Size/i.
type Reservoir[T any] struct {
	Size  int
	Seen  int
	Slots []T
}

// Offer is what happened to one item: "filled", "replaced", or "passed". Pick is -1 while the
// slots are filling; Slot is -1 when the item passed by.
type Offer[T any] struct {
	Kind     string
	Position int
	Pick     int
	Slot     int
	Dropped  T
}

func NewReservoir[T any](size int) (*Reservoir[T], error) {
	if size < 1 || size > MaxSlots {
		return nil, &SampleError{"bad-size", fmt.Sprintf("A reservoir has 1 to %d slots.", MaxSlots)}
	}
	return &Reservoir[T]{Size: size, Slots: make([]T, 0, size)}, nil
}

func (r *Reservoir[T]) Offer(item T, draw Draw) (Offer[T], error) {
	return r.offer(item, draw, 0)
}

func (r *Reservoir[T]) offer(item T, draw Draw, short int) (Offer[T], error) {
	if int64(r.Seen) >= MaxSeen {
		return Offer[T]{}, &SampleError{"too-many", fmt.Sprintf("A reservoir counts up to %d items.", MaxSeen)}
	}
	position := r.Seen + 1
	if position <= r.Size {
		r.Seen = position
		r.Slots = append(r.Slots, item)
		return Offer[T]{Kind: "filled", Position: position, Pick: -1, Slot: position - 1}, nil
	}
	j, err := pick(draw, position-short) // Algorithm R (short 0): 0 to position − 1, each equally likely
	if err != nil {
		return Offer[T]{}, err
	}
	r.Seen = position
	if j >= r.Size {
		return Offer[T]{Kind: "passed", Position: position, Pick: j, Slot: -1}, nil
	}
	dropped := r.Slots[j]
	r.Slots[j] = item
	return Offer[T]{Kind: "replaced", Position: position, Pick: j, Slot: j, Dropped: dropped}, nil
}

func (r *Reservoir[T]) Sample() []T { return slices.Clone(r.Slots) }
Reading the TypeScriptA plain object, and what an offer returns

A reservoir is a plain object with its size, the count seen, and the slots. offer changes it in place, because copying k slots for every item of a long stream would cost more than the sample.

offer returns a union: filled, replaced with the item that was dropped, or passed. The lab and the story are built from those results, not from a second copy of the rule. Errors are a SampleError whose code matches the Go version.

Reading the GoGenerics, one shared step, and iter.Seq

Reservoir[T] is generic, and Offer and OfferOffByOne are methods that share one unexported step with a count of how many positions to leave out: 0, or 1 for the off-by-one.

ReviewSample takes an iter.Seq[Ticket], so the tickets can come from a slice, a database cursor, or a channel without being collected first. Pick is -1 while the slots fill and Slot is -1 when a ticket passes by, where the TypeScript leaves those fields out.

What is refusedSlots, seeds, draws, and tickets

A reservoir has 1 to 64 slots (bad-size). A seed is a whole number from 1 to 4,294,967,295 (bad-seed). A draw that isn’t a whole number from 0 to one less than its bound is bad-draw, and the reservoir is left as it was. A reservoir counts up to 4,294,967,295 items, so every bound fits in 32 bits; one more is too-many. reviewSample checks the seed, then the slots, then each ticket, and refuses a ticket with no id (empty-id).

Both languages run the same shared cases, apart from a fraction of a slot, which Go’s int can’t hold.

04 / Try a decision

The eighth ticket closes.

Decide what happens to it before the feedback tells you.

The five review slots are full after seven tickets. T-4108, the eighth ticket of the day, closes. What happens to it?

05 / Follow the cost

One pass, k slots.

Reservoir sampling: time and extra space, with n items in the stream and k slots
OperationTimeExtra spaceWhat it assumes
Offer one itemO(1)O(1)One draw once the slots are full. The item is written into a slot or passes by.
Sample a stream of n itemsO(n)O(k)One draw per item after the first k. Memory is the k slots and a count, however long the stream.
Read the sampleO(k)O(k)A copy of the slots, so a caller can’t change the reservoir by accident.
Shuffle the picks for displayO(k)O(k)Fisher–Yates over the k picks, because slot order still hints at arrival order.
Keep everything, pick at the endO(n)O(n)The same fair sample, but every ticket of the day is stored until closing time.
Count every sequence of drawsgrows like n!O(n)What the tests do for streams of up to eight items, to check the chances exactly.

The memory is the point. Two hundred tickets or two million, the desk holds five and a count. The work is one draw per item once the slots are full, so it grows with the stream, but nothing is ever read twice.

For very long streams, drawing for every item is the part that shows. PostgreSQL’s ANALYZE uses Vitter’s skip-ahead algorithms from his 1985 paper (Algorithm X, then Algorithm Z once the table is large), which work out how many rows to skip before the next one enters instead of drawing for each. This lesson doesn’t implement it; Algorithm R is the one to understand first, and the one to reach for until the draws show up in a profile.

06 / Give it a real job

Review a fair five, and say five of how many.

reviewSample reads the day’s closed tickets as they come and returns two things: how many tickets it saw and the ones it kept. The count matters to the lead: five of twelve is most of a quiet day, and five of two hundred is a spot check.

It also shuffles the picks before anyone sees them. The first tickets of the day fill the first slots and stay there until something replaces them, so slot order still hints at when a ticket closed. On Tuesday the slots end as T-4107, T-4102, T-4108, T-4104, and T-4105; the review shows T-4108, T-4104, T-4107, T-4105, and T-4102. The shuffle is Fisher–Yates with the same seeded draw.

Apache Spark does the same work at a larger scale. When sortByKey sorts into more than one partition, its range partitioner samples every input partition with reservoirSampleAndCount, which keeps a reservoir and also returns how many items it saw. Its comment is the rule in one line: “There are k elements in the reservoir, and the l-th element has been consumed. It should be chosen with probability k/l.”

The seed makes a day repeatable: the same tickets and the same seed give the same review, in both languages. That is for examples and tests. A real desk should draw from a source nobody can predict, so nobody can close a ticket at the moment it’s sure to be skipped.

Build UIs?It runs under your pages, in the database they read. A bug report that carries a fair sample of a session’s errors is where you own it.

Where it already is in your components

Not in the components themselves: React and Svelte don’t sample anything, and the browser has no built-in sampler for your events. It runs one layer down. If your pages read from PostgreSQL, hosted or not, the planner picks how to run each query from statistics that ANALYZE gathered with a reservoir: 30,000 rows per table at the default setting. You probably never ran it. PostgreSQL’s documentation says the autovacuum daemon “will automatically issue ANALYZE commands whenever the content of a table has changed sufficiently.”

When you have to own it

A support widget sends a report when a user asks for help, and it should include the errors the page threw. A long session can throw thousands. Keeping the last ten shows only how the session ended; a fair ten shows the whole session, and if the first error matters most, keep that one separately. createErrorSample keeps a fair ten with the lesson’s offer, drawing from crypto.getRandomValues, and reports how many errors it saw alongside the ten it kept.

error-sample.ts
import { MAX_SEEN, drawBelow, offer, reservoir, sample, type Reservoir } from '../sample';

// A fair sample of the errors a long browser session throws, attached to a bug report when the
// user asks for help. Nobody knows how many errors a session will have: the page never holds more
// than `size`, and every error seen so far had the same chance to be one of them. `seen` goes with
// the sample, so whoever triages knows it is 10 errors of 3,412, not 10 of 10.
export type ErrorReport = { message: string; source: string; at: number };

const cryptoNext = () => crypto.getRandomValues(new Uint32Array(1))[0];

export function createErrorSample(size = 10, next: () => number = cryptoNext) {
	let kept: Reservoir<ErrorReport> = reservoir(size);
	const draw = (bound: number) => drawBelow(next, bound);
	return {
		add(report: ErrorReport): void {
			if (kept.seen < MAX_SEEN) offer(kept, report, draw); // an error listener must not throw
		},
		read(): { seen: number; sample: ErrorReport[] } {
			return { seen: kept.seen, sample: sample(kept) };
		},
		reset(): void {
			kept = reservoir(size);
		}
	};
}

// const errors = createErrorSample(10);
// window.addEventListener('error', (event) =>
// 	errors.add({ message: event.message, source: `${event.filename}:${event.lineno}`, at: Date.now() })
// );
// window.addEventListener('unhandledrejection', (event) =>
// 	errors.add({ message: String(event.reason), source: 'promise', at: Date.now() })
// );
// helpButton.addEventListener('click', () => sendReport({ errors: errors.read() }));

Nothing here belongs to React or Svelte. Create the sample once, outside any component, and read it only when the report is sent. The tests check an empty sample, filling, that the same numbers keep the same errors as the lesson’s reservoir, that a sample of four still holds four after a thousand errors, and reset.

07 / Make the call

Use it when you can’t count ahead.

Reach for a reservoir when items arrive one at a time, you can’t or won’t keep them all, and every item should have the same chance: log lines, events, rows in a scan, errors in a session. If you already hold the whole list, you don’t need it. Shuffle with Fisher–Yates and take the first k, or pick k distinct positions.

Know what it doesn’t cover. Every item counts the same; giving some tickets more weight needs a different sampler, which this lesson doesn’t cover. It samples everything since the start, not a sliding last hour; for hourly windows, start a new reservoir each hour. Two reservoirs from two machines can’t be poured together as they are: each item’s chance depends on how many its own machine saw. Spark’s range partitioner weights every key in a partition’s sample by that partition’s count over its sample size (unusually large partitions are sampled again instead): “The weight is 1 over the sampling probability.”

And test the draw, not only the result. The off-by-one produces samples that look perfectly random. Only counting, or replaying thousands of days, shows that the first tickets lose: over 20,000 seeded days with 20 tickets and five slots, Algorithm R kept every ticket within 1.2 percentage points of 25%, and the off-by-one strayed by more than 3.

SourcesDocumentation, source, and the paper’s record, checked 14 and 23 September 2026

08 / Take the idea with you

Explain a fair sample without saying “reservoir.”

“Keep the first k things. For every thing after that, if it’s the i-th thing so far, pick a random whole number from 0 to i − 1. If it’s less than k, the new thing takes that numbered place; otherwise let it go. Every thing ends up kept with the same chance, k in however many there were.”

Before moving on, find a place in your work that keeps “the last N” or “every Nth” of something: log lines, events, errors. Ask whether it should keep a fair N instead, and whether anyone reading it knows how many it saw.

Connections to follow nextRelated lessons