Skip to content

LSM-Trees: What Happens When You Optimize for Writes?

5 min read1 views[Backend]
Cover image for "LSM-Trees: What Happens When You Optimize for Writes?"

A B-tree keeps data organized so a lookup can navigate directly toward the relevant range. That organization has a cost when updates keep arriving at unrelated locations.

A log-structured merge-tree approaches the workload differently: accept changes into a structure suited to recent writes, flush sorted data to storage, and reorganize it later.

That last word matters. “Later” is where compaction, read amplification, and some surprising latency behavior enter the picture.

Follow a key through the system

In the broad RocksDB model, writes go into an in-memory structure called a memtable and can be protected by a write-ahead log according to the configured write options. Memtables are eventually flushed to sorted table files. Reads consult relevant structures to find the visible version of a key. RocksDB overview

Here is a deliberately simplified example:

Write 1: theme = light
Write 2: language = en
Flush: sorted file A

Write 3: theme = dark
Flush: sorted file B

The latest value of theme is in B. A still contains an older version. The engine must know which version wins; it cannot return the first matching bytes it happens to find on disk.

This is already a different mental model from “update one location and forget the previous value.”

Sorted runs make deferred work possible

Because each run is sorted, an engine can merge runs by advancing through them in order. Imagine merging two sorted contact lists while resolving duplicate names using a defined revision order.

Real storage engines also track sequence information, snapshots, files, and metadata. The analogy explains why ordered runs are useful, not the complete correctness protocol.

For the example above, a merge could eventually produce a representation where the obsolete theme = light entry is unnecessary. Whether it can be removed depends on what older views still need to see.

The resulting benefit is not “no sorting” or “no rewriting.” It is a different schedule and organization for that work.

Compaction is the bill coming due

Compaction merges and rewrites files, managing the number of versions and runs reads may need to examine. Different policies trade write, read, and space amplification against each other. RocksDB documents leveled and universal compaction as distinct choices with different tradeoffs. RocksDB compaction

The amplification terms describe work relative to useful application work:

  • Write amplification: physical writing compared with logical data written.
  • Read amplification: extra structures or data examined to answer a read.
  • Space amplification: storage overhead compared with the live data you need.

There is no universal setting that minimizes all three for every workload.

For a concrete thought experiment, imagine updating one small hot set repeatedly while also retaining a large cold history. A policy that repeatedly rewrites cold data may spend substantial I/O preserving bytes that never changed. A different policy may reduce rewriting while making reads examine more runs.

The right question is which tradeoff your workload can afford.

Bloom filters help rule out unnecessary work

Before reading a file for a key lookup, a Bloom filter can tell the engine that the key is definitely absent or might be present. False positives mean “might” still requires checking; the normal guarantee is that inserted keys are not falsely ruled out. Filter configuration has memory and effectiveness tradeoffs. RocksDB Bloom filters

In our example, a lookup for an unrelated key could skip a file whose filter excludes it. The filter does not identify the newest version, return the value, or make a large range scan disappear.

This is a good illustration of why “the database uses a Bloom filter” is not a complete performance explanation. It helps a particular kind of decision.

Deletes also have a history

If an engine simply removed a key from the newest in-memory structure, an older value might still exist in an on-disk run. A deletion therefore needs a representation that suppresses older versions until the engine can safely remove the relevant history.

That deletion marker is often called a tombstone. Its lifecycle depends on compaction and visibility rules. Deleting a large dataset does not necessarily mean the operating system immediately reports the same amount of free disk space.

For an application with frequent expiry, I would measure both logical deletion behavior and physical space reclamation. They answer different questions and affect different operational limits.

A short benchmark can hide an unstable workload

Suppose incoming writes arrive faster than background work can flush and compact them. The engine cannot defer that work indefinitely. RocksDB can slow or stop writes when internal thresholds are exceeded to let background work catch up. RocksDB write stalls

A benchmark lasting only long enough to fill memory may therefore measure a burst capacity rather than sustainable throughput.

I would run a workload long enough to include repeated flushes and compactions, use a dataset larger than the relevant caches, and track latency distributions rather than only average writes per second. Include reads, updates, deletes, and snapshots if the real application uses them.

The interesting result is whether the system reaches a stable operating state with enough headroom for ordinary variation.

Compare engines through the application

B-trees and LSM-trees are families of designs, not personality types. Storage hardware, caching, compression, durability settings, and workload shape all influence the outcome.

A practical comparison starts with the application's questions: how many writes, how random, how many point reads versus range scans, how much history, and how predictable must tail latency be?

An LSM-tree moves some maintenance out of the immediate write path. Understanding where that maintenance goes is how you decide whether the trade is useful.

# Comments (0)

No comments yet. Be the first.

0/1000