# Exercise 2: Tracing a Read Through an LSM Tree

## Scenario

`PulseMetrics` (from Exercise 1) is now running on an LSM-tree-backed store. You're mentoring a new engineer who is confused about why a single `GET` for one metric key sometimes seems to "search around" instead of going straight to the answer the way their prior experience with a relational database's primary key lookup did. They've asked you to walk through, mechanically, what happens on disk for the following sequence of events on a single key, `server_42:cpu_usage`:

```
t1: WRITE server_42:cpu_usage = 12%     (memtable A is active)
t2: WRITE server_42:cpu_usage = 15%     (memtable A is active)
    ... memtable A fills up, flushed to SSTable_1, new memtable B becomes active ...
t3: WRITE server_42:cpu_usage = 9%      (memtable B is active)
    ... memtable B fills up, flushed to SSTable_2, new memtable C becomes active ...
t4: DELETE server_42:cpu_usage          (memtable C is active)
t5: READ server_42:cpu_usage            <- trace this read
```

## Deliverables

Produce all of the following, in this file, below this line:

1. **Trace the READ at t5 step by step**, in the order the engine actually checks things (theory section 4) — memtable first, then SSTables newest-to-oldest — and state what value (or "not found") it returns at each step, stopping at the first authoritative answer.
2. **Explain what physically exists on disk immediately after t5**, before any compaction has run — specifically: does SSTable_1's stale `12%`/`15%` values get removed the moment they're superseded? What about the tombstone from t4? Cite section 5.
3. **Explain what compaction would eventually do** to this specific key's history (SSTable_1's two stale values, SSTable_2's value, and the tombstone) once it runs, and what would remain on disk for `server_42:cpu_usage` afterward.
4. **Answer the new engineer's actual confusion** in 2-3 plain-language sentences: why can't an LSM tree just "go straight to the answer" the way they're used to, and what is the store doing instead to keep that lookup fast anyway (reference the per-SSTable indexing/Bloom-filter aside in section 4).

## Constraints

- Your trace in deliverable 1 must show the search stopping at the FIRST match found, not checking every remaining SSTable "for completeness" — reaching SSTable_1 (where the truly oldest values live) after already finding the answer is incorrect.
- Deliverable 4 is for the new engineer, not for a database internals audience — keep it accessible while still being technically accurate.