Redis Bloom Filters

A Bloom filter answers one question quickly: "Have I seen this item before?" It uses a very small amount of memory and never forgets an item you added. The trade-off is a small chance of a false "yes." A "no" answer is always correct.

The Club Bouncer Analogy

A bouncer glances at a short list of tell-tale features for each member. If a visitor lacks even one feature, the bouncer knows for sure that the person is not a member. If the visitor has all the features, the bouncer says "probably a member" and checks more closely. A Bloom filter behaves like that bouncer.

  Question: Is "asha99" taken?

  Bloom filter says NO        → Definitely not taken. Skip the database.
  Bloom filter says YES       → Probably taken. Confirm in the database.

How It Works

The filter holds a long row of bits, all set to 0. Each added item runs through several hash functions that pick bit positions. Redis turns those bits to 1. A lookup runs the same hash functions and checks the bits.

Add "asha":    hash → positions 2, 7, 11     Bits: 0 0 1 0 0 0 0 1 0 0 0 1
Add "ravi":    hash → positions 4, 7, 9      Bits: 0 0 1 0 1 0 0 1 0 1 0 1

Check "meena": positions 1, 4, 10
               bit 1 is 0 → definitely NOT added

Check "zoya":  positions 2, 4, 9
               all bits are 1 → "probably added" (could be a false alarm)

Different items can set overlapping bits, which causes false positives. No operation turns a bit back to 0, so false negatives never happen.

Creating and Using a Filter

127.0.0.1:6379> BF.RESERVE usernames 0.01 100000
OK
127.0.0.1:6379> BF.ADD usernames "asha99"
(integer) 1
127.0.0.1:6379> BF.EXISTS usernames "asha99"
(integer) 1
127.0.0.1:6379> BF.EXISTS usernames "ravi21"
(integer) 0
127.0.0.1:6379> BF.MADD usernames "meena7" "zoya3"
1) (integer) 1
2) (integer) 1

BF.RESERVE takes an error rate and an expected item count. The example allows a 1 percent false positive rate for 100,000 items. BF.ADD returns 1 when the item is new and 0 when the filter believes it already exists.

Memory Savings

Method                    1 million user names
────────────────────────  ─────────────────────────
Redis Set (store names)   tens of megabytes
Bloom filter (1% error)   about 1.2 megabytes

Roughly ten bits per item deliver a 1 percent error rate, and lowering the error rate raises the bits per item.

Related Structures

• Cuckoo filter: works like a Bloom filter and supports deleting items with CF.DEL.
• Count-min sketch: estimates how many times an item appeared.
• Top-k: keeps the most frequent items from a stream, such as the ten most searched words.

127.0.0.1:6379> TOPK.RESERVE trending 3
OK
127.0.0.1:6379> TOPK.ADD trending "redis" "python" "redis" "sql" "redis"
127.0.0.1:6379> TOPK.LIST trending
1) "redis"
2) "python"
3) "sql"

Practical Example – Fast User Name Check

Sign-up form asks: "Is this user name free?"

Step 1:  App calls BF.EXISTS usernames "newuser"
Step 2:  Reply 0 → name is free. Skip the database lookup.
Step 3:  Reply 1 → name may be taken. Query the database to confirm.
Step 4:  After a real sign-up, app calls BF.ADD usernames "newuser"

Result: Most checks finish in Redis, and the database sees far fewer queries.

When Not to Use a Bloom Filter

• You must list or read back the stored items.
• A false positive causes harm and you have no second check.
• You need to delete items often. Choose a Cuckoo filter instead.

Key Points

• A Bloom filter reports "definitely no" or "probably yes."
• BF.RESERVE sets error rate and size, BF.ADD inserts, and BF.EXISTS checks.
• Memory use stays tiny compared with a Set.
• Cuckoo filters, count-min sketch, and top-k solve neighboring problems.