Why Your Database Writes Are So Fast: The LSM-Tree Story

Log-Structured Merge trees, almost always shortened to LSM-trees, are the storage engine design behind a huge portion of modern databases. Cassandra, RocksDB, LevelDB, HBase, ScyllaDB, and even parts of Lucene’s segment model all lean on the same core idea. If you have ever wondered why these systems are so fast at writes but sometimes need background “compaction” jobs, or why reads occasionally feel slower than writes, the answer lives in the LSM-tree design.

This post breaks down how LSM-trees work, why they were invented, and what tradeoffs you take on when you choose a database built around one.

The Problem LSM-Trees Were Built to Solve

Traditional databases, especially ones built on B-trees, update data in place. When you change a row, the database finds the exact page on disk holding that row and rewrites it. This works well for reads, since each piece of data lives in exactly one predictable location, but it is rough on writes.

Spinning disks made in-place updates especially expensive because of random I/O. Writing to a random page somewhere on a hard drive is far slower than writing many pages back to back in a single pass. Even with SSDs, where random I/O is much cheaper than it was on spinning disks, write amplification and small random writes still carry real overhead.

LSM-trees flip the strategy entirely. Instead of finding and rewriting the exact location of a record, every write is appended sequentially. Old versions of data are reconciled later, in the background, rather than at write time. This trade favors fast, sequential writes and accepts some extra cost on the read side and in background maintenance.

Core Building Blocks

The Memtable

Every write to an LSM-tree based engine first lands in an in-memory structure, commonly called a memtable. This is usually a sorted structure such as a skip list or a balanced tree, so that keys can be scanned in order later.

Because the memtable lives in RAM, writes here are extremely fast. There is no disk seek, no page rewrite, just an insert into an in-memory sorted structure.

The Write-Ahead Log

RAM is fast but volatile. If the process crashes before the memtable is flushed to disk, that data would be lost. To prevent this, every write is also appended to a write-ahead log (WAL) on disk before it is acknowledged as durable. The WAL is purely sequential, append-only, so it is cheap even though it touches disk on every write.

If the system crashes, it can replay the WAL on startup to rebuild the memtable’s contents.

SSTables

Once the memtable grows past a configured size, it gets flushed to disk as an immutable, sorted file called an SSTable, short for Sorted String Table. “Immutable” is the key word here. Once written, an SSTable is never modified. New writes never get inserted into an old SSTable.

This immutability is what makes LSM-trees so friendly to concurrent reads and crash safety, the same property that makes Lucene segments behave the way they do, since Lucene’s segment design is itself a variant of this idea.

Here is a simplified Java sketch of what an SSTable flush might conceptually look like:

import java.io.IOException;
import java.io.Writer;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.Map;
import java.util.TreeMap;

public class Memtable {
  // TreeMap keeps keys sorted
  private final TreeMap<String, String> data = new TreeMap<>();

  public void put(String key, String value) {
      data.put(key, value);
  }

  public void delete(String key) {
      data.put(key, null);
  }

  public int size() {
      return data.size();
  }

  public Map<String, String> entries() {
      return data;
  }
}

import java.io.IOException;
import java.io.Writer;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.Map;

public class SSTableWriter {

  // Writes the memtable out as a sorted, immutable file.
  public static Path flushToSSTable(Memtable memtable, Path directory) throws IOException {
      long timestamp = System.currentTimeMillis();
      Path filePath = directory.resolve("sstable-" + timestamp + ".sst");

      try (Writer writer = Files.newBufferedWriter(filePath, StandardCharsets.UTF_8)) {
          for (Map.Entry<String, String> entry : memtable.entries().entrySet()) {
              String value = entry.getValue() == null ? "<TOMBSTONE>" : entry.getValue();
              writer.write(entry.getKey() + "	" + value);
              writer.newLine();
          }
      }

      return filePath;
  }
}

Over time, many SSTables accumulate on disk, each representing a snapshot of writes from some window of time, all of them sorted internally but never modified after creation.

How Reads Work Across Many SSTables

If data is spread across the memtable and potentially dozens or hundreds of SSTables, how does a read for a single key actually work?

A lookup typically proceeds like this:

• Check the memtable first, since it holds the most recent writes.
• If not found, check SSTables from newest to oldest, since a more recent SSTable might contain an updated or deleted version of the key.
• Stop as soon as a definitive answer is found, either a value or a tombstone marking deletion.

Checking every SSTable on every read would be far too slow, so real implementations use two key optimizations:

• Bloom filters. Each SSTable keeps a compact, probabilistic structure that can quickly answer “this key is definitely not in this file” with no disk access at all. Bloom filters can have false positives but never false negatives, so they are safe to use as a fast skip mechanism.
• Sparse indexes. Since each SSTable is sorted, an in-memory index of “every Nth key and its byte offset” lets a lookup jump close to the right location in the file rather than scanning from the start.

Here is a small illustration of how a bloom filter check fits into a read path:

import java.util.BitSet;

public class SimpleBloomFilter {
  private final int size;
  private final BitSet bits;

  public SimpleBloomFilter(int size) {
      this.size = size;
      this.bits = new BitSet(size);
  }

  // Using two simple hash functions for simplicity.
  private int[] hashesFor(String key) {
      int h1 = Math.abs(key.hashCode() % size);
      int h2 = Math.abs((key + "salt").hashCode() % size);
      return new int[] { h1, h2 };
  }

  public void add(String key) {
      int[] hashes = hashesFor(key);
      bits.set(hashes[0]);
      bits.set(hashes[1]);
  }

  public boolean mightContain(String key) {
      int[] hashes = hashesFor(key);
      return bits.get(hashes[0]) && bits.get(hashes[1]);
  }
}

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class LsmReader {

  /**
   * Looks up a key across the memtable and a list of SSTables ordered
   */
  public static String readKey(
          String key,
          Memtable memtable,
          List<Path> sstablesNewestFirst,
          List<SimpleBloomFilter> bloomFilters) throws IOException {

      if (memtable.entries().containsKey(key)) {
          return memtable.entries().get(key); // May be null, meaning a tombstone
      }

      for (int i = 0; i < sstablesNewestFirst.size(); i++) {
          SimpleBloomFilter bloom = bloomFilters.get(i);
          if (!bloom.mightContain(key)) {
              continue; // Skip this file entirely, saving a disk read
          }

          // In a real engine, this would seek using a sparse index
          Map<String, String> entries = loadSSTable(sstablesNewestFirst.get(i));
          if (entries.containsKey(key)) {
              return entries.get(key);
          }
      }

      return null;
  }

  private static Map<String, String> loadSSTable(Path path) throws IOException {
      Map<String, String> entries = new TreeMap<>();
      for (String line : Files.readAllLines(path)) {
          String[] parts = line.split("	", 2);
          if (parts.length == 2) {
              entries.put(parts[0], "<TOMBSTONE>".equals(parts[1]) ? null : parts[1]);
          }
      }
      return entries;
  }
}

Compaction: Cleaning Up the Mess

Writes keep producing new SSTables, and deletes are just tombstones, so over time the number of files grows and the amount of stale, overwritten, or deleted data piles up. Left unchecked, this would make reads progressively slower since every lookup has to check more and more files.

Compaction is the background process that merges multiple SSTables into fewer, larger ones, dropping anything that has been superseded or tombstoned along the way. This is conceptually identical to Lucene’s segment merging, and it exists for the same reasons: reclaim space and reduce the number of files a read has to consult.

Two common compaction strategies are worth knowing:

• Size-tiered compaction. SSTables of similar size get grouped and merged together once enough of them accumulate. This is write-friendly but can temporarily use more disk space and can leave read performance more variable.
• Leveled compaction. SSTables are organized into levels of increasing size, with each level holding non-overlapping key ranges. This bounds the number of files a read has to check at the cost of more I/O during compaction.

Leveled compaction was introduced by LevelDB and later adopted widely, while size-tiered (sometimes called “universal”) compaction is RocksDB’s own default, with leveled compaction available as a configurable alternative. Cassandra historically defaults to size-tiered as well. Both RocksDB and Cassandra support multiple strategies and let you choose based on your workload’s read versus write balance.

Why Choose an LSM-Tree Based Engine

Write-Heavy Workloads Benefit the Most

If your system ingests a high volume of writes, like event logging, time-series data, or metrics collection, the sequential, append-only write path of an LSM-tree is a significant advantage over the random I/O pattern of in-place B-tree updates.

Read Latency Is a Real Tradeoff

A pure B-tree generally gives more predictable single-key read latency, since data lives in one place. LSM-trees can require checking multiple SSTables, even with bloom filters and indexes helping, especially right after a burst of writes before compaction has caught up. This is sometimes referred to as read amplification.

Space Amplification Is Real Too

Because old versions of data are not removed until compaction runs, disk usage can temporarily balloon well past the size of your actual live dataset, particularly under size-tiered compaction or during heavy update/delete workloads. Monitoring this is genuinely important in production.

LSM-Trees in the Real World

It helps to ground all of this in actual systems you may have used or heard of, since the theory above maps fairly directly onto production behavior.

• Cassandra uses memtables, a commit log (its name for the write-ahead log), and SSTables almost exactly as described above. Its default size-tiered compaction strategy is a big part of why Cassandra is known for excellent write throughput.
• RocksDB, originally forked from LevelDB at Facebook, is widely embedded inside other databases (CockroachDB, TiDB, and Kafka Streams’ state stores all use it) and supports leveled, universal (size-tiered), and FIFO compaction styles, letting each embedding system tune for its own read/write balance.
• HBase, modeled after Google’s Bigtable paper, popularized this design pattern in the Hadoop ecosystem, with memtables called “memstores” and SSTables called “HFiles.”
• Lucene’s segment model, covered in an earlier post, is a close cousin of this same idea applied to search indexes rather than key-value pairs.

Seeing the same memtable, write-ahead log, immutable file, background-merge pattern repeat across so many unrelated systems is a good signal that this is a genuinely fundamental tradeoff in storage engine design, not an implementation quirk specific to any one database.

Practical Takeaways

• LSM-trees trade slower, more variable reads for fast, sequential, append-only writes.
• Data flows from an in-memory memtable, protected by a write-ahead log, into immutable, sorted SSTables on disk.
• Immutability is the foundational design choice, the same one underpinning Lucene segments, and it is what enables lock-free reads and crash safety.
• Bloom filters and sparse indexes are what make checking many SSTables on read feasible instead of prohibitively slow.
• Compaction is mandatory background maintenance, not an optional optimization, and the strategy you pick (size-tiered versus leveled) meaningfully changes your read, write, and space tradeoffs.

Once you see the pattern of “append-only writes, immutable sorted files, background merging to clean up,” you start recognizing it everywhere, not just in dedicated LSM databases but in search engines, log storage systems, and even version control internals. It is one of those ideas that, once understood, makes a surprising number of unrelated systems suddenly make sense.