A Bloom filter is a space-efficient probabilistic data structure that answers set membership queries with a one-sided error guarantee: it may report that an element is in the set when it is not (false positive), but it will never report that an element is absent when it is present (no false negatives). This property makes it an ideal gatekeeper for expensive lookups.
Bloom filters are ubiquitous in storage engines, databases, and networking systems. LSM-tree-based databases like LevelDB, RocksDB, and Cassandra use Bloom filters on every SSTable to skip disk reads for keys that definitely do not exist. For instance, a typical LSM-tree storage engine attaches Bloom filters to each sorted run, avoiding up to 99% of unnecessary disk I/O during point lookups.
The elegance of Bloom filters lies in their simplicity: a bit array and a handful of hash functions. Yet the math behind optimal sizing, hash count, and false-positive rate curves is rich enough to warrant careful study. Choosing the wrong parameters can waste memory or produce unacceptable false-positive rates.
m bits, all initially zero. The size determines the trade-off between memory usage and false-positive rate.k independent hash functions map each element to k bit positions. On insert, all k bits are set to 1. On query, if any bit is 0, the element is definitely absent.k bits happen to be set by other elements. Approximately (1 - e^(-kn/m))^k where n is the number of inserted elements.The optimal number of hash functions is k = (m/n) * ln(2). With this setting, the false-positive rate is minimized at approximately (0.6185)^(m/n). Using 10 bits per element gives a ~1% false-positive rate.
Bloom filters have zero false negatives. If a query returns “not present,” the element is guaranteed absent. This makes them perfect as a first-pass filter before expensive operations like disk reads or network calls.
To add an element, compute k hash values and set each corresponding bit in the array. Modern implementations avoid k independent hash functions by using the double-hashing technique: compute two base hashes h1 and h2, then derive hash i as h1 + i * h2. This gives statistically independent positions with only two hash computations.
To test membership, compute the same k hash positions and check each bit. If all bits are 1, the element is “probably present” (with a quantifiable false-positive probability). If any bit is 0, the element is definitely not in the set.
Given a target false-positive rate p and expected element count n, the optimal bit array size is m = -n * ln(p) / (ln(2))^2. The optimal hash count is k = (m/n) * ln(2). These formulas let you precisely budget memory for a desired accuracy.
The double-hashing technique h_i(x) = h1(x) + i * h2(x) mod m reduces the number of hash computations from k to 2 while maintaining the same theoretical false-positive guarantees. This is why real-world Bloom filters are fast even with 10+ logical hash functions.
In a typical LSM-tree storage engine, Bloom filters are created for each flushed memtable segment. During compaction, filters are regenerated for the merged output. The filter metadata is stored in the SSTable footer for fast loading at query time.
Instead of hashing across the entire bit array, block-aligned filters (used by RocksDB) hash each element into a single cache-line-sized block. This improves CPU cache behavior because a query only touches one cache line instead of k random positions. The trade-off is a slightly higher false-positive rate at the same total bit count.
Replace each bit with a small counter (typically 4 bits). Insertion increments counters, deletion decrements them. A position is considered “set” when its counter is > 0. This enables deletion at the cost of 4x memory overhead.
Divide the bit array into k equal partitions and assign one hash function to each partition. This avoids the (rare) case where two hash functions map to the same bit position, slightly improving the false-positive rate.
const std = @import("std");
pub const BloomFilter = struct {
bits: []u8,
num_bits: u64,
num_hashes: u32,
pub fn init(allocator: std.mem.Allocator, expected_items: u64, fp_rate: f64) !BloomFilter {
const ln2 = @as(f64, 0.693147180559945);
const ln2_sq = ln2 * ln2;
// m = -n * ln(p) / (ln(2))^2
const m_f: f64 = -@as(f64, @floatFromInt(expected_items)) * @log(fp_rate) / ln2_sq;
const num_bits: u64 = @intFromFloat(@ceil(m_f));
const num_bytes = (num_bits + 7) / 8;
// k = (m/n) * ln(2)
const k_f: f64 = (@as(f64, @floatFromInt(num_bits)) /
@as(f64, @floatFromInt(expected_items))) * ln2;
const num_hashes: u32 = @intFromFloat(@max(1.0, @round(k_f)));
const bits = try allocator.alloc(u8, num_bytes);
@memset(bits, 0);
return .{
.bits = bits,
.num_bits = num_bits,
.num_hashes = num_hashes,
};
}
pub fn deinit(self: *BloomFilter, allocator: std.mem.Allocator) void {
allocator.free(self.bits);
}
fn getPositions(self: *const BloomFilter, key: []const u8) [2]u64 {
// Double hashing: two base hashes from different seeds
const h1 = std.hash.XxHash64.hash(0, key);
const h2 = std.hash.XxHash64.hash(1, key);
return .{ h1, h2 };
}
pub fn add(self: *BloomFilter, key: []const u8) void {
const hashes = self.getPositions(key);
for (0..self.num_hashes) |i| {
const pos = (hashes[0] +% i *% hashes[1]) % self.num_bits;
const byte_idx = pos / 8;
const bit_idx: u3 = @intCast(pos % 8);
self.bits[byte_idx] |= @as(u8, 1) << bit_idx;
}
}
pub fn mightContain(self: *const BloomFilter, key: []const u8) bool {
const hashes = self.getPositions(key);
for (0..self.num_hashes) |i| {
const pos = (hashes[0] +% i *% hashes[1]) % self.num_bits;
const byte_idx = pos / 8;
const bit_idx: u3 = @intCast(pos % 8);
if (self.bits[byte_idx] & (@as(u8, 1) << bit_idx) == 0) {
return false;
}
}
return true;
}
};package storage
import (
"hash"
"hash/fnv"
"math"
)
type BloomFilter struct {
bits []uint64
numBits uint64
numHash uint32
}
func NewBloomFilter(n uint64, fpRate float64) *BloomFilter {
// Optimal sizing
m := uint64(math.Ceil(-float64(n) * math.Log(fpRate) / (math.Ln2 * math.Ln2)))
k := uint32(math.Max(1, math.Round(float64(m)/float64(n)*math.Ln2)))
words := (m + 63) / 64
return &BloomFilter{
bits: make([]uint64, words),
numBits: m,
numHash: k,
}
}
func (bf *BloomFilter) Add(key []byte) {
h1, h2 := bf.hash(key)
for i := uint32(0); i < bf.numHash; i++ {
pos := (h1 + uint64(i)*h2) % bf.numBits
bf.bits[pos/64] |= 1 << (pos % 64)
}
}
func (bf *BloomFilter) MayContain(key []byte) bool {
h1, h2 := bf.hash(key)
for i := uint32(0); i < bf.numHash; i++ {
pos := (h1 + uint64(i)*h2) % bf.numBits
if bf.bits[pos/64]&(1<<(pos%64)) == 0 {
return false
}
}
return true
}
// SSTable lookup with Bloom filter gate
func (db *DB) Get(key []byte) ([]byte, error) {
// Check memtable first (always)
if val, ok := db.memtable.Get(key); ok {
return val, nil
}
// Check each SSTable level, newest first
for _, level := range db.levels {
for _, sst := range level.Tables() {
// Bloom filter skip: avoid disk read entirely
if !sst.Filter.MayContain(key) {
continue // definitely not here
}
// Filter says "maybe" — do the real lookup
if val, err := sst.Get(key); err == nil {
return val, nil
}
}
}
return nil, ErrKeyNotFound
}Bloom filters are the most important single optimization in LSM-tree storage engines. A 10-bits-per-element filter with 7 hash functions achieves a ~0.8% false-positive rate, turning O(L) disk reads into O(1) for negative lookups where L is the number of levels.
The space-accuracy trade-off is precisely quantifiable: each additional bit per element roughly halves the false-positive rate. This makes it straightforward to budget memory for a target accuracy, unlike most probabilistic data structures.