Bloom, Cuckoo, Count-Min and Top-K

In one line

Probabilistic structures answer "definitely not / maybe yes", "roughly how often", and "roughly the top K" in tiny, fixed memory. Redis 8 includes Bloom and Cuckoo filters, Count-Min Sketch, Top-K and t-digest; on Valkey, valkey-bloom provides Bloom filters.

0/6 · 0%

Think of it like this

A nightclub bouncer with a blurry list. If your name isn't on it, you're definitely not getting in. If it looks like it's on there, they still check your ID properly. The list saves time for most people without ever wrongly turning away a real guest.

Key ideas

01
Bloom filter: a bit array plus k hash functions. Adding sets k bits; checking tests them. If any bit is 0, the item was definitely never added (no false negatives); if all are 1, it was probably added (false positives possible). Size for n items and false-positive rate p: about −n·ln(p)/(ln 2)² bits, so ~9.6 bits per item for 1%, ~14.4 for 0.1%. 10M items at 1% ≈ 12 MB.
02
Redis Bloom commands: BF.RESERVE key error_rate capacity [EXPANSION n] [NONSCALING], BF.ADD, BF.MADD, BF.EXISTS, BF.MEXISTS, BF.INFO, BF.CARD. Filters scale by adding sub-filters when capacity is reached (each one tighter), which keeps the error bound but costs memory and lookup time. You can't delete from a Bloom filter.
03
Cuckoo filter (CF.RESERVE, CF.ADD, CF.DEL, CF.EXISTS, CF.COUNT): similar purpose, supports deletion, and is often faster for lookups; it can fail inserts when too full and deleting an item that was never added corrupts it.
04
Count-Min Sketch (CMS.INITBYPROB key error probability, CMS.INCRBY, CMS.QUERY): approximate frequency of each item, never under-counting, in fixed memory. Top-K (TOPK.RESERVE key k, TOPK.ADD, TOPK.LIST WITHCOUNT): tracks the approximate most frequent items in a stream (heavy hitters), great for hot-key detection and trending. t-digest (TDIGEST.CREATE, TDIGEST.ADD, TDIGEST.QUANTILE) estimates percentiles such as p99 latency.
05
Lifecycle: filters don't shrink and can't forget (except Cuckoo deletes), so plan rebuilds. A common pattern is a daily or rolling filter (bf:products:v12) rebuilt from the database in the background, then atomically switched via a pointer key. The Bloom Filters course covers the maths, variants, and the full rebuild and Kafka-update lifecycle in depth.

Code & diagrams

bloom.redisredis

127.0.0.1:6379> BF.RESERVE bf:products 0.01 10000000
OK
127.0.0.1:6379> BF.MADD bf:products 1001 1002 1003
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> BF.EXISTS bf:products 1002
(integer) 1          # probably exists -> check cache/DB
127.0.0.1:6379> BF.EXISTS bf:products 999999999
(integer) 0          # definitely not -> reject immediately
127.0.0.1:6379> BF.INFO bf:products
 1) Capacity  2) (integer) 10000000
 3) Size      4) (integer) 12004720
 5) Number of filters 6) (integer) 1
 7) Number of items inserted 8) (integer) 3
 9) Expansion rate 10) (integer) 2

127.0.0.1:6379> TOPK.RESERVE hot:keys 10
OK
127.0.0.1:6379> TOPK.ADD hot:keys product:iphone product:iphone product:tv
127.0.0.1:6379> TOPK.LIST hot:keys WITHCOUNT
1) "product:iphone"
2) (integer) 2
3) "product:tv"
4) (integer) 1

bloom-gate.mermaiddiagram

Rendering diagram…

Interview problem

The problem

Stop queries for products that don't exist

Attackers (or buggy clients) request random product IDs that don't exist. Every request misses the cache and hits the database. Design a Bloom-filter gate, including sizing, false positives, adding new products, deleted products, and rebuilds.

You're given

20M products
Attack traffic up to 100K req/sec of random IDs
New products added continuously
Products are sometimes deleted

The interviewer follows up

Why not just cache "not found" for every missing ID and skip the Bloom filter?

When it breaks

A Bloom filter created far smaller than the real item count

What you see

The filter keeps expanding (with EXPANSION) and lookups slow down, or with NONSCALING it saturates and the false-positive rate climbs towards 100%, so it stops protecting anything.

Fix & prevent

Reserve for expected growth; monitor BF.INFO item count vs capacity; rebuild into a larger filter.

Explain it without notes

Why can a Bloom filter have false positives but not false negatives?

When would you choose a Cuckoo filter over a Bloom filter?

Practice

Compute the memory for a Bloom filter of 100M usernames at 0.1% false positives, and explain what a false positive costs in a "username taken?" check.

Trade-offs

↔
Lower false-positive rates cost more memory (about 4.8 extra bits per item for each 10× improvement).
↔
Probabilistic structures in Redis 8 core vs modules on other servers: check availability before designing around them.

Done when you can

I can size a Bloom filter and explain its guarantees.
I can design a cache-penetration gate with rebuilds and negative caching.
I know what Cuckoo, Count-Min, Top-K and t-digest are for.

Command Palette