The problem/use-case that the feature addresses

Bloom filters are an efficient probabilistic data structure for checking set membership with minimal memory usage. However, Redis currently only supports standard Bloom filters via the RedisBloom module, which do not support element removals.

A Counting Bloom Filter (CBF) extends a Bloom filter by associating a counter with each bit in the bit array, allowing both insertions and deletions. This makes it particularly useful for:

  1. Rate limiting – Tracking API calls per user/IP while allowing decays over time.
  2. Frequency counting – Monitoring how often an element appears in a dataset (e.g., tracking login attempts, spam detection, abuse prevention).
  3. Cache eviction strategies – Keeping track of access frequencies to improve cache management.

Currently, users must use HyperLogLog, approximate counters, or full hash sets, which either lack removals or have higher memory usage. Adding Counting Bloom Filters would provide a more memory-efficient way to track occurrences while allowing deletions.

Description of the feature

I propose extending RedisBloom to support Counting Bloom Filters (CBF). The feature should include:

  1. New data structure: A Counting Bloom Filter (CBF) where each bit is replaced by a small counter (e.g., 4- or 8-bit counters).
  2. Insertion (CBF.ADD key value) – Similar to a standard Bloom filter, but increments counters instead of setting bits.
  3. Deletion (CBF.REMOVE key value) – Decrements counters, allowing elements to be removed.
  4. Membership check (CBF.EXISTS key value) – Returns whether an element is likely present.
  5. Frequency check (CBF.COUNT key value) – Returns an estimated count of occurrences for an element.
  6. Expiration support (CBF.RESERVE key capacity error_rate) – Allows preallocating filter size and tuning false-positive rate.

This feature would significantly improve Redis' capabilities in use cases requiring approximate frequency counting and dynamic set membership tracking.

Alternatives you've considered

  1. HyperLogLog – Efficient for cardinality estimation but does not support decrementing/removal of elements.
  2. Cuckoo Filters – Alternative probabilistic structure but less memory-efficient for counting than CBF.
  3. Full hash sets (HINCRBY) – Precise but consumes significantly more memory compared to Bloom filters.
  4. Redis Lua scripting – Implementing CBF logic manually in Lua scripts, but this lacks native efficiency and requires handling counter overflows manually.

Existing issues related to probabilistic data structures in RedisBloom discuss extending Bloom filters but do not address counting use cases. This feature request would fill that gap.

Additional information redablooms was a redis extension that was abandoned. It added counting bloom filters to redis: https://github.com/RedisLabsModules/redablooms

Which was inspired by this: https://github.com/bitly/dablooms

And this: https://github.com/FastFilter/fastfilter_cpp/blob/f27873fac4fae130c58592bbb1ca295f7296cf90/src/bloom/counting_bloom.h#L610