Ch.14: Algorithms: Bloom Filters and the Cost of Maybe

0:00 A request asks for a record that doesn't exist. A tiny array in memory rejects it before the database has to search its files. A Bloom filter. Which is allowed to make mistakes, somehow. I'd like that job. How can we trust it to decide which searches disappear? Because we only trust one answer: definitely absent. If it says maybe present, we'll check the database. A mistake costs extra work there, without inventing a record. Right, so the expensive check survives where we need it. The filter can waste a lookup, but it can't be allowed to hide a record we actually have.

0:36 Yes. It's a checklist where one missing mark ends the search. Finding every mark just means we still have to go look. Okay, but a checklist sounds like it stores information about each record. How are we fitting a big set of keys into something tiny? By letting keys share the marks. Let's try 12 bits: they won't remember who set them, which turns out to be both useful and risky. Okay, let's build one. Our 12 positions, zero through 11, start empty. Each key's three hash calculations pick positions where we'll leave marks by setting the bits to one. Suppose A hashes to positions one, four and eight. I'll set those three, but that's all we store. No little name tags saying A was here.

1:21 Then B chooses four, seven and 10. Its insertion turns on the two new positions while four stays as it was, already one. Now ask about A again. The same hashes lead back to its three marks, still set, because all we've done since insertion is turn more bits on. That's the guarantee in this insertion-only version. Every inserted key finds its bits set, assuming consistent hashes and an intact array. But I can see the trap. Suppose an unseen key C chooses one, seven and eight. Those are all set, even though we never inserted C.

1:56 Oh, right. C borrows bits from A and B. We call that a false positive: the filter says maybe, and the database discovers C isn't there. And the collision doesn't require identical hashes. Here, the false match can be assembled from several different keys. Yes. For a different query, D, use positions two, four and 10. Position two is still zero. Then D can't have been inserted, because inserting it would have set that bit. One zero is enough to reject it, regardless of the other two positions. And that rejection is the read we wanted to avoid.

2:31 We learned something definite from an array that can't even list the keys it represents. That is cheap. I can imagine a reviewer asking us to keep every filter at 12 bits. When would that stop working? Keep adding keys and eventually the array is almost all ones. Nearly every answer becomes maybe, so the database gets all its work back. So the filter's official recommendation is to ignore the filter. We've built a very small manager. Who forwards every request. Still safe, just not earning the memory it occupies.

3:02 We need enough empty positions left to reject something. So we'd size it for the key count we expect and the error we can live with. Redis defines that over absent queries: for example, 1% falsely pass. We might read that as a 99% chance that a maybe is real. Different question, though. It really depends on how many queries asked for absent keys. Let's actually count the work. Imagine 1,000 requests, 900 missing keys and 100 real ones, with that 1-percent false-positive probability. 1% of those absent queries means nine expected false alarms.

3:40 The other 891 stop before the database check. Add the hundred real keys, which all pass. That's 109 expected database checks instead of 1,000. Nine of those checks find nothing. Which sounds great, but we've invented the workload. It isn't a benchmark or our tiny example's error rate, and checking the filter also costs something. What if, though, almost every requested key exists? Would you still expect that kind of saving? No. Existing keys still need their database checks. A filter earns its keep when useful rejections save enough work to cover checking and maintaining it. The standard Bloom sizing formula puts a 1-percent target just under 10 bits per inserted key, before implementation overhead.

4:25 Reducing those false alarms costs more memory. And that budget assumes the planned capacity. Overfill a fixed filter and its bits get crowded, which raises the chance that an absent key finds all ones. Then maybe deleting old keys would free bits. B used positions four, seven and 10. Could we just clear those when we delete B? Tell me that works. Not in this basic design. A also uses four. Clear it for B and a later query for A finds zero, even though A should remain present. Oh, that's nasty. Clearing B's marks also erases A's evidence.

5:02 We threw away ownership to save space, and now deletion needs the information we discarded. There are other designs supporting deletion. But ordinary shared bits don't. That gives us a design decision before implementation: whether removing keys is required. But even without deletion, we can break the application. Say you add a database record but forget its filter. Your next read may reject the record you just added. Yeah, if you've chased a stale cache, this should feel familiar. The array correctly says, I never saw that key, while the database is sitting there holding it.

5:35 Exactly. One represents the old set; the other holds the new one. Its mathematical guarantee doesn't repair that mismatch. So before trusting a no, I'd ask what data that filter belongs to. For example, could it describe one particular database file? It can, yeah. RocksDB is a database storage library. Its full-file version covers one entire file. Inside are chunks called blocks, and an index tells us where to look. My first thought is to consult the index, then check the candidate block. But a definite no from the file's filter would, I mean, make both steps unnecessary.

6:11 That's exactly the move RocksDB documents. Older filters were checked after the index located the candidate data block; a full-file filter gets checked first. And when the answer is maybe? Then we follow the index to a candidate block and check for the actual key. A false alarm costs that extra check. Verification still decides the answer. Now the on-call engineer says, I know this key exists. Tell me how often it's hammering us. That takes counts. A sketch is a compact summary. Let's give our Count-Min toy three rows of counters.

6:45 Each arriving key hashes to one counter per row and increments the selected counters. I'd start with 1 row, honestly. A counter for each hash position sounds pretty straightforward. What do the extra rows buy? Different collisions. Each row uses a different hash, so keys mixed together in one row may separate in another. It's several noisy views of one count. For example, our target appears four times. Those appearances contribute four to its chosen counter in every row. Other keys may have incremented the same counters too.

7:17 Suppose the three counters read seven, four and six. Querying the target takes the minimum, four. In this case 1 row escaped the extra traffic. But we're looking at mixed counters. Are we choosing the smallest just because we're hoping it's the least contaminated? Well, with nonnegative increments, collisions only add. Each chosen counter contains the target's full count plus possible extras. The minimum keeps the smallest excess we found. So it's an upper estimate in that model. Still, I don't see why any row has to be clean.

7:50 It doesn't. I mean, keep the true count at four but imagine readouts of seven, five and six. The minimum is now five. We've reduced the noise, not removed it. Yeah. Even the least polluted counter can make a quiet key look busy. Useful for deciding where to investigate, maybe. I'd want better evidence before blaming it for an incident. If a sketch advertises an error fraction, is that a fraction of this particular key's count? No. Choose a toy allowance of 1% of a million requests. That's 10,000 extra counts, even for a key seen just four times.

8:27 Redis defines it against total traffic. 10,000 against four. That puts 1% in perspective. The separate probability setting controls how often our error can exceed that allowance. And that reasoning assumes counts only go up. If the on-call tool also subtracts events, we need to check its guarantees before relying on that upper estimate. But even huge traffic might come from one enthusiastic visitor. Suppose the dashboard wants different people, and we can't afford to keep every identifier. HyperLogLog tackles that.

8:59 It looks for rare patterns in hashes, a bit like finding an unusually long run of heads among coin tosses. With more different identifiers, we have more chances to encounter those rare patterns. Repeated visits give us the same hash again, so they don't create fresh evidence. Let me follow one person through it. Say Alice visits, and we hash her identifier. What happens to the resulting string of bits? We split the hash. 2 bits select among four buckets in our toy, numbered zero through three. Alice's first two are zero one, so she lands in bucket one. Mm-hmm.

9:33 So Alice has a destination. What's in the rest of her hash? Say it begins zero, zero, one. That's two leading zeros, so adding one gives rank three. Her bucket keeps that number in a little storage slot, a register. So we've stored three, not Alice. Now Bob's hash picks that same bucket, but the remainder begins with four zeros before a one. His rank is five, which replaces three because the register keeps only the largest rank. Another visit from Bob produces five again and changes nothing. Ah, the summary ignores his return without remembering Bob.

10:09 Even 1,000 repeat visits can't make that five grow. That's a neat way to forget someone. Though a new visitor might also leave the register unchanged. We're collecting the strongest rarity evidence in each bucket, rather than ticking up once per person. Hold on, though. We could get Bob's rare pattern on the very first visit. How does that become a believable estimate of the crowd? One bucket can get lucky, so HyperLogLog, Combines a lot of them. Rare patterns across lots of buckets are stronger evidence of a large crowd than one freak result. Like running several coin experiments.

10:47 One long streak I can imagine getting by luck. I'd be less comfortable, honestly, waving away lots of them. Right. And the original HyperLogLog paper combines register evidence using the probabilities of hash patterns. Its population estimate can miss in either direction. That's one server. Now imagine two, both visited by Bob. Adding their distinct-user estimates would count the overlap twice. Can we combine their evidence instead? We can, if hashing and register layout match. At each corresponding slot, the larger value survives.

11:17 Then the merged registers give us the combined estimate. That recreates the evidence one sketch would have collected from both streams. Bob's five meeting another five still gives five. So the result estimates their union. That's clever. All different visitors across the two servers, counted together. But could we use those registers to check whether Alice herself visited? No, we've thrown away identities. Many different visitor sets can produce the same registers, so that membership question still needs other data.

11:45 So a dashboard can get a compact, mergeable audience estimate. It hasn't acquired a tiny database of everyone who was there. And the customer disputing a bill won't be pleased with, roughly 10 people, trust the buckets. We need exact evidence for the charge. Well, fair complaint. If we can't show the records supporting that charge, we're stuck defending it. A dashboard estimate had one job; proving this bill has another. Whereas the Bloom filter we started with only gambled on doing extra work. Every maybe still reached verification, and the database decided the answer.

12:20 That's what I'd put beside the accuracy number in a design review: what happens when it's wrong. Extra checking and an incorrect customer answer are very different costs. Sources are in the description. Next time, we'll see gzip compress repeated text without losing words. Thanks for listening to Learning Podcasts.