BLOOM FILTER
Complete Beginner's Guide

Answer:

A Bloom Filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set. It can definitively say "NO" (element is not in the set) but can only say "MAYBE" for positive results (might produce false positives).

How it works:

1. Initialize: Create a bit array of size m, all set to 0
2. Choose k hash functions: Each maps input to a position in the bit array
3. To ADD an item:
   • Run item through all k hash functions
   • Get k positions in bit array
   • Set all k positions to 1
4. To CHECK if item exists:
   • Run item through all k hash functions
   • Get k positions in bit array
   • If ANY position is 0 → "DEFINITELY NOT in set"
   • If ALL positions are 1 → "MAYBE in set"

Key Properties:

• No false negatives (never says "NO" when item exists)
• May have false positives (might say "MAYBE" when item doesn't exist)
• Cannot delete items (standard Bloom Filter)
• Extremely space efficient (bits instead of storing actual data)

Answer:

A false positive occurs when a Bloom Filter says "MAYBE exists" for an item that was never actually added to the set.

Why it happens:

The bits that correspond to an item might already be set to 1 by OTHER items that were added previously.

Example:

Bit array: [0,0,0,0,0,0,0,0,0,0]

Add "Apple":  hash1("Apple")=2, hash2("Apple")=7
Array: [0,0,1,0,0,0,0,1,0,0]

Add "Banana": hash1("Banana")=4, hash2("Banana")=9
Array: [0,0,1,0,1,0,0,1,0,1]

Check "Orange": hash1("Orange")=2, hash2("Orange")=9
Positions 2 and 9 are both 1!
Bloom Filter says: "MAYBE exists"
But we never added "Orange"! → FALSE POSITIVE

Factors affecting false positive rate:

• m (bit array size): Larger m → Lower false positive rate
• n (items added): More items → Higher false positive rate
• k (hash functions): Optimal k = (m/n) × ln(2) ≈ 0.7 × (m/n)

Formula for false positive rate:

Example rates:

• m=100 bits, k=3 hashes, n=10 items → FP rate ≈ 1%
• m=100 bits, k=3 hashes, n=50 items → FP rate ≈ 60%

Answer:

You cannot delete items from a standard Bloom Filter because multiple items share the same bits.

The Problem:

Add "Apple":  sets bits [2, 7]
Add "Banana": sets bits [2, 9]

Array: [0,0,1,0,0,0,0,1,0,1]
              ↑           ↑
         Shared!      Only Banana

To delete "Apple", we would need to:
- Set bit[2] = 0
- Set bit[7] = 0

But bit[2] is also used by "Banana"!
If we set bit[2]=0, checking "Banana" will fail!

Why this happens:

• Bloom Filters use shared bit positions
• One bit can represent multiple items
• No way to know which item(s) set a bit to 1
• Clearing a bit could break other items

Solutions if you need deletions:

1. Counting Bloom Filter:
   • Instead of bits (0/1), use counters (0,1,2,3...)
   • Add: increment counter
   • Delete: decrement counter
   • Downside: 4-8 bytes per position vs 1 bit!
2. Rebuild periodically:
   • Keep track of active items separately
   • Rebuild Bloom Filter from scratch periodically
   • Used by Cassandra (rebuilds on compaction)
3. Use expiration:
   • Items expire after time period
   • Rebuild filter without expired items

Answer:

Cassandra uses Bloom Filters to avoid unnecessary disk reads when checking if data exists in SSTables (sorted string table files on disk).

The Problem Without Bloom Filters:

• Cassandra stores data in multiple SSTable files on disk
• A table might have 100+ SSTables
• To find if a row exists: must check each SSTable
• Each disk read: ~10ms
• Total: 100 SSTables × 10ms = 1 second just to say "NOT FOUND"!

How Cassandra Uses Bloom Filters:

1. Each SSTable has its own Bloom Filter stored in memory
2. Bloom Filter contains all partition keys in that SSTable
3. Before reading SSTable from disk:
   • Check Bloom Filter: "Is partition key X in this SSTable?"
   • If "DEFINITELY NOT" → Skip this SSTable entirely!
   • If "MAYBE" → Read SSTable from disk and check

Performance Impact:

Scenario: Looking for user_id=12345 across 100 SSTables

WITHOUT Bloom Filters:
- Check all 100 SSTables from disk
- 100 × 10ms = 1000ms (1 second)

WITH Bloom Filters:
- Check 100 Bloom Filters in memory: 100 × 0.001ms = 0.1ms
- 99 say "DEFINITELY NOT" → skip
- 1 says "MAYBE" → read from disk: 10ms
- Total: 10.1ms (100x faster!)

Configuration:

• bloom_filter_fp_chance: False positive rate
  • Default: 0.01 (1%)
  • Lower value = larger filter, less false positives
  • Higher value = smaller filter, more false positives

Why It's Critical:

• Enables Cassandra to handle millions of reads/second
• Reduces disk I/O by 99%+
• Makes "NOT FOUND" queries nearly free
• Essential for Cassandra's horizontal scalability

Comparison Table:

Example with 1 billion items:

Bloom Filter:
- Space: 10 bits/item = 10 billion bits = 1.25 GB
- Lookup: O(k) where k=3-5 hash functions
- False positive: 1% (1 in 100 wrong "MAYBE")

HashSet:
- Space: 32 bytes/item = 32 GB (25x larger!)
- Lookup: O(1) average
- Accuracy: 100% correct

Memory savings: 32 GB - 1.25 GB = 30.75 GB saved!

When to use which:

• Use Bloom Filter when:
  • Memory is extremely limited
  • Need to handle billions of items
  • 1-5% false positives acceptable
  • Don't need to delete or list items
  • Example: Cassandra SSTable filtering
• Use HashSet when:
  • Need 100% accuracy
  • Need to delete items
  • Need to iterate over items
  • Have sufficient memory
  • Example: In-memory caching