If someone asks you how many people were at a concert, you don’t count them one by one: you look, make a rough guess and say “about five thousand”. You might be off by a few hundred, but it took you two seconds and you didn’t need to write down anyone’s name. Probabilistic data structures do exactly that: they give an approximate answer, with an error you know in advance, in exchange for using a tiny fraction of the memory.
Anton Zhiyanov, the same author behind Go Concurrency Distilled, has published a walkthrough of five of them along with unsure, a Go package that implements them using only the standard library. It’s one of those articles that explains something you’ve heard of and that, by the end, you finally understand.
The five structures
What helps most to understand what they’re for is seeing how much space they take compared with the “exact” solution (a map or a set), with the article’s own figures for a million elements:
| Structure | For | Exact | Probabilistic | Error |
|---|---|---|---|---|
| Bloom filter | Is this element here? | ~64 MB | ~1.24 MB | 1% false positives |
| Count-min sketch | How many times has it appeared? | ~64 MB | ~0.55 MB | 0.01% of total |
| HyperLogLog | How many distinct ones are there? | ~64 MB | 16 KB | ~0.8% |
| T-digest | What’s the 99th percentile? | 8 MB | ~8 KB | ~0.03% in rank |
| Top-k | Which are the most frequent? | — | ~360 KB for the top 1000 | almost always exact |
Sixteen kilobytes to count a million distinct elements. Hard to believe until you see how it works.
Bloom filter. A bit array and several hash functions: adding an element turns on a few bits, and querying checks whether they’re all on. It can tell you something is there when it isn’t (false positive), but never that it isn’t there when it is. It’s perfect for skipping an expensive disk or network lookup when you know for sure the data doesn’t exist. You can’t delete or iterate over elements.
Count-min sketch. A table of counters with several rows; each element adds one to a counter per row and the estimate is the minimum of them all. It never undercounts, though it can overcount, and it’s less accurate for rare elements. It’s useful for things like rate-limiting by IP or deciding which key deserves to be cached.
HyperLogLog. It looks at how many leading zeros the hashes have: if you’ve seen a hash starting with lots of zeros, you’ve probably seen lots of distinct elements (like someone guessing they’ve tossed a lot of coins because they got ten heads in a row). It’s what many databases use to estimate cardinalities; DuckDB, for example, stores HyperLogLog statistics in its format, something I mentioned when writing about DuckDB file formats.
T-digest. For percentiles over a stream of numbers, like latencies. It keeps groups of values (centroids) small at the extremes and large in the middle, so it’s most accurate right where it matters: the 99th percentile that wakes you up at night.
Top-k. For finding the most frequent elements (the most requested URLs, the most active users) without keeping a count of all of them. It works best when a few elements stand out well above the rest, which is usually the case with real traffic.
The unsure package
The API is as simple as you’d expect:
filter := bloom.New(1000, 0.01)
filter.Add([]byte("alice"))
filter.Contains([]byte("alice")) // true
sketch := hll.New()
sketch.Add([]byte("alice"))
sketch.Count() // approximately 1
You install it with go get github.com/nalgeon/unsure and each structure lives in its own subpackage (bloom, countmin, hll, tdigest and topk). It has no dependencies, which in Go is always welcome.
The article includes comparisons with the usual libraries (bits-and-blooms, BoomFilters, axiom, influxdata, dgryski…), and it comes out ahead in almost all of them: according to the author’s numbers, the Bloom filter is about four times faster than bits-and-blooms and the HyperLogLog counts hundreds to thousands of times faster than axiom’s. Mind you, these are the author’s own benchmarks of his own package, so before changing anything in production, measure with your own data. He himself admits that in some cases (HyperLogLog with very few elements) the alternative is more accurate and smaller.
Why I like it
The best part of the article isn’t the package, but that it takes the fear out of these structures. There are plenty of everyday problems (counting unique visitors, knowing which endpoints get called the most, computing latency percentiles) that we solve with a map that grows and grows until one day the process runs out of memory. Knowing there’s an alternative that takes kilobytes and is off by less than 1% changes how you approach the problem. You don’t always need the exact figure: often it’s enough to know there were about five thousand people at the concert.
