Muhammad Ahsan Farooq

Posted on Oct 11

LSM-Trees Explained: The Storage Engine Behind Millions of Writes per Second

#distributedsystems #backend #systemdesign #database

MemTables, write-ahead logs, SSTables, Bloom filters, and compaction, from the first write to the last merge

Most databases are designed around reading. Then you build a chat app, an IoT platform or an event log, and the job flips. The database spends its life absorbing writes, millions per second.

Classic relational engines, such as InnoDB in MySQL, are built around B+ trees that update fixed-size disk pages in place. Scattered updates mean random disk I/O, and under heavy write load that becomes the bottleneck.

Log-structured merge-trees (LSM-trees) take the opposite approach: never modify anything on disk. Buffer writes in memory, record them in a log, flush them as sorted immutable files, and tidy up later in the background. This design powers Apache Cassandra, ScyllaDB, HBase, Google Bigtable, LevelDB and RocksDB.

This post explains how LSM-trees work from the inside, with a worked example and diagrams for each step.

In this post:

Why B+ trees struggle with writes, and the idea behind LSM-trees
The parts: MemTable, write-ahead log, SSTables, sparse indexes and Bloom filters
A worked example, following real writes from memory to disk
Reads, deletes and tombstones
Compaction, and the read, write and space trade-offs it creates
Use cases, case studies and tuning advice

Why B+ trees struggle with heavy writes

A B+ tree keeps data sorted inside fixed-size pages, commonly 4 to 16 KB. To change a record, the database finds the right page, reads it into memory, modifies it, and writes the page back to the same place. If a page is full, it splits in two and the tree rebalances.

That works well when updates are local. It works badly when keys arrive in random order, because every write lands on a different page. The disk jumps around, and each small change costs a full page read and write.

in-place page updates vs sequential flush · 3 writes

Sequential I/O is much cheaper than random I/O. The gap is largest on spinning disks, but SSDs also handle large sequential writes more efficiently than many small scattered ones.

The LSM-tree idea

An LSM-tree turns every write into an append. It does four things:

Accept the write in memory, in a sorted buffer.
Record it in a log on disk, so a crash cannot lose it.
Flush the buffer to disk as one sorted, immutable file when it fills up.
Merge files in the background so reads stay fast.

An analogy: the library cart

Imagine a library that receives thousands of new books a day. A strict librarian would walk each book to its exact shelf spot, shifting other books to make room. That is a B+ tree.

An LSM librarian drops new books on a cart. When the cart is full, they sort it once and seal it into a labeled box. Boxes are never reopened. Every so often, a few boxes are merged into one bigger sorted box. Adding a book is almost free. Finding one means checking the cart and then the boxes, newest first. That is the trade you accept with an LSM-tree: cheap writes, more work on reads and in the background.

Anatomy of an LSM-tree

An LSM-tree has a few cooperating parts spread across memory and disk. Follow one write through them, from left to right:

LSM-tree write path · 5 stages across memory and disk

1. The write-ahead log (WAL)

RAM is volatile, so a MemTable alone would lose data in a crash. Before a write is acknowledged, it is appended to an on-disk write-ahead log. The log is strictly append-only, so it uses fast sequential I/O. After a crash, the engine replays the log to rebuild the MemTable.

How strong the guarantee is depends on the sync setting. If the engine waits for the log to reach the disk, the write is durable. Some systems default to syncing on a timer instead. Cassandra's commit log, for example, defaults to periodic sync, and relies on replication to cover a single node's crash.

2. The MemTable

The MemTable is an in-memory buffer that keeps keys in sorted order. Engines typically build it from a skip list or a balanced tree. Writes touch only RAM, so they finish almost instantly. RocksDB, for instance, defaults to a 64 MB write buffer.

3. SSTables

When the MemTable reaches its size limit, the engine freezes it into a read-only MemTable and starts a fresh active one for incoming writes. A background thread then writes the frozen table to disk as a Sorted String Table (SSTable).

An SSTable has two defining properties:

Sorted: keys are stored in order, which makes lookups and merges efficient.
Immutable: once written, the file is never modified. An update is a newer record in a newer SSTable. A delete is a special marker called a tombstone.

SSTable anatomy · 3 data blocks, 2 helpers

4. The sparse index and Bloom filters

Over time, many SSTables pile up. A lookup could in theory open every one of them. Two small in-memory structures prevent that:

Sparse index: because keys inside a file are sorted, the engine only stores the first key of each block, for example every 4 KB. To find a key, it binary-searches this index and reads just one block.
Bloom filter: a compact probabilistic structure that answers "is this key in the file?" with either definitely not or maybe. It never gives a false negative, so a definitely not lets the engine skip the file without touching the disk. It can give false positives, but at about 10 bits per key the rate is around 1%.

A worked example: eight writes

Let's trace a tiny key-value store that maps a user name to a city. To keep the example small, assume the MemTable flushes after every 4 writes. A real engine flushes after tens of megabytes.

Step	Operation	MemTable afterwards	On disk afterwards
1	`put(alice, Lahore)`	alice=Lahore	nothing yet
2	`put(bob, Karachi)`	alice=Lahore, bob=Karachi	nothing yet
3	`put(alice, Dubai)`	alice=Dubai, bob=Karachi	nothing yet
4	`put(carol, Berlin)`, then the MemTable is full and flushes	empty	SSTable 1: alice=Dubai, bob=Karachi, carol=Berlin
5	`put(bob, Oslo)`	bob=Oslo	SSTable 1
6	`delete(carol)`	bob=Oslo, carol=TOMBSTONE	SSTable 1
7	`put(dave, Paris)`	bob=Oslo, carol=TOMBSTONE, dave=Paris	SSTable 1
8	`put(erin, Rome)`, then the MemTable is full and flushes	empty	SSTable 1, plus SSTable 2: bob=Oslo, carol=TOMBSTONE, dave=Paris, erin=Rome

Four things are worth noticing:

Overwrites in memory are free. In step 3, Lahore was replaced inside the MemTable. It never reached the disk.
A flush is one sequential write. Each SSTable was produced in a single pass, already sorted.
The same key can live in several files. bob is in both SSTables, with different values. The newest one wins.
A delete is a write. In step 6, nothing was erased. carol=Berlin still sits in SSTable 1, and a tombstone in a newer place now hides it.

All eight writes were also appended to the write-ahead log. Once a MemTable is safely flushed, the log segment that covered it can be discarded.

This is the state the next section starts from.

The read path and tombstones

Reading from an LSM-tree means searching from the newest data to the oldest and stopping at the first answer:

Check the active MemTable, then any frozen MemTables.
For each SSTable, newest first: ask the Bloom filter, then the sparse index, then read one data block.
Return the newest version found. If the newest record is a tombstone, the key does not exist.

Here are three lookups against the store from the worked example:

read path · 3 lookups across 3 layers

Notice that get(alice) needed one disk read, even though two files exist. The Bloom filter ruled out SSTable 2 for free.

Why reads cost more

A key might need to be checked in several files. This extra work is called read amplification. Bloom filters, block caches and compaction all exist to keep it small. Compaction matters most, because it reduces the number of files a read can touch.

Deletes and tombstones

SSTables are immutable, so a delete cannot erase anything. The engine writes a tombstone, a marker saying "this key is deleted as of now". Reads treat a newest-record tombstone as a missing key. The tombstone and the data it hides are physically removed later, during compaction.

Tombstones cannot always be dropped right away. Cassandra, for example, keeps them for gc_grace_seconds, which defaults to 10 days, so that a replica that was offline during the delete still learns about it. Drop the tombstone too early and the deleted data can come back.

This makes delete-heavy workloads risky. Using a table as a queue, where rows are inserted and then deleted, leaves piles of tombstones that every read has to scan past. Discord ran into a version of this: when it migrated its message store, the migration stalled at 99.9999% because the last token ranges held huge runs of tombstones that had never been compacted away.

Compaction: keeping the files in check

Without cleanup, SSTables accumulate forever. Reads must check more files, and old versions of keys and tombstones waste disk space. Compaction is the background process that fixes this. It reads several SSTables, merge-sorts them, discards overwritten values and deleted data, and writes new consolidated files.

Here is compaction applied to the two files from our worked example:

compaction merge · 2 files into 1

Because both inputs are already sorted, the merge is a single streaming pass over the disk. It is sequential I/O again, which is exactly what the design wants.

A tombstone can be dropped only when it is safe, meaning the compaction includes every older file that could still hold the deleted key. Otherwise the old value would reappear.

Two main strategies

Engines differ in which files they merge and when. The two classic strategies make opposite trade-offs:

size-tiered vs leveled compaction

Strategy	How it works	Strengths	Costs	Fits best
Size-tiered (STCS)	Groups files of similar size. When enough exist, merges them into one larger file	Low write amplification and fast ingestion	High space amplification. Large merges can need up to 50% free disk	Write-heavy workloads such as event logs and metrics
Leveled (LCS)	Stores data in levels. Each level is about 10x larger than the last, and files do not overlap above L0	Low read amplification and good space efficiency, with roughly 10% overhead	High write amplification and steady background I/O	Read-heavy or space-constrained workloads

In the leveled diagram, a read checks at most one file in each of L1 and below, because those files do not overlap. It must still check every L0 file, since fresh files can overlap.

Time-series data has its own option. Cassandra's time-window compaction groups files by time window, so when data carries a time-to-live, whole windows can be dropped cheaply once they expire.

The three amplifications

Compaction is a balancing act between three costs. Every tuning decision moves weight from one to another:

Amplification	What it measures	What drives it up
Read	How many files or blocks a read must check	Many overlapping files
Write	Bytes written to disk for each byte the application wrote	Compacting often, since every merge rewrites data
Space	Disk used compared with the size of the live data	Old versions and tombstones waiting to be merged away

Size-tiered compaction favors low write amplification. Leveled compaction favors low read and space amplification. No strategy wins on all three.

Compaction is not free

Compaction competes with your queries for disk and CPU. If it falls behind, reads touch more files and latency climbs. Discord described this problem in its Cassandra clusters: nodes fell behind on compactions, which made reads more expensive and caused cascading latency. Watching the compaction backlog is as important as watching query latency.

Where LSM-trees shine, and where they do not

LSM-trees fit workloads that write constantly, read mostly recent data, and rarely update or delete in place.

Use cases

Chat and message history: messages are appended per channel and read mostly newest first. Discord stores its messages this way.
IoT telemetry and metrics: millions of sensor readings per second, each keyed by device and time.
Event logs, audit trails and activity feeds: append-mostly data that is queried by key and time range.
User activity history: Netflix described its viewing-history store as write-heavy, with a write-to-read ratio of about 9:1.
Embedded state stores: RocksDB sits inside stream processors such as Kafka Streams and Apache Flink to hold large local state.
Foundations of other databases: CockroachDB, TiKV and YugabyteDB build on LSM-tree engines, and MyRocks brings RocksDB to MySQL.

Example: sensor readings with automatic expiry

A time-series table in Cassandra pairs the write path with a compaction strategy built for time data:

CREATE TABLE sensor_readings (
  sensor_id text,
  day       date,
  ts        timestamp,
  value     double,
  PRIMARY KEY ((sensor_id, day), ts)
) WITH compaction = {
    'class': 'TimeWindowCompactionStrategy',
    'compaction_window_unit': 'DAYS',
    'compaction_window_size': 1
  }
  AND default_time_to_live = 2592000;  -- 30 days

Here is why this fits:

Appends only. Every reading is a new row, so there are no in-place updates.
Bounded partitions. The (sensor_id, day) partition key caps how large any one partition grows.
Cheap expiry. Files are grouped by day, so data older than 30 days disappears when a whole file expires, instead of through millions of individual deletes.

When an LSM-tree is the wrong tool

The costs we covered earlier define the limits:

Read-heavy random lookups that a cache cannot absorb. A B+ tree reads one predictable path.
Strict, flat tail latency. Compaction competes with queries and can cause spikes.
Delete-heavy or queue-like tables. Tombstones pile up, and reads must scan past them.
Tight disk budgets with size-tiered compaction, which can need a lot of free space during merges.

Workload	Better fit	Why
Millions of appends per second, mostly recent reads	LSM-tree	Writes stay sequential
Read-heavy transactions with random lookups	B+ tree	One predictable lookup, no compaction
Time-series data with a retention window	LSM-tree with time-window compaction	Whole files expire at once
A table used as a work queue	A real message queue	Insert-then-delete churn creates tombstones
Strict, flat read latency	B+ tree, or a carefully tuned LSM-tree	Compaction can cause latency spikes

Case studies

Two engineering teams have written openly about running LSM-tree databases at scale. Their stories show both the strengths and the sharp edges.

Discord: from Cassandra to ScyllaDB

Discord stores its chat messages in a database partitioned by channel and a time bucket. In 2017 the cluster ran 12 Cassandra nodes holding billions of messages. By early 2022 it had grown to 177 nodes holding trillions, and it had become what Discord called a high-toil system. Three problems traced back to the LSM-tree design and its runtime:

Reads cost more than writes. A write goes to the commit log and the MemTable. A read must check the MemTable and possibly several SSTables. Heavy concurrent reads on one channel created hot partitions, which slowed the nodes serving them.
Compaction fell behind. When compaction lags, reads touch more files. Discord's operators resorted to taking nodes out of rotation so they could catch up on compactions without serving traffic.
JVM garbage collection. Cassandra runs on the JVM, and garbage collection pauses caused latency spikes that took a lot of tuning to contain.

Discord moved the messages cluster to ScyllaDB, a Cassandra-compatible database written in C++ with no garbage collector. It also put Rust data services in front of the database. These coalesce identical concurrent requests into a single query, and route requests by channel ID so that coalescing works well. The cut-over happened in May 2022. Here is how the two clusters compared afterwards, according to Discord:

	Cassandra	ScyllaDB
Nodes	177	72
Disk per node	about 4 TB on average	9 TB
p99 latency, fetching historical messages	40 to 125 ms	15 ms
p99 latency, inserting a message	5 to 70 ms	about 5 ms, steady

The lesson is that both databases use the same LSM-tree design. The gains came from removing garbage collection pauses, giving each CPU core its own shard of work, and shielding the database from hot partitions. An LSM-tree is only as predictable as its compaction, its runtime and its access pattern.

Netflix: Cassandra for write-heavy data

Netflix has used Cassandra's LSM-tree engine in two well-documented places.

Viewing history. Netflix's first cloud-native viewing-history store used Cassandra because the data is time-series shaped and write-heavy, at a ratio of about 9 writes to 1 read. Netflix later redesigned it for a smaller storage footprint and consistent read and write performance as each member's history grows, splitting each member's data into a small set of recent records that change often and a larger set of older records that are stored compressed.

Live streaming origin. For live events, Netflix needed storage with very high write availability. It treats any write that fails within 500 ms as a bug. Its requirements and how they were met:

Requirement	How it was met
Writes almost never fail	A key-value layer on Cassandra with local-quorum writes, which keep working even if an entire availability zone is down
Large payloads of a few megabytes	Values are split into chunks, and each chunk can be retried and hedged safely
High write throughput	Cassandra's write-optimized LSM-tree engine
Read storms without hurting writes	A write-through cache in front of Cassandra, so almost all reads are served from memory

Netflix reports that Cassandra could serve reads at network line rate, but that doing so degraded concurrent writes. Adding a cache separated the read path from the write path. The write latency at the 99th percentile ended up close to the old S3-based design's median. The new setup was significantly more expensive, but low latency and high availability mattered more than cost.

The pattern to take away is common to both companies. An LSM-tree gives you cheap writes, and you pair it with a cache or a coalescing layer to protect the read path.

A practical tuning checklist

Exact settings differ between Cassandra, ScyllaDB and RocksDB, but the same levers exist everywhere:

Lever	What it changes	Guidance
Compaction strategy	The balance of read, write and space amplification	Size-tiered for write-heavy ingest with disk headroom. Leveled for read-heavy data. Time-window for time series with a TTL
MemTable size	How often data flushes, and how many files appear	Larger buffers mean fewer, bigger flushes and less compaction, but use more RAM and mean a longer log replay after a crash
Bloom filter size	False-positive rate against memory	About 10 bits per key gives roughly a 1% false-positive rate. Spend more memory on read-heavy tables
Block and key caches	Repeated reads of hot data	Size them to hold your hot set
Free disk space	Whether big merges can finish	Leave generous headroom, especially with size-tiered compaction
Compaction throughput limit	Background I/O against query latency	Cap it so queries are not starved, but not so low that compaction falls behind
Partition and key design	Hot spots and partition size	Bound partition size, for example with a time bucket, so no single partition grows without limit
TTLs and deletes	Tombstone volume	Prefer TTLs with time-window compaction over mass deletes

What to monitor

Pending compactions. A growing backlog is an early warning that reads are about to slow down.
Files touched per read. This is your read amplification, measured directly.
Tombstones scanned per read. High numbers point to a delete-heavy access pattern.
Free disk space. Running low during a large merge can stop compaction entirely.
p99 read latency, not just the average. Compaction trouble shows up in the tail first.

Common mistakes

Benchmarking a fresh database. An LSM-tree behaves differently once data volume is large and compaction is running. Test at realistic size and let compaction reach a steady state.
Treating the log as a guarantee. Check whether the write waits for the log to reach disk, or only to reach the operating system.
Unbounded partitions. One very large or very hot key undermines everything else you tuned.
Using deletes as a core operation. If your design needs constant deletes, reconsider the design.

Summary: B+ tree vs LSM-tree

	B+ tree	LSM-tree
Write pattern	In-place page updates	Sequential appends to a log and to immutable files
Write throughput	Limited by random I/O and page splits	Very high
Read cost	One tree lookup	Checks the MemTable and possibly several files. Bloom filters and caches soften this
Deletes	Removed in place	Written as tombstones, removed later by compaction
Background work	Page splits and rebalancing	Compaction
Space overhead	Fragmentation inside pages	Old versions and tombstones until they are compacted
Typical systems	MySQL (InnoDB), SQLite, and the indexes in PostgreSQL	Cassandra, ScyllaDB, HBase, Bigtable, LevelDB, RocksDB

Conclusion

An LSM-tree makes one big bet: writes should be cheap and sequential, and the cost of keeping data organized can be paid later, in the background. That bet pays off for chat history, telemetry, event logs and any workload that writes far more often than it reads in place.

Keep three ideas in mind:

Every write is an append. The write-ahead log protects it, the MemTable sorts it, and a flush turns it into an immutable sorted file.
Reads pay for it. Bloom filters, sparse indexes and caches keep that cost down, and compaction keeps the file count under control.
Compaction is the engine's real workload. Choose its strategy deliberately, watch its backlog, and design keys and deletes so it can keep up.