# LSM trees > An LSM tree, or log-structured merge tree, is a storage structure that buffers writes in memory and periodically writes sorted files to disk. It supports high write throughput by batching disk work, but reads and background compaction must deal with data spread across multiple files. Source: https://sysround.com/concepts/lsm-tree Updated: 2026-11-05 ## How lsm trees works A typical write is appended to a write-ahead log (WAL) for crash recovery and inserted into a sorted in-memory structure called a memtable. Acknowledgment durability depends on when the WAL is synced to durable storage; writing only to memory is not enough. When the memtable reaches a size limit, the engine freezes it and starts a new one. It flushes the frozen memtable into an immutable sorted file, commonly called an SSTable, while new writes continue. Updates create newer versions rather than modifying existing SSTables. For example, setting user:42 to a new value can leave the previous value in an older file; sequence numbers or timestamps let the engine identify the version visible to a read. A point lookup checks relevant memtables and SSTables, resolving versions according to the read's visibility rules. Per-file Bloom filters can rule out files that definitely lack a key, while indexes locate the relevant blocks within candidate files. Background compaction merges sorted files, reconciles duplicate keys, and removes obsolete versions when safe. Leveled compaction generally reduces overlapping data and read work at the cost of more rewriting; tiered compaction generally favors writes but leaves more runs to search. Deletes usually write tombstones instead of immediately removing old values. Compaction can discard a tombstone only when older values cannot become visible again, considering snapshots and, where applicable, the distributed database's repair rules; range scans merge sorted iterators across the relevant files. ## Worked example: Sizing a write-heavy metrics shard Suppose a metrics shard receives 50,000 samples per second, each occupying 100 bytes before storage overhead: 5 MB/s of logical writes. Use keys ordered by series ID and timestamp so a query for one series over ten minutes is a bounded range scan. Writes enter the WAL and memtable, then flush into sorted files. If load testing measures total device writes at six times logical input, budget about 30 MB/s of write bandwidth, plus compaction reads and query traffic. That factor is an assumption to validate, not an LSM constant. Monitor pending compaction bytes, write stalls, and p99 reads; add capacity or apply backpressure before background work falls permanently behind. ## Trade-offs - **Write throughput versus write amplification.** Buffered writes avoid many small in-place updates, but the WAL, flushes, and repeated compaction can write each logical byte multiple times. - **Read amplification.** A lookup may inspect several files, so Bloom filters, block caches, and compaction policy strongly affect read latency. - **Temporary disk overhead.** Old versions, tombstones, and compaction outputs consume extra space until obsolete files can be safely removed. - **Background work versus tail latency.** Compaction competes with foreground requests for CPU and disk bandwidth, and falling behind can eventually stall writes. - **Deferred deletion.** Logical deletion can be immediate while physical reclamation waits for compaction, snapshot expiration, and any required repair safety. - **Memory allocation.** Memtables, Bloom filters, indexes, and block caches compete for RAM, requiring a workload-specific balance between ingestion and reads. ## When to use it in a system design interview - You are designing a durable key-value store with sustained writes, frequent updates, and a dataset larger than memory. - A metrics or observability store needs high ingestion throughput plus key-based lookups or bounded time-range scans. - The interviewer asks how a storage engine turns many small writes into efficient disk operations. - You need to explain write stalls, delayed disk reclamation, or why storage traffic is much larger than application write traffic. ## How to bring it up in the interview - Start with the workload: write rate, value size, read patterns, retention, and latency targets; justify an LSM engine against a B-tree rather than claiming it is universally faster. - Walk through WAL, memtable, SSTable, and compaction in that order, explicitly stating when a write becomes durable and how recovery replays unflushed writes. - Explain both point reads and range scans; expect follow-up questions about Bloom filters, overlapping files, cache misses, and scan fan-out. - Budget for compaction rather than sizing disks from logical writes alone; interviewers may ask what happens when ingestion exceeds sustainable compaction throughput. - Separate storage layout from distributed guarantees: an LSM tree does not determine replication, consistency, transactions, or conflict resolution. ## Common mistakes - Calling the WAL and the LSM tree the same thing: the WAL supports recovery, while memtables, sorted files, and compaction organize stored data. - Saying writes are cheap because data is written only once, while ignoring compaction and its write amplification. - Assuming Bloom filters locate values or eliminate range-scan work; they primarily rule out point-lookup candidates and can return false positives. - Dropping tombstones after a fixed delay without checking whether older values, snapshots, or stale replicas can still require them. - Choosing an LSM tree solely because the system is write-heavy without addressing read latency, disk headroom, or compaction stalls. ## Interview questions where it comes up - [Design a distributed key-value store](https://sysround.com/questions/design-key-value-store): An LSM engine provides a concrete foundation for explaining durable local writes, tombstones, recovery, and compaction competing with repair traffic. - [Design a metrics monitoring system like Datadog](https://sysround.com/questions/design-metrics-monitoring-system): An LSM-backed time-series design requires explicit choices about ingestion capacity, series-and-time key ordering, retention, and compaction costs. - [Design a distributed tracing system](https://sysround.com/questions/design-distributed-tracing): An LSM-backed span and attribute-index store makes the trade-off between sustained ingestion, searchable data, and background storage work central to capacity planning. ## FAQ ### What is the difference between an LSM tree and a B-tree? A B-tree maintains a page-oriented search structure, typically updating affected pages as records change. An LSM tree buffers changes and merges immutable sorted files in the background. LSM trees often favor sustained writes, while B-trees can offer more predictable reads; the actual result depends on caching, storage hardware, and workload. ### Why do LSM trees need compaction? Flushes create multiple sorted files containing overlapping keys and old versions. Compaction merges these files to control read work and reclaim obsolete data. It consumes CPU, I/O bandwidth, and temporary disk space, so it must keep pace with ingestion. ### Are LSM trees eventually consistent? Not inherently: an LSM tree is a local storage structure, not a distributed consistency model. A database using one can provide strong or eventual consistency depending on its replication, coordination, and transaction protocols. ## Related concepts - [Write-ahead log](https://sysround.com/concepts/write-ahead-log) - [Bloom filters](https://sysround.com/concepts/bloom-filter) - [Write amplification](https://sysround.com/concepts/write-amplification) - [B-trees](https://sysround.com/concepts/b-tree) --- SysRound (https://sysround.com) is an AI practice tool for system design interviews: a voice or typed AI interviewer, a shared whiteboard, then feedback on every skill and a model answer. Its feedback is AI-generated and can be wrong.