Bloom Filters for Fast Negative Lookups

Fast Negative Lookups

Bloom filters sit in SSTable metadata to answer "key definitely not in this file" without disk reads. A negative lookup saves an I/O; a positive lookup must still check the data block because false positives are allowed.

Filter Mechanics

Hash key with k independent functions into m bits. Insert sets bits; query requires all k bits set.

c
Loading…

Choose m and k from desired false-positive rate and expected key count
One filter per SSTable in LevelDB/RocksDB
Negative lookup avoids opening data blocks on misses
Count false positives on a test set to validate math

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement a Bloom filter with configurable bit array and hash count. This exercise asks you to report false positive rate on a provided key set.

Write a C program that implements a Bloom filter for SSTable negative lookups.

Requirements:

Define FILTER_SIZE as 64 bits (uint64_t for simplicity)
Implement hash1(key) = key * 31 % 64, hash2(key) = key * 17 % 64, hash3(key) = key * 7 % 64
Implement bloom_add(filter, key): set bits at hash1, hash2, hash3
Implement bloom_check(filter, key): return 1 if all three bits are set, 0 otherwise
Create a filter and add these keys: 10, 20, 30, 40, 50
Test lookups for:
- Present keys: 10, 30, 50 (should all return 1)
- Absent keys: 15, 25, 35, 45, 99 (should mostly return 0, but may have false positives)
Print the filter bit pattern as a 64-character binary string
Count and print the number of false positives in the test
Calculate the theoretical false positive rate for n=5, m=64, k=3 using the formula p = (1 - e^(-kn/m))^k
Explain why Bloom filters have no false negatives

Fast Negative Lookups

Filter Mechanics

Hash key with k independent functions into m bits. Insert sets bits; query requires all k bits set.

c
Loading…

Choose m and k from desired false-positive rate and expected key count
One filter per SSTable in LevelDB/RocksDB
Negative lookup avoids opening data blocks on misses
Count false positives on a test set to validate math

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement a Bloom filter with configurable bit array and hash count. This exercise asks you to report false positive rate on a provided key set.

Write a C program that implements a Bloom filter for SSTable negative lookups.

Requirements:

Define FILTER_SIZE as 64 bits (uint64_t for simplicity)
Implement hash1(key) = key * 31 % 64, hash2(key) = key * 17 % 64, hash3(key) = key * 7 % 64
Implement bloom_add(filter, key): set bits at hash1, hash2, hash3
Implement bloom_check(filter, key): return 1 if all three bits are set, 0 otherwise
Create a filter and add these keys: 10, 20, 30, 40, 50
Test lookups for:
- Present keys: 10, 30, 50 (should all return 1)
- Absent keys: 15, 25, 35, 45, 99 (should mostly return 0, but may have false positives)
Print the filter bit pattern as a 64-character binary string
Count and print the number of false positives in the test
Calculate the theoretical false positive rate for n=5, m=64, k=3 using the formula p = (1 - e^(-kn/m))^k
Explain why Bloom filters have no false negatives

Topic Overview

Fast Negative Lookups

Filter Mechanics

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source

Bloom Filters for Fast Negative Lookups

Topic Overview

Fast Negative Lookups

Filter Mechanics

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source