Bloom filters and sketches

Bloom filter, HyperLogLog and count-min sketch: small memory, small known error.

On the roadmap:Staff Engineer · step 2: Approximate answers at scale

Intermediateabout 10 to 15 min7 experiments

Experiments

New here? A few short steps show what happens, one at a time.

Settings

Which structure

Bits in the filter8,192

Hash functions3

Items stored1,000

Bits set

31%

Wrongly says yes

2.8%

Formula predicts

2.9%

Memory

1.0 KB

2.8% of absent items were wrongly reported as present, against 2.9% predicted. The best number of hash functions for this size is 6. A 'no' is always right.

The first 1,024 bits (dark means set)

False positives as the number of hash functions changes

false positive rate

Wrongly says yes

For 8,192 bits and 1,000 items. The lowest point is the best number of hash functions: about 6.

In plain words

Some questions do not need an exact answer. A Bloom filter says whether an item is probably in a set, HyperLogLog estimates how many different items there are, and a count-min sketch estimates how often each item appears. Each uses a tiny, fixed amount of memory, and pays with a small, known error.

Why it matters

Keeping every user, key or event in memory is impossible at large scale, and often unnecessary. A structure a thousand times smaller that is right to within a few per cent, and wrong in one safe direction, can answer the question that matters. Here you can resize each one and watch the error respond.

How real systems do it

The simulation is a simplified model. Here is what production systems add or do.

Bigtable, HBase, Cassandra and RocksDB keep a Bloom filter for each file of data, so a lookup for a key that is not there usually skips reading the file at all.
Redis has HyperLogLog built in (PFADD and PFCOUNT). Each one uses at most about 12 KB and has a standard error of about 0.81%, however many items it counts.
Large analytics systems offer approximate distinct counts, such as approx_count_distinct in Spark and Presto and BigQuery's APPROX_COUNT_DISTINCT, which use HyperLogLog variants.
Count-min sketches track heavy hitters in a stream, such as trending queries, without storing every item. A false positive from a Bloom filter or an overcount from a sketch is acceptable when the cost of being wrong is small.