jonnify·redis /redis-patterns/data-modeling/probabilistic-data-structures/bloom-and-cuckoo

R7.03.2 · dive 2

Membership, one-sided error.

A Bloom filter answers “is this item in the set?” with possible false positives but zero false negatives — a “no” is certain, a “yes” is “probably”.

That one-sided error is the whole point: it is safe to skip work on a “no” because a “no” is never wrong. Select a query below — a present item, an absent item, a false positive — and read what the bits say. It is also the error in the wrong direction for EchoMQ's idempotency, which keeps an exact de: key.

How it works Cache penetration Cuckoo The EchoMQ contrast References
k hashes into a bit array. Select a query; the readout reports what the bits say and whether the answer can be wrong.
bit array (set bits in green) — three earlier adds 1 0 1 1 0 1 0 1 1 0 1 0 a member bits 0,2,5 — all set a non-member bits 1,4,6 — a zero a false positive bits 3,7,10 — all set a “no” needs one zero — never wrong. a “yes” needs all set — may be a false positive. zero false negatives, by construction; false positives possible, at a tunable rate
§1

How a Bloom filter works

probabilistic-data-structures.md.txt · membership

A Bloom filter is a bit array plus k hash functions. To add an item, hash it k ways and set the k bits. To test an item, hash it the same k ways and read those bits: if any bit is zero the item is definitely absent; if all are set the item is probably present. A false positive happens when other items happened to set all of one absent item's bits. A false negative cannot happen — adding an item only sets bits, never clears them, so a present item always reads back all-set.

The false-positive rate is a dial. More bits per item and more hash functions lower it; a 1% rate for a million items is a typical reservation. You pay memory and a little CPU for a smaller error. The commands are module commands — Valkey-Bloom or Redis-Stack, not the core engine:

BF.RESERVE usernames 0.01 1000000   # 1% false-positive rate, capacity 1M — a module command
BF.ADD usernames "john_doe"
BF.EXISTS usernames "john_doe"

Notes on ValkeyThe Bloom-filter commands — BF.RESERVE, BF.ADD, BF.EXISTS, BF.MADD — are provided by the Valkey-Bloom module, not the core engine, so a deployment must load the module to use them; BF.RESERVE takes a target error rate and capacity that fix the bit count and the number of hashes — valkey.io/commands.

A Bloom filter's error is one-sided by construction: a “no” is certain, a “yes” may be a false positive at a rate you set. That asymmetry is what makes it useful in front of an expensive lookup.

§2

The signature use — cache penetration

probabilistic-data-structures.md.txt · cache penetration

Without a membership pre-check, a flood of requests for keys that do not exist each misses the cache and falls through to the database — an attacker can turn “look up a user that isn't there” into database load. A Bloom filter holding the set of real keys rejects the absent ones immediately: if the filter says “absent”, skip the cache and the database entirely.

The zero-false-negative guarantee is what makes this safe — the filter never wrongly says “absent” for a key that exists, so a real key is never rejected. A false positive only costs one needless lookup, which the cache absorbs. The asymmetry lands exactly where it helps: the dangerous answer (reject a real key) cannot happen, and the harmless answer (one extra lookup) is the only error.

A Bloom filter in front of the cache turns “every absent key hits the database” into “every absent key is rejected in memory”, safely — because a “no” is never wrong and a false “yes” costs only a lookup.

§3

Cuckoo — Bloom with deletion

probabilistic-data-structures.md.txt · Cuckoo

A Bloom filter cannot delete: clearing a bit might unset a bit another item relies on, breaking the no-false-negative guarantee. A Cuckoo filter stores small fingerprints in a cuckoo hash table, so it supports deletion. The commands are module commands, CF.*:

CF.RESERVE sessions 1000000
CF.ADD sessions "session:abc123"
CF.EXISTS sessions "session:abc123"
CF.DEL sessions "session:abc123"   # delete — what Bloom cannot do

Choose Bloom when the set only grows and inserts dominate; choose Cuckoo when items must leave the filter — tracking active sessions that expire, for instance, where a logged-out session should drop out of the set. Hover the columns below to compare the trade.

Bloom vs Cuckoo. Select a filter; the readout reports where it wins and what it costs.
Bloom (BF.*) bit array + k hashes delete: no insert: faster lookup: slightly slower module command Cuckoo (CF.*) fingerprints, cuckoo hash delete: yes insert: slightly slower lookup: faster module command

Bloom and Cuckoo answer the same membership question with the same one-sided error; Cuckoo adds deletion and faster lookups at a slightly slower insert. Reach for Cuckoo when items must leave the set.

§4

The EchoMQ contrast — exact membership

echo_mq/metrics.ex · echo_mq/jobs.ex

EchoMQ also answers a membership question — “have I already seen this idempotency key?” — but it answers it exactly, with a real key, not a filter:

echo/apps/echo_mq/lib/echo_mq/metrics.ex & jobs.ex · exact membershipfrozen
# metrics.ex — every id stored at a real key
def get_deduplication_job_id(conn, queue, dedup_id) do
  key = Keyspace.queue_key(queue, "de:" <> dedup_id)
  ...
end

-- jobs.ex — @enqueue, the exact dup-refusal by job key
if redis.call('EXISTS', KEYS[1]) == 1 then
  return 0
end

A Bloom filter's error is one-sided in the wrong direction for idempotency. It never wrongly says “absent” — but it can wrongly say “present”, a false positive. For a cache pre-check a false “present” is harmless (one extra real lookup). For dedup a false “present” means “already seen, drop it” — and the job is lost, silently. So EchoMQ stores every id exactly, pays O(n) memory, and accepts zero false positives.

the pattern

A Bloom (or Cuckoo) filter: membership at a fraction of the exact memory, no false negatives, a tunable false-positive rate. Safe in front of an expensive lookup.

EchoMQ (counter-example)

The emq:{q}:de:<dedupId> key (plus the @enqueue EXISTS refusal) is exact membership: O(n) memory, zero false positives. A false “already seen” would drop a job, so the filter's one-sided error is unacceptable here.

A Bloom filter's value is its one-sided error — a “no” is certain, so it is safe to skip work on it; a “yes” may be wrong, so confirm it. Use it where a false positive is cheap (a wasted cache lookup). Where a false positive is catastrophic — dropping a job — use the exact key EchoMQ uses.

/redis-patterns/data-modeling/primary-database/system-of-record

The exact-dedup home

The emq:{q}:de:<dedupId> key and the @enqueue EXISTS refusal are taught in full in R7.1, the system of record: the job HASH is the record of truth, and its membership check is exact for the same reason the dedup is.

/bcs

The architecture

The exact membership check follows from the Branded Component System discipline — the branded id is the identity the de: key is built from. The Branded Component System is the architecture EchoMQ is built to.

§5

References

sources · related

Sources

Related in this course