RedisBloom: Probabilistic Data Structures Beyond HyperLogLog

1. Where HyperLogLog Reaches Its Limits

HyperLogLog answers a single question very efficiently: how many distinct elements were seen. For the often equally important question of whether one specific element has already been seen, HyperLogLog was never designed, it only provides the cardinality of a set, not membership information about a single element.

RedisBloom closes exactly this gap with a family of probabilistic data structures, each optimized for a different question: has this element already been seen, which elements occur most frequently, and how can a membership test also be reversed, something classic Bloom filters fundamentally cannot do.

2. Bloom Filters: Basic Principle and False-Positive Rate

A Bloom filter is a fixed-size bitmap together with several hash functions. When adding an element, several bit positions are set based on the hash functions; on a query, it is checked whether all relevant bits are set. If they are not, the element was definitely not present, if they are, the element was probably present, but not certainly, because different elements can set the same bits.

This uncertainty is called the false-positive rate and can be explicitly configured when creating the filter: a lower false-positive rate requires more bits per element and thus more memory, a higher rate saves memory but risks more frequent false hits. RedisBloom lets you set this error rate explicitly when creating the filter instead of accepting it implicitly.

redis-cli BF.RESERVE seen_articles:user4711 0.01 100000

redis-cli BF.ADD seen_articles:user4711 article:9981

redis-cli BF.EXISTS seen_articles:user4711 article:9981
# 1

redis-cli BF.EXISTS seen_articles:user4711 article:1234
# 0 or 1 (a 1 could be a false positive, at rate 0.01)

3. Practical Example: Has This Article Already Been Seen

A classic e-commerce use case is the question of whether a user has already viewed a specific product, for example to avoid showing already-seen recommendations again or to detect repeat visits for retargeting purposes. With millions of users and products, an exact set per user would be memory intensive, while a Bloom filter per user only needs a few kilobytes, even with tens of thousands of viewed articles.

The false-positive rate is usually well tolerable for this use case: if an article that has not actually been seen is occasionally misclassified as seen and therefore excluded from a recommendation, the harm is minor compared to the memory cost of an exact set across all users and articles. Exactly in such cases with a tolerable error rate, a Bloom filter fully leverages its memory advantage.

4. Cuckoo Filters: A Bloom Filter Alternative with Delete Support

A fundamental problem with classic Bloom filters is that individual elements cannot be removed again without accidentally also removing other elements that share the same bits. For use cases where elements need to be removed again, such as a time-limited visibility window for seen articles, a classic Bloom filter is therefore unsuitable.

Cuckoo filters solve this problem by storing compact fingerprints of elements in a hash table with cuckoo hashing instead of set bits. A single element can be removed in a targeted way by deleting its fingerprint from the corresponding bucket position, without affecting other elements. The price for this is a somewhat higher memory footprint per element compared to an equally accurate Bloom filter.

redis-cli CF.RESERVE seen_articles_temp:user4711 100000

redis-cli CF.ADD seen_articles_temp:user4711 article:9981

redis-cli CF.DEL seen_articles_temp:user4711 article:9981

5. Top-K: The Most Frequent Elements Without Counting Everything

While Bloom and Cuckoo filters answer pure membership tests, the Top-K structure solves a different question: which elements occur most frequently in a data stream, without every single element having to be counted exactly. This is relevant, for example, for the most searched terms in a shop search or the most clicked products within a time window, at a very high number of distinct terms.

Internally, TOPK works with a fixed memory budget for a limited number of candidates and thereby approximates the actual ranking, instead of maintaining an exact count over every term ever seen. For most use cases where only the top of the frequency distribution matters, such as the ten most searched terms of the day, this delivers a very good approximation at constant, predictable memory usage.

redis-cli TOPK.RESERVE top_search_terms 10 2000 7 0.9

redis-cli TOPK.ADD top_search_terms "summer jacket" "summer jacket" "hiking boots"

redis-cli TOPK.LIST top_search_terms WITHCOUNT

6. Sizing the False-Positive Rate Correctly

Choosing the false-positive rate is not a purely technical decision, it depends on the actual harm a false hit causes. For duplicate detection meant to prevent the same email from being sent twice, a low error rate is important, because a false-positive hit would suppress a legitimate email. For a pure display optimization like already-seen product recommendations, a higher error rate is usually unproblematic.

RedisBloom lets you make this trade-off explicit when creating the filter through the desired error-rate parameter, instead of leaving it to a fixed, unchangeable implementation. Importantly, the error rate applies to the expected capacity specified on RESERVE, if that capacity is noticeably exceeded, the actual false-positive rate rises noticeably above the configured value.

7. Estimating Memory Usage Realistically

The memory advantage of probabilistic structures over exact sets is the central reason for using them, but it should not be assumed blindly. A Bloom filter for one hundred thousand elements with a false-positive rate of one percent usually needs only a few hundred kilobytes, whereas an exact set with the same elements as full strings can easily take up several megabytes, depending on the average element length.

With a very large number of small filters, such as one Bloom filter per individual user across millions of users, even a small overhead per filter quickly adds up to a considerable total memory requirement. In such cases it is worth doing a realistic projection beforehand with MEMORY USAGE on a representative sample, instead of relying solely on the theoretical space savings per individual filter.

redis-cli MEMORY USAGE seen_articles:user4711 SAMPLES 0

8. Distinguishing from Count-Min Sketch and HyperLogLog

Besides Bloom, Cuckoo, and Top-K filters, RedisBloom also ships a Count-Min Sketch structure that, unlike Top-K, does not just return the most frequent elements but estimates an approximate frequency for any arbitrary element. That is suited for questions such as how often was this specific search term queried, while Top-K is better suited for the question what are the most frequent terms overall.

HyperLogLog remains its own data type built into the Redis core and continues to cover exclusively cardinality estimation. Anyone who wants to know both how many distinct users have seen an article and whether one specific user has seen it typically combines HyperLogLog for the first question with a Bloom or Cuckoo filter for the second in practice.

9. Practical Limits of RedisBloom

All structures in RedisBloom are deliberately approximate, they are not suited for cases where absolute correctness is strictly required, such as financial transactions or inventory management. For such use cases, exact data types like sets, sorted sets, or relational databases remain the right choice, regardless of the memory advantage of probabilistic structures.

Another practical point: like RedisJSON and RediSearch, RedisBloom is not part of the standard Redis server, it must be provided as a module through Redis Stack or an equivalent managed environment. Before production use, it is therefore worth checking the module list of the Redis instance in use, to avoid surprises from missing BF.*, CF.*, or TOPK.* commands.

redis-cli MODULE LIST

10. Summary

11. FAQ: RedisBloom: The Essentials at a Glance