Case Study 3.3: How LSM trees handle Spotify-scale activity
Concept. This example uses an LSM tree to batch writes for play counters, playback positions, and friend activity.
Intuition. In this example, 700 million users generate continuous like and play events. An LSM-backed cluster buffers each event in RAM, flushes immutable SSTables, and combines the MemTable with relevant SSTables during reads.
Figure: Three workloads share the same write pathIllustrative Spotify-style architecture. Play increments, timestamped playback positions, and listening events enter a compact RAM MemTable. Flushes produce sorted SSTables, and compaction merges them using the workload's rule. Thin red bars mark RAM and green bars mark disk. The next slide contrasts sum, newest timestamp, and merging events in time order.
Figure 1. In this example, a play writes a counter increment, a pause writes a timestamped position, and a listen appends an activity event. The shared write path buffers records in RAM, flushes sorted SSTables, and compacts them using the appropriate merge rule. The key prefixes distinguish the three example workloads.
Three LSM use cases in Spotify
| Use case | What gets written | What the read does |
|---|---|---|
| 1. Counters | Each play adds +1 |
Sum the counts |
| 2. Latest position wins | Playback position and timestamp | Return the newest position |
| 3. Friend activity | Timestamped listening events | Merge events in time order |
Random B+Tree writes become the bottleneck
A B+Tree update targets the leaf page for its key. Updates spread across 100 million songs can touch many pages and create random IO. At millions of updates per second, storage IO becomes the bottleneck.
An LSM tree buffers those updates in memory and flushes sorted files sequentially. The LSM Tree Indexes page explains MemTables, flushes, and compaction. The three workloads below show how different merge rules use that machinery.
Use case 1: counters
Spotify appends each like and play to the MemTable as (song_id, +1, timestamp). To compute the current total, the query sums matching fragments across the MemTable and relevant SSTables. The SUM merge function combines them.
Use case 2: latest position wins
When you pause a 3-hour podcast, Spotify appends (user_id, podcast_id, position, timestamp) to the MemTable. When you resume, Spotify searches the MemTable and newer SSTables before older ones, then returns the newest position.
The pick-latest merge function chooses the newest version. Compaction later removes superseded positions.
Use case 3: friend activity
Spotify's Friend Activity feed tracks what friends are playing. Spotify appends each event and builds the feed by merging recent SSTable segments at read time.
Because this workload adds events instead of updating them in place, it avoids random overwrite traffic.
Additional detail: tombstone deletes
To remove a like from an immutable SSTable, Spotify appends a tombstone. A newer tombstone makes the read return "not found" even while an older value remains in another SSTable. Once Spotify can safely discard the tombstone, a later compaction removes both records.
A tombstone implements DELETE for immutable files and delays physical cleanup until compaction.
Takeaway: LSM merge functions support counters, latest-value reads, event feeds, and deletes while compaction reclaims superseded versions.