Bloom Filters and Probabilistic Data Structures

Bloom filters

Start with an array of m bits, all 0, and k hash functions. To add an item, hash it k times and set those k bits to 1. To check an item, hash it the same way: if any of its bits is 0, it was definitely never added. If all are 1, it was probably added, or other items happened to set those same bits.

position:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
bits:      0 0 0 1 0 0 0 0 0 1 0  0  0  0  1  0

add "cat"   hashes to 3, 9, 14   -> set those bits
check "dog" hashes to 3, 6, 14   -> bit 6 is 0: definitely not added
check "cow" hashes to 9, 3, 14   -> all 1: probably added (a false positive)

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.util.BitSet;

class BloomFilter {
    private final BitSet bits;
    private final int m;
    private final int k;

    BloomFilter(int m, int k) {
        this.bits = new BitSet(m);
        this.m = m;
        this.k = k;
    }

    private int[] positions(String item) {
        try {
            byte[] d = MessageDigest.getInstance("MD5").digest(item.getBytes(StandardCharsets.UTF_8));
            long h1 = 0;
            long h2 = 0;
            for (int i = 0; i < 4; i++) {
                h1 = (h1 << 8) | (d[i] & 0xff);
                h2 = (h2 << 8) | (d[i + 4] & 0xff);
            }
            int[] out = new int[k];
            for (int i = 0; i < k; i++) {
                out[i] = (int) ((h1 + i * h2) % m);
            }
            return out;
        } catch (Exception e) {
            throw new IllegalStateException(e);
        }
    }

    void add(String item) {
        for (int p : positions(item)) {
            bits.set(p);
        }
    }

    boolean mightContain(String item) {
        for (int p : positions(item)) {
            if (!bits.get(p)) {
                return false; // definitely not added
            }
        }
        return true;          // probably added
    }
}

import hashlib

class BloomFilter:
    def __init__(self, m, k):
        self.m = m
        self.k = k
        self.bits = bytearray((m + 7) // 8)

    def _positions(self, item):
        digest = hashlib.md5(item.encode()).hexdigest()
        h1, h2 = int(digest[:8], 16), int(digest[8:16], 16)
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item):
        for p in self._positions(item):
            self.bits[p // 8] |= 1 << (p % 8)

    def might_contain(self, item):
        # False means definitely not added; True means probably added.
        return all(self.bits[p // 8] & (1 << (p % 8)) for p in self._positions(item))

The false positive rate is about (1 − e^(−kn/m))^k for n items. With m = 10,000 bits, n = 1,000 items and k = 7 that is under 1%, and the tests above check it stays below 3%. Items cannot be removed from a basic Bloom filter (clearing a bit could remove other items); counting Bloom filters or cuckoo filters allow deletes.

• LSM-tree databases (Cassandra, RocksDB, HBase) keep a Bloom filter per data file to skip files that cannot contain a key.
• Web crawlers: "have I already queued this URL?" over billions of URLs.
• Cache guards: avoid a database lookup for usernames or IDs that do not exist.

HyperLogLog: counting distinct items

Counting unique visitors exactly needs a set of every visitor ID: gigabytes for big sites. HyperLogLog hashes each item and looks at how many leading zeros the hash has: seeing a hash with many leading zeros is rare, so it suggests many distinct items have been seen. Splitting items into many buckets and averaging gives a good estimate.

Redis implements HyperLogLog with a standard error of 0.81% using at most 12 KB per key, whatever the count (PFADD to add, PFCOUNT to estimate). Sketches from different servers or days can be merged, so "unique visitors this week" is the merge of seven daily sketches.

Count-Min Sketch: how often?

A Count-Min Sketch is a small grid of counters with one hash function per row. Adding an item increments one counter in each row; the estimate is the minimum of those counters. Collisions only ever add, so the estimate is never too low, and taking the minimum keeps the over-count small. It is used to find heavy hitters (top searches, most active IPs for rate limiting) in a stream without storing every item.

Common mistakes

• Treating a Bloom filter "yes" as a definite yes.
• Sizing the filter for today's item count; the false positive rate climbs as more items are added.
• Trying to delete from a basic Bloom filter.
• Using exact sets for analytics counts where an estimate within 1% is fine.

Interview questions

Try answering out loud before you open each one.

Check yourself

Related topics

• Database IndexesDatabases
• Cache Strategies: Cache-Aside, Read-Through, Write-Through, Write-BehindCaching
• Rate LimitingEdge and Traffic

Further reading

• Probabilistic data types Redis documentation
• HyperLogLog Redis documentation
• Bloom filter Wikipedia