Big Data AcademyQuery · move · process · govern

Chapter 11 · Probabilistic Data Structures and Approximate Analytics

Cuckoo Filters: Membership, Deletion, Count Semantics, and Capacity Planning

Use Cuckoo filters only when deletion is justified by authoritative insertion provenance, and measure approximate membership/count behavior explicitly.

Intermediate165–200 minutesCuckoo deletion and capacity labRedis Open Source 8.10.1Free/local-firstLast reviewed: September 6, 2026

Learning outcomes

AtlasMart now needs a compact “recently processed token” filter where entries may be retired after their authoritative lifecycle ends. Cuckoo filters support membership plus deletion, but that extra power creates a deletion-safety constraint Bloom filters do not have.

01

Explain Cuckoo membership, fingerprints, buckets, false positives, and why deletion is possible.

02

Use CF.RESERVE/CF.ADD/CF.EXISTS/CF.COUNT/CF.DEL and interpret approximate multiplicity correctly.

03

Plan capacity, bucket size, expansion, and relocation work without universal tuning values.

04

Demonstrate the dangerous case: deleting an item that was never actually inserted can corrupt membership guarantees.

05

Choose Cuckoo versus Bloom versus exact Set based on deletion and false-positive costs.

Exact lab baseline

All Chapter 11 mandatory labs reuse the disposable Chapter 01 environment: Redis Open Source 8.10.1 from Docker Official Image redis:8.10.1, container atlasmart-redis-ch01, standalone topology, host publication 127.0.0.1:6379, TLS disabled only because traffic stays on loopback, default ACL user disabled, named users atlasmart-app and academy-admin, logical database 0, AOF with appendfsync everysec plus RDB snapshots, persistent /data, and no explicit maxmemory limit or eviction policy. Redis 8 integrates Bloom filters, Cuckoo filters, Count-Min Sketch, Top-K, and t-digest into Redis Open Source; HyperLogLog remains a long-standing core Redis data type. Fixtures stay under atlasmart:ch11:*. Mandatory work is local and uses deterministic synthetic AtlasMart data; no paid service, production endpoint, or real credential is required.

Redis 8 integration and ACL/version discipline

Redis 8 integrated five probabilistic structures that historically lived in RedisBloom/Redis Stack: Bloom filter, Cuckoo filter, Count-Min Sketch, Top-K, and t-digest. Redis 8 also added ACL categories @bloom, @cuckoo, @cms, @topk, and @tdigest, while these commands also participate in broader @read/@write/@fast/@slow categories. That can widen an old ACL rule after an upgrade, so verify effective permissions rather than assuming module-era ACL behavior. Redis 8.10.1 is a security release and specifically fixes a Count-Min Sketch RDB-loading memory-safety issue and a Top-K cleanup issue; do not downgrade the chapter lab to an older moving tag.

1. Cuckoo filters store compact fingerprints, not full elements

A Cuckoo filter stores short fingerprints in candidate buckets rather than retaining every original value. That allows compact probabilistic membership and supports removal of a fingerprint occurrence. Collisions are still possible, so positive membership and multiplicity remain approximate.

Need Bloom Cuckoo Exact Set
Negative membership certainty Yes under correct append-only use Yes under correct use Yes
Positive membership exactness No No Yes
Delete individual item No Yes, with strict precondition Yes
Enumerate members No No Yes
Compactness Very high High Lower as cardinality/member size grows

2. Reserve before inserting when capacity matters

redis-cli · create a bounded Cuckoo filter 
docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:cuckoo:tokensdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.RESERVE atlasmart:ch11:cuckoo:tokens 1000 BUCKETSIZE 2 MAXITERATIONS 20 EXPANSION 1docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.INFO atlasmart:ch11:cuckoo:tokens

capacity is the intended initial number of entries. BUCKETSIZE, MAXITERATIONS, and EXPANSION change memory, false-positive probability, insertion behavior, and growth. Do not copy values from a blog without a representative insert/query benchmark.

3. Add duplicates and observe approximate multiplicity

redis-cli · duplicates, membership, and count 
docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.ADD atlasmart:ch11:cuckoo:tokens token:abcdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.ADD atlasmart:ch11:cuckoo:tokens token:abcdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.ADD atlasmart:ch11:cuckoo:tokens token:defdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.EXISTS atlasmart:ch11:cuckoo:tokens token:abcdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.COUNT atlasmart:ch11:cuckoo:tokens token:abcdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.COUNT atlasmart:ch11:cuckoo:tokens token:missing

CF.COUNT returns an estimate of how many times an item was added. Redis documents that overestimation is possible but underestimation is not expected under the command’s model. That still does not make the count suitable for financial accounting.

4. Deletion removes one occurrence at a time

redis-cli · safe deletion of known inserts 
docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.DEL atlasmart:ch11:cuckoo:tokens token:abcdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.COUNT atlasmart:ch11:cuckoo:tokens token:abcdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.DEL atlasmart:ch11:cuckoo:tokens token:abcdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.EXISTS atlasmart:ch11:cuckoo:tokens token:abc

The crucial phrase is known inserts. Redis explicitly warns not to call CF.DEL for an item unless you are certain it was previously added.

5. Why deleting a merely “probably present” item is dangerous

A false positive means CF.EXISTS missing-item can occasionally return 1 because its fingerprint collides with a stored fingerprint. If your code then calls CF.DEL missing-item, it may remove another item’s fingerprint and create a false negative. This is a structural corruption of the filter’s intended membership behavior, not just a harmless failed delete.

Safe deletion rule

Only delete when an authoritative transaction/log says that exact item was previously inserted into this Cuckoo filter. Never use CF.EXISTS as the sole proof that makes CF.DEL safe.

6. CF.INFO is the capacity dashboard

redis-cli · inspect Cuckoo state 
docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.INFO atlasmart:ch11:cuckoo:tokensdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app MEMORY USAGE atlasmart:ch11:cuckoo:tokens

Track size, bucket count, number of sub-filters, items inserted/deleted, bucket size, expansion rate, and max iterations. Operationally, growth in sub-filter count and insertion retries matters as much as the nominal capacity.

7. Validate Cuckoo estimates against exact ground truth

A probabilistic filter must be evaluated against an exact reference dataset. For AtlasMart, keep an exact insertion log or Counter in the test harness, then compare CF.EXISTS and CF.COUNT with that ground truth. Present-item trials should not produce false negatives under correct operation; absent-item trials reveal the observed false-positive rate; multiplicity comparisons reveal any overestimation. The exact log—not CF.EXISTS—also determines whether a later CF.DEL is authorized.

python · ground-truth harness for Cuckoo membership and counts 
from collections import Counterinserted = ["token:abc", "token:abc", "token:def"]exact_counts = Counter(inserted)# Compare these exact counts with CF.COUNT results from the Redis lab.for item in ["token:abc", "token:def", "token:missing"]:    print(item, "exact_count=", exact_counts[item], "was_inserted=", item in exact_counts)# Only the authoritative insertion record authorizes a CF.DEL demonstration.assert exact_counts["token:abc"] == 2assert exact_counts["token:missing"] == 0

This harness does not simulate Cuckoo hashing; it supplies the exact ground truth needed to score Redis observations. Record false positives separately from count overestimation so one error model is not mistaken for the other.

8. ADDNX/INSERTNX are not exact uniqueness guards

Cuckoo NX variants decide based on probabilistic membership. A false positive can suppress insertion of a truly new value. Use them only when occasional false-positive suppression is acceptable. For idempotency keys, payments, inventory, or uniqueness constraints, use an exact authoritative mechanism.

8. Capacity planning is workload-specific

A larger bucket can improve fill ratio but raise false-positive probability; more relocation iterations may improve insertion success but cost CPU; expansion adds sub-filters and query work. Measure inserted cardinality, duplicate rate, positive/negative query mix, false-positive trials, bytes/item, insert p95/p99, and sub-filter growth on representative data.

9. Controlled failure injection: fixed small capacity

Create a separate tiny non-production fixture and push it toward its capacity so you can observe insertion failure or expansion behavior without touching the main lab key. The exact threshold depends on configuration and hash placement, so the lesson does not fabricate the insertion number at which failure must happen.

redis-cli · tiny isolated capacity fixture 
docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:cuckoo:tinydocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.RESERVE atlasmart:ch11:cuckoo:tiny 10 BUCKETSIZE 1 MAXITERATIONS 5 EXPANSION 1docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.INFO atlasmart:ch11:cuckoo:tiny

11. Cluster and persistence boundaries

Single-key Cuckoo operations route naturally by key. Persistence and replication preserve the filter state but not original values. If an operational requirement says “rebuild every filter from source,” keep the source-of-truth event/member data elsewhere and test rebuild time. Never treat a Cuckoo-filter backup as a list of the original tokens.

12. Wrong approach: use CF.COUNT for exact license billing

Approximate multiplicity can overestimate. A billing counter that charges based on CF.COUNT therefore violates exact-accounting requirements. Use an exact integer/ledger for billing and reserve Cuckoo counts for approximate operational signals.

12. Reproducible cleanup

redis-cli · remove Cuckoo fixtures 
docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:cuckoo:tokens atlasmart:ch11:cuckoo:tiny

13. Production judgment

Choose Cuckoo when compact probabilistic membership plus deletion is materially useful and you can guarantee deletion provenance. Monitor false positives, deletion count, sub-filter growth, memory, insertion failures, and query latency. Use exact Sets when false positives/false negatives are unacceptable, and Bloom when you do not need deletion and want a simpler membership/error model.

14. Summary and next step

Cuckoo filters add deletion and approximate multiplicity to probabilistic membership, but deletion is safe only for known inserts. Lesson 4 shifts from membership to frequency, heavy hitters, and quantiles using three different sketches with three different error models.

Check your understanding

  1. What makes Cuckoo deletion possible compared with Bloom?
  2. Why is CF.EXISTS not enough proof to call CF.DEL safely?
  3. Can CF.COUNT overestimate multiplicity?
  4. When should you prefer an exact Set?
  5. What does persistence fail to preserve?
Review the answers

Cuckoo filters store removable fingerprint occurrences in buckets.

A positive can be a false positive; deleting it can remove another item’s colliding fingerprint and create false negatives.

Yes; the command documents possible overestimation.

When membership/deletion/enumeration must be exact.

The original full member identities are not recoverable from the probabilistic filter alone.

Authoritative references

Keep knowledge open

Help the academy stay free and grow.

If these tutorials save you time, a small donation supports new lessons, technical review, diagrams, examples, and long-term maintenance.

ETHEthereum / ERC-20 only
0x716c4Ab160C4B66F31a28AE2448BfF68fc3a2ef0

Send only Ethereum or ERC-20 compatible assets to this address.