Streaming Approximate Histograms in Go

Posted by Preetam Jinka on Jul 8, 2013 5:04:00 AM

If you’re looking at response time, what’s more useful: a mean or a percentile? Not sure? Let’s look at an example. The following graphs are from Github’s status page. They had a little issue earlier, which affected their web response time:

Approximate_Histograms

It’s clear that there’s a huge difference (almost an order of magnitude!) between the mean and the 98th percentile values. Outliers are much easier to detect using percentiles. Michael Kopp’s “Why Averages Suck and Percentiles are Great” also demonstrates how percentiles are much more useful.

You probably know how to calculate the average or mean of a sample, but what about percentiles? It’s very simple. Let’s say you have a 100-element set and you wanted to know the 95th percentile value. You would have to sort the set from least to greatest and get the 95th element. If you wanted the 50th percentile value, you would look at the 50th element.

It’s very easy to calculate percentiles for small sample sets. What if we’re working with those that are larger? Maybe a couple of orders of magnitude larger? What if we keep getting a stream of values rapidly? At that scale, it’s going to take longer to sort all those elements, and we’ll be using a lot of space to store them, and our method of finding percentiles becomes inefficient.

If we’re dealing with a large amount of values and we need know the characteristic of our data, we should be fine with approximations. If we settle for statistics that are good enough, we’re suddenly exposed to a variety of neat techniques that solve our problem. One technique uses histograms. The other technique is called reservoir sampling, which uses a statistically representative subset of a large amount of data.


Reservoir Sampling

Coda Hale’s Metrics package includes a few interesting histogram implementations which use a technique called reservoir sampling.

By maintaining a small, manageable reservoir which is statistically representative of the data stream as a whole, we can quickly and easily calculate quantiles which are valid approximations of the actual quantiles. This technique is called reservoir sampling.

With reservoir sampling, we still have to maintain a set of values and we still have to sort to be able to calculate quantiles. It’s better than calculating the exact quantiles by storing every single value, but what if we don’t want to store individual values at all? Fortunately, we don’t have to.

Histograms

Histogram

Histograms are useful representations of distributions. Each “bin” or bar in a histogram represents a range of values, and the height of the bar represents the frequency (or count) of values in that bin. With histograms, we don’t have to keep track of individual values. We can just find which bin a value belongs to and increment the frequency counter.

Streaming Histograms

We’ve decided to implement histograms based on those found in “A Streaming Parallel Decision Tree Algorithm.” These histograms are dynamic, compressed, and offer efficient quantile approximations. They’re dynamic in that they do not have fixed bin values, and bins adapt to the data that streams in. The histograms also have a fixed maximum bin count, so resource usage stays constant regardless of how many values stream in.

The algorithm is fairly simple. A histogram is created with a maximum bin count. Each new value streamed into the histogram creates an additional bin with a count of 1. If the current bin count is higher than the maximum, the closest bins are merged. Close refers to the distance between the values of the bins. The higher the maximum bin count, the better the approximations at the cost of greater resource utilization and computation time.

Merging_Bins

We’ve also added an implementation of a weighted histogram where each bin’s frequency count is an exponentially-weighted moving average. This would allow the histograms to be used for long periods of time with many values without worrying too much about overflows. Moving averages also give more recent values more weight.

Other thoughts

The Apache Hive project includes an implementation in Java. They recommend using between 20 and 80 bins.

We’ve open-sourced our implementations (written in Go) under the MIT license. They’re available on Github.

Subscribe to Email Updates

Posts by Topic

see all