Course contentsShow
← System Design
Lesson 416 of 1,91912. NoSQL: Wide-Column StoresFree lesson

Read Path and Bloom Filters

Understanding how reads work with memtables, SSTables, and bloom filters to minimize disk seeks.

Read Path and Bloom Filters

What you'll learn: How wide-column stores minimize expensive disk reads using bloom filters and a multi-tier lookup strategy.


The Read Challenge

In the previous lesson, you learned that writes go to a memtable and eventually flush to immutable SSTables on disk. But what happens when you need to read data? The system must check:

  1. Memtable (in-memory) — fastest
  2. Multiple SSTables on disk — potentially slow

Without optimization, the database might need to open and scan every SSTable file to find your key. Imagine searching through dozens of filing cabinets just to confirm a document doesn't exist!


Bloom Filters to the Rescue

A bloom filter is a space-efficient probabilistic data structure that answers: "Is this key definitely not in this SSTable?"

Think of it like a quick checklist at the door of each filing cabinet. Before opening the cabinet (expensive disk seek), you glance at the checklist:

  • If it says "NO," the key is guaranteed absent — skip this SSTable entirely
  • If it says "MAYBE," you must check inside (false positive possible)

Bloom filters use minimal memory and eliminate most unnecessary disk reads.


The Full Read Path

  1. Check memtable — if found, return immediately
  2. For each SSTable (newest to oldest):
    • Check its bloom filter
    • If bloom filter says "NO," skip
    • If "MAYBE," read the SSTable's index and data blocks
  3. Return the most recent version of the key found

This approach keeps read latency manageable even with many SSTables, though compaction (merging old SSTables) further optimizes this over time.


Key Takeaway:
Bloom filters act as fast, memory-efficient gatekeepers that prevent unnecessary disk seeks during reads, making wide-column stores viable for high-throughput workloads despite their LSM tree architecture.