Most lookups are for things that don't exist
A Bloom filter in front of Cassandra. The cluster got 60% smaller. Here is how we got there, because the interesting part is not the filter.
The service
One endpoint, one question: have we seen this file hash before. Behind it, a Cassandra cluster holding every hash we know. A few million requests a second at peak.
When I got it, those endpoints lived inside a bigger service and scaled with it, which is to say they didn't. Whatever the monolith needed, the lookups got. My first job was to carve them out into their own service so it could scale on its own traffic. That worked.
Then it started falling over.
The pods
Each request got a goroutine. Nothing capped how many. Traffic on this thing arrives in bursts, and a big enough burst would push a pod past its memory, the pod would die, its share of the burst would land on the other pods, and they would follow. If nobody caught it in the first minutes, the whole service went. I worked out how many in-flight requests fit in a pod's memory, capped it there, returned 429 above it, and scaled the pods on the rate of 429s. The alerts went quiet. That fix gets its own post.
It also moved the problem. The pods now survived bursts. Cassandra now received them. On the busy days the cluster was the thing struggling, and the pods were sitting there with their new rate limit, politely forwarding the whole burst to it.
So I went to look at what the burst actually was.
What the traffic was
Most of it was "no".
About 80% of lookups returned not found. Once you see it, it's obvious. Most files in the world are ordinary files. We get asked about whatever people run, and we have stored a very small slice of that. So four out of five requests existed only to confirm that something wasn't there, and each one paid the full price: coordinator, fan-out to the replicas, every replica checking every SSTable it had, and back. That was the load. Not the hits. The misses.
The first idea is a cache of misses. It doesn't survive a minute of thought. A miss is a hash we have never seen, and most of them we will never see again, so a cache of them almost never hits. You'd be spending memory remembering questions nobody asks twice.
What you want is a structure that can say "no" about hashes it has never been asked about. That's a Bloom filter.
The filter
A bit array and a handful of hash functions. Adding an element sets the bits its hashes land on. Checking an element reads those bits. Any zero means the element was never added. All ones means it was added, or other elements happened to cover the same bits.
The property that matters is the asymmetry. It never says "no" about something it holds. It can say "maybe" about something it doesn't. Which gives you a read path where the filter can only ever cost you an extra lookup, never a wrong answer:
go
func (s *Lookup) Seen(ctx context.Context, h Hash) (bool, error) {
maybe, err := s.filter.MayContain(ctx, h)
if err == nil && !maybe {
return false, nil // a "no" from the filter is a real no
}
// "maybe", or the filter is unreachable: ask the source of truth
return s.cassandra.Exists(ctx, h)
}
"No": answer now, Cassandra never hears about it. "Maybe": do what we always did. Redis down: do what we always did. The caller gets the same answer in every case. The filter lives in Redis because the service runs as many pods and they need to agree on the bits, and a Redis round trip is nothing next to a Cassandra fan-out.
The pushback
My teammates didn't want it. Two objections, both fair.
Correctness. "Probabilistic" sounds like "sometimes wrong", and being right is this service's entire job. And writes: every new hash would now need a second write, to Redis, on top of Cassandra.
I made a presentation. I would have rather not, but it was the right tool, because the objection was about where the filter can be wrong and the answer to that is a diagram, not an argument. It can be wrong in one direction: a "maybe" for a hash we don't have, which costs one lookup and still returns the right answer. It cannot be wrong in the other. For the writes I pulled the read to write ratio from the dashboards. Writes are a rounding error next to reads. One more per new hash is nothing against the 80% of reads we would stop sending.
What settled it was the failure mode. Redis slow or gone: skip it, go to Cassandra, the service is exactly what it was last month. The one thing you must never do is read "Redis unavailable" as "not found". The code above can't.
Which write goes first
Redis, then Cassandra.
go
func (s *Lookup) Add(ctx context.Context, h Hash) error {
if err := s.filter.Add(ctx, h); err != nil {
return err
}
return s.cassandra.Insert(ctx, h)
}
Filter write lands, Cassandra write doesn't: the filter knows a hash Cassandra doesn't. A false positive. Harmless, the lookup falls through and Cassandra says no. The other order lies: a hash in Cassandra that isn't in the filter yet gets a confident "no". So the filter goes first, and if that write fails the add fails and the caller retries.
"Cassandra already has Bloom filters"
Someone will say this. It's true. One per SSTable, so a read can skip files that can't hold the key. That saves disk reads after the request is inside the cluster. It doesn't save the request. The coordinator still takes it, still fans out, every replica still checks its filters. At our rate the handling was the cost, not the disk. Ours stops the request before it reaches the cluster at all.
Sizing
Textbook: about 10 bits per element and 7 hash functions gives roughly a 1% false positive rate. We sized for a low single-digit rate, so a few percent of the "no" lookups still reach Cassandra. They were all reaching it before.
Rollout
Critical service, so: a few production environments first, watch the Cassandra load and the error rate, then the rest.
The cluster got 60% smaller.
The presentation mattered more than the code. They were right to push back. They needed to see exactly where the filter can be wrong and where it can't. So did I.