skip to content

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?

level: middleimportance: should knowfreq 38%

answer

  1. one question shape per structure
  2. membership, frequency, heavy hitters, quantiles
  3. named item versus unnamed items
  4. over-count, false yes, misrank, estimate

basics

~20 s

Use 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 s

Redis 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
plaintext
> 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

for a junior

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.

for a middle

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.

for a senior

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.

for a principal

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.