skip to content

Bloom, Cuckoo & Top-K

Bloom and cuckoo filters, count-min sketch, top-k and t-digest are built into Redis 8. Interviewers ask which one answers a given question, and what its error means for the caller.

part ofRedisread it →
on this pageshow

explore

questions

6

With Redis BF.RESERVE, what do error_rate, capacity, EXPANSION and NONSCALING decide for a sign-up username filter, and what do BF.ADD and BF.EXISTS replies mean?

level: middleimportance: should knowfreq 46%

answer

  1. error rate comes before capacity
  2. memory versus rate
  3. sub-filters stack past capacity
  4. BF.ADD 0 is not an error
  5. missing key also replies 0

basics

~20 s

BF.RESERVE key error_rate capacity sets the false-positive target and expected items; EXPANSION sizes extra sub-filters and NONSCALING forbids them. BF.ADD replies 1 if new, 0 if probably present. BF.EXISTS 1 means probably added; 0 means not added, or no such key.

solid answer

~40 s

`BF.RESERVE key error_rate capacity` comes in that order: `0.001 50000000` asks for 0.1% over 50 million names, about 90 MB by the documented 14.378 bits per item, a little more in a scaling filter. Past `capacity`, a scaling filter stacks a sub-filter sized by `EXPANSION` (default 2), so memory and check time grow while the rate stays bounded. `NONSCALING` saves a little memory, and at capacity a new item gets `ERR non scaling filter is full`. On the sign-up path, `BF.EXISTS` replying `0` means the name was definitely not added, so create the user and call `BF.ADD`; `1` means check the database or refuse. `BF.ADD` replies `1` when new and `0` when probably present. A missing key also makes `BF.EXISTS` reply `0`, so the database's unique constraint stays the authority.

code

plaintext · 18 lines
plaintext
> BF.RESERVE signup:usernames 0.001 50000000
OK
> BF.RESERVE signup:usernames 0.001 50000000
(error) ERR item exists
> BF.ADD signup:usernames "ada"
(integer) 1
> BF.ADD signup:usernames "ada"
(integer) 0
> BF.EXISTS signup:usernames "ada"
(integer) 1
> BF.RESERVE signup:frozen 0.001 2 NONSCALING
OK
> BF.ADD signup:frozen "a"
(integer) 1
> BF.ADD signup:frozen "b"
(integer) 1
> BF.ADD signup:frozen "c"
(error) ERR non scaling filter is full

go deeper

for a junior

Recall the argument order, rate then capacity, and the meaning of each reply: 1 from BF.ADD is new, 0 is probably present, and 0 from BF.EXISTS is definitely not added.

for a middle

Explain what EXPANSION and NONSCALING do at capacity and predict the memory using the bits-per-item figures. Know the defaults a first BF.ADD applies when it creates the key.

for a senior

Diagnose a filter past capacity with BF.INFO, and explain why the rate holds while memory and check time grow. Describe rebuilding from the database with both keys written until the swap.

for a principal

Decide whether teams may rely on auto-creation at all, who owns the capacity number, and which alert fires when a filter gains a second sub-filter. Reserving with headroom is cheaper than a rebuild.

## The command In Redis 8.10 the syntax is `BF.RESERVE key error_rate capacity [EXPANSION expansion] [NONSCALING]`. The rate comes first, a decimal between 0 and 1, so `0.001` means 0.1%. Swapping the two numbers fails with an error, because `1000000` is outside the allowed rate range. Reserving a key that already exists fails with `ERR item exists`. | Argument | What it decides | Value if `BF.ADD` creates the key | |---|---|---| | `error_rate` | Upper bound on false positives, and so bits per item | `bf-error-rate`, default `0.01` | | `capacity` | Items the first sub-filter holds before growth is needed | `bf-initial-size`, default `100` | | `EXPANSION` | Each new sub-filter's size, as a multiple of the last one | `bf-expansion-factor`, default `2` | | `NONSCALING` | No new sub-filters: adding past capacity fails | Off | The `bf-*` settings are ordinary configuration from Redis 8.0, readable and settable with `CONFIG GET` and `CONFIG SET`. Rates above `0.25` are capped at `0.25` with a warning in the log, and the source accepts capacities up to 2^30. ## Reading the replies on a sign-up path - **`BF.EXISTS` replies `0`:** the name was definitely not added, so the application can skip the database read, create the user and call `BF.ADD`. - **`BF.EXISTS` replies `1`:** the name was probably added. The docs give two choices: check the main database, or refuse the name. Refusing means a small share of free names get turned away. - **`BF.ADD` replies `1`:** the item looked new and was recorded. - **`BF.ADD` replies `0`:** the item looks already present. This is not an error, and it can be a false positive for a name nobody has used. Nothing new is recorded, which does no harm because the filter already answers yes for that name. - **A missing key:** `BF.EXISTS` also replies `0` when the key does not exist, and the source treats a wrong-type key the same way. A definite no holds only while the filter exists and was fully loaded. The filter never replaces the database's unique constraint: two simultaneous sign-ups can both see `0`. ## Memory The docs give these figures: **9.585 bits per item at 1%**, **14.378 at 0.1%** and **19.170 at 0.01%**. For 50 million usernames at 0.1%, that comes to about 90 MB with `NONSCALING`. A scaling filter costs a little more. The RedisBloom source builds its first sub-filter at half the requested rate and halves the rate again for each later sub-filter, keeping the sum under your target. The same reservation is therefore about 99 MB. `BF.INFO key SIZE` reports what was actually allocated. ## What happens past capacity Suppose the filter was reserved for 1 million names at 0.1% with the default `EXPANSION 2`, and now holds 40 million. 1. **The rate stays bounded.** Sub-filters of 1, 2, 4, 8, 16 and 32 million names were added, each at a tighter rate. 2. **Memory roughly doubles.** Those six sub-filters allocate about 171 MB, against about 79 MB for a filter reserved at 40 million from the start. 3. **Reads and writes slow down.** A new name has to be checked against every sub-filter, for `BF.EXISTS` and for `BF.ADD`, since `BF.ADD` tests for presence before it inserts. A `NONSCALING` filter takes the other path: an already-present item still replies `0`, and a new one gets `ERR non scaling filter is full`. The sign-up path has to handle that error, or sign-ups fail on the day the count is reached. ## Choosing the numbers - **The rate:** if every `1` triggers a database read, the rate sets how many needless reads you pay for: at 0.1%, about one in a thousand free names. Tightening from 1% to 0.1% costs about 4.8 more bits per item, by the figures above. - **Known size:** reserve the expected total with headroom. The docs recommend `EXPANSION 1` when the item count is known, to reduce memory. - **Unknown size:** keep `EXPANSION` at 2 or more, so that there are fewer sub-filters. - **Many small filters:** a small capacity with a higher `EXPANSION` suits one filter per user or product, where most stay small and a few grow. - **Never rely on auto-creation.** A filter made by a first `BF.ADD` has capacity 100 at 1%, so a large set quickly becomes a long stack of sub-filters.

  • A filter reserved for 1 million names now holds about 40 million. How do you confirm it and fix it?
    BF.INFO shows Number of filters above 1, a Size well over what the item count needs, and a Number of items inserted far past the original reservation. To fix it, reserve a new key at the real size, re-add every name from the database while writing new names to both, then RENAME it over the old key. BF.SCANDUMP copies the existing structure and does not resize it.
  • Why might BF.CARD report fewer items than the number of distinct names you added?
    BF.CARD counts items detected as unique, meaning those that caused at least one bit to be set. A new name that happens to be a false positive is not recorded, so it is not counted. The shortfall stays small at a low error rate, but BF.CARD is an estimate rather than a row count.
  • When is EXPANSION 1 the wrong choice?
    When the set keeps growing past its reservation. Each new sub-filter is then the same size as the last, so reaching 40 million from 1 million takes 40 sub-filters instead of 6, and a new name must be checked against all of them. The docs recommend EXPANSION 1 only when the item count is known.

  • BF.RESERVE takes capacity first and the error rate second.
  • BF.ADD replying 0 means the command failed and should be retried.
  • Going past capacity on a scaling filter makes the false-positive rate climb without limit.
  • A NONSCALING filter keeps accepting new items at capacity and only loses accuracy.
  • A BF.ADD that creates its key picks a capacity suited to the expected data.
  • Since BF.EXISTS can say no with certainty, the database's unique constraint can be dropped.

Assumes Redis 8.10; the bf-error-rate, bf-initial-size and bf-expansion-factor settings are the Redis 8.0 and later form, replacing arguments passed when loading the module.

open as a page

Redis Top-K and t-digest keys have no time window, so how do you serve a last-hour trending panel and a last-hour latency percentile from them?

level: middleimportance: should knowfreq 24%

basics

~20 s

Neither key has a clock: Top-K decay reacts to collisions, not time, and t-digest observations cannot be removed. Use one key per time bucket with EXPIRE. TDIGEST.MERGE combines buckets, but Top-K has no merge command, so stagger its sketches.

open as a page

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%

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.

open as a page

A Redis cuckoo filter of unused coupon codes starts rejecting valid codes after weeks of CF.DEL calls: what went wrong, and how do you repair and prevent it?

level: seniorimportance: should knowfreq 26%

basics

~20 s

CF.DEL removes a matching fingerprint, not the item. Deleting a code that was never added, or deleting one twice, can erase another code's fingerprint, causing false negatives. Rebuild the filter from the database and delete only after it confirms the code.

open as a page

When should a team accept a Redis Bloom, count-min, top-k or t-digest answer in a user-visible feature, and what standing rules does a lead set first?

level: principalimportance: should knowfreq 18%

basics

~20 s

Accept one when a wrong answer is cheap or an exact store can confirm it, and an exact structure costs too much. First require a stated error direction, explicit sizing, a rebuild path and a plan for losing the key.

open as a page

A fraud feature counts events per card with Redis CMS.INCRBY, and cards with few events report counts in the hundreds: why, and how should the sketch be sized and used?

level: seniorimportance: nice to knowfreq 20%

basics

~20 s

Count-min estimates over-count through collisions, by up to about error times the sketch's total count, so low counts are noise. Set error from the smallest count you must trust, rotate sketches per time window, and confirm against exact data before acting.

open as a page