TairBloom

Overview

In Redis, you can implement similar functionality by using Hash, Set, or a bitset stored in a String. However, these methods either consume a large amount of memory or cannot scale dynamically while maintaining a stable false positive rate. TairBloom is ideal for use cases that require efficient membership tests on large datasets and can tolerate a small false positive rate. You can use the TairBloom API directly, without custom wrappers or a local implementation.

Key features

• Low memory footprint.

• Supports auto-scaling.

• Customizable false positive rate that remains stable during auto-scaling.

Use cases

Best practices

void recommendedSystem(userid) {
    while (true) {
        // Get a candidate article ID.
        docid = getDocByRandom()
        if (bf.exists(userid, docid)) {
            // The article was probably already recommended, so skip it.
            continue;
        } else {
            // The article was definitely not recommended, so send it.
            sendRecommendMsg(docid);
            // Record the recommendation.
            bf.add(userid, docid);
            break;
        }
    }
}

bool crawlerSystem( ) {
    while (true) {
        // Get a URL to crawl.
        url = getURLFromQueue()
        if (bf.exists(url_bloom, url)) {
            // The URL was probably already crawled, so skip it.
            continue;
        } else {
            // Download the URL content.
            doDownload(url)
            // Add the URL to TairBloom.
            bf.add(url_bloom, url);
        }
    }
}

How it works

TairBloom is an implementation of a Scalable Bloom Filter. It supports auto-scaling and maintains a stable false positive rate. A Scalable Bloom Filter is an optimized version of a bloom filter. The following sections describe the basic principles of bloom filters and Scalable Bloom Filters.

• Bloom filter

  A bloom filter is a space-efficient probabilistic data structure proposed by Burton Bloom in 1970. It is used to test whether an element is a member of a set.

  A new bloom filter is a bit array of m bits, with all bits initially set to 0. It also uses k different hash functions that generate a uniform random distribution, where k is a constant smaller than m. When you add an element to the bloom filter, the k hash functions map the element to k positions in the bit array, and the bits at these positions are set to 1. A single bit can be shared by multiple elements. The following figure shows how elements X1 and X2 are inserted into a bloom filter where k is 3.

  To query an element, the same k hash functions are used to get the corresponding k bit positions. If all bits at these positions are 1, the element is considered present in the bloom filter. If any bit is 0, the element is definitely not present. The following figure shows how to check whether Y1 and Y2 exist in the bloom filter.

  As shown in the figure, although the element Y2 was never inserted into the bloom filter, the filter reports that Y2 exists. This is a false positive. Based on this, we can summarize the characteristics of a bloom filter:

  • Bit positions can be shared by different elements.

  • False positives can occur. The more elements in the bloom filter, the higher the probability of a false positive. However, false negatives do not occur. If an element is reported as not present, it is definitely not present.

  • Elements can be added to a bloom filter but cannot be removed. This is because bit positions can be shared, and clearing a bit for one element might affect other elements.

• Scalable Bloom Filter

  As more elements are added to a bloom filter, the false positive rate increases. To keep the false positive rate stable, the size of the bloom filter must be increased. However, a standard bloom filter cannot be resized. A Scalable Bloom Filter addresses this by creating new bloom filters and stacking them into a single logical filter.

  The following figure shows the basic model of a Scalable Bloom Filter (SBF), which contains two layers: BF0 and BF1. Initially, the SBF contains only the BF0 layer. Assume that after elements a, b, and c are inserted, the BF0 layer can no longer maintain the user-defined false positive rate. At this point, a new layer (BF1) is created. Subsequent elements d, e, and f are inserted into the BF1 layer. Similarly, when the BF1 layer can no longer meet the false positive rate, a new layer (BF2) is created, and so on. For more information, see Scalable Bloom Filter.

  Important

  When TairBloom auto-scales, the new layer has double the capacity and four times the memory usage of the previous one.

  Each additional layer increases query time because a query may need to traverse multiple bloom filter layers. A Scalable Bloom Filter always inserts data into the latest layer, and queries start from the latest layer and continue back to the first layer (BF0). As a result, auto-scaling operations in TairBloom can create large keys and degrade performance. The performance degradation increases as the number of elements grows.

  In practice, you should avoid triggering TairBloom auto-scaling and treat this feature as a safeguard. Reserve enough memory for the instance to prevent write failures after an auto-scaling event, which could trigger a prolonged data eviction process and make the instance unresponsive. You can use the BF.INFO command to check if a key is about to trigger an auto-scaling event. When the number of items in the latest layer reaches its capacity, an auto-scaling event is imminent.

  When the actual capacity exceeds the preset capacity, TairBloom auto-scales to ensure write operations can continue, thus preventing production incidents. After TairBloom completes an auto-scaling operation, rebuild the key as soon as possible to improve performance and reduce the risks associated with the next auto-scaling event.

Prerequisites

Usage notes

• The commands in this topic operate on TairBloom data in a Tair instance.

• Plan the initial capacity and false positive rate in advance. If the expected capacity of the target key is much larger than 100, use the BF.RESERVE command to create the TairBloom key. Avoid creating the key with the BF.ADD command.

  The following list describes the differences between running the BF.ADD command and the BF.RESERVE command.

  • BF.ADD (or BF.MADD): If the target key does not exist when the command is executed, Tair automatically creates a TairBloom instance with a default capacity of 100 and a false positive rate (error_rate) of 0.01. If your required capacity is much larger than 100, you can only add more elements later by expanding the capacity. As the number of internal layers in TairBloom increases, query operations must traverse multiple Bloom filters, which severely degrades performance.

  • BF.RESERVE (or BF.INSERT): When you run this command, you must set the capacity (initial capacity). This command initializes the capacity in the first layer of the TairBloom key. A TairBloom key with fewer layers provides faster queries.

  Note

  For example, to insert 10,000,000 elements with a false positive rate of 0.01, creating a TairBloom key with the BF.ADD command requires 176 MB of memory. In contrast, creating the key with the BF.RESERVE command requires only 16 MB.

  The following table lists the memory usage for keys created with different initial capacities and false positive rates with the BF.RESERVE command. The values are for reference only.

  Capacity	False positive rate: 0.01	False positive rate: 0.001	False positive rate: 0.0001
  100,000	0.12 MB	0.25 MB	0.25 MB
  1,000,000	2 MB	2 MB	4 MB
  10,000,000	16 MB	32 MB	32 MB
  100,000,000	128 MB	256 MB	256 MB
  1,000,000,000	2 GB	2 GB	4 GB

  When creating a key with a very large capacity, consider the error_rate. A key with a very large capacity and high precision (a low error_rate) may fail due to insufficient instance memory. 

• TairBloom allows you to insert new elements but not to delete existing elements. As a result, the memory usage of a TairBloom key only increases. To prevent a TairBloom key from growing excessively and causing out of memory (OOM) errors, consider the following suggestions.

  • Split business data: Split and refine your business data to avoid storing a large amount of data in a single TairBloom key. This not only prevents the key from becoming too large and affecting query performance but also prevents most query traffic from being directed to the Redis instance where the key is located, which can create a hot key and cause access skew.

    Split your business data and distribute the data across multiple TairBloom keys. If you use a cluster instance, you can distribute the TairBloom keys across the nodes in the cluster to balance memory and traffic, which helps you take full advantage of a distributed cluster.

  • Rebuild periodically: If your business allows, you can periodically rebuild the TairBloom key. Use the DEL command to delete the TairBloom key and then pull data from the backend database to rebuild it. This helps control the size of the TairBloom key.

    You can also create multiple TairBloom keys initially and rotate between them to control the size of individual keys. This approach avoids frequent rebuilds but consumes more memory.

Command reference

BF.RESERVE

BF.RESERVE BFKEY 0.01 100

OK

BF.ADD

BF.ADD BFKEY item1

(integer) 1

BF.MADD

BF.MADD BFKEY item1 item2 item3

(integer) 1
(integer) 1
(integer) 1

BF.EXISTS

BF.EXISTS BFKEY item1

(integer) 1

BF.MEXISTS

BF.MEXISTS BFKEY item1 item5

(integer) 1
(integer) 0

BF.INSERT

BF.INSERT bfkey1 CAPACITY 10000 ERROR 0.001 ITEMS item1 item2 item3

(integer) 1
(integer) 1
(integer) 1

BF.INFO

BF.INFO bk1

1) "total_items:6,num_blooms:2"
2) "bytes:4 bits:32 hashes:7 hashwidth:64 capacity:3 items:3 error_ratio:0.01"
3) "bytes:16 bits:128 hashes:9 hashwidth:64 capacity:10 items:3 error_ratio:0.0025"