LSM Tree Indexes
Concept. An LSM tree buffers inserts in a RAM MemTable, flushes them to immutable SSTables, and merges SSTables in the background. The design turns random writes into sequential disk writes.
Intuition. Spotify can ingest 1 million listen events per second. Scattered B+Tree inserts can cause random page writes. An LSM tree batches writes in RAM, then flushes them to disk as one SSTable. Then starts a new batch of writes in RAM, and writes to the next SSTable. A read probes the MemTable, then probes the on-disk SSTables.
Prerequisites. SSTables introduces the immutable file format LSM trees are built from.
What Gets Stored
Every record is a (key, value, timestamp) triple. For a song-play counter, that looks like:
(S_102, +1, 13:42:05)
Song ID is the key, the increment is the value, and wall-clock time is the version. No row is ever updated in place. A new (S_102, +1, …) is appended for every play, and the "current state" of S102 is whatever you get when you add all of its values together.
Writes: How Writes are Batched from RAM to Disk
Writes flow downward through three tiers. The caption below names each piece and walks the live S75 example.
Figure: Buffer writes, flush files, then compactLSM write path at 1:44 PM. Top lane: incoming plays land in the live MemTable in RAM. Middle lane: every 15 minutes the MemTable is flushed as a Level-0 SSTable on disk; the 1:01, 1:15, and 1:30 files are already there. Bottom lane: every hour compaction merges Level-0 files into one larger Level-1+ SSTable. Song S75 has +2 plays in the MemTable, +18 across the Level-0 flushes, and 5420 in the compacted history. Color key: red strip is the MemTable in RAM (volatile), green strip is SSTables on disk (persistent).
Figure 1. LSM write path at 1:44 PM, RAM on top and disk below, time flowing downward. Incoming plays land in the in-RAM MemTable (fast, no seek, lost on crash unless replayed from the WAL). Every 15 minutes the engine flushes it to an immutable Level-0 SSTable on disk (1:01pm.sst, 1:15pm.sst, 1:30pm.sst). Hourly compaction merges those into one larger sorted, de-duplicated Level-1+ file. Total plays for S75 spread across tiers (+2 in the MemTable, +10, no matching entry, and +8 in Level-0, 5,420 in compacted history) and the read path sums them to 5,440 (merge-on-read). The merge operator is configurable: "add" for counters, "newest wins" for last-write-wins keys, "set union" for tags, "max" for high-water-marks. The merge section walks through more examples.
The MemTable buffers updates in RAM. Flushes and compaction turn batches into large sequential transfers, reducing scattered write IO. Throughput depends on hardware, workload, and compaction.
Compaction does additional work. Every time it merges a key into a larger level it rewrites that data, so one logical insert becomes several physical writes over its life. The ratio of physical bytes written to logical bytes written is called write amplification, and caps sustained write throughput.
Reads: Merge on Read
For this counter, a read computes the current total by combining relevant fragments. For replacement values, a read selects the newest applicable version.
Figure: Combine recent writes with stored historyRead S75 from the MemTable and SSTables. MemTable contributes 2; 1:30pm.sst contributes 10; 1:15pm.sst has no matching entry; 1:01pm.sst contributes 8; before1:00pm.sst contributes 5420. Sum: 5440. Red and green top rules indicate RAM and disk.
Figure 2. Merge-on-read computes S75's play count at read time instead of storing it, by summing every tier that holds a fragment. The live in-RAM MemTable (red) adds +2, the three flushed Level-0 SSTables on disk (green) add 10 + 0 + 8 = 18, and the compacted Level-1+ SSTable on disk (green) adds +5,420, for a total of 2 + 18 + 5,420 = 5,440 (the merge function is "add" because plays are a counter). Each SSTable carries a bloom filter, so the reader skips any tier that cannot hold the key with no disk read, making most reads far cheaper than this worst case.
A naïve read would touch every SSTable. In practice each SSTable carries a bloom filter, so tiers that can't possibly contain the key are skipped without a disk read. Hot keys in recent SSTables answer fast, and cold keys may walk deep.
How "Merge" Is Defined
The meaning of the stored values determines the merge rule. Four patterns cover most systems. The first two:
| Pattern | Merge logic | Example |
|---|---|---|
| Counter | sum(v₁, v₂, …) | Song play counts. Sum the +1 fragments. |
| Latest-wins | pick max(timestamp) | User profile updates. Newest overwrites. |
The other two keep partial state or filter by time:
| Pattern | Merge logic | Example |
|---|---|---|
| Statistical | sum(sums), sum(counts) | Rolling averages. Keep running totals. |
| TTL / retention | filter(time > now − window) | Session logs. Drop events older than 24 hours. |