System Design Cases
Probabilistic Data Structures Overview
Probabilistic Data Structures Overview — concept page covering five families of sketches (Bloom, Cuckoo, HyperLogLog, Count-Min Sketch, t-digest) with comparison vs exact baselines (HashSet, HashMap, sorted array). Six animated scenarios: family overview, Bloom dedup, HLL count distinct, CMS heavy hitters, t-digest percentile, and trade-offs comparison. One ADR on probabilistic vs exact decision criteria.
Probabilistic data structures
Probabilistic structures trade exactness for bounded memory and fast operations. The correct choice starts with the query, the error direction, and the failure policy.
Do not treat "approximate" as one contract
| Structure | Query | Normal answer semantics |
|---|---|---|
| Bloom filter | membership | no-match is absent; match is maybe, under no-false-negative lifecycle assumptions |
| Cuckoo filter | membership + deletion | no-match is absent; fingerprint match is maybe; insertion can fail |
| Count-Min Sketch | point frequency | for nonnegative streams, a one-sided overestimate with an additive probabilistic bound |
| HyperLogLog | distinct count | a statistical cardinality estimate with precision-dependent error |
These guarantees are not interchangeable. CMS does not answer membership exactly; HLL cannot return which elements exist; a Bloom or cuckoo filter does not count frequency.
End-to-end guarantee includes lifecycle
The theorem assumes more than an inner loop. Production correctness also depends on:
- stable hash functions, seeds, normalization, and namespace;
- parameter and counter/register widths;
- atomic rebuild and generation publication;
- overflow, saturation, and insertion-failure handling;
- merge compatibility and retry semantics;
- time-window/expiry semantics;
- concurrency control and durable authority.
A failed cuckoo insertion can create a false negative if the application pretends it succeeded. A wrapped CMS counter invalidates its bound. A partial Bloom rebuild can create false negatives. Adding one CMS partial twice double-counts it; HLL max-merge is idempotent.
Decision policy
Approximate negatives/positives may be used to reduce exact work only when the selected error direction is safe. Money, access control, legal retention, hard quota, irreversible deletion, and deduplication invariants need an exact authoritative path. Around thresholds, escalate rather than converting a confidence statement into a fact.
Sizing and measurement
Derive parameters from expected cardinality/mass and an explicit error budget. Monitor load, empirical error against samples, failed inserts, saturation, merge lag, and generation mismatch. Test adversarial/skewed inputs and restart/rebuild paths.
Diagram scenarios
The animation distinguishes Bloom, cuckoo, CMS, and HLL semantics, chooses by question, escalates to exact state, and fails closed on lifecycle faults.