Cassandra's LSM-Tree Architecture

Hello! Welcome back to the course.

In our previous lesson, we analyzed Cassandra's consistency model, focusing on how N, W, and R are configured to manage trade-offs between consistency and availability across the cluster. We established that these settings control the external behavior of a distributed write or read.

Today, we move from the cluster level to the node level. We will dissect the internal mechanics that allow Cassandra to achieve its renowned high write throughput. This lesson directly addresses the learning outcome: Explain Cassandra's storage architecture: Log-Structured Merge-Tree, Memtables, and SSTables.

We will explore:

• The fundamental data structure, the Log-Structured Merge-Tree (LSM-Tree), and why it's preferred over B-Trees for write-heavy workloads.
• The detailed path of a write operation, from the commit log for durability to the in-memory memtable.
• The process of flushing data to immutable on-disk files called SSTables.
• The architectural consequences for read operations and the mechanisms used to maintain read performance.

Your background in building low-latency and high-load systems has given you firsthand experience with the critical importance of I/O patterns. This lesson will deconstruct how Cassandra's design is fundamentally optimized to transform random writes into sequential disk I/O, a key factor in its performance characteristics.

1. The Foundation: Log-Structured Merge-Tree (LSM-Tree)

Traditional relational databases often use B-Tree structures, which are highly efficient for reads but can require random disk I/O for writes and updates (read-modify-write). For a system designed to ingest data at a massive scale, this can become a bottleneck. Cassandra takes a different approach.

The core idea of the LSM-Tree is to buffer writes in an in-memory structure (the Memtable) and periodically flush this structure to a new, immutable, on-disk file (the SSTable). This strategy converts many small, random writes into a single, large, sequential write to disk, which is significantly faster on both spinning disks and SSDs.

However, this design introduces a key trade-off: while writes are extremely fast, data for a single partition key may now exist in multiple places: the current memtable and several SSTables on disk. This complicates read operations, a challenge we will explore later in the lesson.

2. The Write Path: A Step-by-Step Journey

When a write request arrives at a Cassandra node, it follows a precise, two-step process designed for both durability and speed.

As the documentation outlines, the sequence is:

1. Log the write to the commit log.
2. Write the data to the memtable.

Let's examine each component.

Step 1: The Commit Log (Durability)

Before a write is even acknowledged as successful, it must be made durable. Cassandra achieves this by first appending the write to a commit log on disk. This is a classic Write-Ahead Log (WAL).

Key characteristics of the commit log:

• Durability: It provides durable storage. If a node crashes, upon restart, the commit log is replayed to rebuild any data in the memtables that had not yet been flushed to disk, preventing data loss.
• Sequential I/O: Writes are appended to the end of the log file. This sequential disk access is extremely fast and is a cornerstone of Cassandra's write performance.
• Configuration: The commitlog_sync parameter controls how and when the log is fsync'd to disk.
  • periodic: Acknowledges the write to the client immediately and syncs the log to disk periodically (e.g., every 10s). This offers higher performance at the risk of losing a few seconds of data if the node fails before the sync.
  • batch: Waits to acknowledge the write until the commit log has been synced to disk. This is safer but introduces higher latency. Your work on trading systems likely involved similar trade-offs between performance and guaranteed persistence.

Step 2: The Memtable (In-Memory Performance)

After being written to the commit log, the data is placed in the memtable, an in-memory data structure.

The memtable serves two primary purposes:

1. Buffering: It aggregates writes in memory.
2. Sorting: It maintains the data in sorted order by partition key. This is critical because when the memtable is flushed, the data is already sorted, allowing it to be written sequentially to a new SSTable without any extra sorting overhead.

When the memtable reaches a configured size limit, or when the commit log space is under pressure, a flush is triggered. The memtable's contents are written to a new, immutable SSTable on disk. Once the flush is complete, the corresponding data in the commit log can be safely purged.

3. SSTables and the Read Path

SSTables (Sorted String Tables) are the immutable on-disk files that persist data. Because memtables are flushed periodically, a table's data is typically spread across multiple SSTable files.

An SSTable is not a single file but a collection of components, including:

• Data.db: The actual row data, sorted by partition key.
• Partitions.db (or Index.db): An index that maps partition keys to their offset (position) in the Data.db file.
• Filter.db: A Bloom filter of the partition keys contained within this SSTable.
• Summary.db: A down-sampled version of the partition index, held in memory to speed up lookups.
• Statistics.db: Metadata about the SSTable, used for compaction and other operations.

The Read Path Challenge and Optimizations

A read operation is more complex than a write. To satisfy a read for a given partition key, Cassandra must check, in order:

1. The active Memtable.
2. The Row Cache (if enabled).
3. The SSTables on disk.

Checking every SSTable for every read would be prohibitively slow. Cassandra employs several mechanisms to optimize this process, leveraging the SSTable components.

1. Bloom Filter (Filter.db): This is the first check. A Bloom filter is a probabilistic data structure that can definitively say "this key is not in this SSTable" or "this key is probably in this SSTable." By checking the Bloom filter first (which is very fast and can be held in memory), Cassandra can avoid seeking to disk for SSTables that do not contain the requested key. This eliminates a huge amount of I/O, especially for keys that don't exist.

2. Partition Summary and Index (Summary.db, Partitions.db): If the Bloom filter returns a "maybe," Cassandra consults the in-memory Partition Summary to find the approximate location of the key in the on-disk Partition Index. This allows it to perform a single seek into the index file to find the exact offset of the data in the Data.db file, from which it can read the data sequentially. This multi-level index structure is designed to minimize expensive random disk seeks.

4. Compaction: The "Merge" Phase

Over time, as memtables are flushed, a large number of SSTables accumulate on disk. This degrades read performance (more files to check) and wastes space (outdated or deleted data is retained in older SSTables).

Compaction is the background process that merges multiple SSTables into a new, single SSTable.

During compaction, Cassandra reads data from several SSTables, merges it in memory (keeping only the latest version of each row based on its timestamp), and writes out a new, consolidated SSTable. This process is also when data marked with a tombstone (a deletion marker) is permanently removed.

Compaction is essential for maintaining a healthy and performant Cassandra cluster, but it also consumes I/O and CPU resources.

Conclusion

Today, we've unpacked the core of Cassandra's storage engine, revealing the elegant design that prioritizes write performance.

Key Takeaways:

• Cassandra is built on a Log-Structured Merge-Tree (LSM-Tree), which optimizes for high write throughput by converting random writes into sequential disk I/O.
• The write path is a two-step process: first, an append to the on-disk Commit Log ensures durability, and second, a write to the in-memory Memtable provides high performance.
• When a Memtable is full, it is flushed to an immutable, on-disk SSTable.
• The write-optimized design creates read-path complexity. This is mitigated by structures like Bloom filters and multi-level partition indexes that minimize disk I/O.
• Compaction is a crucial background process that merges SSTables to improve read performance, reclaim disk space, and permanently delete data.

Preview of the Next Lesson:

We've established that compaction is a vital maintenance process. However, how Cassandra performs compaction is not one-size-fits-all. In our next lesson, we will explore the different compaction strategies (Size-Tiered, Leveled, and Time-Windowed), analyzing their characteristics and learning how to choose the right strategy for different workload patterns—a critical decision for tuning production systems.