Reservoir sampling: a fair sample of a stream you cannot store

The problem

You want a small, unbiased sample of a stream: log lines, requests, events. You cannot store the whole stream, and you do not know how long it will be. "Keep every 1,000th item" is not random and can be biased by periodic traffic. "Pick random items" needs to know the total in advance.

Reservoir sampling keeps exactly k items so that, at any moment, each of the n items seen so far has the same probability k / n of being in the sample.

Algorithm R

1. Put the first k items in the reservoir.
2. For each later item number i (counting from 1), draw a random integer j between 1 and i.
3. If j is at most k, replace reservoir slot j with the new item. Otherwise discard the new item.

100%

Figure SDA-SAG-06-1 · Algorithm R for one new item · © forcsguy.com

function reservoir<T>(stream: Iterable<T>, k: number, rand = Math.random): T[] {
  const sample: T[] = []; let i = 0;
  for (const item of stream) {
    i++;
    if (sample.length < k) sample.push(item);
    else { const j = Math.floor(rand() * i); if (j < k) sample[j] = item; }
  }
  return sample;
}

Why it is fair

Item i enters with probability k / i. Then it survives each later step m with probability 1 - (k / m) x (1 / k) = (m - 1) / m. Multiply them for item i after n items: (k / i) x (i / (i + 1)) x ... x ((n - 1) / n) = k / n. Every item ends with the same chance, whatever its position.

Where it is used

• Debug and audit samples of request logs or events, at constant memory.
• Estimating statistics, such as the share of requests with a certain property, from the sample.
• Training data selection from a live stream.
• Approximate quantiles when a small error is acceptable (for tighter tail accuracy see the t-digest lesson).

Sampling many streams

100%

Figure SDA-SAG-06-2 · Merging samples from several servers · © forcsguy.com

Keep the count with every sample; without it you cannot merge correctly. A simple way is to draw each output slot by choosing a server with probability equal to its share of the total count, then taking a not-yet-used item from that server's reservoir.

Variants and limits

• Weighted sampling (Efraimidis and Spirakis, A-Res) lets some items be more likely, for example by traffic weight.
• Sliding windows need extra structure: plain reservoir sampling treats the whole history equally.
• A sample answers "what does a typical item look like?" It does not answer exact counts or rare-event questions; for those use sketches such as HyperLogLog or count-min.

Real-world reading