Choose Approximate Structures When Memory Savings Outweigh Exactness Requirements

Learning outcomes

AtlasMart now has six candidate approximate structures. The final problem is not command syntax; it is deciding whether the memory/latency benefit is worth the business consequences of approximation, and proving that decision with an evaluation harness.

1. Start from the question, not the Redis command

2. Approximation is safe only when the downstream decision tolerates its error mode

A 1% Bloom false-positive target may be trivial for “do an unnecessary cache lookup,” but unacceptable for “deny customer access.” A 0.81% HLL standard error may be excellent for dashboard DAU but inappropriate for per-customer billing. The same numeric error can have radically different business cost depending on which side of a decision boundary it pushes.

3. Write an acceptance contract before benchmarking

4. One deterministic exact baseline should feed all approximate candidates

from collections import Counterfrom math import ceil# Deterministic AtlasMart fixture. Redis is not involved in this exact baseline.events = [    "u01","u02","u03","u01","u04","u05","u02","u06","u01","u07",    "u08","u09","u10","u03","u11","u12","u13","u01","u14","u15",]exact_unique = len(set(events))exact_freq = Counter(events)print("exact unique:", exact_unique)print("u01 exact frequency:", exact_freq["u01"])print("top exact:", exact_freq.most_common(5))# For a quantile ground truth, pick an explicit rank convention and document it.latencies = sorted([18,21,19,23,22,24,25,20,28,31,26,27,35,29,30,42,38,33,40,55])def nearest_rank(q):    i=max(0,min(len(latencies)-1,ceil(q*len(latencies))-1))    return latencies[i]for q in (0.5,0.9,0.99):    print(q, nearest_rank(q))

5. Measure error distributions, not a single happy-path output

Repeat trials across different deterministic seeds/data partitions, cardinalities, skews, and query mixes. Report median and tail error, not only mean error. For Bloom/Cuckoo, separate present-item and absent-item trials. For CMS, stratify head/tail frequencies. For Top-K, report precision/recall of heavy-hitter membership. For t-digest, report error by quantile because tails often matter most.

6. Memory savings include structure overhead and scaling behavior

Do not compare theoretical bits/item alone. Capture actual Redis memory after realistic population. HLL sparse-to-dense transitions, Bloom/Cuckoo sub-filters, CMS width/depth, Top-K heap/sketch state, t-digest centroids, allocator overhead, replication buffers, AOF growth, and fork headroom all contribute to capacity planning.

docker exec -e REDISCLI_AUTH=AtlasMart-Admin-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user academy-admin INFO memorydocker exec -e REDISCLI_AUTH=AtlasMart-Admin-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user academy-admin MEMORY STATSdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app MEMORY USAGE atlasmart:ch11:decision:hlldocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app MEMORY USAGE atlasmart:ch11:decision:bloomdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app MEMORY USAGE atlasmart:ch11:decision:cuckoo

7. Wrong comparison: different capacity/error targets

A Bloom filter configured for 10 million items at 0.1% false positives is not fairly compared with a Cuckoo filter configured for 100,000 items at default parameters. Match expected cardinality, query mix, deletion requirements, target false-positive impact, and evaluation dataset before comparing bytes or latency.

8. Exactness is part of correctness in some domains

Prefer exact state for payment ledgers, inventory quantities, quota enforcement, legal/audit counts, authorization, idempotency guarantees, and any operation where a false positive/negative changes a contractual state transition. Approximate structures can still sit beside the exact system for observability, candidate filtering, or capacity planning.

9. Approximate structures can be layered safely

A common architecture is probabilistic prefilter → exact verification. Bloom might avoid expensive lookups for definite negatives; Cuckoo might reduce candidate work; CMS/Top-K might nominate suspicious hot products for exact investigation; t-digest might alert on tail-latency trends that trigger a precise trace query. The approximate layer accelerates discovery without becoming the final authority.

10. Rebuildability is a first-class operational requirement

Most probabilistic structures discard information. If the key is corrupted, evicted, accidentally deleted, or incompatible after an upgrade, you need an authoritative event/member/sample source to rebuild it. Define maximum rebuild time, source retention, replay order, merge strategy, and rollback before relying on the sketch for an operational decision.

11. Persistence, replication, and Cluster are not hidden details

Large sketch writes participate in AOF/RDB persistence and replication. Multi-key merges such as PFMERGE, CMS.MERGE, and TDIGEST.MERGE need Cluster slot locality. Replication is asynchronous, failover can lose acknowledged writes depending on topology/settings, and persistence does not transform an approximate structure into exact state.

12. Security boundary: Redis 8 ACL expansion can widen old roles

After Redis 8 integration, broad +@read +@write roles include commands from the new probabilistic families. Review existing ACLs, use named users, constrain key patterns, test with ACL DRYRUN, and avoid exposing analytics keys across tenants merely because their contents are approximate.

docker exec -e REDISCLI_AUTH=AtlasMart-Admin-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user academy-admin ACL DRYRUN atlasmart-app BF.RESERVE atlasmart:ch11:acl:test 0.01 10docker exec -e REDISCLI_AUTH=AtlasMart-Admin-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user academy-admin ACL DRYRUN atlasmart-app CMS.INITBYPROB atlasmart:ch11:acl:cms 0.01 0.01docker exec -e REDISCLI_AUTH=AtlasMart-Admin-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user academy-admin ACL DRYRUN atlasmart-app TDIGEST.CREATE atlasmart:ch11:acl:td

13. Version gate and security patch gate

Record redis_version, container digest/tag, chosen client version, command availability, and restore compatibility in every benchmark artifact. Redis 8.10.1 specifically fixes CMS and Top-K memory-safety issues during RDB/cleanup paths, so “works on Redis 8” is not a sufficiently precise production statement.

14. Migration strategy: shadow before cutover

When replacing exact analytics with a sketch, dual-write exact and approximate paths for a representative period. Compare outputs and operational cost, then switch only the read path after acceptance. Keep rollback simple: exact source remains authoritative. If replacing one sketch configuration with another, build a new versioned key in parallel rather than mutating assumptions invisibly.

15. Capstone lab: build a tiny decision matrix

Create six bounded fixtures under atlasmart:ch11:decision:*, populate them from the same deterministic event source, then record exact answer, approximate answer, absolute/relative error, Redis memory, and query latency. Do not copy expected latency numbers from this lesson; your machine is the evidence source.

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:decision:hll atlasmart:ch11:decision:bloom atlasmart:ch11:decision:cuckoo atlasmart:ch11:decision:cms atlasmart:ch11:decision:topk atlasmart:ch11:decision:tddocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app PFADD atlasmart:ch11:decision:hll u01 u02 u03 u01 u04docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.RESERVE atlasmart:ch11:decision:bloom 0.01 100docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CF.RESERVE atlasmart:ch11:decision:cuckoo 100docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app CMS.INITBYPROB atlasmart:ch11:decision:cms 0.01 0.01docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TOPK.RESERVE atlasmart:ch11:decision:topk 3 64 7 0.9docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app TDIGEST.CREATE atlasmart:ch11:decision:td COMPRESSION 100

16. Acceptance checklist

• The exact business question is written in one sentence.
• The sketch’s error direction/model is documented, not just called “approximate.”
• Capacity/error/compression parameters come from measured workload assumptions.
• Ground truth is deterministic and independent of Redis.
• Error distribution and p50/p95/p99 latency are measured on representative cardinality.
• Memory includes actual Redis accounting and scale-out overhead.
• False-positive/overestimate/under-rank/tail-error business consequences are tested.
• Persistence, replication, Cluster slot locality, ACLs, patch version, rebuild, and rollback are part of the review.

17. Cleanup

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:decision:hll atlasmart:ch11:decision:bloom atlasmart:ch11:decision:cuckoo atlasmart:ch11:decision:cms atlasmart:ch11:decision:topk atlasmart:ch11:decision:td atlasmart:ch11:acl:test atlasmart:ch11:acl:cms atlasmart:ch11:acl:td

18. Production judgment

Probabilistic structures are a deliberate correctness trade: lower memory/CPU or faster streaming analytics in exchange for specific uncertainty. Use them where error has bounded business cost and exact verification/reconciliation is available when needed. Reject them where approximate output would violate a state-machine, accounting, security, compliance, or customer guarantee. Operational maturity means knowing how to measure the error, rebuild the state, patch the server, and roll back the design.

19. Summary and bridge to Chapter 12

You can now choose probabilistic structures by question and error model rather than novelty. Chapter 12 continues the “bounded state plus explicit retention” theme with Redis Time Series and geospatial workloads, where timestamp semantics, labels, retention, duplicate policy, aggregation, and coordinate/radius behavior become the next set of precise contracts.

Authoritative references

• Redis probabilistic data types — current integrated probabilistic data-structure overview
• Redis data types — current Redis data-type surface
• HyperLogLog — cardinality-estimation model and operations
• PFADD — HyperLogLog insertion semantics
• PFCOUNT — standard error, memory, and union-count semantics
• PFMERGE — persistent HLL union/merge semantics
• Bloom filter — Bloom membership model and examples
• BF.RESERVE — capacity, false-positive rate, scaling, and memory formulas
• BF.INFO — Bloom capacity/filter/memory evidence
• Cuckoo filter — Cuckoo membership/deletion tradeoffs
• CF.DEL — safe deletion requirement and corruption warning
• CF.COUNT — Cuckoo multiplicity estimate semantics
• Count-Min Sketch — frequency-estimation model
• CMS.INITBYPROB — error/probability sizing controls
• CMS.MERGE — same-dimension merge and weights
• Top-K — HeavyKeepers-based heavy-hitter model
• TOPK.LIST — ranked top-k output and WITHCOUNT
• TOPK.COUNT — deprecated count command and undercount note
• t-digest — percentile/CDF model and merge operations
• TDIGEST.CREATE — compression versus memory/accuracy tradeoff
• TDIGEST.QUANTILE — quantile estimate semantics
• TDIGEST.INFO — observations, nodes, compression, memory evidence
• Probabilistic command compatibility — current command/Redis product compatibility matrix
• Redis 8.0 release notes — integrated probabilistic features and ACL-category change
• Redis 8.10 release notes — 8.10.1 security baseline for CMS/Top-K