Bloom Filters

A Bloom filter is a compact bit array used to test set membership. It can tell you an item is definitely not in the set, or possibly in the set. It never has false negatives, but it can have false positives. This makes it perfect as a fast, memory-cheap *first check* before an expensive lookup — if the filter says "no", you skip the database entirely.

1. Learning Objectives

By the end of this lesson, you will be able to:

• Explain the mathematical guarantees of a Bloom filter, including why it yields zero false negatives but allows for false positives.
• Derive the optimal size of a bit array ($m$) and the number of hash functions ($k$) based on target false positive probability ($p$) and expected element count ($n$).
• Compare Bloom filters with alternatives such as Cuckoo filters, Quotient filters, and traditional in-memory hash tables on space complexity and CPU metrics.
• Understand and apply the Kirsch-Mitzenmacher optimization to reduce hash function generation to a simple arithmetic combination of two seed hash functions.
• Integrate Bloom filters into production-ready distributed system architectures to bypass expensive disk and network operations.

2. Prerequisites

To get the most out of this lesson, you should be familiar with:

• Basic Hash Functions: Knowledge of how hash functions distribute keys uniformly across a range and the concept of hash collisions.
• Bitwise Operations: Familiarity with operations like AND, OR, and bit shifts, as well as accessing specific bits within byte arrays.
• Logarithms and Exponents: Comfort with standard mathematical formulas containing natural logarithms ($\ln$) and Euler's constant ($e$).
• Database I/O Patterns: Understanding the latency differences between reading from physical disk storage (SSD/HDD) versus accessing CPU caches and RAM.

3. Why This Topic Matters

In modern high-scale systems, data volume dominates. Databases and object storage engines store petabytes of data, but lookup speed is bounded by physical disk seeks or network latency. Querying a storage layer for a key that does not exist represents a major source of resource wastage.

A Bloom filter solves this issue by acting as an in-memory sentinel. If a key is absent, the filter guarantees it is absent, preventing expensive physical I/O requests. For example, if 90% of your incoming search queries for usernames or URLs target non-existent data, a Bloom filter can intercept them in RAM at sub-microsecond speeds. This reduces disk read utilization by up to 90%, reduces latencies for absent checks, and lowers cloud infrastructure costs by minimizing read throughput requirements.

4. Real-world Analogy

Imagine a high-security international airport security gate checking passports against a massive database of banned individuals. The database is stored in a main central mainframe computer that takes 10 seconds to respond to each network query.

To optimize this flow, the gate officer is given a small, fast paper checklist containing a grid of 1,000 blank squares. During preparation:

• When adding a banned person (e.g., "John Doe") to the checklist, the system uses 3 distinct rubber stamp tools based on the name. Let's say "John Doe" stamps boxes 12, 105, and 850. The boxes are inked green.
• When a traveler named "Jane Smith" arrives, the officer checks her name with the 3 stamps. The stamps point to boxes 5, 105, and 410.
• The officer looks at box 5, which is empty (white).

Since box 5 is empty, the officer immediately knows that Jane Smith's name could not have been added to the list (because if it had been, box 5 would be inked green). Jane Smith is cleared to proceed within a millisecond, without contacting the mainframe database.

If another traveler, "Bob Carter", arrives and his stamp locations (12, 105, and 850) are all green, the officer cannot be 100% sure if Bob is actually banned, or if those three boxes were stamped green by a combination of other banned individuals (e.g., John Doe stamped 12 and 105, while another banned traveler stamped 850). The officer then contacts the slow mainframe database to verify. This represents a false positive, but it is acceptable because the slow check is only triggered occasionally, and no banned traveler is ever mistakenly cleared (no false negatives).

5. Core Concepts

To design and implement a Bloom filter, you must understand its core mathematical and logical pillars:

• Bit Array ($m$): A flat sequence of $m$ bits initialized to 0. The size of the array is fixed at creation and dictates the capacity and accuracy bounds.
• Independent Hash Functions ($k$): A set of $k$ distinct hash functions. Each function must map an input key uniformly across the indices $0$ to $m-1$. They must be fast, non-cryptographic, and independent of each other.
• No False Negatives: If an element was inserted, the hash functions set all its corresponding bit indices to 1. When querying, checking those indices will find only 1s. Thus, the filter will never say an item is missing when it is actually in the set.
• Possible False Positives: If an element was not inserted, its hash indices might still point to bits that have all been set to 1 by other, previously inserted elements. The query will return true, falsely claiming membership.
• Set Membership Operation: A binary state check returning either "Definitely Not Present" (100% certain) or "Probably Present" (probabilistic confidence).

6. Visualization

The following diagram illustrates how keys are mapped to a shared bit array, demonstrating an insertion and a query path that results in a false positive check.

7. How It Works

The operational lifecycle of a Bloom filter consists of three distinct phases: Initialization, Insertion, and Querying. Let's break down each step-by-step.

Phase 1: Initialization

1. We allocate a bit array of size $m$, setting all bits to 0.
2. We choose $k$ independent hash functions: $h_1, h_2, \dots, h_k$.

Phase 2: Insertion

When inserting an item $x$:

1. Feed $x$ into the $k$ hash functions to get $k$ output values: $h_1(x), h_2(x), \dots, h_k(x)$.
2. Apply the modulo operator to scale the hashes to the size of the bit array:

Set the bits at these calculated indices to 1. If a bit is already 1, it remains 1.

Phase 3: Querying

To check if an item $y$ is in the set:

1. Feed $y$ into the $k$ hash functions to calculate the $k$ target indices.
2. For each index, read the corresponding bit in the array:
   • If any of the bits is 0, the check halts immediately and returns false. (Proof: If $y$ had been inserted, all those bits would have been turned to 1).
   • If all of the bits are 1, the check returns true. The item is probably present.

8. Internal Architecture

A Bloom filter's internal components work together to provide high-speed, space-efficient lookups. The table below details the components, their responsibilities, and primary failure modes:

9. Request Lifecycle

In a microservices or database system, a client request travels through layers. Here is the path of a request querying a key-value store optimized with a Bloom filter:

1. Request Ingress: The client sends a GET request for a key (e.g., UUID:9a7f-43e9) to the API Service.
2. First Level Guard: The API Service routes the lookup to the storage driver. The driver checks the in-memory Bloom filter before accessing cache nodes or databases.
3. Bloom Filter Execution:
   • The key's bytes are hashed using $k$ hash values.
   • The corresponding bits are read.
4. Outcome A: Guard Negative (Definite Miss):
   • At least one bit is 0.
   • The Bloom filter instantly reports "Key does not exist".
   • The API Service returns a 404 Not Found response to the client. The cache and physical database are completely bypassed. Latency: < 1 ms.
5. Outcome B: Guard Positive (Possible Hit):
   • All bits are 1.
   • The database proceeds to query the fast in-memory cache (e.g., Redis). If it hits, it returns the value (Latency: 1-5 ms).
   • If it misses the cache, the database triggers a disk read (e.g., index scans and SSTable lookups) to pull the record.
   • If the key exists on disk, it is returned. If it does not exist (a false positive match), the database returns a 404. Latency: 10-100 ms.

10. Deep Dive

Let's explore the mathematical framework of Bloom filters, their configuration math, and alternative advanced structures.

1. Mathematical Derivation of False Positives

Assuming an array of size $m$ bits and a perfectly uniform hash function. When we set a single bit, the probability that a specific bit is not set by a single hash run is:

If we insert one element using $k$ independent hash functions, the probability that this specific bit remains 0 is:

After inserting $n$ distinct elements, the probability that the bit remains 0 is:

Using the limit approximation $(1 - x/y)^y \approx e^{-x}$ as $y$ becomes large, we approximate:

Consequently, the probability that a specific bit is set to 1 after $n$ insertions is:

For a false positive to occur, an element that was never inserted must hash to $k$ indices that are all already set to 1. The probability $p$ of this event is:

2. Sizing Optimization Formulas

To configure a Bloom filter correctly, we must determine optimal values for $m$ (size) and $k$ (number of hash functions) for a given target capacity $n$ and false positive rate $p$:

• Optimal Number of Hash Functions ($k$): The probability $p$ is minimized when the bit array is exactly half full of 1s (i.e. $e^{-kn/m} = 0.5$). Solving for $k$ gives:

Optimal Bit Array Size ($m$): Substituting the optimal $k$ back into the probability formula, we solve for $m$:

3. Advanced Variants

• Counting Bloom Filter (CBF): A standard Bloom filter cannot support deletion because setting a bit to 0 could accidentally delete other overlapping elements. CBFs solve this by replacing the bit array with an array of multi-bit cell counters (usually 3 or 4 bits per counter). Insertion increments the counter at the hashed indices, and deletion decrements them. If a counter drops to zero, the bit is considered unset. This costs 4x more memory than a standard filter.
• Scalable Bloom Filter (SBF): SBFs solve the capacity problem. Instead of being bounded by a fixed $n$, an SBF dynamically handles growth by appending a new, separate Bloom filter with a tighter false positive rate and larger capacity whenever the current active filter reaches a density threshold. Lookups check all active filters in the chain.
• Cuckoo Filter: A modern alternative that uses cuckoo hashing to store small fingerprints of items in a hash table. Cuckoo filters support deletion, have better CPU cache locality, and require less space than Bloom filters when target false positive rates are low (< 3%).

11. Production Example

Let's look at how large-scale companies leverage Bloom filters in production:

1. Apache Cassandra Read Path

Cassandra stores data on disk in immutable files called SSTables. A single partition query might need to scan dozens of SSTables. To avoid reading disk indices for files that do not contain the target partition key, Cassandra stores a Bloom filter in RAM for each SSTable. The read path executes as follows:

• The query coordinator receives a read request.
• It looks at the in-memory Bloom filter for each candidate SSTable file.
• If the filter returns false, Cassandra skips that file completely.
• This restricts disk checks to only the SSTables that are highly likely to contain the data, keeping Cassandra read latencies under 5 milliseconds.

2. Google Chrome Safe Browsing

Chrome protects users from phishing and malware URLs by warning them when they visit unsafe sites. Querying Google's central database for every page load introduces massive latency and raises privacy concerns. Chrome downloads and caches a Bloom filter containing hashes of malicious URLs locally on the user's machine. When a user visits a page:

• Chrome checks the local Bloom filter.
• If it does not match, the page loads instantly.
• If it matches, Chrome makes a targeted API call to Google's backend, sending a small prefix of the URL hash to verify if it is a real match or a false positive. This secures the user's privacy and keeps the browser fast.

3. Medium Recommendations

Medium wants to avoid recommending articles that a reader has already viewed. Each time a reader views an article, the article's ID is added to a Bloom filter mapped to the user. When recommending stories, Medium checks candidate articles against the user's Bloom filter. Matches are excluded, ensuring fresh recommendations without traversing massive relational join tables on every feed refresh.

12. Advantages

• Exceptional Space Efficiency: Unlike hash tables or binary trees that store the keys themselves, Bloom filters store only bit flags. A filter with a 1% false positive rate requires only ~9.6 bits per item, regardless of key size (e.g. 100-character URLs take the same space as 4-byte integers).
• Fixed, Constant Time Complexity: Both insert and lookup operations operate in $O(k)$ time, where $k$ is the number of hash functions. It is independent of the number of items currently in the set.
• Strict Privacy Guarantees: Since keys are never stored and cannot be reconstructed from set bits, Bloom filters are ideal for privacy-sensitive data like security blacklists, passwords, and user tracking.
• Zero Memory Fragmentation: The bit array is allocated as a single, contiguous block of memory. This prevents overhead associated with dynamic memory allocation, pointer chasing, or garbage collection.

13. Limitations

• No Item Deletion Support: In a standard Bloom filter, setting a bit back to 0 is forbidden, as that bit could be shared by other elements. Attempting to delete items corrupts the filter and introduces false negatives.
• Unbounded False Positive Rate on Overfill: The accuracy of a Bloom filter degrades as the number of elements increases. If you write more items than the capacity $n$, the bit array fills up, and the false positive rate climbs to 100%.
• Cannot List Elements: You cannot iterate over or retrieve the elements inside a Bloom filter. It can only answer membership queries.
• No Key-Value Storage: It cannot associate values with keys; it is strictly a set membership checker.

14. Trade-offs

When designing systems with Bloom filters, you must balance these three trade-offs:

• Memory Size ($m$) vs. False Positive Rate ($p$): Allocating more RAM reduces the likelihood of false positives. If RAM is scarce, you must tolerate more false positive checks falling back to the database.
• CPU Hash Operations ($k$) vs. False Positive Rate ($p$): A higher $k$ reduces the false positive rate up to the mathematical limit, but increases CPU cycles for hashing and causes more cache misses.
• Standard vs. Counting Bloom Filters: Choosing a Counting Bloom filter allows you to delete keys, but increases memory usage by 4x to 8x (due to using counters instead of a single bit flag).

15. Performance Considerations

To achieve high throughput under heavy workloads, keep these performance optimizations in mind:

1. CPU Cache Locality

When a Bloom filter's bit array is several megabytes, checking $k$ random locations forces the CPU to jump across different cache lines. This triggers several L1/L2/L3 cache misses. To optimize this, production systems often use Blocked Bloom Filters. A Blocked Bloom filter divides the array into cache-line-sized blocks (e.g. 64 bytes). Insertion and lookups are restricted to a single block, keeping all bit checks within a single L1 cache access.

2. Choice of Hash Function

Never use cryptographic hash functions like SHA-256 or MD5. They are computationally expensive and will choke CPU performance. Instead, use fast, non-cryptographic hashes designed for hash tables, such as:

• MurmurHash3: Excellent distribution, fast, and mixes bits thoroughly.
• FNV-1a: Very simple to implement and fast for small inputs.
• xxHash: Extremely fast, near RAM limits, and works well on modern 64-bit architectures.

3. The Kirsch-Mitzenmacher Optimization

Computing $k$ distinct hashes for every item can be slow. Kirsch and Mitzenmacher proved that you can generate $k$ independent-like hash values using only two base hash functions, $h_1(x)$ and $h_2(x)$, using the formula:

Where $i$ ranges from $0$ to $k-1$. This optimization drops the hashing cost from $O(k)$ to $O(1)$ hash calls, followed by simple multiplication and addition, with zero loss in filter accuracy.

16. Failure Scenarios

Bloom filters can fail or degrade in silent ways. You must plan for the following conditions:

• Filter Saturation (Occupancy Death): If a service runs continuously and adds items past the target capacity $n$, the ratio of 1 bits in the array approaches 1.0. Once all bits are 1, every lookup returns true. The filter fails silently: it does not crash, but it passes all requests to the database, causing a database load spike.
• Underestimated Capacity ($n$): If the system experiences a traffic surge or data growth that exceeds the estimated capacity by 2x, the false positive rate escalates exponentially. For example, a filter sized for 1% error rate at $n=1M$ will jump to over 10% error rate at $n=1.5M$.
• Lost Updates under High Concurrency: If multiple threads write to the bit array without atomic synchronization (e.g. using regular read-modify-write), concurrent writes can overwrite each other. This results in missing bits, creating false negatives, which violates the filter's primary contract.

17. Best Practices

• Size for Peak Capacity: Always estimate peak capacity ($n$) with a 50% safety buffer. Sizing a Bloom filter larger than needed has negligible memory costs relative to database load spikes.
• Monitor Bit Density: Set up telemetry alerts to track the fraction of bits set to 1 (density). If density exceeds 50%, trigger a rebuilding process or scale the filter.
• Use Atomic Bitwise Operations: Ensure thread safety during concurrent writes by using atomic instructions (e.g., Atomics.or in JavaScript/TypeScript, or atomic CPU primitives).
• Leverage the Kirsch-Mitzenmacher Double Hashing: Implement double hashing to minimize CPU overhead in hot paths.

18. Common Mistakes

• Attempting to Delete Items: Trying to delete keys from a standard Bloom filter by setting their bits to 0. This causes catastrophic silent corruption. Use a Counting Bloom filter or Cuckoo filter if deletions are required.
• Using Cryptographic Hashes in Hot Paths: Using MD5, SHA-1, or SHA-256 inside high-throughput servers. Hashing cost will dominate CPU utilization, neutralizing the benefits of the filter.
• Never Rebuilding the Filter: Stale keys for deleted database entries remain in the filter forever, slowly inflating the false positive rate. Implement a background job to periodically rebuild the filter from the primary data source.

19. Implementation

Below is a fully functional, highly optimized TypeScript implementation of a Bloom filter. It features dynamic sizing calculations, double hashing optimization, and raw byte manipulation for efficiency.

20. Interview Questions

Easy Question

Q: Explain why a Bloom filter has no false negatives, but can yield false positives.

A: When an element is inserted, the filter hashes the key using $k$ hash functions and sets the corresponding bits in the array to 1. Therefore, if the item is in the set, checking those same $k$ positions is guaranteed to find only 1s. This guarantees zero false negatives. However, multiple items can set overlapping bits. A key that was never inserted may map to $k$ bits that were already flipped to 1 by other keys. This leads to a false positive.

Medium Question

Q: How does a Counting Bloom filter support item deletions, and what are its trade-offs?

A: A standard Bloom filter cannot support deletion because setting a bit back to 0 might delete overlapping bits set by other elements. A Counting Bloom filter solves this by replacing each bit with a multi-bit counter (typically 3 or 4 bits). When an item is inserted, the counters at the $k$ hashed locations are incremented. When deleted, those counters are decremented. If a counter drops to zero, the bit is treated as 0. The trade-off is memory: replacing a single bit with a 4-bit counter increases the memory footprint by 4x.

Hard Question

Q: How does the Kirsch-Mitzenmacher optimization work? Why is it crucial for high-throughput stream processing systems?

A: Calculating $k$ independent hashes (e.g. 8 hashes) for every input key is expensive. Kirsch and Mitzenmacher showed that you only need to compute two base hashes, $h_1(x)$ and $h_2(x)$, using FNV-1a or MurmurHash. You can then generate $k$ hash values using the mathematical combination $g_i(x) = (h_1(x) + i \cdot h_2(x)) \pmod m$ for $i \in [0, k-1]$. This is crucial for high-throughput systems because it reduces the CPU hashing work from $O(k)$ to $O(1)$, replacing expensive string hashing operations with cheap CPU multiplication and addition instructions.

21. Practice Exercises

Note: These exercises are designed for active learning. Answers are omitted so you can solve them independently.

Easy Exercise

Given a capacity of $n = 50,000$ elements and a target false positive rate of $p = 0.05$ (5%), calculate the required size of the bit array ($m$) and the optimal number of hash functions ($k$). Convert $m$ to kilobytes (KB) to understand the memory footprint.

Medium Exercise

Write a pseudocode or Python script that implements a Counting Bloom Filter. The filter should support insert(item), delete(item), and exists(item). Include check logic to prevent counter overflow (e.g., if a 4-bit counter reaches 15, it should not increment further).

Hard Exercise

Design a Scalable Bloom Filter wrapper class. This wrapper should hold an array of standard Bloom filters. When the occupancy of the current active filter exceeds 60%, the wrapper should instantiate a new Bloom filter with double the capacity of the previous one and a smaller target false positive rate. Implement insert and exists across the dynamic chain of filters.

22. Challenge Problem

Scenario: You are designing a distributed Web Crawler that parses millions of pages per second. The crawler must keep track of all visited URLs to avoid crawling the same pages repeatedly. The total number of unique URLs is estimated to reach 10 billion over a 30-day period. Each URL is roughly 100 characters long.

Constraints:

• The visited set checker must fit inside distributed Redis RAM clusters. The maximum budget allocated for this is 20 GB.
• Checking if a URL has been crawled must take less than 2 milliseconds.
• False negatives are not allowed (we must never crawl the same page twice). False positives are acceptable, but must be kept below 2%.

Tasks: Describe your design addressing the following points:

1. Calculate the total size $m$ in bits and check if the 20 GB budget is sufficient.
2. How will you handle partitioning the Bloom filter across multiple Redis nodes to avoid hot spot servers?
3. Explain how you will handle updates and synchronization as multiple crawler worker nodes query and update the visited set concurrently.

23. Summary

A Bloom filter is a fundamental probabilistic data structure that provides space-efficient set membership queries. Key takeaways include:

• It answers whether an item is in a set with no false negatives but with a configurable probability of false positives.
• It is highly space-efficient because it stores only bit flags rather than the raw keys, making it independent of item sizes.
• It operates in $O(k)$ time complexity for both inserts and lookups, which is constant relative to the size of the set.
• Its mathematical optimization relies on choosing an optimal bit size ($m$) and number of hash functions ($k$) based on target item count ($n$) and error rate ($p$).
• In production, it serves as an in-memory sentinel to prevent slow, expensive physical disk reads or network lookups.

24. Cheat Sheet

25. Quiz

1. 1. Which of the following statements is TRUE regarding a standard Bloom filter?

   • A. It can return false negatives but never false positives.
   • B. It can return false positives but never false negatives.
   • C. It supports adding, querying, and deleting items.
   • D. It requires more space as the size of individual inserted items grows.

   Answer: B. A Bloom filter is guaranteed to have no false negatives because a present item's bits are always set to 1. However, bit collisions can cause false positives.

2. 2. What happens if a standard Bloom filter is filled far beyond its designed capacity $n$?

   • A. The filter throws an OutOfMemory error.
   • B. The filter automatically resizes itself, allocating a new larger bit array.
   • C. The bit array saturates (all bits become 1), causing the false positive rate to reach 100%.
   • D. The query latency increases from O(k) to O(N).

   Answer: C. Overfilling sets almost all bits to 1, meaning any query will hit only 1s, leading to a 100% false positive rate.

3. 3. Which hash function type is most appropriate for a high-performance Bloom filter?

   • A. Cryptographic hash functions like SHA-256 for maximum collision resistance.
   • B. Non-cryptographic hash functions like MurmurHash3 or xxHash for raw execution speed.
   • C. Simple modulo arithmetic on character codes without mixing.
   • D. Reversible encryption functions like AES.

   Answer: B. Non-cryptographic hashes are much faster than cryptographic ones, ensuring that the filter lookup is not a bottleneck.

4. 4. Why is item deletion not supported in a standard Bloom filter?

   • A. The hash functions are one-way.
   • B. Clearing a bit to 0 can inadvertently remove other items that mapped to that same bit.
   • C. Deleting items causes memory fragmentation.
   • D. The array size is fixed.

   Answer: B. Bits are shared between elements. Resetting a bit to 0 affects all other elements mapping to that same bit, introducing false negatives.

5. 5. What is the core benefit of the Kirsch-Mitzenmacher optimization?

   • A. It reduces the false positive rate by half.
   • B. It enables dynamic resizing of the bit array.
   • C. It allows generating k hash values using only two base hash functions, saving CPU cycles.
   • D. It allows deletes without needing a Counting Bloom Filter.

   Answer: C. It uses the formula (h1 + i * h2) % m to generate k hashes from just two real hash operations.

6. 6. In Cassandra, what is the role of the Bloom filter?

   • A. To store database rows in memory.
   • B. To sort primary keys in alphabetical order.
   • C. To check if an SSTable contains a requested key before doing disk read.
   • D. To encrypt data blocks written to disk.

   Answer: C. Checking the Bloom filter first avoids wasting disk reads on SSTables that do not have the requested partition key.

7. 7. How does a Counting Bloom filter represent each index instead of a single bit?

   • A. With a string pointer.
   • B. With a small integer counter (e.g. 3 or 4 bits).
   • C. With a float representing probability.
   • D. With a nested sub-Bloom filter.

   Answer: B. Multi-bit counters allow tracking of how many elements set that specific index, facilitating safe decrements during deletion.

8. 8. Under optimal conditions, what is the target occupancy density of a Bloom filter?

   • A. 10%
   • B. 50%
   • C. 75%
   • D. 100%

   Answer: B. The false positive rate is mathematically minimized when the bit array is exactly 50% full (half 0s and half 1s).

9. 9. Which of the following is a key advantage of Cuckoo Filters over Bloom Filters?

   • A. They support 100% zero false positives.
   • B. They support dynamic resizing without limit.
   • C. They natively support item deletion and have better CPU cache locality.
   • D. They do not use hash functions.

   Answer: C. Cuckoo filters support deletion natively and pack items in contiguous buckets, improving cache performance.

10. 10. If the size of individual keys increases from 10 bytes to 1,000 bytes, what happens to the size of the Bloom filter?

    • A. It increases by 100x.
    • B. It remains unchanged.
    • C. It increases logarithmically.
    • D. It decreases because larger keys have fewer collisions.

    Answer: B. Bloom filters only store bit signatures generated by hash functions. The key size does not affect the size of the bit array.

26. Further Reading

• Original Paper: Bloom, Burton H. (1970). "Space/time trade-offs in hash coding with allowable errors". Communications of the ACM.
• Double Hashing Optimization: Kirsch, Adam; Mitzenmacher, Michael (2008). "Less Hashing, Same Performance: Building a Better Bloom Filter". Random Structures & Algorithms.
• Cuckoo Filters Paper: Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael (2014). "Cuckoo Filter: Practically Better Than Bloom". CoNEXT '14.

27. Next Lesson Preview

In the next lesson, we will move from probabilistic set structures to Log-Structured Merge-Trees (LSM-Trees). We will see how Cassandra and RocksDB organize data on disk sequentially to achieve high write throughput, and how they integrate Bloom filters as part of their core read-path optimization to maintain sub-millisecond lookup speeds.