Bloom filters and other probabilistic structures

Trading exactness for space

Sometimes you need an answer that is almost always right using a tiny fraction of the memory. Probabilistic data structures do that, with errors that are small and predictable.

Bloom filter: "have I seen this?"

A Bloom filter is a bit array plus several hash functions.

• Add an item: hash it k ways, and set those k bits to 1.
• Check an item: hash it the same way. If any bit is 0, it was never added. If all are 1, it was probably added.

100%

Figure SDA-CORE-16-1 · Bloom filter: "have I seen this?" · © forcsguy.com

Properties:

• No false negatives: an item you added is always reported present.
• Possible false positives: other items may have set the same bits. The rate depends on the array size, the number of items and the number of hashes. About 10 bits per item gives roughly 1%.
• Tiny and fast: constant-time operations and a fixed memory footprint.
• No deletion in the basic version (use a counting Bloom filter or a cuckoo filter).

Typical uses

• Avoid expensive lookups: databases check a Bloom filter before reading disk, skipping files that cannot contain the key (as in log-structured storage).
• Cache penetration: reject requests for keys that do not exist before they hit the database.
• Crawlers: remember which URLs were visited.
• Safe browsing checks and "username already taken" fast paths.

100%

Figure SDA-CORE-16-2 · How a false positive happens · © forcsguy.com

Counting distinct items: HyperLogLog

Counting unique visitors exactly needs memory proportional to the number of visitors. HyperLogLog estimates the count of distinct items in a few kilobytes with about 1 to 2% error, by observing patterns in hashed values. It is built into Redis, and sketches can be merged, so you can combine counts from many servers.

Frequency estimates: count-min sketch

A count-min sketch estimates how often each item appears, using a small table of counters and several hashes. It can over-estimate but never under-estimate. Useful for finding heavy hitters ("top trending terms") in a stream.

When to use them

Use probabilistic structures when the data is huge, memory is the constraint, and a small error is acceptable. If you must be exact (money, permissions), do not.

Real-world reading