Forem: rajeevrajeshuni

Introduction to Bloom Filters

rajeevrajeshuni — Sun, 01 Mar 2026 05:03:53 +0000

Introduction to Bloom Filters
Operation on the Bloom Filter
Example
Advantages of a Bloom Filter Over a Set Data Structure
Choosing a Hash Function
Tuning a Bloom Filter
Example Use Cases

Introduction to Bloom Filters

Bloom filter is a probabilistic data structure used to solve the set membership problem. A relaxed constraint here is that false positives are tolerated to an acceptable level.

Bloom filter uses a bit array to store the presence of items. Bloom filter uses hash functions to save the presence of an item without saving the actual item.

Bloom filters can give false positives, but never false negatives. This means that if the bloom filter returns positive, it means that the element may be present in the set, but if it returns negative, it means that the element is definitely not present in the set.

Now let us define a few variables before jumping into the algorithm:

n - The number of elements to be added in to the set.
k - The number of hash functions we use.
m - The length of the bit array we will use.

Let us assume we have n elements to insert into the set. Before inserting elements, let us create a bit array of size m with all values set to 0, and k hash functions which return values in the range of (0, m-1).

Operation on the Bloom Filter

Steps for Adding an Element

For each element we run k hash functions and then use the result as the index in the bit array. We mark the element at that index as 1. We will also store the elements in secondary storage for bookkeeping.

func addElement(item SetItem) {
    // Iterate over the array of hash functions
    for _, hashFunction := range hashFunctions {
        v := hashFunction(item)
        bitarray[v] = 1
    }
    // Here you'd save the item to secondary storage.
}

Steps for Looking Up an Element

Similar to above, we run k hash functions on an element and use the result as an index in the bit array. We check the value in each of those indexes and if the value is 1 in all of them, the bloom filter returns true.

func lookUpElement(item SetItem) bool {
    // Iterating over the array of hash functions
    for _, hashFunction := range hashFunctions {
        v := hashFunction(item)
        if bitarray[v] == 0 {
            return false
        }
    }
    return true
}

The bits at those indexes could be made 1 by different elements resulting in a false positive, but that is a tradeoff with bloom filter.

Steps for Deleting an Element

You cannot delete an element from the bloom filter. This is a significant drawback, but that is the tradeoff for reducing space utilization.

Example

We choose three hash functions and a bit array of size 16 with all bits as 0. Let us add elements A and B.

Flow for Adding the Elements

We take the element and get the hash value from the three functions and mark the corresponding bits as 1 in the bit array.

Let the hash values for A be 7, 1, and 14. So the array will change to:

Values	0	1	0	0	0	0	0	1	0	0	0	0	0	0	1	0
Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

Let the hash values for B be 8, 1, and 15. So the array will change to:

Values	0	1	0	0	0	0	0	1	1	0	0	0	0	0	1	1
Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

Flow for Looking Up an Item

Let's say we are searching for the element C, whose hash values are 1, 15, and 9. The values in the bit array at index 1, 15 are 1, but the value at index 9 is 0. So we can safely say that the C is not part of the set.

Why Array Lengths in Powers of 2?

When hashing, why do we usually take array lengths in powers of 2? This is because, usually we do a mod of the size of the array to find the index. If the array size is a power of 2, then taking a mod is simply a bitwise operation. Let's say the number is 254 which is 11111110. 254 \% 16 will be the last 4 bits which is 1110 which is 14.

Advantages of a Bloom Filter Over a Set Data Structure

Optimized Space Usage:
- Usually a set data structure is maintained using a self-balancing binary tree, hash table, array, linked list, or trie.
- These data structures require storing at least the elements themselves (except for trie). The items could be a small integer or a large string.
- In contrast, the bloom filter takes the same amount of space for an item of any length.
Constant Insertion and Lookup Time:
- Bloom filters also have the advantage that the insertion time is a constant value \mathrm{O}(k). The same is the case for lookup time.
Parallelizing Hash Functions:
- There is also the advantage of parallelizing the execution of hash functions.

Choosing a Hash Function

Requirements for the Hash Function:
- Fast computation
- Uniform distribution
- Cryptographic security to avoid reverse engineering is not a concern here.
Common Hash Functions:
- In line with the above requirements, bloom filters typically use the hash functions MurmurHash, JenkinsHash, and FNV Hash.

Tuning a Bloom Filter

We can intuitively see that if we keep adding elements to a bloom filter, the collisions increase and hence the false positive rate also increases. In the worst case, the bloom filter returns true for any given element. Since we have all the elements saved in secondary storage, we need to increase the values m and k and create another bloom filter.

We can see that there is a tradeoff between the false positive probability p, the number of elements n, blooom filter T with the number of bits m, and the number of hash functions k.

For simplicity, let us assume that for any element e and hash function h_i, h_i(e) is distributed independently and uniformly over the range of values 1 to m. Let us also assume that the probabilities that the different bits in the filter T, T[l] are set to 1 are independent.

For any 1 ≤ l ≤ m, we evaluate the probability that T[l] = 0, after inserting all n elements into the table.

For each e ∈ S and 1 ≤ i ≤ k, the probability that h_i(e) ≠ l is (1 - 1/m).

The probability that T[l] = 0 after inserting all n elements with k probes each is simply (1 - 1/m)^{kn}.

Thus, the probability that an entry T[l] = 1 after n insertions is simply 1 - (1 - 1/m)^{kn}.

A false positive occurs when e' ∉ S but T[h_i(e')] = 1, for all 1 ≤ i ≤ k. Hence:

\left( 1 - \left( 1 - \frac{1}{m} \right)^{kn} \right)^k \approx (1 - e^{-kn/m})^k

For a given n and m, one can find the k that minimizes the probability p by differentiating the right-hand side of Equation 1 with respect to k and setting it to zero. Solving for k provides the following.

\approx (\ln 2) \cdot (m/n)

Plugging in the value of k from Equation 2 into Equation 1, we get the following relation.

\approx 2^{-k} \approx 2^{-(m/n)\ln 2}

You can explore https://hur.st/bloomfilter/ to get these values.

Example Use Cases

Akamai's Caching Strategy:
- Akamai uses a bloom filter to avoid caching one-hit wonders. They cache an item only when it is accessed for the second time.

Unpacking the Google File System Paper: A Simple Breakdown

rajeevrajeshuni — Mon, 15 Dec 2025 18:31:56 +0000

Core Philosophy: Keep It Simple, Scale Big

GFS prioritizes simplicity, high throughput, and fault tolerance over strict consistency. Key ideas:

Relaxed consistency: Trades strict data guarantees for performance.
Single master: Simplifies metadata management but risks bottlenecks (minimized by design).
Workload focus: Optimized for large files and sequential access, not small files.

GFS Architecture: Masters, Chunkservers, Clients

GFS has three main components:

Master: Stores metadata (file structure, chunk locations) in memory for speed.
Chunkservers: Store 64 MB data chunks, replicated (usually 3x) on local disks.
Clients: Applications that get metadata from the master and data directly from chunkservers.

The single master simplifies the design while staying lightweight by handling only metadata operations.

Design Choice #1: Big 64 MB Chunks

GFS uses 64 MB chunks instead of the typical 4 KB blocks found in most file systems.

Why?

Fewer master queries: Large chunks mean less metadata communication overhead.
Stable connections: Long-lived TCP connections to chunkservers reduce network overhead.
Small metadata footprint: Fewer chunks keep the master's memory usage low.

Downsides

Small files waste space: A tiny file still consumes an entire 64 MB chunk.
Hotspots: Popular small files can overload individual chunkservers (mitigated with extra replicas).

Design Choice #2: Split Control and Data Planes

GFS separates metadata management (master) from data storage (chunkservers).

How It Works

Master handles file namespace and chunk location mapping.
Clients communicate directly with chunkservers for actual data transfer.

Benefits

Lightweight master: No data handling keeps the master fast and responsive.
High throughput: Direct client-chunkserver communication maximizes bandwidth.
Simple design: Clear separation of concerns makes GFS easier to manage.

This architecture supports thousands of concurrent clients without bottlenecking.

How Reads Work

Reading in GFS follows a simple pattern:

Client converts file name and byte offset into a chunk index (offset ÷ 64 MB).
Client requests chunk handle and chunkserver locations from master.
Master responds with metadata; client caches this information.
Client directly requests data from the appropriate chunkserver.
Chunkserver returns the requested byte range.

Design Choice #3: Two Write Patterns

GFS handles writes differently depending on the operation type:

Concurrent Writes

Master designates one replica as the primary for each chunk.
Clients send writes to the primary, which coordinates with secondary replicas.
Primary ensures all replicas apply writes in the same order.

Concurrent Appends

Still uses the primary replica for coordination and ordering.
GFS (via the primary) automatically selects the append offset to avoid client coordination overhead.
Clients receive the actual offset where data was written.

Benefits

Lock-free: Multiple clients can append simultaneously without coordination.
Atomic Append Guarantees: Each append operation is guaranteed to complete atomically.

Design Choice #4: Relaxed Consistency Model

GFS deliberately avoids strict consistency guarantees.

Why?

Simplifies the overall system design and improves performance.
Aligns with Google's append-heavy, read-mostly application patterns.

Implications

Consistent metadata: File creation and deletion operations are strongly consistent.
Relaxed data consistency: Concurrent writes may result in interleaved data; clients must identify valid data regions.

This trade-off works well for Google's specific use cases but requires application-level awareness.

Fault Tolerance Mechanisms

GFS ensures high availability through several techniques:

Write-Ahead Logging (WAL): Master operations are logged to disk before acknowledgment, ensuring metadata durability.
Shadow masters: Backup master servers provide read-only access and failover capability.
Simplified recovery: Only namespace and file-to-chunk mappings are persisted; chunk locations are rediscovered by querying chunkservers at startup.

Data Integrity: Checksums

GFS employs checksums to detect data corruption (critical with thousands of commodity disks):

Chunkservers verify data integrity during both reads and writes.
Essential for maintaining reliability.

Challenges and Limitations

GFS has some inherent limitations:

Single master bottleneck: Though rare due to the lightweight design and shadow replicas for reads.
Small file inefficiency: 64 MB chunks are suboptimal for small files.
Consistency complexity: Clients must handle potentially inconsistent data regions.

Conclusion

GFS revolutionized distributed storage by demonstrating how to build massively scalable systems through careful trade-offs. Its large chunk size, separated control/data planes, and relaxed consistency model deliver exceptional performance and fault tolerance for specific workloads.

Forem: rajeevrajeshuni

Introduction to Bloom Filters

Table of Contents

Introduction to Bloom Filters

Operation on the Bloom Filter

Steps for Adding an Element

Steps for Looking Up an Element

Steps for Deleting an Element

Example

Flow for Adding the Elements

Flow for Looking Up an Item

Why Array Lengths in Powers of 2?

Advantages of a Bloom Filter Over a Set Data Structure

Choosing a Hash Function

Tuning a Bloom Filter

Example Use Cases

Unpacking the Google File System Paper: A Simple Breakdown

Core Philosophy: Keep It Simple, Scale Big

GFS Architecture: Masters, Chunkservers, Clients

Design Choice #1: Big 64 MB Chunks

Why?

Downsides

Design Choice #2: Split Control and Data Planes

How It Works

Benefits

How Reads Work

Design Choice #3: Two Write Patterns

Concurrent Writes

Concurrent Appends

Benefits

Design Choice #4: Relaxed Consistency Model

Why?

Implications

Fault Tolerance Mechanisms

Data Integrity: Checksums

Challenges and Limitations

Conclusion