How Does a Write-Ahead Log Relate to an LSM-Tree?
Understand how a write-ahead log fits inside an LSM-tree with memtables, SSTables, and compaction for fast durable writes.
Expected Interview Answer
A write-ahead log provides crash durability for a single write, while an LSM-tree is the broader storage engine architecture that uses that WAL alongside an in-memory memtable and immutable on-disk sorted segments (SSTables) to make writes fast and durable at scale — the WAL is one component inside the LSM-tree write path, not a competing alternative.
In an LSM-tree engine, every write is first appended to the WAL for durability, then inserted into an in-memory sorted structure called the memtable, which serves reads with very low latency. When the memtable fills up, it is flushed to disk as an immutable, sorted SSTable file, and a fresh memtable takes over; only once a memtable’s SSTable is safely flushed can its corresponding WAL segment be discarded, since the WAL’s only job is to protect data that has not yet reached durable, sorted disk storage. Over time, background compaction merges multiple SSTables together, removing overwritten and deleted keys, which keeps read amplification bounded. This design trades some read complexity (a read may need to check the memtable and several SSTables) for extremely fast, sequential writes, which is why systems like Cassandra, RocksDB, and LevelDB are built this way.
- Combines WAL durability with memtable speed so writes are both safe and fast
- Converts random writes into sequential I/O twice over: WAL append and sorted SSTable flush
- Background compaction keeps storage compact and read amplification bounded over time
- Scales extremely well for write-heavy workloads compared to in-place B-tree updates
AI Mentor Explanation
The WAL is like the paper scoresheet a scorer fills ball by ball, while the LSM-tree is the whole scoring operation: the scorer also keeps a quick mental tally (memtable) for instant answers about the current innings, and periodically transcribes that tally into a neatly organized ledger page (SSTable) once an innings session ends. Old scoresheet pages can be archived once their tally has been safely transcribed into the ledger. Occasionally, old ledger pages from past matches are merged and cleaned up (compaction) to keep the records tidy. The scoresheet alone gives durability; the full system of tally, ledger and merging is what makes the whole operation fast and organized.
Step-by-Step Explanation
Step 1
Write hits the WAL
Every write is first durably appended to the write-ahead log, guaranteeing crash safety.
Step 2
Write hits the memtable
The same write is inserted into an in-memory sorted structure that serves fast reads and writes.
Step 3
Memtable flushes to an SSTable
When the memtable is full, it is flushed as an immutable, sorted file on disk, and its WAL segment can be discarded.
Step 4
Background compaction runs
Multiple SSTables are periodically merged to remove overwritten/deleted keys and bound read amplification.
What Interviewer Expects
- Correctly frames the WAL as a component inside the LSM-tree write path, not a competing design
- Explains the memtable and its role in serving fast reads/writes before flush
- Describes SSTables as immutable and the role of compaction
- Names real systems: Cassandra, RocksDB, LevelDB
Common Mistakes
- Treating WAL and LSM-tree as two alternative, mutually exclusive designs
- Forgetting that WAL segments can only be discarded after their data is safely flushed to an SSTable
- Not mentioning compaction and its role in bounding read amplification
- Confusing SSTables (immutable, sorted, on disk) with the mutable memtable
Best Answer (HR Friendly)
“A write-ahead log protects a single write from being lost in a crash, and an LSM-tree is the bigger design that uses that log together with a fast in-memory buffer and organized on-disk files to make writes both safe and very fast. Think of the log as the safety net, and the LSM-tree as the whole system built around it — the log, the memory buffer, and the periodic cleanup of old files all work together.”
Code Example
class LSMTree:
def __init__(self, wal, flush_threshold=1000):
self.wal = wal
self.memtable = {}
self.sstables = [] # list of immutable sorted dicts on disk
self.flush_threshold = flush_threshold
def put(self, key, value):
self.wal.append(f"PUT {key} {value}".encode()) # durable first
self.memtable[key] = value
if len(self.memtable) >= self.flush_threshold:
self.flush()
def flush(self):
sorted_items = dict(sorted(self.memtable.items()))
sstable_path = write_sstable_to_disk(sorted_items)
self.sstables.append(sstable_path)
self.memtable.clear()
self.wal.truncate_up_to_last_flush() # old WAL segment no longer needed
def get(self, key):
if key in self.memtable:
return self.memtable[key]
for sstable in reversed(self.sstables): # newest first
value = lookup_in_sstable(sstable, key)
if value is not None:
return value
return None
def compact(self):
# merge multiple SSTables, dropping overwritten/deleted keys
merged = merge_sstables(self.sstables)
self.sstables = [merged]Follow-up Questions
- Why can a WAL segment only be truncated after its memtable has been flushed to an SSTable?
- What is read amplification in an LSM-tree, and how does compaction reduce it?
- How does a Bloom filter speed up SSTable lookups for keys that do not exist?
- How does write amplification in LSM-trees compare to that of B-tree based engines?
MCQ Practice
1. What is the relationship between a write-ahead log and an LSM-tree?
The WAL protects writes that have landed in the memtable but not yet reached a durable, sorted SSTable — it is part of the LSM-tree architecture.
2. When can a WAL segment safely be discarded in an LSM-tree engine?
The WAL exists to protect data not yet durably flushed; once flushed to an SSTable, the covering WAL segment is redundant and can be truncated.
3. What is the purpose of compaction in an LSM-tree?
Compaction periodically merges immutable SSTables to reclaim space and keep the number of files a read must check bounded.
Flash Cards
Is a WAL part of an LSM-tree? — Yes — it is the durability mechanism at the start of the LSM-tree write path, not an alternative design.
What is a memtable? — An in-memory sorted structure that receives writes after the WAL and serves fast reads before flushing.
What is an SSTable? — An immutable, sorted file on disk produced when a memtable is flushed.
Why does compaction matter? — It merges SSTables to remove stale data and bound how many files a read must check.