Bloom filters and sketches

The problem it solves

A web crawler has found 10 billion URLs. It must check every newly found link against them: “have we seen this one?” As strings, the set is about 800 GB. Even as 8 byte fingerprints in a hash table, it’s about 160 GB with overhead. That’s too much for one machine’s RAM. So each of tens of thousands of link checks a second becomes a disk read or a network call.

The same wall shows up for three questions that every large system asks:

Question	Exact answer costs	Probabilistic answer costs	And gives up
Have we seen this URL? (10 billion URLs)	160 GB of fingerprints, 800 GB of strings	12 GB Bloom filter	1% of new URLs wrongly say “seen”
How many distinct visitors today? (200 million)	3.2 GB of 16 byte IDs, several times that in a set	12 KB HyperLogLog	About ±0.8% on the count
How often did each item appear? (1 billion events)	A counter per distinct item: GBs for 100 million keys	5.4 MB Count-Min	Any count may be up to 10,000 too high

These structures answer a narrower question than a set or a map, with a small error of known bound. Memory drops by 10 times or more for membership and by over 100,000 times for distinct counts. Three more properties make them fit distributed systems:

• Fixed size. Memory is chosen up front from the error you can accept, not from how much data arrives.
• Mergeable. Sketches built on different shards, regions or hours combine into the sketch of the whole, by OR, addition or max.
• One-sided or bounded errors. A Bloom filter never says “no” to an item it holds. A Count-Min Sketch never counts low. The error has a direction you can design around.

The cost: you cannot list the items, and you usually cannot delete. And the error is a probability, so some answers are wrong by more than the typical figure.

How it works

Step 1: One hash, one bit array

Start with the simplest membership structure that is not a set: an array of m bits, all zero, and one hash function. To add an item, hash it to a position and set that bit. To check an item, look at its bit. If the bit is 0, the item was never added, guaranteed. If it is 1, either this item set it or some other item hashed to the same place.

With n items in m bits, a fraction of about 1 − e^(−n/m) of the bits is set, and that is the false-positive rate. At 10 bits per item it is 9.5%. Getting to 1% with one hash needs about 100 bits per item, worse than storing a 64 bit fingerprint. One hash is too weak.

Step 2: k hashes, the Bloom filter

Burton Bloom’s 1970 idea: use k hash functions. Adding an item sets k bits. A check reports “maybe present” only if all k bits are set, and “definitely not present” if any is 0. A stranger now has to hit k set bits by chance, not one.

Adding two words, then checking a third

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Failure

More hashes cut both ways. Each one adds a bit a stranger must find set, but each also sets more bits per item, so the array fills faster. With n items, m bits and k hashes:

• Fraction of bits set: 1 − e^(−kn/m)
• False-positive rate: p ≈ (1 − e^(−kn/m))^k
• The best k is (m/n) ln 2, about 0.7 times the bits per item. At that k, half the bits are set when the filter holds its design capacity.
• Solving for m: m = −n ln p / (ln 2)², which is 1.44 × log₂(1/p) bits per item.

Target false positives	Bits per item	Best k	1 billion items
10%	4.8	3	0.6 GB
1%	9.6	7	1.2 GB
0.1%	14.4	10	1.8 GB
0.01%	19.2	13	2.4 GB

Each 10 times fewer false positives costs a constant 4.8 more bits per item. And the size depends only on n and p, not on item size: 10 billion URLs cost the same as 10 billion user IDs.

Where the k hashes come from. Computing seven independent hashes per lookup is wasteful. Kirsch and Mitzenmacher showed in 2006 that two are enough. Take one 64 bit hash, and split it into halves h1 and h2. Then use positions h1 + i × h2 mod m, for i from 0 to k − 1. The false-positive rate is asymptotically the same as with k independent hashes. Guava and most libraries do this.

Try it. Add 10 random items a few times at m = 256 and k = 3, and watch the predicted and measured false-positive rates climb together. Then drag k to 10 and see the filter fill faster, or check a word you never added until you find a false positive. Last, delete an item and count the damage.

Bloom filterHyperLogLog

Bits, m = 256Hashes, k = 3

AddCheck

Add 10 randomAdd 50Delete the last itemReset

set probed by the last add or check

Items added, n

0

Bits per item, m/n

-

Bits set

0%

Best k for this m and n

-

False positives, predicted vs measured on 2,000 strangers

0% vs 0%

False negatives among added items

0

An empty filter: m bits, all zero. Add a word, or add 10 random items a few times and watch the predicted and measured false-positive rates climb together.

The code sizes the filter from n and p, derives k, and runs it to twice its design capacity. Its hash is FNV-1a plus a 64 bit mixer, short enough to write the same way in five languages. Production filters use MurmurHash3 or xxHash.

JMain.javaPybloom_filter.pyC#BloomFilter.csGobloom_filter.goTSbloom-filter.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

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

public class Main {
    // The splitmix64 finalizer: spreads every input bit over all 64 output bits. Every filter
    // and sketch assumes its hash outputs look uniformly random; a weak hash breaks the math.
    static long mix64(long z) {
        z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L;
        z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL;
        return z ^ (z >>> 31);
    }

    // FNV-1a over the UTF-8 bytes, then mixed. Production code uses MurmurHash3 or xxHash; this
    // pair is short enough to write identically in every language, so all clients agree on bits.
    // (Never String.hashCode(): 32 bits, poorly mixed, and Java-only.)
    static long hash64(String s) {
        long h = 0xCBF29CE484222325L;
        for (byte b : s.getBytes(StandardCharsets.UTF_8)) {
            h = (h ^ (b & 0xFF)) * 0x100000001B3L;
        }
        return mix64(h);
    }

    static final class BloomFilter {
        final long m;
        final int k;
        final BitSet bits;

        BloomFilter(int expectedItems, double fpRate) {
            // Size from the two numbers you actually know: how many items, and how wrong you can be.
            // m = -n ln p / (ln 2)^2 bits, about 9.6 bits per item at 1%.
            m = (long) Math.ceil(-expectedItems * Math.log(fpRate) / (Math.log(2) * Math.log(2)));
            // k = (m / n) ln 2 hashes leaves about half the bits set at capacity, which minimizes
            // false positives. More hashes is not better: each one also fills the filter faster.
            k = (int) Math.max(1, Math.round((double) m / expectedItems * Math.log(2)));
            bits = new BitSet((int) m);
        }

        // Double hashing (Kirsch and Mitzenmacher): k positions from one 64 bit hash, split into
        // two 32 bit halves. As good as k independent hashes for a Bloom filter, and k times cheaper.
        long[] positions(String item) {
            long h = hash64(item);
            long h1 = h & 0xFFFFFFFFL, h2 = h >>> 32;
            long[] out = new long[k];
            for (int i = 0; i < k; i++) out[i] = (h1 + i * h2) % m;
            return out;
        }

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

        // False is certain: some bit the item would have set is clear. True only means "maybe".
        boolean mightContain(String item) {
            for (long p : positions(item)) if (!bits.get((int) p)) return false;
            return true;
        }
    }

    // Chance that all k probed bits were set by the n items already added.
    static double predictedFp(long m, int k, int n) {
        return Math.pow(1 - Math.exp(-(double) k * n / m), k);
    }

    static double measured(BloomFilter bf, int n) {
        int hits = 0;
        for (int i = 0; i < n; i++) if (bf.mightContain("stranger:" + i)) hits++;
        return 100.0 * hits / n;
    }

    public static void main(String[] args) {
        int n = 100_000;
        BloomFilter bf = new BloomFilter(n, 0.01);
        System.out.printf("m = %d bits (%.0f KB), k = %d%n", bf.m, bf.m / 8.0 / 1024, bf.k); // m = 958506 bits (117 KB), k = 7
        for (int i = 0; i < n; i++) bf.add("user:" + i);
        // Never a false negative: every added item is still reported.
        boolean all = true;
        for (int i = 0; i < n; i++) all &= bf.mightContain("user:" + i);
        System.out.println(all); // true

        System.out.printf("at capacity: measured %.2f%%, predicted %.2f%%%n", measured(bf, n), 100 * predictedFp(bf.m, bf.k, n));
        // at capacity: measured 1.00%, predicted 1.00%

        // Twice the design capacity: nothing breaks loudly, the filter just says "maybe" far more often.
        for (int i = n; i < 2 * n; i++) bf.add("user:" + i);
        System.out.printf("at 2x capacity: measured %.2f%%, predicted %.2f%%%n", measured(bf, n), 100 * predictedFp(bf.m, bf.k, 2 * n));
        // at 2x capacity: measured 15.79%, predicted 15.75%
    }
}

Common mistake

"More hash functions means fewer false positives"

Only up to the optimum, (m/n) ln 2. Past it, every extra hash sets more bits and the filter fills faster than the extra check helps. At 9.6 bits per item, k = 7 gives 1.0%, k = 14 gives 2.5%, and k = 1 gives 9.9%. Too few hashes is the more expensive mistake, but neither direction is free. Size m from n and p first, then derive k.

TradeoffA Bloom filter at 1% in front of an exact store

We gain

9.6 bits per item, no matter how large the items are. A “no” that is always right. k memory reads per lookup. And no network call for the 99% of strangers it rejects.

We give up

One stranger in 100 still pays for the exact lookup. Items cannot be listed, removed, or counted, and the filter cannot grow: past its design capacity the error climbs fast.

Step 3: Deletes, counting filters and cuckoo filters

A Bloom filter cannot delete. Clearing an item’s k bits also clears bits that other items share, and those items then test “definitely not present”. That is a false negative, the one error a Bloom filter promises never to make. The demo’s delete button shows it: in a half-full filter, deleting one item usually breaks several others.

Counting Bloom filter. Replace each bit with a small counter, usually 4 bits. Add increments k counters. Delete decrements them. A check asks whether all k are non-zero. It deletes correctly, at 4 times the memory. The catch: deleting an item that was never added decrements counters that belong to others. So it is only safe when you know the item is present.

Cuckoo filter (Fan, Andersen, Kaminsky and Mitzenmacher, 2014). Store a short fingerprint of each item, say 8 to 16 bits, in a hash table of buckets with 4 slots each. Each item has two candidate buckets: i1 = hash(x) and i2 = i1 XOR hash(fingerprint).

The XOR trick means the alternate bucket can be computed from the fingerprint alone. So when both buckets are full, inserting kicks an existing fingerprint to its other bucket. That may kick another, cuckoo style. Lookup reads two buckets. Delete removes one copy of the fingerprint.

Filter	Delete	Bits per item at 1%	Lookup cost	Watch out for
Bloom	No	9.6	k = 7 random bit reads	Cannot remove, cannot grow
Counting Bloom (4 bit)	Yes	38	k counter reads	4 times the memory, deleting absent items corrupts
Cuckoo (4 per slot)	Yes	About 9 to 11	2 bucket reads	Inserts fail near 95% full, at most 8 duplicates
Rebuild periodically	Yes, by not copying	9.6	Same as Bloom	Needs the source of truth and a rebuild job

Below a few percent, cuckoo filters are also smaller than Bloom filters. Each extra fingerprint bit halves the false-positive rate. A Bloom filter pays 1.44 bits for the same halving. Their hard failure is the insert. Near 95% occupancy, it can run out of its kick limit (500 moves in the reference code), and fail. An overfilled Bloom filter degrades. A full cuckoo filter refuses.

TradeoffA cuckoo filter where items come and go

We gain

Real deletes, two memory reads per lookup instead of seven, and less space than a Bloom filter at low error rates.

We give up

Inserts can fail when the table is nearly full, so capacity must be planned with margin. An item added more than 8 times fills both its buckets, and deleting something never inserted removes another item’s fingerprint.

Step 4: Counting how often, the Count-Min Sketch

The next question is “how many times?”: requests per client, views per video, searches per term. An exact map needs a counter per distinct key, and the long tail of keys seen once is most of it.

The Count-Min Sketch (Cormode and Muthukrishnan, 2005) is d rows of w counters, each row with its own hash. Adding an item increments one counter per row, in the column its row’s hash picks. Estimating an item reads those d counters and returns the minimum.

One item touches one counter per row, and the smallest wins

Scroll or pinch to zoom, drag to pan

• Color key
• Service

Every counter holds the item’s own count plus whatever else hashed there, so each is an overestimate, and the smallest is the tightest. The guarantee, with N the total of all counts:

• width w = ⌈e / ε⌉ keeps the overcount at most ε × N
• depth d = ⌈ln(1/δ)⌉ makes that hold with probability 1 − δ for each query
• The estimate is never below the true count, as long as counts only go up.

ε (error as a share of N)	δ	Width × depth	Memory, 4 byte counters	At N = 1 billion, overcount at most
1%	1%	272 × 5	5.4 KB	10 million
0.1%	1%	2,719 × 5	54 KB	1 million
0.001%	1%	271,829 × 5	5.4 MB	10,000

Read the last column carefully. The error is a share of the whole stream, not of the item. An overcount of 10,000 is 0.02% of an item with 50 million views. It’s 100,000% of an item with 10. A Count-Min Sketch is accurate for heavy items, and meaningless for light ones. That’s exactly what a top list or a hot-key detector needs, and exactly what billing does not.

Heavy hitters need a heap beside it. The sketch stores no item names, so it cannot list the top 100. So each update also offers the item’s new estimate to a min-heap of the top k candidates. An item already there is updated. A new one replaces the minimum, if its estimate is higher.

Conservative update (Estan and Varghese, 2002). When adding c to an item, compute the new estimate min + c. Raise each of its d counters only up to that value, never past it. Counters that were already higher, inflated by other items, are left alone. The estimate is still never below the truth. And overcounts on light items typically fall by half or more. The price: counters no longer hold plain sums, so the sketch cannot be subtracted. That breaks sliding windows built by subtracting the oldest minute.

JMain.javaPytop_k.pyC#CountMinSketch.csGotop_k.goTStop-k.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class Main {
    // The splitmix64 finalizer: spreads every input bit over all 64 output bits.
    static long mix64(long z) {
        z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L;
        z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL;
        return z ^ (z >>> 31);
    }

    // FNV-1a over the UTF-8 bytes, then mixed: short enough to match in every language.
    static long hash64(String s) {
        long h = 0xCBF29CE484222325L;
        for (byte b : s.getBytes(StandardCharsets.UTF_8)) {
            h = (h ^ (b & 0xFF)) * 0x100000001B3L;
        }
        return mix64(h);
    }

    static final class CountMinSketch {
        final int width, depth;
        final long[][] rows;
        final boolean conservative;
        long total; // N in the error bound: every count ever added

        CountMinSketch(double epsilon, double delta, boolean conservative) {
            // width = e / epsilon bounds the overcount at epsilon x (total of all counts);
            // depth = ln(1 / delta) rows make that bound hold with probability 1 - delta.
            width = (int) Math.ceil(Math.E / epsilon);
            depth = (int) Math.ceil(Math.log(1 / delta));
            rows = new long[depth][width];
            this.conservative = conservative;
        }

        // One column per row. Each row needs its own hash, so remix the item's hash with a
        // different constant per row instead of hashing the string d times.
        int[] columns(String item) {
            long h = hash64(item);
            int[] cols = new int[depth];
            for (int r = 0; r < depth; r++) {
                cols[r] = (int) Long.remainderUnsigned(mix64(h + (r + 1) * 0x9E3779B97F4A7C15L), width);
            }
            return cols;
        }

        long minOf(int[] cols) {
            long m = Long.MAX_VALUE;
            for (int r = 0; r < depth; r++) m = Math.min(m, rows[r][cols[r]]);
            return m;
        }

        long add(String item, long count) {
            int[] cols = columns(item);
            total += count;
            if (conservative) {
                // Conservative update: raise each counter only as far as the new estimate needs.
                // Overcounts shrink a lot, but the sketch can no longer be subtracted.
                long est = minOf(cols) + count;
                for (int r = 0; r < depth; r++) rows[r][cols[r]] = Math.max(rows[r][cols[r]], est);
                return est;
            }
            for (int r = 0; r < depth; r++) rows[r][cols[r]] += count;
            return minOf(cols);
        }

        // Every counter holds the item's count plus whatever collided with it, so the smallest
        // is the best guess. Never below the true count, often above it.
        long estimate(String item) {
            return minOf(columns(item));
        }
    }

    // The sketch answers "how many for this item?" but cannot list items. A small candidate set
    // beside it remembers which items looked heaviest when they arrived. Production code keeps
    // a min-heap; for k = 10 a scan for the smallest is just as fast and easier to read.
    static final class TopK {
        final int k;
        final CountMinSketch sketch;
        final Map<String, Long> top = new HashMap<>();

        TopK(int k, CountMinSketch sketch) {
            this.k = k;
            this.sketch = sketch;
        }

        void add(String item, long count) {
            long est = sketch.add(item, count);
            if (top.containsKey(item) || top.size() < k) {
                top.put(item, est);
                return;
            }
            String smallest = null;
            for (var e : top.entrySet()) if (smallest == null || e.getValue() < top.get(smallest)) smallest = e.getKey();
            if (est > top.get(smallest)) {
                top.remove(smallest);
                top.put(item, est);
            }
        }

        List<Map.Entry<String, Long>> items() {
            var out = new ArrayList<>(top.entrySet());
            out.sort((a, b) -> Long.compare(b.getValue(), a.getValue()));
            return out;
        }
    }

    public static void main(String[] args) {
        // A skewed stream: item:i appears 10,000 / i times, 2,000 distinct items, interleaved in
        // 10 rounds so heavy and light items arrive mixed together.
        Map<String, Long> truth = new LinkedHashMap<>();
        for (int i = 1; i <= 2000; i++) truth.put("item:" + i, (long) (10_000 / i));
        CountMinSketch plain = new CountMinSketch(0.005, 0.01, false); // 544 x 5 counters
        CountMinSketch careful = new CountMinSketch(0.005, 0.01, true);
        TopK top = new TopK(10, plain);
        for (int rnd = 0; rnd < 10; rnd++) {
            for (var e : truth.entrySet()) {
                long c = e.getValue();
                long part = c / 10 + (rnd < c % 10 ? 1 : 0);
                if (part > 0) {
                    top.add(e.getKey(), part);
                    careful.add(e.getKey(), part);
                }
            }
        }

        long n = plain.total;
        System.out.printf("N = %d, bound = %.0f%n", n, 0.005 * n); // N = 80835, bound = 404
        for (var e : top.items().subList(0, 3)) {
            System.out.println(e.getKey() + " " + e.getValue() + " " + truth.get(e.getKey())); // item:1 10025 10000, item:2 5015 5000, item:3 3344 3333
        }
        System.out.printf("tail overcount: plain %.0f, conservative %.0f%n", avgOver(plain, truth), avgOver(careful, truth));
        // tail overcount: plain 18, conservative 9, on true counts of 5 to 9. Light items suffer most.
    }

    static double avgOver(CountMinSketch s, Map<String, Long> truth) {
        long sum = 0;
        for (int i = 1001; i <= 2000; i++) sum += s.estimate("item:" + i) - truth.get("item:" + i); // true counts 5 to 9
        return sum / 1000.0;
    }
}

Step 5: Counting how many distinct, HyperLogLog

“How many distinct users visited today?” needs every ID seen, because a counter double counts repeat visits. 200 million 16 byte IDs is 3.2 GB, per day and per slice.

The trick behind HyperLogLog (Flajolet, Fusy, Gandouet and Meunier, 2007) starts with a coin flip. Hash each item to a uniformly random 64 bit number. Half of all hashes start with a 1, a quarter with 01, and an eighth with 001. A hash that starts with 20 zeros turns up about once in 2²⁰ distinct items. So the longest run of leading zeros you have seen says roughly how many distinct items you have seen. Seeing the same item again changes nothing, because it has the same hash.

One such maximum is a terrible estimate: a single lucky hash ruins it. So HyperLogLog splits the stream into m buckets and averages:

1. Hash the item to 64 bits.
2. The first p bits pick one of m = 2^p registers.
3. In the remaining bits, find the position of the first 1 (leading zeros + 1). That is the item’s rank.
4. Store max(register, rank). Registers only ever grow.
5. To estimate, take the harmonic mean of 2^register across registers, times m, times a bias constant of about 0.72. The harmonic mean keeps one register with a freak rank from dragging the estimate up.
6. While many registers are still empty (estimate below 2.5m), it switches to linear counting: m × ln(m / empty registers). That’s far more accurate for small counts. HyperLogLog++ (Google, 2013) adds an empirical bias table for the middle range, where the raw estimate runs high. It also uses a 64 bit hash, which removes the paper’s large-range correction.

The standard error is 1.04 / √m. Each register needs only 6 bits, because a rank can never exceed 64 − p + 1, which is under 64. Quadrupling the registers halves the error:

p	Registers	Standard error	Memory at 6 bits	Used by
10	1,024	3.25%	768 bytes	Coarse counts for millions of long-tail keys
12	4,096	1.63%	3 KB	Tighter than Presto’s approx_distinct default, 2.3%
14	16,384	0.81%	12 KB	Redis PFADD and PFCOUNT
16	65,536	0.41%	48 KB	When a sketch per key is affordable and 0.8% is not

The memory does not grow with the count. A 12 KB HyperLogLog counts 1,000 or 10 billion distinct items, with at most the same relative error. Redis goes further. Small sketches use a sparse encoding that starts at a few bytes. It switches to the dense 12 KB form only past about 3 KB. So a million keys holding small counts do not cost 12 GB.

The second half of the demo above streams visitors into a HyperLogLog. Switch the register count, and watch the error band shrink by half for every four times the registers. Then click “1,000 revisits”, and see that the estimate does not move.

JMain.javaPyhyper_log_log.pyC#HyperLogLog.csGohyper_log_log.goTShyper-log-log.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.nio.charset.StandardCharsets;

public class Main {
    // The splitmix64 finalizer: spreads every input bit over all 64 output bits.
    static long mix64(long z) {
        z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L;
        z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL;
        return z ^ (z >>> 31);
    }

    // FNV-1a over the UTF-8 bytes, then mixed: short enough to match in every language.
    static long hash64(String s) {
        long h = 0xCBF29CE484222325L;
        for (byte b : s.getBytes(StandardCharsets.UTF_8)) {
            h = (h ^ (b & 0xFF)) * 0x100000001B3L;
        }
        return mix64(h);
    }

    static final class HyperLogLog {
        final int p, m;
        final byte[] registers; // 6 bits each would do; Redis packs them into 12 KB

        // 2^p registers. p = 14 is Redis's choice: 16,384 registers, 0.81% standard error.
        HyperLogLog(int p) {
            this.p = p;
            this.m = 1 << p;
            this.registers = new byte[m];
        }

        void add(String item) {
            long h = hash64(item);
            int idx = (int) (h >>> (64 - p)); // the first p bits pick a register
            long rest = h << p; // the other 64 - p bits, shifted to the top
            // Rank = position of the first 1 bit. A rank of r turns up about once in 2^r items, so
            // the largest rank a register has seen says roughly how many distinct items reached it.
            int rank = Math.min(Long.numberOfLeadingZeros(rest), 64 - p) + 1;
            // Max, not add: seeing the same item again changes nothing. That is what makes it distinct.
            if (rank > registers[idx]) registers[idx] = (byte) rank;
        }

        long count() {
            double alpha = 0.7213 / (1 + 1.079 / m); // bias correction from the HyperLogLog paper
            // Harmonic mean of 2^rank across registers: one unlucky register with a huge rank
            // cannot drag the estimate up the way it would with an ordinary mean.
            double sum = 0;
            int zeros = 0;
            for (byte r : registers) {
                sum += Math.pow(2, -r);
                if (r == 0) zeros++;
            }
            double est = alpha * m * m / sum;
            if (est <= 2.5 * m && zeros > 0) {
                // Small counts: many registers are still empty, and linear counting on the empty
                // ones is far more accurate than the raw estimate.
                est = m * Math.log((double) m / zeros);
            }
            return Math.round(est);
        }

        // Union is register-wise max, exact and lossless: merged sketches equal one sketch of
        // both streams. Only sketches with the same p and the same hash can be merged.
        void merge(HyperLogLog other) {
            if (other.p != p) throw new IllegalArgumentException("cannot merge sketches with different precision");
            for (int i = 0; i < m; i++) registers[i] = (byte) Math.max(registers[i], other.registers[i]);
        }
    }

    public static void main(String[] args) {
        // Two shards see overlapping visitors: users 0 to 149,999 and 100,000 to 249,999.
        HyperLogLog a = new HyperLogLog(14), b = new HyperLogLog(14);
        for (int i = 0; i < 150_000; i++) a.add("user:" + i);
        for (int i = 100_000; i < 250_000; i++) b.add("user:" + i);
        for (int i = 0; i < 100_000; i++) a.add("user:" + i); // repeat visits do not move the count
        System.out.println(a.count() + " " + b.count()); // 151285 151915, true 150,000 each
        System.out.println(a.count() + b.count()); // 303200: adding counts double counts the 50,000 in both
        a.merge(b);
        System.out.println(a.count()); // 252911, true 250,000: 1.2% high, about 1.4 standard errors, from 16 KB of registers
    }
}

TradeoffHyperLogLog for distinct counts

We gain

12 KB for 0.81% at any cardinality, repeats ignored by construction, and exact, lossless union across shards, regions and days.

We give up

The error is statistical: about 1 count in 20 is off by more than 1.6%. It cannot list who visited, cannot remove a visitor, and estimates intersections badly.

Step 6: Merge, the property that makes them distributed

Each structure has a merge operation that gives exactly the structure you would have built from the combined input:

Structure	Merge	So you can	But not
Bloom	Bitwise OR	Union filters built by different workers	Intersect reliably: AND gives extra positives
Count-Min	Add counters cell by cell	Sum per-minute sketches into an hour, regions into a global count	Subtract once conservative update is on
HyperLogLog	Register-wise max	Union shards, then days into a week (PFMERGE)	Subtract a day, or intersect without large error

The merge only works when both sides were built identically:

• Same m and k, for a Bloom filter.
• Same width, depth and per-row hashes, for Count-Min.
• Same precision, hash function and seed, for HyperLogLog.

Store those parameters with every serialized sketch, and refuse to merge mismatches.

Unique visitors: per shard, then per day, then per week

Scroll or pinch to zoom, drag to pan

• Color key
• Database
• Service

Daily counts cannot be added, because a Monday and Tuesday visitor is in both. Seven daily sketches merged by max give the weekly count with the same 0.81% error.

Options and tradeoffs

Which question are you asking

Picking a structure from the question

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database

Membership filters

Filter	Bits per item at 1%	Delete	Lookup	Wins when
Bloom	9.6	No	7 scattered bits	Append-only sets, the default
Blocked Bloom (one cache line)	About 10 to 11	No	One 64 byte line	Hot lookups where cache misses dominate, such as LSM reads
Cuckoo	About 9 to 11	Yes	2 buckets	Items expire or are removed, rates below a few percent
Static xor or ribbon filters	About 8	No	3 reads (xor), a few (ribbon)	The set is built once and never changes, such as an SSTable

TradeoffPlain Bloom as the default membership filter

We gain

Simplest to build and reason about, supported everywhere (Guava, RedisBloom, every LSM engine), merges by OR, and never fails an insert.

We give up

No deletes, and seven scattered memory reads. About 44% more space than the theoretical floor of log₂(1/p) bits per item. Cuckoo, xor and ribbon filters get closer to that floor.

Frequency and heavy hitters

Approach	Memory	Error	Can subtract	Wins when
Exact hash map	One counter per distinct key	None	Yes	Distinct keys fit: tens of millions on one box
Count-Min + heap	w × d counters + k names	Over by ≤ εN, with probability 1 − δ	Yes	Sliding windows and cross-region merges
Count-Min, conservative update	Same	Same bound, typically half or less in practice	No	One long window, accuracy on light items
Space-Saving (Metwally, 2005)	k counters with names	Over by ≤ N/k, deterministic	No	Only the top list is needed, from one stream

Space-Saving’s summaries merge only approximately, which is why the top-k problem picks Count-Min for windows that slide and regions that merge.

TradeoffCount-Min plus a heap for live top lists

We gain

Linear: per-minute sketches sum into any window and subtract out of it exactly, and regional sketches add into a global one.

We give up

Two structures to keep consistent. An error relative to total traffic, so light items are wrong by orders of magnitude. And a heap that only knows items that looked heavy when they arrived.

Distinct counts

Approach	Memory for 100 million distinct	Error	Merge	Wins when
Exact set of IDs	1.6 GB raw, more in a hash set	None	Union of sets	Counts are small, or the result is billed
Bitmap of dense integer IDs (Roaring)	12.5 MB per 100 million of range	None	Bitwise OR	IDs are integers in a known range
HyperLogLog (p = 14)	12 KB	0.81% standard error	Register max	Large cardinalities, many keys, unions
Theta sketch (Apache DataSketches)	Tens of KB	Similar, configurable	Union, intersect, difference	You need “visited A and not B”

TradeoffHyperLogLog per key and per day

We gain

Uniques for any union of days or shards from stored sketches, with no raw IDs kept, which also helps with data minimization.

We give up

No exact answers, no “who”, and no subtraction for rolling windows. Intersections only by inclusion-exclusion, whose error is relative to the union and swamps small overlaps.

When exact is required

Situation	Why a sketch is wrong here	Use instead
Billing, payouts, quotas that cost money	Overcounts are charges the customer did not incur; ±1.6% is a dispute	Exact counts from an idempotent event log
Access control (“is this token revoked?”)	A false positive locks out a valid user; a stale filter misses a revocation	The filter as a pre-check, exact lookup on “maybe”
Uniqueness that must hold (usernames)	“Maybe taken” is fine, but “not taken” must be confirmed by a unique constraint	Bloom to skip the DB for free names, unique index to enforce
Small sets	1 million 8 byte IDs is 8 MB; a sketch saves nothing worth an error	A hash set
You need the items, not a count	Sketches cannot enumerate	A set, a log, or a sample

TradeoffExact counts for money, sketches for everything else

We gain

Billing and enforcement can be audited and reproduced. Dashboards, ranking and pre-checks stay cheap.

We give up

Two pipelines for the same events, which must be reconciled, and the exact one carries the storage cost the sketch was avoiding.

Go deeperMore filters and sketches: blocked, Space-Saving, quantiles, similarity3 min

Blocked Bloom filters. Hash each item to one 512 bit block (a 64 byte cache line) first. Then set all k bits inside it. So a lookup is one cache miss, instead of seven. The false-positive rate rises a little, because blocks fill unevenly. That’s repaid many times over in CPU. RocksDB’s newer filter formats use this layout. RocksDB also offers a ribbon filter. It’s about 30% smaller for the same rate, at a higher construction cost. That’s a good fit for SSTables, which are written once.

Space-Saving (Metwally, Agrawal and El Abbadi, 2005) keeps exactly k (item, count) pairs. An untracked item replaces the pair with the smallest count, and inherits that count plus one. So every count is an overestimate by at most N/k. And any item with more than N/k occurrences is guaranteed to be in the list.

Exact below a threshold. Elasticsearch’s cardinality aggregation is close to exact below a precision_threshold (3,000 by default) and switches to HyperLogLog++ above it. Redis’s sparse encoding gets much of the same benefit for small counts.

The same idea covers two more questions, and both appear in problem pages on this site.

Quantiles. “What is the p99 latency?” over billions of samples. There are three approaches:

• A t-digest keeps clusters of samples: small near the tails, and large in the middle. So p99 and p99.9 are accurate in a few KB.
• KLL keeps a hierarchy of sampled buffers. Its error is a uniform share of the rank. That’s fine for a median, and coarse for the extreme tail.
• Prometheus native histograms and HDR histograms use fixed exponential buckets, with a known relative error.

All of them merge. That’s why per-host latency summaries can be combined into a fleet p99, while averages of per-host p99s cannot.

Similarity. MinHash keeps the minimum hash of a document’s shingles, under each of a few hundred hash functions. The fraction of matching minimums estimates the Jaccard similarity of two documents. Simhash folds a document’s features into one 64 bit fingerprint, where near duplicates differ in few bits. The web crawler uses simhash for near duplicate pages.

How it fails

Failure	What you see	Blast radius	Fix
Filter past its design capacity	False positives climb from 1% to 16% at twice the items, 44% at three times	Every lookup’s fallback path: disk, DB, network	Alarm on fill ratio; rebuild larger from the source; scalable filters
Sketches with different configs merged	Merge errors, or worse, silently wrong counts	Every report built on the merge	Store m, k, p, width, depth and hash seed with every sketch; refuse mismatches
Weak or inconsistent hash	Measured error above predicted; false negatives across processes	Every lookup	One fixed 64 bit hash (Murmur3, xxHash) in every language; test vectors
Naive delete from a Bloom filter	Items that are present test “definitely not”	Correctness: the one guarantee breaks	Never clear bits; counting or cuckoo filter, or rebuild
Error read as a guarantee in billing	Customers billed for traffic they did not send	Money and trust	Exact counts for anything invoiced
Cuckoo filter near full	Inserts fail	New items not recorded	Size for 80 to 90% load; rebuild larger on failure

Overfilling is the common one, and it is silent. Nothing throws when a filter sized for 100 million gets 200 million items. The math just keeps going:

Items vs design capacity	Bits set	False-positive rate (sized for 1%, k = 7)
1×	52%	1.0%
1.25×	60%	2.8%
1.5×	67%	5.8%
2×	77%	15.8%
3×	89%	44%

If the filter guards a disk read, that is 16 times the wasted reads, with no error in any log.

Detect it by the fraction of bits set. A correctly sized filter at capacity sits near 50%. And n ≈ −(m/k) × ln(1 − bits set / m) recovers how many items it really holds. Fix it by rebuilding larger, from the source of truth. Or plan for growth with a scalable Bloom filter. When one fills, add another with twice the capacity and a tighter error, and check all of them. RedisBloom’s BF.RESERVE does this by default (EXPANSION 2). Each layer adds a lookup.

Inconsistent hashing turns false positives into false negatives. Python’s hash() of a string and .NET’s string.GetHashCode() are randomized per process. So a filter built by one worker, and checked by another, reports “definitely not” for items it holds. A library upgrade that changes the hash or seed makes every stored sketch unmergeable with new ones. Pin one 64 bit hash, and version the format. Ship test vectors (keys, and the bits each must set) that every client checks.

Where attackers choose the items and know the hash, they can craft items that collide with a target’s bits or cells. Use a keyed hash such as SipHash with a secret seed for hostile input.

Common mistake

"The sketch is approximate, so it is fine for billing as long as the error is small"

The error is small on average, and it has a direction. Take a Count-Min Sketch with ε = 0.001 over 10 billion monthly API calls. It can overcount a customer who made 1,000 calls by up to 10 million. A HyperLogLog at 0.81% standard error misses by more than 1.6% in about 1 month in 20. On a 10 million device customer, that’s 160,000 devices. Neither is a rounding error on an invoice. Bill from exact counts. Use sketches to rank, alert and display.

At scale

Operation	Cost, roughly
Bloom check, in RAM	7 cache misses scattered over GBs, 100 to 500 ns; blocked: one miss
Bloom check vs the SSD read it saves	0.1 to 0.5 µs against 50 to 100 µs
Count-Min update, d = 5	One hash, 5 counter increments, tens to a hundred ns
HyperLogLog add	One hash, one register max, tens of ns
PFCOUNT over 7 keys	A 16,384 register merge, microseconds
Sizes	1.2 GB per billion items at 1%; 12 KB per HLL; 5.4 MB per CMS at ε = 10⁻⁵

At 10 times the items, a Bloom filter grows 10 times. It is linear in n, with a much smaller constant than a set. Past tens of GB, shard it like the data: one filter per partition, routed by the same key hash, and rebuildable from that partition’s records. HyperLogLog does not grow with the count. But the number of keys does (pages × days × countries). So sparse encodings, and lower precision for long-tail keys, matter. Count-Min’s absolute error grows with N. Widen it, or keep a sketch per window so each N stays small.

At 100 times, the merge path becomes the design. Sketches move between machines every minute. So their parameters become a schema. A change of width, precision or seed is a migration with a cutover date, because old and new sketches cannot be merged. Rebuilding filters becomes scheduled work too. Rebuilding a 12 GB filter means reading every key in the source.

What to monitor:

• Bloom filters: items against design capacity, and fraction of bits set (alarm near 55 to 60%).
• Measured false-positive rate: the share of “maybe” answers the exact lookup then rejected (RocksDB: bloom.filter.full.positive against bloom.filter.full.true.positive). Above the design rate means overfull or a broken hash.
• Sketch error against ground truth: exact counts for a small sample of keys, compared daily. HyperLogLog should land within 2 standard errors about 95% of the time. Count-Min should never be below.
• Count-Min’s N per window, with εN next to the smallest count you report.
• Cuckoo filter load factor and insert failures, and sketch format versions in flight.

In the interview

Interviewer asksSize a Bloom filter for 1 billion keys at 1% false positives. How many hash functions?

The formula is m = −n ln p / (ln 2)². That’s about 9.6 bits per key at 1%, so 9.6 billion bits, or 1.2 GB. The best k is (m/n) ln 2, about 7. At 0.1%, it’s 14.4 bits per key, 1.8 GB and 10 hashes. Every 10 times fewer false positives costs 4.8 bits per key. The seven positions come from one 64 bit hash, split in two halves: h1 + i·h2. At capacity, about half the bits are set. I would alarm on the fill ratio, because at twice the keys, the rate is about 16%.

Interviewer asksUsers can delete their accounts. How does a Bloom filter of taken usernames handle that?

It cannot remove a name. Clearing its bits clears bits that other names share. Then they would test “definitely not taken”, which is a false negative. Usually that does not matter. Say the filter only lets signup skip the database for names that are certainly free. Then a deleted name staying “maybe taken” costs one lookup, and the unique index decides. I would rebuild the filter from the users table on a schedule, to shed stale entries. If deletions are frequent and stale entries are expensive, a cuckoo filter supports real deletes in about the same space. The cost is inserts that can fail near 95% full. A counting Bloom filter also works, at 4 times the memory.

Interviewer asksShow unique visitors per page per day, and per week.

One HyperLogLog per page per day, with PFADD on each view. That’s at most 12 KB per key, at 0.81% standard error, and far less for small pages, thanks to the sparse encoding. Daily numbers cannot be added, since repeat visitors would count twice. But PFCOUNT over the seven daily keys merges them by register max, and gives the week with the same error. A rolling 30 days is a merge of the last 30 daily sketches, recomputed daily, because a sketch cannot subtract a day. If advertisers are billed on it, the official figure is computed exactly, in batch.

Common mistake

"HyperLogLog is accurate to 0.81%"

0.81% is one standard error, not a maximum. About 1 count in 3 is further off than that, and about 1 in 20 is off by more than 1.6%. Likewise a Count-Min Sketch’s ε is a share of all traffic, not of the item.

Mid-level covers

Knows a Bloom filter has false positives and no false negatives. Uses HyperLogLog for unique counts, and Count-Min for frequencies. Puts the filter in front of an exact store.

Senior adds

Sizes from n and p (9.6 bits and k = 7 at 1%). Knows the fill-ratio failure, and how to detect it. Picks cuckoo, or rebuilds, when deletes matter. States Count-Min’s error as εN, and HLL’s as a standard error. Merges sketches across shards and windows, while keeping configurations identical. Refuses sketches for billing.

Seen in

• Design a web crawler: a 12 GB Bloom filter at 1% for 10 billion URLs, in front of 8 byte fingerprints on SSD. A Bloom-only false positive would mean a URL is never crawled.
• Design a key-value store: one Bloom filter per SSTable at 10 bits a key. That’s 1.1 GB per node for 860 million keys, so most reads touch one file.
• Design top-k heavy hitters: Count-Min sketches per minute with a candidate heap, windows that slide by subtraction, and regional sketches merged cell by cell.
• Design a URL shortener: a HyperLogLog per short code per day for unique visitors, merged into weekly counts.
• Design search autocomplete: daily aggregates store distinct users per query as HyperLogLog, which feeds the score and the 50 distinct users privacy threshold.
• Design an ad click aggregator: unique users per ad from mergeable HyperLogLogs, and a live top 100 ads from Count-Min with a heap.
• Design a distributed cache: W-TinyLFU, one of the eviction policies it compares, admits keys by a frequency sketch of a few bits per key.
• Design a leaderboard: the counterexample, where a uniform error quantile sketch would be wrong for rank estimates and exact bucket counts are used instead.

Outside these problems, the best known use is at the CDN edge. Akamai’s Maggs and Sitaraman (2015) reported that about 74% of the objects in a sample of its edge traffic were requested only once. Akamai uses a Bloom filter to cache an object only on its second request, so those one-hit wonders never reach disk.

A CDN edge that caches only on the second request

Scroll or pinch to zoom, drag to pan

• Color key
• Service

A false positive here only means caching a one-hit wonder. That’s what happened before the filter existed, so a high error rate is cheap. That is the pattern to look for in every use above. Put the sketch where its error costs little, and back it with something exact where it costs a lot.

Go deeperMore systems that ship these structures1 min

Bigtable, HBase, Cassandra and RocksDB keep a Bloom filter per SSTable. (Cassandra exposes the rate per table as bloom_filter_fp_chance.) Redis has HyperLogLog built in (PFADD, PFCOUNT, PFMERGE). Its Bloom, cuckoo, Count-Min, top-k and t-digest types (BF.*, CF.*, CMS.*, TOPK.*, TDIGEST.*) came with Redis Stack. They’re part of Redis Open Source from Redis 8. BigQuery, Presto and Druid offer approximate distinct counts built on HyperLogLog. And Caffeine, the standard Java cache, uses a frequency sketch for admission.

Recap

The idea. Answer one narrow question in fixed memory, with an error of known bound and often known direction.

Bloom filter. m bits, k hashes. “No” is certain, “maybe” is wrong with probability (1 − e^(−kn/m))^k. 9.6 bits per item and k = 7 for 1%, plus 4.8 bits for each 10 times fewer false positives. Half the bits are set at capacity. k positions from two hashes. No deletes.

Deletes. Counting Bloom filters: 4 bit counters, at 4 times the memory. Or cuckoo filters: fingerprints in two candidate buckets, with real deletes, but inserts can fail near 95% full.

Count-Min Sketch. d rows of w counters, take the minimum. Never under, over by at most εN with probability 1 − δ, where N is the whole stream. Add a heap to list heavy hitters. Conservative update tightens it but cannot subtract.

HyperLogLog. Registers keep the longest leading-zero run of the hashes routed to them. It uses a harmonic mean, and linear counting for small counts. Error is 1.04/√m: 12 KB and 0.81% in Redis. It merges by max across shards and days. It cannot subtract or list.

Failures. Overfilled filters (16% at twice capacity, so watch the fill ratio). Configs or hashes that differ between writers. Naive deletes. And errors treated as guarantees in billing.

Further reading

• Caching for Bloom filters against cache penetration and TinyLFU’s frequency sketch, and indexing for the Bloom filter on every SSTable in an LSM tree. The top-k and web crawler problems take Count-Min and Bloom filters through a full design.
• An improved data stream summary: the count-min sketch and its applications, Cormode and Muthukrishnan: the sketch, its error bound and its proofs.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm, Flajolet, Fusy, Gandouet and Meunier, 2007. It covers registers, the harmonic mean, the 1.04/√m error, and the small and large range corrections.
• Cuckoo Filter: Practically Better Than Bloom, Fan, Andersen, Kaminsky and Mitzenmacher, CoNEXT 2014. It covers partial-key cuckoo hashing, deletes, and space against Bloom filters by target error rate.