Reservoir sampling (Wikipedia)

Ideas you will meet

Distributed Systems

Consensus, time, failure and the fundamentals of scale-out.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Search, Analytics and Geo · 9 minReservoir sampling: a fair sample of a stream you cannot storeHow to keep k uniformly random items from a stream of unknown length using only k slots of memory, why it works, and where it is used.Read hereClose

  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

  Related reading

  • Random Sampling with a ReservoirJeffrey Vitter · University of Maryland (hosted copy)Papers
  • Reservoir sampling (Wikipedia)Wikipedia contributors · WikipediaDocumentation
  • Computing Extremely Accurate Quantiles Using t-DigestsTed Dunning and Otmar Ertl · arXivPapers

  Open this lesson with its quiz and exercise