LSM-Tree Write Path Lab (Interactive)
Stream writes to the memtable, flush SSTables, drop tombstones, then compact. Watch sequential writes become immutable SSTables, deletes become tombstones, and reads fan across tables behind bloom filters — then compact and measure the space-amplification payoff.
Cassandra LSM-Tree: Writes, Memtable Flush & Compaction
Append-only writes are free — until reads must merge every SSTable. Pay the cost at compaction time.
Ingest writes — every one is a sequential commit-log append plus an in-memory skiplist insert. That is why Cassandra sustains hundreds of thousands of writes/sec per node.
Modeling note (CQL): PRIMARY KEY ((device_id), timestamp) — the partition key routes to nodes, the clustering column sorts rows inside the SSTable so “last 1,000 readings for this device” is one sequential read. Query anything else and you pay ALLOW FILTERING across every partition.
How It Works Under the Hood
Column-family stores like Cassandra, ScyllaDB, and RocksDB optimize writes by appending: the CommitLog fsyncs, the Memtable sorts in RAM, and when full it flushes to an immutable SSTable — nothing is ever rewritten in place. That is the B+Tree's inverse trade. The cost moves to reads: probe the Memtable, then check each SSTable through a bloom filter that skips non-matching files with zero disk I/O, and merge surviving results. Deletes only append tombstones until compaction discards them, and compaction merges tables to shrink read fan-out while spending write amplification.
Core Architectural Principles
- Writes touch only the CommitLog and the in-RAM Memtable; SSTable flushes are sequential appends, never in-place updates.
- Reads probe the Memtable plus every candidate SSTable, skipped cheaply by bloom filters with a ~1% false-positive rate.
- Tombstones defer delete cost to compaction, which trades background write amplification for lower read amplification and reclaimed space.
For high-write ingestion designs, choose the LSM store and justify it: sequential appends beat random page writes for write-heavy velocity. Then state the honest costs — tombstone buildup, compaction I/O spikes, and multi-SSTable read fan-out. Mention that the partition key decides which node and which sorted runs a read must touch.
The LSM write path buys near-memory write speed by pushing cost onto reads, background compaction I/O, and delayed deletes.