What path does a write take in a log-structured storage engine, from arrival to an immutable sorted file on disk?
answer
- append, don't overwrite
- log first, then memory
- sorted buffer in RAM
- flush when full
- files never change
basics
~20 sThe write is appended to a commit log for durability and inserted into a sorted in-memory buffer, then acknowledged. When the buffer fills it is flushed to disk as a new immutable sorted file, and background compaction later merges those files.
solid answer
~40 sA log-structured merge (LSM) engine never updates data in place. A write is first **appended to a commit log** on durable storage, so it survives a crash, and then inserted into an **in-memory sorted buffer** (often called a memtable); at that point it can be acknowledged. When the buffer reaches a size threshold it is frozen, a new buffer takes over, and the frozen one is **flushed** sequentially to disk as an **immutable sorted file**. Files are never modified: updates and deletes are simply newer entries in newer files. Over time a **compaction** process merges files, keeping the newest version of each cell and dropping superseded data. The payoff is that every disk write is sequential, which makes sustained write throughput high.
go deeper
List the write path in order, commit log, sorted memory buffer, flush to an immutable sorted file, compaction, and say why writes are fast.
Explain why files are immutable and how updates and deletes become newer entries, and what triggers a flush.
Connect the write path to operational effects such as flush storms, log growth and compaction backlog under sustained write load.
Be ready to argue why an engine built on this path fits a write-heavy system and what it commits the team to operate.
## The idea: turn random writes into sequential ones A traditional engine updates data **in place**: to change a row, it finds the page holding it and rewrites that page, which means random I/O. A **log-structured merge (LSM)** engine instead buffers writes in memory and writes them to disk only in large, **sequential**, sorted batches. It then merges those batches in the background. The design dates from research on indexes with very high insert rates and underlies wide-column stores and many embedded key-value engines. ## The steps of a write 1. **Append to the commit log.** The mutation is appended to a write-ahead log on durable storage. Appending is sequential and cheap. The log exists only to recover the in-memory state after a crash. 2. **Insert into the memory buffer.** The mutation goes into a **sorted in-memory structure** (a skip list or balanced tree), keyed by row key and column. Reads can see it immediately. 3. **Acknowledge.** The write is now durable (subject to how often the log is synced) and visible. 4. **Flush.** When the buffer reaches a size threshold, or the log grows too large, the buffer is **frozen**, a fresh buffer takes new writes, and the frozen one is written to disk in sorted order as a new **immutable sorted file** with its own index and filter. 5. **Compact.** Background merges combine several files into fewer, larger ones, keeping the newest version of each cell and dropping data that has been superseded or deleted. ## Immutability is the key property Once written, a sorted file is **never changed**. So: - an **update** is a newer entry for the same key in a newer file; - a **delete** is a newer entry that marks the key deleted; - the current value is found by looking at the newest entries first. This makes files easy to cache, copy and replicate, and makes crash recovery simple — only the buffer needs rebuilding from the log. ## What it costs | benefit | cost | |---|---| | sequential writes, high write throughput | a key's data may be spread across several files, so reads may check several | | no in-place page rewrites | background compaction rewrites data, using disk I/O and space | | simple crash recovery | old versions and deletes occupy space until compaction removes them | ## Names across the family Different stores name the parts differently — commit log or write-ahead log, memtable or memstore, SSTable or store file — but the structure is the same: **log, sorted memory buffer, flush to immutable sorted files, compaction**. ## Interview angle Interviewers expect the steps in order, the reason each exists, and the insight that immutability turns updates and deletes into newer writes.
- Why is the write acknowledged before it reaches a sorted file on disk?Durability comes from the commit log, which can rebuild the memory buffer after a crash. Waiting for a flush would make every write pay for a large sequential file write and destroy write latency.
- What triggers a flush besides the buffer filling up?Commonly the commit log growing past its space limit, because old log segments can be reclaimed only after the data they protect has been flushed. Operators also flush manually before shutdown to shorten log replay on restart.
It is like a clerk who jots every incoming note in a notebook, sorts the day's notes on a desk tray, and at the end of the tray files them as one sealed, sorted folder; old folders are never edited, only merged later.
saying these in an interview costs you the question
- Saying an LSM engine updates the row in place in its data file
- Believing a write is not durable until it has been flushed to a sorted file
- Thinking a delete immediately removes data from disk
- Assuming the in-memory buffer is unsorted and sorted only at flush