RedisBloom

Bloom filters and other probabilistic data structures for Redis

RedisBloom adds four probabilistic data structures to Redis: a scalable Bloom filter, a cuckoo filter, a count-min sketch, and a top-k. These data structures trade perfect accuracy for extreme memory efficiency, so they're especially useful for big data and streaming applications.

Bloom and cuckoo filters are used to determine, with a high degree of certainty, whether an element is a member of a set.

A count-min sketch is generally used to determine the frequency of events in a stream. You can query the count-min sketch get an estimate of the frequency of any given event.

A top-k maintains a list of k most frequently seen items.

Bloom vs. Cuckoo filters

Bloom filters typically exhibit better performance and scalability when inserting items (so if you're often adding items to your dataset, then a Bloom filter may be ideal). Cuckoo filters are quicker on check operations and also allow deletions.

Academic sources

Bloom Filter

• Space/Time Trade-offs in Hash Coding with Allowable Errors by Burton H. Bloom.
• Scalable Bloom Filters

Cuckoo Filter

• Cuckoo Filter: Practically Better Than Bloom

Count-Min Sketch

• An Improved Data Stream Summary: The Count-Min Sketch and its Applications

Top-K

• HeavyKeeper: An Accurate Algorithm for Finding Top-k Elephant Flows.

References

Webinars

1. Probabilistic Data Structures - The most useful thing in Redis you probably aren't using

Blog posts

1. RedisBloom Quick Start Tutorial
2. Developing with Bloom Filters
3. RedisBloom on Redis Enterprise
4. Probably and No: Redis, RedisBloom, and Bloom Filters
5. RedisBloom – Bloom Filter Datatype for Redis

Mailing List / Forum

Got questions? Feel free to ask at the RedisBloom forum.

License

RedisBloom is licensed under the Redis Source Available License Agreement