How do you pick a fair random sample from a list when you do not know how long the list is? If you know the length, it is easy: pick random positions. But what if the data is a live stream of events, or a log file too big to count first, or a feed that never ends?
The answer is a small trick known as reservoir sampling. Jeffrey Vitter's 1985 paper studies it carefully and makes it fast. The paper describes sampling when the number of records is unknown beforehand, such as records on a magnetic tape of indeterminate length. Today the same trick is used on logs, events and metrics.
Keep a reservoir of k items. Put the first k items in. Then, for item number t, keep it with probability k / t, replacing a random item in the reservoir. When the stream ends, the reservoir is a uniform random sample of everything seen. It uses constant space and one pass.
The simple rule
The basic method is called Algorithm R in the paper, credited to Alan Waterman. It needs only a handful of lines.
- Copy the first k items into the reservoir.
- For every later item, number t: pick a random number between 0 and 1.
- If it is below k / t, keep the item and let it replace one of the k reservoir items, chosen at random.
- Otherwise skip it. When the stream ends, the reservoir is the sample.
The chance of keeping a new item shrinks as the stream grows. Item 100 is kept with chance k / 100, while item 1,000,000 is kept with chance k / 1,000,000. That makes sense. A longer stream means each item should have a smaller share of the limited room.
