Implementation and Application of Bloom Filter in Redis

I. Overview of Bloom Filter
A Bloom filter is a probabilistic data structure used to quickly determine whether an element exists in a set. Its characteristics are:

• Extremely high space efficiency, far surpassing traditional data structures such as hash tables
• Query results are either "may exist" or "definitely does not exist"
• Has a certain false positive rate, but no false negatives

II. Implementation Principle of Bloom Filter in Redis

1. Basic Structure
   Redis implements Bloom filters through the RedisBloom module, which uses a bit array and multiple hash functions at its core:

• Create a bit array of length m, with all bits initially set to 0
• Use k different hash functions, each mapping an element to a specific position in the bit array

2. Element Addition Process

Assume adding the element "apple":
Step 1: Calculate hash values for "apple" using k hash functions respectively
Step 2: Take the modulo of each hash value with the bit array length m to get k position indices
Step 3: Set the values at these positions to 1

Specific example:

# Assuming 3 hash functions and a bit array length of 10
hash1("apple") % 10 = 3 → Set bit_array[3]=1
hash2("apple") % 10 = 7 → Set bit_array[7]=1  
hash3("apple") % 10 = 2 → Set bit_array[2]=1

3. Element Query Process

Query whether element "apple" exists:
Step 1: Similarly calculate hash values using k hash functions and take modulo
Step 2: Check if all k positions are set to 1
Step 3: If all are 1, return "may exist"; if any bit is 0, return "definitely does not exist"

III. Parameter Configuration of Redis Bloom Filter

1. Key Parameters

• error_rate: Expected false positive rate, default 0.1 (10%)
• capacity: Expected number of elements to be contained
• Automatically calculates the optimal bit array size and number of hash functions based on these two parameters

2. Parameter Calculation Formula

Bit array size m = - (n × ln(p)) / (ln(2))²
Number of hash functions k = (m/n) × ln(2)

Where: n=number of elements, p=false positive rate

IV. Practical Operations with Redis Bloom Filter

1. Adding Elements

BF.ADD myfilter "apple"    # Add "apple" to Bloom filter myfilter
BF.MADD myfilter "banana" "orange"  # Add multiple elements in batch

2. Checking Elements

BF.EXISTS myfilter "apple"  # Check if "apple" exists
# Returns 1 if it may exist, 0 if it definitely does not exist

BF.MEXISTS myfilter "apple" "grape"  # Batch check

3. Creating a Bloom Filter

# Specify parameters during creation
BF.RESERVE myfilter 0.01 1000
# error_rate=1%, capacity=1000 elements

V. Application Scenarios of Redis Bloom Filter

1. Cache Penetration Prevention

Traditional approach: Query cache → Query database
Problem: Malicious queries for non-existent data cause database pressure

Bloom filter solution:
1. Add all valid data keys to the Bloom filter first
2. Check the Bloom filter before querying:
   - If returns non-existent, directly return empty result
   - If returns may exist, proceed to query cache/database

2. Duplicate Content Detection

# Detect if a URL has been crawled
BF.ADD crawled_urls "http://example.com/page1"
if BF.EXISTS crawled_urls $new_url == 0:
    # New URL, proceed to crawl
else:
    # May have been crawled, skip

3. User Recommendation Deduplication

# Record content viewed by a user
BF.ADD user:123:viewed "item_456"
# Filter viewed content during recommendation

VI. Performance Optimization and Considerations

1. False Positive Rate Trade-off

• Lower false positive rate requires more memory space
• Need to balance space and accuracy based on business requirements

2. No Deletion Support

• Traditional Bloom filters do not support deletion (due to shared bits)
• RedisBloom provides a deletable Bloom filter (BF.SCANDIGEST)

3. Capacity Planning

• If the actual number of elements exceeds the preset capacity, the false positive rate increases sharply
• Reasonable capacity estimation based on business growth is needed

Through this implementation, the Redis Bloom filter ensures high performance while significantly saving memory space, making it an ideal solution for handling massive data existence checks.