(12%) Read the following description about the LSM tree and answer the questions.

An LSM-tree is a disk-oriented data structure that improves write efficiency by buffering updates in memory and flushing them to disk in batches. By doing so, it turns many small random writes into fewer sequential writes, which is especially beneficial for write-heavy workloads.

LevelDB is a popular open-source LSM-tree based key-value store. New updates are first appended to a write-ahead log (WAL) for crash recovery, then inserted into an in-memory MemTable (typically a skip list). When the MemTable becomes full, it is frozen as an Immutable MemTable, and a new MemTable is created for incoming writes. The Immutable MemTable is then flushed to disk as an SSTable, where keys are stored in sorted order.

On disk, LevelDB organizes SSTables into multiple levels (L0, L1, ...). Data is first flushed into L0, where SSTables may overlap in key ranges. When L0 grows beyond a threshold, LevelDB triggers compaction: it selects one or more SSTables from level $L_i$ and merges them with overlapping SSTables in level $L_{i+1}$ using a merge-sort. The merged output is written as new SSTables in $L_{i+1}$. From L1 onward, SSTables are maintained to be non-overlapping within each level.

Deletes are handled using tombstones. A delete inserts a marker rather than immediately removing data. During compaction, entries covered by tombstones are dropped, which permanently removes the data. Reads search for the newest version first, checking the MemTable, then the Immutable MemTable, then SSTables from L0 down to deeper levels until the key is found or confirmed absent.

(a) (4%) Explain where write amplification comes from in an LSM-tree KV store such as LevelDB. Your answer should connect amplification to the maintenance workflow described above.

(b) (4%) Explain where read amplification comes from in an LSM-tree KV store. In particular, why can L0 increase the number of files a lookup must examine?

(c) (4%) Under what conditions does compaction become the bottleneck and lead to higher tail latency or write stalls? Describe the situation using the LSM maintenance workflow (MemTable, Immutable MemTable, flush to L0, and compaction across levels).