RedisBloom: Probabilistic Data Structures for Redis

Overview

RedisBloom adds a set of probabilistic data structures to Redis, including Bloom filter, Cuckoo filter, Count-min sketch, Top-K, and t-digest. Using this capability, you can query streaming data without needing to store all the elements of the stream. Probabilistic data structures each answer the following questions:

Bloom filter and Cuckoo filter:
- Did value v already appear in the data stream?
Count-min sketch:
- How many times did value v appear in the data stream?
Top-k:
- What are the k most frequent values in the data stream?
t-digest:
- Which fraction of the values in the data stream are smaller than a given value?
- How many values in the data stream are smaller than a given value?
- Which value is smaller than p percent of the values in the data stream? (What is the p-percentile value?)
- What is the mean value between the p1-percentile value and the p2-percentile value?
- What is the value of the nᵗʰ smallest/largest value in the data stream? (What is the value with [reverse] rank n?)

Answering each of these questions accurately can require a huge amount of memory, but you can lower the memory requirements drastically at the cost of reduced accuracy. Each of these data structures allows you to set a controllable trade-off between accuracy and memory consumption. In addition to having a smaller memory footprint, probabilistic data structures are generally much faster than accurate algorithms.

RedisBloom is part of Redis Stack.

Setup

You can either get RedisBloom setup in a Docker container or on your own machine.

Docker

To quickly try out RedisBloom, launch an instance using docker:

docker run -p 6379:6379 -it --rm redis/redis-stack-server:latest

Build it yourself

You can also build RedisBloom on your own machine. Major Linux distributions as well as macOS are supported.

First step is to have Redis installed, of course. The following, for example, builds Redis on a clean Ubuntu docker image (docker pull ubuntu):

mkdir ~/Redis
cd ~/Redis
apt-get update -y && apt-get upgrade -y
apt-get install -y wget make pkg-config build-essential
wget https://download.redis.io/redis-stable.tar.gz
tar -xzvf redis-stable.tar.gz
cd redis-stable
make distclean
make
make install

Next, you should get the RedisBloom repository from git and build it:

apt-get install -y git
cd ~/Redis
git clone --recursive https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
./sbin/setup
bash -l
make

Then exit to exit bash.

Note: to get a specific version of RedisBloom, e.g. 2.4.5, add -b v2.4.5 to the git clone command above.

Next, run make run -n and copy the full path of the RedisBloom executable (e.g., /root/Redis/RedisBloom/bin/linux-x64-release/redisbloom.so).

Next, add RedisBloom module to redis.conf, so Redis will load when started:

apt-get install -y vim
cd ~/Redis/redis-stable
vim redis.conf

Add: loadmodule /root/Redis/RedisBloom/bin/linux-x64-release/redisbloom.so under the MODULES section (use the full path copied above).

Save and exit vim (ESC :wq ENTER)

For more information about modules, go to the Redis official documentation.

Run

Run redis-server in the background and then redis-cli:

cd ~/Redis/redis-stable
redis-server redis.conf &
redis-cli

Give it a try

After you setup RedisBloom, you can interact with it using redis-cli.

Create a new bloom filter by adding a new item:

# 127.0.0.1:6379> BF.ADD newFilter foo
(integer) 1

Find out whether an item exists in the filter:

# 127.0.0.1:6379> BF.EXISTS newFilter foo
(integer) 1

In this case, 1 means that the foo is most likely in the set represented by newFilter. But recall that false positives are possible with Bloom filters.

# 127.0.0.1:6379> BF.EXISTS newFilter bar
(integer) 0

A value 0 means that bar is definitely not in the set. Bloom filters do not allow for false negatives.

Client libraries

Project	Language	License	Author	Package
jedis	Java	MIT	Redis	Maven
redis-py	Python	MIT	Redis	pypi
node-redis	Node.JS	MIT	Redis	npm
nredisstack	.NET	MIT	Redis	nuget
redisbloom-go	Go	BSD	Redis	GitHub
rueidis	Go	Apache License 2.0	Rueian	GitHub
rebloom	JavaScript	MIT	Albert Team	GitHub
phpredis-bloom	PHP	MIT	Rafa Campoy	GitHub
phpRebloom	PHP	MIT	Alessandro Balasco	GitHub
vertx-redis-client	Java	Apache License 2.0	Eclipse Vert.x	GitHub
rustis	Rust	MIT	Dahomey Technologies	GitHub