Probabilistic data structures give approximate answers in exchange for much lower memory use. The unsure Go package implements several of them using only the standard library.
Probabilistic data structures answer questions about data approximately, such as whether an item is in a set, how many unique items exist, or which items appear most often. In return for exact answers, they can greatly reduce memory usage. The author introduces unsure, a Go package that implements these structures. Its core logic for each structure is roughly 100 to 300 lines of code, and it is usually several times faster than other implementations.
A Bloom filter stores no items, only bits, so it can say that an item is definitely absent or probably present. For one million 8-byte strings with a 1% false positive rate, it needs about 1.24 MB, compared with about 64 MB for a regular set. Unsure uses a blocked variant that keeps each check within a single CPU cache line, which helps on large filters. It needs about 3% more memory than a standard Bloom filter at a 1% false positive rate. In the author's benchmarks, unsure was about four times faster than bits-and-blooms and twice as fast as gloom.
A count-min sketch estimates how often each item appears. The estimate is never lower than the true count but may be higher. For the same one million strings, a sketch with estimates within 0.01% of the total count, with 99% probability, uses about 0.55 MB. Unsure adds a conservative update that cuts the actual error roughly in half and uses 32-bit counters, which halve memory use. According to the benchmarks, it is about 1.5 times faster for adds and 4 times faster for counts.
HyperLogLog counts distinct items regardless of how often each one appears. For one million 8-byte strings with about 0.8% error, a sketch uses only 16 KB, almost 4,000 times less than a regular set. The excerpt available ends before covering the rest of this structure.
Source: antonz.org
