10.18 — Probabilistic Structures at Scale

A web crawler has visited ten billion URLs and must answer one question before every fetch: have I seen this one already?

Store them exactly and you need a set of ten billion strings. At around fifty bytes each that is 500 GB of memory, which means a cluster of machines existing purely to remember what you have already done.

Or you accept being wrong about one URL in a hundred — and skip a page you have not actually crawled — and the same question is answered from 12 GB. Forty times less memory for an error you cannot even measure in the output.

That trade is what this page is about. Every structure here gives up exactness and buys an enormous amount of space, and the skill is knowing which questions tolerate a wrong answer and which do not.

1. Bloom filter: is this thing in the set?

A Bloom filter answers set membership with a specific and very useful asymmetry:

• "Definitely not present" — always correct.
• "Probably present" — correct most of the time, wrong at a rate you choose.

There are no false negatives. If the filter says something is absent, it is absent. That asymmetry is what makes it useful, because you can use it as a guard: anything the filter rejects can be discarded with confidence, and anything it accepts gets checked properly.

How it works

An array of bits, all zero, and k different hash functions.

To add an item, hash it k ways, and set those k bits to one.

To test an item, hash it the same k ways and look at those bits. If any of them is zero, the item was definitely never added — adding it would have set that bit. If all of them are one, it was probably added, or the bits were set by other items that happened to overlap.

Figure 1 — Why there are no false negatives. Adding an item only ever turns bits on, so a bit that is still zero proves nothing set it. A positive can be an accident of overlap; a negative cannot.

class BloomFilter {
  #bits: Uint8Array;
  constructor(private readonly bitCount: number, private readonly hashCount: number) {
    this.#bits = new Uint8Array(Math.ceil(bitCount / 8));         // (1)
  }

  add(item: string): void {
    for (const bit of this.#positions(item)) {
      this.#bits[bit >> 3] |= 1 << (bit & 7);                     // (2) turn the bit on
    }
  }

  mightContain(item: string): boolean {
    for (const bit of this.#positions(item)) {
      if ((this.#bits[bit >> 3] & (1 << (bit & 7))) === 0) {
        return false;                                              // (3) definitely absent
      }
    }
    return true;                                                   // (4) probably present
  }

  *#positions(item: string): Generator<number> {
    const h1 = hash1(item), h2 = hash2(item);
    for (let i = 0; i < this.hashCount; i++) {
      yield Math.abs((h1 + i * h2) % this.bitCount);               // (5) k hashes from two
    }
  }
}

(1) Eight bits per byte, so a million-bit filter is 125 KB. (2) bit >> 3 finds the byte and bit & 7 the position inside it. (3) One zero bit is a definitive no — this is the line that makes the whole structure useful. (4) All ones means probably, never certainly. (5) Two real hash functions combined arithmetically give you as many as you need, which is cheaper than computing seven separate hashes and provably just as good.

Sizing it

Two numbers you choose, and the rest follows.

Given n items to store and a target false positive rate p, the number of bits you need is m = -n × ln(p) / (ln 2)², and the number of hash functions is k = (m/n) × ln 2.

The useful way to hold this is bits per item:

False positive rate	Bits per item	Hashes
10%	4.8	3
1%	9.6	7
0.1%	14.4	10
0.01%	19.2	13

Two things to notice, and they are the reason Bloom filters are so widely used.

The cost does not depend on how big the items are. Ten bits per item whether the item is a 6-character username or a 2,000-character URL. This is where the forty-fold saving in the opening comes from — you are storing ten bits instead of fifty bytes.

Tightening the error is cheap. Going from 1% to 0.1% costs five more bits per item, not ten times the memory. Each extra factor of ten in accuracy costs roughly the same fixed increment, so if you are unsure, over-provision — it is nearly free.

Our crawler: ten billion URLs at 1 percent is 9.6 × 10^10 bits, which is 12 GB. Against 500 GB for the exact set.

The two limitations

You cannot delete. Clearing an item's bits would clear bits that other items also rely on, producing false negatives — which destroys the one guarantee the structure has. Once added, always present.

It fills up. A filter sized for ten million items and given a hundred million has almost every bit set, so it answers "probably present" to everything and stops being useful. It fails silently, which is the dangerous part: nothing errors, the answer is just always yes. Monitor the fill ratio, and when a filter is near capacity, build a new one and switch over.

2. Counting Bloom filter, when you need to delete

Replace each bit with a small counter, usually four bits. Adding increments the counters; deleting decrements them. Now deletion works.

The cost is four times the memory, and a new failure: a counter that saturates at its maximum can never be decremented back correctly, so a heavily repeated item can leave permanent residue.

A cuckoo filter is the modern alternative — it also supports deletion, uses less space than a counting Bloom filter at low error rates, and is more complicated to implement. If an interviewer asks how to delete from a Bloom filter, the complete answer is "you cannot, so use a counting variant or a cuckoo filter, and here is what each costs".

3. Count-Min Sketch: how many times have I seen this?

A Bloom filter answers whether. A Count-Min Sketch answers how many times, approximately, in a fixed amount of memory no matter how many distinct keys there are.

The structure is a small two-dimensional array — say four rows by two thousand columns — with one hash function per row.

To record an event, hash the key once per row and increment the counter at that row's column.

To ask for a count, hash the same way and take the minimum of the values you find.

The minimum is the clever part. Each cell may have been incremented by other keys that collided, so every cell is an over-estimate of the true count. Taking the smallest of four independent over-estimates gives you the tightest bound available — so the sketch never under-counts and over-counts by a bounded amount.

class CountMinSketch {
  #rows: Uint32Array[];
  constructor(private readonly depth = 4, private readonly width = 2048) {
    this.#rows = Array.from({ length: depth }, () => new Uint32Array(width));
  }

  record(key: string, by = 1): void {
    for (let r = 0; r < this.depth; r++) {
      this.#rows[r][hashAt(key, r) % this.width] += by;            // (1) one cell per row
    }
  }

  estimate(key: string): number {
    let min = Infinity;
    for (let r = 0; r < this.depth; r++) {
      min = Math.min(min, this.#rows[r][hashAt(key, r) % this.width]);   // (2) smallest wins
    }
    return min;
  }
}

(1) Every row records the event, at a different column. (2) Collisions only ever inflate a cell, so the minimum is the closest to the truth. Four rows of two thousand 32-bit counters is 32 KB — for any number of distinct keys, which is the property that matters.

Where this is exactly the right tool.

Finding hot keys. 10.14.2 needed to know which cache key is receiving disproportionate traffic without counting every key. A sketch gives you that in kilobytes.

Deciding what a cache should admit. The modern eviction policies from 10.14.1 use a sketch to ask "has this new arrival been requested more often than the item LRU wants to evict?" — so a one-time scan never displaces the hot set.

Approximate rate limiting where an occasional over-count is acceptable and per-key exact counters would not fit.

Where it is the wrong tool: anything where over-counting has a cost. Billing, quota enforcement that must not falsely reject, or any number a customer will read. The error is one-directional and the direction is against the user.

4. HyperLogLog: how many distinct things have I seen?

Counting unique visitors exactly means remembering every visitor id you have seen. A hundred million uniques is gigabytes.

HyperLogLog estimates the count of distinct items in about 12 KB, with roughly 0.8 percent error, for cardinalities up to billions. The compression is so extreme it sounds impossible, so the intuition is worth having.

The intuition. Hash each item to a random-looking bit pattern. In truly random data, about half of all values start with a zero bit, a quarter start with two zeros, an eighth with three, and so on. So if the longest run of leading zeros you have ever seen is 10, you have probably seen around 2^10 distinct values — because seeing that pattern at all requires roughly that many attempts.

That single estimate is extremely noisy, so HyperLogLog splits the hash space into thousands of buckets, tracks the longest run in each, and averages them in a way that suppresses outliers. With 16,384 buckets of six bits each — 12 KB — the error settles around 0.8 percent.

The property that makes it genuinely important is that sketches merge. The union of two HyperLogLogs is computed by taking the maximum in each bucket, and the result is exactly the sketch you would have got by feeding both streams into one.

That means you can keep an hourly sketch per server, and afterwards answer "unique visitors this week across the whole fleet" by merging 168 sketches — without storing a single visitor id. Exact distinct counting cannot do this at all: unique-per-day counts cannot be added together to give unique-per-week, because you would double-count the people who came on two days. Mergeability turns a fundamentally non-additive metric into an additive one, and that is why every analytics system uses it.

5. Choosing

Question	Structure	Memory	Error direction
Is this in the set?	Bloom filter	~10 bits per item	Says yes when it means no
Is this in the set, with deletes?	Counting Bloom or cuckoo	4× a Bloom filter	Same
How many times seen?	Count-Min Sketch	Fixed, ~32 KB	Never under, sometimes over
How many distinct?	HyperLogLog	~12 KB	±0.8% either way
What are the top K?	Sketch + a small heap	Fixed	Misses near-ties

The question to ask before using any of them: what happens when the answer is wrong? If a wrong answer costs a wasted lookup, a slightly-off dashboard, or a skipped page out of ten billion, use them and enjoy the space. If a wrong answer means a customer is billed incorrectly, denied access, or shown someone else's data, do not.

6. Where these already run

Databases skip disk reads with Bloom filters. Storage engines that write data in immutable sorted files keep a small filter per file, so a lookup for a missing key skips files instead of reading them. A key absent from the database might otherwise require touching every file on disk; with filters it touches almost none. This is why write-optimised databases can still answer point lookups quickly.

Caches guard against requests for things that do not exist. 10.14.2 named the problem: a request for a non-existent id misses the cache, finds nothing, and caches nothing, so every repeat reaches the database. A Bloom filter of existing ids rejects those requests before they touch anything.

Crawlers deduplicate URLs, which is the opening example.

Analytics counts uniques with HyperLogLog, and merges sketches across servers and time windows.

Caches decide admission using a frequency sketch, so a scan cannot evict the hot set.

7. What the interviewer will push on

"How does a Bloom filter work, and what is its guarantee?" The mechanism is k hashes setting k bits, and the guarantee is the asymmetry: no false negatives, some false positives. The reason to say the asymmetry rather than "it is approximate" is that the asymmetry is what makes it usable as a guard — a rejection is final, so anything it rejects can be dropped without checking.

"Can you delete from one?" No, and the why is the answer they want: clearing an item's bits would clear bits shared with other items, producing false negatives and destroying the only guarantee the structure has. Then name the alternatives — a counting Bloom filter at four times the memory, or a cuckoo filter which is smaller at low error rates and harder to implement.

"How much memory for a billion items at one percent error?" They want to see you carry the number. Roughly ten bits per item, so a billion items is about 1.2 GB — and the memorable follow-up is that the item's size does not matter, so this is true whether the items are short ids or long URLs. Add that tightening to 0.1 percent costs only five more bits per item, so over-provisioning is nearly free.

"How would you count unique visitors across a hundred servers for a month?" HyperLogLog, and the answer must include mergeability, because that is the whole reason it fits. Each server keeps an hourly sketch, and any time range or any set of servers is answered by merging — taking the maximum per bucket. Then the sharp observation: exact daily unique counts cannot be added to give a monthly figure, because the same person appearing on two days would be double-counted, so this is a metric that only becomes additive through sketching.

"Why does Count-Min take the minimum?" Because collisions can only ever increase a cell, so every cell is an over-estimate and the smallest of them is the tightest bound. Hence the guarantee: never under-counts, sometimes over-counts. And therefore never use it where over-counting hurts — billing, or a quota that must not falsely reject.

"When would you not use these?" When a wrong answer is expensive and invisible. A false positive that costs one extra database lookup is free. A false positive that denies a customer access, bills them twice, or shows them someone else's record is not, and no amount of memory saving justifies it.

The thing to volunteer that nobody asks for: a Bloom filter fails silently when full. Sized for ten million and given a hundred million, nearly every bit is set, so it answers "probably present" to everything and quietly stops filtering — no error, no exception, just a guard that has become a pass-through. Monitoring the fill ratio, and rotating to a fresh filter before saturation, is the operational detail that separates people who have run one from people who have read about one.

Next: 10.19 collects the recurring trade-offs from the whole Part into one page you can argue from both sides.

Recall

• Bloom filter: k hashes set k bits. No false negatives, some false positives — a "no" is final, so it works as a guard. Cannot delete, because clearing shared bits would create false negatives.
• ~10 bits per item for 1% error, and the item's size is irrelevant. Tightening to 0.1% costs about five more bits, so over-provision.
• A full Bloom filter fails silently — every bit set means "probably present" for everything. Monitor the fill ratio and rotate.
• Counting Bloom filter (4× memory) or a cuckoo filter if you need deletion.
• Count-Min Sketch: counts frequency in fixed memory for any number of keys. Take the minimum because collisions only inflate cells, so it never under-counts. Use for hot keys and cache admission; never for billing or quotas.
• HyperLogLog: distinct count in ~12 KB with ~0.8% error. The essential property is that sketches merge by taking the per-bucket maximum, so any time range and any set of servers can be answered without storing a single id. Exact daily uniques cannot be summed into monthly uniques; sketches can.
• The question before using any of them: what does a wrong answer cost? A wasted lookup, fine. A wrong bill or a denied customer, never.

Self-test: Why can a Bloom filter have false positives but not false negatives? Why can't you delete? How much memory for a billion items at 1%, and does item size matter? Why does Count-Min take the minimum, and what does that guarantee? Why is mergeability the point of HyperLogLog?

Quiz Bank

FoundationalExplain a Bloom filter's mechanism and prove to yourself why false negatives are impossible.

The structure is an array of bits, all starting at zero, plus k independent hash functions.

Adding an item means hashing it k ways and setting those k bits to one. Note the important detail: bits are only ever turned on. Nothing in the add operation ever turns a bit off.

Testing an item means hashing it the same k ways and looking at those bits. If any of them is zero, the item was never added. If all of them are one, it was probably added.

Why false negatives are impossible. Suppose item X was added. That means at the moment of adding, all k of its bits were set to one. Bits are never cleared, so all k of them are still one now, and a test for X therefore finds them all set and reports "probably present". There is no sequence of operations that can make a previously-added item test as absent — which is exactly why deletion is forbidden, since clearing bits is the one thing that would break this.

Why false positives are possible. Item Z was never added, but its k bit positions may all have been set by other items. With ten thousand items in a filter, many bits are on, and Z's three or seven positions can coincidentally all be among them. The filter has no way to tell "these bits were set by you" from "these bits were set by someone else", because it stores no identity at all.

Why that asymmetry is the useful part rather than a curiosity. A "no" is definitive, so a Bloom filter works as a guard: anything it rejects can be discarded with no further checking, and only the things it accepts need a real lookup. In the crawler case, one percent of URLs are needlessly skipped out of ten billion, and ninety-nine percent of repeat checks are answered from 12 GB of memory instead of 500 GB.

And the sizing intuition worth carrying: roughly ten bits per item for one percent error, independent of how large each item is. That independence is where the saving comes from — you store ten bits whether the item is a short id or a two-thousand-character URL — and it also means the structure is equally attractive for very large items, which is often when you need it most.

AppliedDesign the deduplication layer for a web crawler that will visit ten billion URLs, and say what you do when the filter fills up.

Establish the constraint first. Ten billion URLs stored exactly, at around fifty bytes each, is roughly 500 GB — a cluster of machines whose only job is remembering. A Bloom filter at one percent error is about ten bits per URL, so 12 GB, which fits on one machine. That is the decision, and the cost of it is that one crawl in a hundred is skipped unnecessarily. Out of ten billion pages, skipping a hundred million is genuinely acceptable, because the crawl is best-effort anyway and those pages will be reached by another link later.

What matters is that the error direction is the safe one. A false positive means "I think I have seen this, skip it" — a page missed. A false negative would mean crawling a page twice, which wastes bandwidth. Bloom filters give no false negatives, so the failure we get is the one we chose, and there is no chance of an infinite re-crawl loop.

Normalise before hashing, or the whole thing is undermined. example.com/page, example.com/page/, EXAMPLE.com/page and example.com/page?utm_source=x are the same page. Canonicalise the host case, strip tracking parameters, resolve the path, and hash the result. A crawler that skips normalisation is deduplicating strings rather than pages, and its effective hit rate collapses.

Now the fill problem, which is the real question. A filter sized for ten billion and given twenty billion is nearly all ones, so it answers "probably present" to everything and stops crawling entirely. Crucially it fails silently — no error, no exception, just a crawler that gradually finds nothing new. The symptom is a mysterious decline in discovery rate that looks like the web running out of pages.

So: monitor the fill ratio, meaning the fraction of bits set. It is cheap to sample and it tells you the true error rate, because the observed false positive rate is a direct function of it. Alert well before saturation.

Handle growth with rotation rather than one enormous filter. Keep a sequence of filters, each sized for a fixed number of URLs. When the current one reaches its capacity, seal it and start a new one. A test checks all of them, so lookup cost grows slowly with the number of generations, and each is a fixed, predictable size. This also gives you an ageing story: very old generations can be dropped if re-crawling ancient URLs is acceptable, which turns unbounded growth into a bounded window.

Two refinements a strong answer adds.

Two tiers. Keep a small, exact, recent set — the last few million URLs in a hash set — in front of the filter. Most duplicate discoveries are recent, so this catches the common case exactly and with no error, and the filter handles the long tail.

Partition by host. One filter per domain, or per group of domains, means each is smaller, they can live on different machines, and crawling one site heavily does not degrade accuracy for every other site. It also makes politeness policies and per-host rate limits natural, since the state is already partitioned that way.

InterviewYou need to count unique visitors per day, per week and per month, across a hundred servers. Design it.

The naive approach fails on a property people do not expect. Storing every visitor id per day and counting distinct values gives an exact answer for a day — and gives you nothing for a week, because unique counts cannot be added. Monday's 100,000 uniques plus Tuesday's 100,000 is not 200,000 for the two days, since most of them are the same people. To get the weekly figure exactly you must keep every id for the whole week and count distinct across all of it, and monthly means keeping a month. The storage grows with the window, and merging across a hundred servers means shipping all those ids somewhere.

HyperLogLog solves it, and the reason is mergeability rather than compression. A sketch is about 12 KB and estimates distinct count to within roughly 0.8 percent. Two sketches are merged by taking the maximum in each bucket, and the result is exactly the sketch you would have built by feeding both streams into one from the start. Merging is lossless with respect to the estimate.

So the design is: keep one sketch per server per hour. That is it. Everything else is merging.

Daily uniques — merge that server's twenty-four hourly sketches, and merge across servers. Weekly — merge 168 hours. Monthly — merge about 720. One server's contribution, or one region's — merge only those sketches. Any arbitrary window somebody asks for later — merge the hours it covers.

The storage arithmetic makes the case. A hundred servers × 24 hours × 12 KB is about 29 MB per day, and roughly 10 GB per year — for a system that can answer any time range, any subset of servers, retrospectively, without ever having stored a single visitor id. Exact counting for the same flexibility would need every id for every window you might later be asked about.

Three details worth adding.

Not storing ids is a privacy benefit as well as a storage one. A sketch cannot be reversed to recover who visited, so the analytics store carries no personal data, which simplifies retention and deletion obligations considerably.

Cardinality can be sliced. Keep separate sketches per country or per device type and you can answer "unique visitors in Germany on mobile last week" by merging that subset — as long as you decided the slices in advance, which is the one thing sketches cannot do retrospectively.

Know the error and state it. 0.8 percent is fine for a traffic dashboard and not fine for a number in a contract. If somebody bills on unique users, you need exact counting for that specific number, and the honest answer is to use both: sketches for the dashboards and exact counting for the small set of figures that carry money.

StaffYour database team wants to remove Bloom filters from the storage engine to save memory. Argue the case with numbers.

Start by naming precisely what the filters are doing, because "saving memory" only sounds sensible if you do not know what you are removing.

The engine writes data as a series of immutable sorted files. A point lookup for a key does not know which file holds it, so without help it must check each file in turn, newest to oldest. Each check that finds nothing is a wasted disk read. With a small Bloom filter per file, a key absent from a file is rejected in memory, so almost all of those reads never happen.

The numbers, which is what makes the argument rather than the explanation.

Say a table has ten files. A lookup for a key that exists in the newest file costs one read either way — filters do not help there. But a lookup for a key that does not exist costs ten reads without filters and, at a one percent false positive rate, about 0.1 unnecessary reads with them. That is a hundredfold difference on the missing-key path.

Missing-key lookups are not rare. They are what happens on every "does this user already exist" check, every cache miss that falls through, every unique-constraint check, and every request for an id that has been deleted. In many workloads they are the majority of lookups.

Now the cost being saved. Ten bits per key is roughly 1.2 GB per billion keys. So on a table of a billion rows, removing the filters returns 1.2 GB of memory and multiplies the disk reads for missing keys by up to the number of files.

And here is the part that turns it from a trade into a mistake. That 1.2 GB was not idle. It was preventing disk reads. Reclaim it and it becomes page cache, which is worth something — but a gigabyte of page cache holds a small fraction of a large table, while a gigabyte of Bloom filter covers every key in the table. Bits per key is a far more efficient use of memory than bytes per cached row, for this specific question.

What I would propose instead of removal.

Tune the false positive rate rather than deleting the filters. Moving from 1 percent to 5 percent cuts memory by about a third, at a cost of five wasted reads per hundred missing-key lookups instead of one. That is a real dial with a real curve, and it is almost always a better answer than off.

Drop filters only on the largest, coldest files. The newest and smallest files are checked first and matter most; the ancient ones are checked rarely. Filters can be kept where they earn their memory and dropped where they do not.

Measure before deciding. The read-amplification metric for missing keys is exactly the number that will move, and it can be observed for a day before touching anything.

The sentence to close on: this is memory buying a hundredfold reduction in disk reads on the most common failure path, at ten bits per key. If we need the gigabyte back there are three ways to get most of it that do not multiply our disk reads, and removing the filters is the only option on the table that does.

Flashcards

FlashBloom filter guarantee

No false negatives, some false positives. "Not present" is always correct, so it works as a guard. Cannot delete — clearing shared bits would create false negatives.

FlashBloom sizing

~10 bits per item for 1% error, ~14 for 0.1%. Independent of item size. A billion items at 1% is ~1.2 GB. Over-provisioning is nearly free.

FlashBloom filter fails silently

When full, every bit is set and it answers "probably present" to everything — no error, just a guard that has become a pass-through. Monitor fill ratio and rotate to a fresh filter.

FlashCount-Min Sketch

Frequency in fixed memory for any number of keys. Take the minimum, because collisions only inflate cells. Never under-counts. Use for hot keys and cache admission; never for billing.

FlashHyperLogLog

Distinct count in ~12 KB at ~0.8% error. The point is that sketches merge by per-bucket maximum, so any time range or server subset is answerable without storing ids. Exact daily uniques cannot be summed; sketches can.

FlashThe question before using any of them

What does a wrong answer cost? A wasted lookup or a skipped page in ten billion — fine. A wrong bill, a denied customer, or someone else's data — never.