In Redis 8, which probabilistic structure fits a username check, per-card counts, a trending panel and latency percentiles, and how does each one err?
answer
- one question shape per structure
- membership, frequency, heavy hitters, quantiles
- named item versus unnamed items
- over-count, false yes, misrank, estimate
basics
~20 sUse Bloom for the username check, count-min for per-card counts, top-k for trending and t-digest for percentiles. Bloom can falsely say yes, count-min over-counts, top-k can miss or misrank items, and t-digest returns an estimate.
solid answer
~40 sRedis 8 ships these structures in Redis Open Source, and each answers one shape of question. A username check is membership, so `BF.RESERVE` and `BF.EXISTS`: a `1` can be false, a `0` is definite while the key exists. Per-card counts are the frequency of a named item, so `CMS.INITBYPROB`, `CMS.INCRBY` and `CMS.QUERY`: estimates err upward, by an amount tied to the total count. A trending panel asks for items you cannot name in advance, so `TOPK.RESERVE`, `TOPK.ADD` and `TOPK.LIST`: items can be missed or misranked. Percentiles need `TDIGEST.CREATE`, `TDIGEST.ADD` and `TDIGEST.QUANTILE`: the value is an estimate, guaranteed exact only at 0 and 1. Cuckoo is the membership alternative when you need `CF.DEL`, at a false-positive floor near 0.78%.
code
plaintext · 19 lines> BF.RESERVE signup:usernames 0.001 1000000
OK
> BF.ADD signup:usernames "ada"
(integer) 1
> CMS.INITBYPROB fraud:card-events 0.001 0.002
OK
> CMS.INCRBY fraud:card-events card-42 3
1) (integer) 3
> TOPK.RESERVE trending:items 5 2000 7 0.925
OK
> TOPK.ADD trending:items sku-1 sku-2
1) (nil)
2) (nil)
> TDIGEST.CREATE latency:api COMPRESSION 1000
OK
> TDIGEST.ADD latency:api 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5
OK
> TDIGEST.QUANTILE latency:api 0.5
1) "4"go deeper
Recall one question per structure: seen or not, how often, which are the most frequent, what value sits at a percentile. Being able to name the write and read command for each is enough.
Explain why the shape of the question decides the structure, and state each one's error direction. Mention which commands create a key on first write and which reply with an error.
Show what each error does to the caller: a false yes on a username, an inflated count on a card, a trending item that never surfaces. Name the confirmation step that makes the error safe.
Treat the choice as a decision about who absorbs the error and what keeps the exact answer available. Be ready to argue for an exact structure when the set is small enough to afford it.
## Five structures, five question shapes Redis 8 ships five **probabilistic data structures** in Redis Open Source. Each gives an approximate answer in exchange for far less memory than storing every item. Choosing one is mostly a matter of naming the shape of the question, because each structure answers one shape well and the others badly. | Question shape | Structure | Write | Read | How it errs | |---|---|---|---|---| | Was this item seen? | Bloom filter | `BF.ADD` | `BF.EXISTS` | `1` can be false; `0` is definite while the key exists | | Was it seen, and can I remove it? | Cuckoo filter | `CF.ADD`, `CF.DEL` | `CF.EXISTS` | `1` can be false; a bad delete makes `0` false too | | How often did this named item occur? | Count-min sketch | `CMS.INCRBY` | `CMS.QUERY` | Over-counts, by an amount tied to the total count | | Which items are most frequent? | Top-K | `TOPK.ADD` | `TOPK.LIST` | Can miss or misrank items; counts are not reliable | | What value sits at this percentile? | t-digest | `TDIGEST.ADD` | `TDIGEST.QUANTILE` | Estimate, guaranteed exact only at 0 and 1 | Counting distinct items is a sixth shape, answered by HyperLogLog rather than by any of these five. ## The four scenarios - **Sign-up username check: Bloom.** The caller names one item and wants yes or no. `BF.RESERVE` fixes the false-positive target and the expected number of items. When `BF.EXISTS` replies `1`, the application either checks the main database or refuses the name, which is the choice the Redis docs describe for this use case. - **Fraud feature counting events per card: count-min.** The caller names the card and wants a number. `CMS.INCRBY` adds to it and `CMS.QUERY` reads it. The estimate is never below the true count unless a counter saturates, so the failure is a card that looks busier than it is. Results below `error * total_count` are noise, so very low counts need a much wider sketch. - **Trending-items panel: Top-K.** The caller cannot name the items, which rules out count-min and Bloom: neither has a command that lists what it holds. `TOPK.LIST` returns up to `k` items, sorted by decreasing count estimate. - **Latency percentile report: t-digest.** The question is about the distribution of a value. `TDIGEST.QUANTILE` takes a fraction, so p99 is `0.99`. Sketches from several servers combine with `TDIGEST.MERGE`, which averaging per-server percentiles cannot do correctly. ## Bloom or cuckoo Both answer membership, and the choice comes down to three facts: 1. **Deletion.** `CF.DEL` exists; there is no `BF.DEL`. A Bloom filter only grows until you replace the key. 2. **Rate control.** `BF.RESERVE` takes the rate directly as `error_rate`. `CF.RESERVE` has no rate argument: the rate follows from an 8-bit fingerprint and `BUCKETSIZE`, with a documented floor of about 0.78% at `BUCKETSIZE 1`. A 0.1% target therefore means Bloom. 3. **Workload.** The docs describe Bloom as typically better for inserts and cuckoo as quicker for checks, so a write-heavy set leans to Bloom. ## Differences that catch people out - **Creation.** `BF.ADD` and `CF.ADD` create a default-sized filter on a missing key. `CMS.INCRBY`, `TOPK.ADD` and `TDIGEST.ADD` reply with an error, so those three must be created first. - **Missing keys on read.** `BF.EXISTS` and `CF.EXISTS` reply `0` on a missing key, while `CMS.QUERY` and `TOPK.LIST` reply with an error. A lost filter therefore looks like an empty one. - **Counts on Top-K.** `TOPK.COUNT` is deprecated, and its page says the value does not represent the number of appearances. If the number itself matters, count-min is the structure that holds it. - **Sizing inputs.** Bloom is sized from a rate and a capacity, cuckoo from a capacity and a bucket size, `CMS.INITBYPROB` from an error and a probability, `TOPK.RESERVE` from `k`, width, depth and decay, and `TDIGEST.CREATE` from `COMPRESSION`. - **Merging.** `CMS.MERGE` and `TDIGEST.MERGE` combine sketches. Top-K and the two filters have no merge command. ## Packaging These commands are part of Redis Open Source from 8.0, included in all binary distributions, with their own ACL categories: `@bloom`, `@cuckoo`, `@cms`, `@topk` and `@tdigest`. Earlier releases needed the RedisBloom module or Redis Stack. A build from a git checkout gets them from `redis-full.conf`, or from a release tarball's `redis.conf`; a plain build started without that configuration does not have them. A command page's `since` value, such as `1.0.0` on `BF.EXISTS`, is the module's own history rather than a Redis release.
- The fraud team asks for the top 20 riskiest cards from the same count-min sketch. Can it answer that?Not by itself. A count-min sketch only answers about items you name through CMS.QUERY, and it has no command that lists what it holds. To get the leaders, feed a Top-K sketch from the same stream and read TOPK.LIST, then use CMS.QUERY for each card's number, since TOPK.COUNT is deprecated.
- Can a cuckoo filter replace Bloom on the sign-up path if usernames are sometimes released?Yes, if the target rate allows it. CF.DEL handles released names, but CF.RESERVE has no rate argument: the documented floor is about 0.78%, and the default bucket size of 2 is worse. Each CF.DEL must also match a name that really was added, or it can erase another name's fingerprint.
- A Redis Bloom filter can report how many times an item was added.
- A count-min sketch can list its most frequent items without being told which items to query.
- The counts returned by TOPK.COUNT are exact appearance totals for each item.
- TDIGEST.QUANTILE takes a percent, so p99 is written as 99.
- Redis 8 binaries still need RedisBloom installed separately to get these commands.
Assumes Redis 8.10; these five structures have been part of Redis Open Source since 8.0, and older releases needed the RedisBloom module or Redis Stack.