Bloom Filter — Deletion Bugs Cause Mass False Negatives

import java.nio.charset.StandardCharsets;
import java.util.BitSet;

/**
 * A production-quality Bloom filter implementation.
 *
 * Sizing is driven by two inputs you actually know at design time:
 *   - expectedInsertions: how many items you plan to store
 *   - falsePositiveProbability: the maximum acceptable false-positive rate (0 < p < 1)
 *
 * The constructor derives optimal m (bit array size) and k (hash function count)
 * so you never have to guess at magic numbers.
 */
public class BloomFilter {

    private final BitSet   bitArray;          // the underlying m-bit array
    private final int      bitArraySize;      // m
    private final int      hashFunctionCount; // k
    private       long     insertionCount;    // tracks n so we can report current fpp

    // ── Constructor ─────────────────────────────────────────────────────────────

    public BloomFilter(int expectedInsertions, double falsePositiveProbability) {\n        if (expectedInsertions <= 0)        throw new IllegalArgumentException(\"expectedInsertions must be > 0\");\n        if (falsePositiveProbability <= 0\n         || falsePositiveProbability >= 1)  throw new IllegalArgumentException(\"falsePositiveProbability must be in (0, 1)\");\n\n        // Optimal bit array size:  m = -(n * ln p) / (ln 2)^2\n        this.bitArraySize = optimalBitCount(expectedInsertions, falsePositiveProbability);\n\n        // Optimal hash function count:  k = (m / n) * ln 2\n        this.hashFunctionCount = optimalHashCount(bitArraySize, expectedInsertions);\n\n        this.bitArray      = new BitSet(bitArraySize);\n        this.insertionCount = 0;\n    }\n\n    // ── Public API ───────────────────────────────────────────────────────────────\n\n    /**\n     * Insert an element. Returns 'this' for fluent chaining.\n     */\n    public BloomFilter put(String element) {\n        long[] hashes = murmur3DoubleHash(element);\n        long h1 = hashes[0];\n        long h2 = hashes[1];\n\n        for (int i = 0; i < hashFunctionCount; i++) {\n            // Double-hashing: gi(x) = h1(x) + i * h2(x)  mod m\n            // Using Math.floorMod to guarantee a non-negative index\n            int index = (int) Math.floorMod(h1 + (long) i * h2, bitArraySize);\n            bitArray.set(index);             // set the bit at this position to 1\n        }\n        insertionCount++;\n        return this;\n    }\n\n    /**\n     * Query membership.\n     * Returns FALSE  → element is DEFINITELY NOT in the set (zero false negatives)\n     * Returns TRUE   → element is PROBABLY in the set (false positives possible)\n     */\n    public boolean mightContain(String element) {\n        long[] hashes = murmur3DoubleHash(element);\n        long h1 = hashes[0];\n        long h2 = hashes[1];\n\n        for (int i = 0; i < hashFunctionCount; i++) {\n            int index = (int) Math.floorMod(h1 + (long) i * h2, bitArraySize);\n            if (!bitArray.get(index)) {\n                return false;   // even ONE zero bit means definitely absent\n            }\n        }\n        return true;            // all k bits are set → probably present\n    }\n\n    /** Current estimated false-positive probability given actual insertions so far. */\n    public double estimatedFalsePositiveProbability() {\n        // p ≈ (1 - e^(-k*n/m))^k\n        double exponent = -((double) hashFunctionCount * insertionCount) / bitArraySize;\n        return Math.pow(1 - Math.exp(exponent), hashFunctionCount);\n    }\n\n    public int   getBitArraySize()      { return bitArraySize; }\n    public int   getHashFunctionCount() { return hashFunctionCount; }\n    public long  getInsertionCount()    { return insertionCount; }\n\n    // ── Sizing helpers ───────────────────────────────────────────────────────────\n\n    static int optimalBitCount(long n, double p) {\n        // m = -(n * ln p) / (ln 2)^2\n        return (int) Math.ceil(-n * Math.log(p) / (Math.log(2) * Math.log(2)));\n    }\n\n    static int optimalHashCount(long m, long n) {\n        // k = (m / n) * ln 2\n        // Clamp to at least 1 to avoid degenerate cases\n        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));\n    }\n\n    // ── Hash function (MurmurHash3-inspired double hash) ─────────────────────────\n\n    /**\n     * Returns [h1, h2] — two independent 64-bit hashes derived from MurmurHash3.\n     * We use these to simulate k hash functions via double hashing.\n     */\n    private static long[] murmur3DoubleHash(String element) {\n        byte[] data  = element.getBytes(StandardCharsets.UTF_8);\n        long   seed1 = 0xDEADBEEFL;\n        long   seed2 = 0xCAFEBABEL;\n\n        long h1 = seed1;\n        long h2 = seed2;\n\n        // Simple mix — in production use a proper Murmur3/xxHash library\n        for (byte b : data) {\n            h1 = Long.rotateLeft(h1 ^ b, 31) * 0x9e3779b97f4a7c15L;\n            h2 = Long.rotateLeft(h2 ^ b, 17) * 0xbf58476d1ce4e5b9L;\n        }\n\n        // Final avalanche mix\n        h1 ^= h1 >>> 33;  h1 *= 0xff51afd7ed558ccdL;  h1 ^= h1 >>> 33;\n        h2 ^= h2 >>> 33;  h2 *= 0xc4ceb9fe1a85ec53L;  h2 ^= h2 >>> 33;\n\n        return new long[]{ h1, h2 };\n    }\n\n    // ── Demo main ────────────────────────────────────────────────────────────────\n\n    public static void main(String[] args) {\n        int    expectedUrls = 1_000_000;   // 1 million known-malicious URLs\n        double targetFpp    = 0.01;        // we're okay with 1% false positives\n\n        BloomFilter maliciousUrlFilter = new BloomFilter(expectedUrls, targetFpp);\n\n        System.out.printf(\"Bit array size  (m): %,d bits  (~%.1f KB)%n\",\n                maliciousUrlFilter.getBitArraySize(),\n                maliciousUrlFilter.getBitArraySize() / 8.0 / 1024.0);\n        System.out.printf(\"Hash functions  (k): %d%n\",\n                maliciousUrlFilter.getHashFunctionCount());\n\n        // Insert known-bad URLs\n        String[] knownMalicious = {\n            \"http://evil-phishing-site.com/login\",\n            \"http://malware-dropper.ru/payload.exe\",\n            \"http://fake-bank.net/secure/account\"\n        };\n        for (String url : knownMalicious) {\n            maliciousUrlFilter.put(url);\n        }\n\n        // Query\n        System.out.println(\"\\n── Membership queries ──\");\n        System.out.println(maliciousUrlFilter.mightContain(\"http://evil-phishing-site.com/login\"));\n            // true  — we inserted this\n        System.out.println(maliciousUrlFilter.mightContain(\"http://legitimate-news.com/\"));\n            // false — definitely not inserted (no false negative possible)\n        System.out.println(maliciousUrlFilter.mightContain(\"http://malware-dropper.ru/payload.exe\"));\n            // true  — we inserted this\n\n        // Simulate filling to capacity and check estimated fpp\n        System.out.println(\"\\n── Filling to capacity ──\");\n        for (int i = 0; i < expectedUrls; i++) {\n            maliciousUrlFilter.put(\"synthetic-url-\" + i + \".com\");\n        }\n        System.out.printf(\"Estimated false-positive rate after %,d insertions: %.4f%%%n\",\n                maliciousUrlFilter.getInsertionCount(),\n                maliciousUrlFilter.estimatedFalsePositiveProbability() * 100);\n    }\n}",
        "output": "Bit array size  (m): 9,585,059 bits  (~1,170.5 KB)\nHash functions  (k): 7\n\n── Membership queries ──\ntrue\nfalse\ntrue\n\n── Filling to capacity ──\nEstimated false-positive rate after 1,000,003 insertions: 1.0014%"
      }

public class VisualWalkthrough {
    // Simulate a tiny Bloom filter with m=10, k=3
    static java.util.BitSet bitArray = new java.util.BitSet(10);
    static int k = 3;

    // Dummy hash functions for demonstration (not suitable for production)
    static int[] hash(String s) {
        int h1 = (s.hashCode() & 0x7fffffff) % 10;
        int h2 = (s.hashCode() * 31 & 0x7fffffff) % 10;
        int h3 = (s.hashCode() * 17 & 0x7fffffff) % 10;
        return new int[]{h1, h2, h3};
    }

    static void insert(String s) {
        for (int i : hash(s)) bitArray.set(i);
    }

    static boolean mightContain(String s) {
        for (int i : hash(s)) if (!bitArray.get(i)) return false;
        return true;
    }

    public static void main(String[] args) {
        System.out.println("Initial: " + bitArray);            // {}
        insert("apple");
        System.out.println("After apple: " + bitArray);       // positions depend on hashCode
        insert("banana");
        System.out.println("After banana: " + bitArray);
        System.out.println("contains apple? " + mightContain("apple"));   // true
        System.out.println("contains banana? " + mightContain("banana")); // true
        System.out.println("contains cherry? " + mightContain("cherry")); // likely false
    }
}

// Example: Crawler URL deduplication (pseudocode)
BloomFilter<String> visitedUrls = new BloomFilter<>(1_000_000_000, 0.01); // 1B expected

// On discovering a new URL:
if (!visitedUrls.mightContain(url)) {
    crawl(url);                    // Definitely not visited — crawl it
    visitedUrls.put(url);          // Mark as visited
} else {
    skip(url);                     // Probably visited — skip (may waste some work if false positive)
}

// This uses ~1.2 GB for 1B URLs — impossible with a HashSet.

/**
 * A Counting Bloom Filter that supports deletion.
 *
 * Each position holds a small integer counter instead of a single bit.
 * Insertion increments counters; deletion decrements them.
 *
 * Memory cost: ~4x a standard Bloom filter for the same m.
 * Risk:        counter overflow if a single key is inserted > MAX_COUNTER times.
 */
public class CountingBloomFilter {

    private static final int COUNTER_MAX = 15;   // 4-bit counter ceiling

    private final int[]  counters;               // the counter array of size m
    private final int    arraySize;              // m
    private final int    hashFunctionCount;      // k
    private       long   insertionCount;

    public CountingBloomFilter(int expectedInsertions, double falsePositiveProbability) {\n        this.arraySize         = BloomFilter.optimalBitCount(expectedInsertions, falsePositiveProbability);\n        this.hashFunctionCount = BloomFilter.optimalHashCount(arraySize, expectedInsertions);\n        this.counters          = new int[arraySize];  // all zeroes by default\n    }

    public void put(String element) {
        for (int index : getIndices(element)) {
            if (counters[index] < COUNTER_MAX) {
                counters[index]++;   // increment counter — safe increment with overflow guard
            } else {
                // Overflow! Log a warning in production — this is a hotspot key.
                System.err.println("WARNING: Counter overflow at index " + index + " for element '" + element + "'");
            }
        }
        insertionCount++;
    }

    /**
     * Removes an element.
     * IMPORTANT: Only call delete() if you're certain the element was previously inserted.
     * Deleting a non-existent element decrements counters erroneously, causing false negatives.
     */
    public boolean delete(String element) {
        if (!mightContain(element)) {
            return false;   // safe guard: definitely not present, nothing to delete
        }
        for (int index : getIndices(element)) {
            if (counters[index] > 0) {
                counters[index]--;   // decrement — restores zero if this was the only user
            }
        }
        insertionCount = Math.max(0, insertionCount - 1);
        return true;
    }

    public boolean mightContain(String element) {
        for (int index : getIndices(element)) {
            if (counters[index] == 0) {
                return false;  // counter is zero → element definitely absent
            }
        }
        return true;
    }

    private int[] getIndices(String element) {
        long[] hashes = BloomFilter.murmur3DoubleHash == null
                ? privateHash(element)  // see note below
                : privateHash(element);
        long h1 = hashes[0];
        long h2 = hashes[1];
        int[] indices = new int[hashFunctionCount];
        for (int i = 0; i < hashFunctionCount; i++) {
            indices[i] = (int) Math.floorMod(h1 + (long) i * h2, arraySize);
        }
        return indices;
    }

    // Reuse the same hash strategy from BloomFilter for consistency
    private static long[] privateHash(String element) {
        byte[] data = element.getBytes(java.nio.charset.StandardCharsets.UTF_8);
        long h1 = 0xDEADBEEFL, h2 = 0xCAFEBABEL;
        for (byte b : data) {
            h1 = Long.rotateLeft(h1 ^ b, 31) * 0x9e3779b97f4a7c15L;
            h2 = Long.rotateLeft(h2 ^ b, 17) * 0xbf58476d1ce4e5b9L;
        }
        h1 ^= h1 >>> 33; h1 *= 0xff51afd7ed558ccdL; h1 ^= h1 >>> 33;
        h2 ^= h2 >>> 33; h2 *= 0xc4ceb9fe1a85ec53L; h2 ^= h2 >>> 33;
        return new long[]{ h1, h2 };
    }

    public static void main(String[] args) {
        CountingBloomFilter sessionFilter =
                new CountingBloomFilter(500_000, 0.02); // 2% fpp, 500k sessions

        // A user logs in → insert their session token
        String sessionToken = "user-8821-sess-a7f3c1";
        sessionFilter.put(sessionToken);

        System.out.println("After insert:");
        System.out.println("  mightContain: " + sessionFilter.mightContain(sessionToken));  // true

        // User logs out → delete their session token
        boolean removed = sessionFilter.delete(sessionToken);
        System.out.println("\nAfter delete (removed=" + removed + "):");
        System.out.println("  mightContain: " + sessionFilter.mightContain(sessionToken));  // false

        // Attempting to delete a token that was never inserted
        boolean removedNonExistent = sessionFilter.delete("ghost-session-xyz");
        System.out.println("\nDelete of non-existent token: " + removedNonExistent);         // false
    }
}

import java.io.*;
import java.nio.file.*;
import java.util.BitSet;

/**
 * Demonstrates how to persist a Bloom filter's bit array to disk
 * and reload it — critical for avoiding false negatives after restarts.
 */
public class BloomFilterPersistence {

    private static final Path FILTER_SNAPSHOT_PATH = Path.of("/tmp/malicious_url_filter.bin");

    public static void saveFilter(BloomFilter filter, Path path) throws IOException {\n        // BitSet.toByteArray() gives us a compact byte[] representation\n        byte[] serializedBits = filter.bitArray.toByteArray();\n\n        // Write a simple header: [bitArraySize (4 bytes)] [hashCount (4 bytes)] [insertionCount (8 bytes)] [bits]\n        try (DataOutputStream out = new DataOutputStream(\n                new BufferedOutputStream(Files.newOutputStream(path)))) {\n\n            out.writeInt(filter.getBitArraySize());       // m — needed to reconstruct correctly\n            out.writeInt(filter.getHashFunctionCount());  // k\n            out.writeLong(filter.getInsertionCount());    // n — for fpp estimation after reload\n            out.write(serializedBits);                    // the actual filter state\n        }
        System.out.printf("Filter snapshot saved: %d bytes on disk%n",
                Files.size(path));
    }

    public static BloomFilter loadFilter(Path path) throws IOException {
        try (DataInputStream in = new DataInputStream(
                new BufferedInputStream(Files.newInputStream(path)))) {

            int  savedBitArraySize      = in.readInt();
            int  savedHashFunctionCount = in.readInt();
            long savedInsertionCount    = in.readLong();

            // Read remaining bytes as the bit array
            byte[] rawBits = in.readAllBytes();
            BitSet restoredBitSet = BitSet.valueOf(rawBits);

            // Reconstruct the BloomFilter shell — pass 0.01 as placeholder;
            // the real state comes from the snapshot, not fresh sizing
            BloomFilter restoredFilter = new BloomFilter(1_000_000, 0.01);

            // Overwrite the in-memory state with the persisted state
            // (In a real codebase, expose a package-private constructor for this)
            restoredFilter.bitArray.clear();          // clear freshly-initialised zeros
            restoredFilter.bitArray.or(restoredBitSet); // load persisted bits
            // NOTE: insertionCount is stored but not shown restored here for brevity

            System.out.printf("Filter loaded: bitArraySize=%d, hashFunctions=%d, insertions=%d%n",
                    savedBitArraySize, savedHashFunctionCount, savedInsertionCount);

            return restoredFilter;
        }
    }

    public static void main(String[] args) throws IOException {
        // Create and populate a filter
        BloomFilter originalFilter = new BloomFilter(1_000_000, 0.01);
        originalFilter.put("http://evil-phishing-site.com/login");
        originalFilter.put("http://malware-dropper.ru/payload.exe");

        System.out.println("Before save — mightContain('http://evil-phishing-site.com/login'): "
                + originalFilter.mightContain("http://evil-phishing-site.com/login"));

        // Persist to disk
        saveFilter(originalFilter, FILTER_SNAPSHOT_PATH);

        // Simulate a service restart — load from disk
        BloomFilter restoredFilter = loadFilter(FILTER_SNAPSHOT_PATH);

        System.out.println("After reload — mightContain('http://evil-phishing-site.com/login'): "
                + restoredFilter.mightContain("http://evil-phishing-site.com/login"));

        System.out.println("After reload — mightContain('http://legitimate-news.com/'): "
                + restoredFilter.mightContain("http://legitimate-news.com/"));
    }
}

// From BloomFilter.java — the core double-hashing logic
long[] murmur3DoubleHash(String element) {
    byte[] data = element.getBytes(StandardCharsets.UTF_8);
    // Two different seeds to produce independent hashes
    long seed1 = 0xDEADBEEFL;
    long seed2 = 0xCAFEBABEL;
    long h1 = seed1, h2 = seed2;
    for (byte b : data) {
        h1 = Long.rotateLeft(h1 ^ b, 31) * 0x9e3779b97f4a7c15L;
        h2 = Long.rotateLeft(h2 ^ b, 17) * 0xbf58476d1ce4e5b9L;
    }
    h1 ^= h1 >>> 33; h1 *= 0xff51afd7ed558ccdL; h1 ^= h1 >>> 33;
    h2 ^= h2 >>> 33; h2 *= 0xc4ceb9fe1a85ec53L; h2 ^= h2 >>> 33;
    return new long[]{ h1, h2 };
}

// Then to get k indices:
for (int i = 0; i < k; i++) {
    int index = Math.floorMod(h1 + (long) i * h2, m);
    bitArray.set(index);
}

// Monitoring example using Guava's BloomFilter
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

// Create filter for 1M expected insertions at 1% fpp
BloomFilter<CharSequence> filter = BloomFilter.create(
        Funnels.stringFunnel(StandardCharsets.UTF_8),
        1_000_000,
        0.01);

// ... after many inserts ...
long currentCount = filter.approximateElementCount();
double currentFpp = filter.expectedFpp();

if (currentCount > 800_000) {
    System.err.println("WARNING: Bloom filter at " + currentCount + " elements, fpp now " + currentFpp);
    // Initiate migration to a larger filter
}

// Persistence on shutdown
filter.writeTo(new FileOutputStream("/tmp/bloom.ser"));

// Reload on startup
BloomFilter<CharSequence> loaded = BloomFilter.readFrom(
        new FileInputStream("/tmp/bloom.ser"),
        Funnels.stringFunnel(StandardCharsets.UTF_8));

// io.thecodeforge — system-design tutorial

import hashlib
from bitarray import bitarray

class CostAwareBloomFilter:
    def __init__(self, size, hash_count, query_latency_ms=50):
        self.size = size
        self.hash_count = hash_count
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)
        self.fp_rate = (1 - 1/size) ** (hash_count * 1000)  # simplified
        self.query_latency_ms = query_latency_ms

    def expected_daily_cost(self, daily_queries=10_000_000, error_cost_per_miss=0.01):
        false_positives = daily_queries * self.fp_rate
        wasted_latency_hours = false_positives * self.query_latency_ms / 3600000
        return {
            'fp_per_day': int(false_positives),
            'wasted_hours': round(wasted_latency_hours, 2),
            'dollar_cost': round(false_positives * error_cost_per_miss, 2)
        }

// io.thecodeforge — system-design tutorial

import hashlib
import redis
from typing import Optional

class CachedBloomFilter:
    def __init__(self, bloom_filter, cache_client: redis.Redis):
        self.bloom = bloom_filter
        self.cache = cache_client
        self.cache_ttl = 300  # 5 minutes

    def maybe_member(self, item: str) -> Optional[bool]:
        # Step 1: Bloom filter (fastest, high false positive)
        if not self.bloom.check(item):
            return False  # definitely not present

        # Step 2: In-memory cache (fast, medium hit rate)
        cached = self.cache.get(item)
        if cached is not None:
            return cached == 'PRESENT'

        # Step 3: Expensive check deferred until both fail
        return None  # caller must hit database

// io.thecodeforge — system-design tutorial

import hashlib
import math

class ScalableBloomFilter:
    def __init__(self, init_capacity=1000, error_rate=0.01, growth=2):
        self.filters = []
        self.growth = growth
        self.error_rate = error_rate
        self._add_filter(init_capacity, error_rate)

    def _add_filter(self, capacity, error_rate):
        self.filters.append(BloomFilter(capacity, error_rate))

    def add(self, item):
        if self.filters[-1].count >= self.filters[-1].capacity:
            new_error = self.error_rate / (len(self.filters) + 1)
            new_cap = int(self.filters[-1].capacity * self.growth)
            self._add_filter(new_cap, new_error)
        self.filters[-1].add(item)

    def contains(self, item):
        return any(f.contains(item) for f in self.filters)

# Simple BloomFilter class omitted for brevity
# Usage:
sbf = ScalableBloomFilter()
sbf.add("user_42")
print(sbf.contains("user_42"))    # True

// io.thecodeforge — system-design tutorial

import threading

class CountingBloomFilter:
    def __init__(self, size, num_hashes):
        self.counters = [0] * size
        self.num_hashes = num_hashes
        self.lock = threading.Lock()

    def add(self, item):
        with self.lock:
            for h in self._hashes(item):
                if self.counters[h] < 255:
                    self.counters[h] += 1
                # Silent overflow — bad design

    def remove(self, item):
        with self.lock:
            for h in self._hashes(item):
                if self.counters[h] > 0:
                    self.counters[h] -= 1

# Simulate race: add twice, remove once
cbf = CountingBloomFilter(100, 3)
cbf.add("hot_key")
cbf.add("hot_key")
cbf.remove("hot_key")
print(cbf.counters[:3])   # [1, 0, 1] — corrupted state

// io.thecodeforge — system-design tutorial

import math

def optimal_k(m: int, n: int) -> int:
    """Return optimal number of hash functions."""
    return max(1, round(m / n * math.log(2)))

def false_positive_rate(m: int, n: int, k: int) -> float:
    """Compute theoretical false positive probability."""
    return (1 - math.exp(-k * n / m)) ** k

m, n = 1000, 100
k = optimal_k(m, n)
fp = false_positive_rate(m, n, k)
print(f"Optimal k={k}, false positive rate={fp:.4f}")

// io.thecodeforge — system-design tutorial

def should_use_bloom(n: int, m: int, exact: bool, deletions: bool):
    if exact:
        return False  # Use hash set
    if deletions and m < n * 16:
        return False  # Counting Bloom overhead too high
    return m / n <= 16  # Bloom efficient only when bits-per-item < 16

print(should_use_bloom(1_000_000, 8_000_000, False, False))