A Sampling Trick

Here's a sampling trick that comes up all the time in industry, but that took me a while to work out. The problem goes like this:

Suppose a server is receiving a sequence of events, for any kind of event you might be interested in, and you want to save off a sample of the events for later analysis. How do you select which events to sample?

Let me show some solutions that I see people try, and then describe a way that seems to beat all those out.

Solutions that don't work well

Choose a fixed percentage. One approach is to choose a percentage, say 5%, and to log that percentage of incoming events. For each event that arrives, you check a random number generator against your percentage, and independently decide for each event whether to log a sample or not. This approach is pretty good except that it's often hard to choose a percentage ahead of time. If you get thousands of events per second, then 5% is going to be way too many. If you get one event per minute, then 5% is going to be way too few. In many cases, you are going to use the same sampling code to run against multiple streams of events, for example to sample access to multiple databases, or to sample requests to multiple RPCs on the same server. As another example, you may run the code in both staging and production environments, and you'll need a different percentage for each environment.

Look at historical data rates. Another way is to use a percentage, but to dynamically adapt the percentage based on historical traffic rates. This way works in theory, but in my experience, systems like this tend to be unstable. For example, the system will dial in a low percentage based on overnight traffic, or because the system paused due to a garbage collection or a spate of disk I/O on the underlying machine. Then a burst of activity will happen, and the system will use its old percentage for a while, thus sampling way too much data. Then the percentage updates, but the burst of activity disappears. Now the server is sampling at a very low percentage and throwing everything away, because the burst of traffic disappeared. In general, I can't say that this method can't work, but in a world where software always has bugs and surprises, it's much better to use algorithms that are more clearly stable and predictable.

Use time-based sampling. Instead of sampling a percentage of traffic, the system can select one event for each window of time, for example one event every 10 seconds. This method adapts to different rates of incoming events, including bursty traffic where the rate isn't steady. Now there's a new problem, though: the events are not randomly selected any more! This method will work fine if the server is receiving a homogenous series of events that are all spaced out the same from each other, but that may or may not be the case. A lot of times, there is some external process, perhaps generated by an end user, where one external event will create a clump of events that arrive at your server at almost the same time as each other. If you select one event every 10 seconds, you will tend to sample events that are at the beginning of the clumps, thus making some of the events more likely to be sampled than others.

A dumb way that works

Here's an approach you could follow that will reliably work, but at the expense of a lot of memory usage. What you could do is collect all of the events for a 10-second window into an in-memory buffer. Each time a new event arrives, you don't think twice, you simply add it to the buffer to be looked at later on. Once the ten-second window expires, you look through the buffer and randomly select one of the events in the buffer. Then you reset the buffer and start again for the next 10-second window.

This way meets all of the constraints, but now it uses a lot of memory. It's close, though, except for the memory problem. Is there a way to do this, but with a smaller buffer? It would need to be some kind of algorithm that discards events as it goes, rather than waiting to the end of the 10-second window to do a whole lot of discarding all at once.

The sampling trick

Here's a way that works. Keep the following two pieces of information in memory.

• The number of events that have arrived, in the current 10-second window.
• One single event from the window. This is the event that will be sampled for sure if no other events arrive.

Given this setup, here's what you do when a new event arrives.

1. Increase the count of events by one.
2. Select a random number from 1 to the new, updated count of events.
3. If the random number is 1, then replace the event in the buffer by the new event; the new event is the one you need, and you know for sure you don't need the old event.
4. If the random number is anything other than 1, then discard the new event; you're done with that event for good and aren't going to use it.

When the 10-second window elapses, emit your current sample and then reset the buffer to its original state: 0 events that have arrived, and null as the currently stored event.

An example walk-through

To see why this works, let's start with a scenario that exactly three events arrive during the window. Here's what happens.

Event 1 arrives. When the first event arrives, increase the count to 1. Roll a number from 1 to 1, which will always result in 1, so store the first event into the buffer. Here's what is in the buffer now:

• Event 1, for sure.

Event 2 arrives. When the second event arrives, increase the count to 2. Roll a number from 1 to 2. This roll has a probability of 1/2 of being a 1, in which case event 2 will replace the first one. At this point, there is a 1/2 probability that event 2 took over the buffer, and a 1/2 probability that event 1 is still in there.

• Event 1, at probability 1/2.
• Event 2, at probability 1/2.

Event 3 arrives. Increase the count to 3, and roll a number from 1 to 3. This roll has a probability of 1/3 of being a 1 and causing event 3 to take over the buffer. At probability 2/3, some other number is rolled, and the existing event is brought forward. Therefore, the probability for event 1 to still be in the buffer is the 1/2 chance that the event already had, times the 2/3 chance that it survives this latest roll of the die. For event 2, the same reasoning applies as for event 1.

• Event 1, at probability 1/2 * 2/3 = 1/3.
• Event 2, at probability 1/2 * 2/3 = 1/3.
• Event 3, at probability 1/3.

Proof of the general case

Property. When using The Sampling Trick described above, after the arrival of N events, each event has 1/N probability of being the one in the sample buffer.

The world's smallest proof by induction. In the base case, suppose N=1. Then there is just one event, and it is always selected. The one event has probability 1/1, which is what we wanted to prove.

For the inductive case, assume the property is correct for N-1, and prove it for N.

For the Nth event, it was the last event that arrived, and the rules of the algorithm are that it will replace all prior events at probability 1/N. So the theorem is true for the Nth event.

For any other event, we know by the inductive assumption that it has a 1/(N-1) chance of being in the buffer when the Nth event arrives. The Nth event will replace the buffered event at probability 1/N, so the probability of the existing event being left alone is (N-1)/N. Therefore, the probability that the prior event is both selected from the first N-1 rounds, and also stays in the buffer after the Nth round, is 1/(N-1) x (N-1)/N, which is 1/N.

Q.E.D.

How do you use this in practice?

Sampling is helpful for always-on computer systems that can never have any down time. In a case like that, you need to not only make the server internally robust for every kind of input it might receive, but also be externally compatible with all the other software that's around it in the current production ecosystem.

There are a lot of tricks and know-how for how to use the sample data once you have it, but the first step is to capture the data at all.