Memtable + Flush

A WAL alone cannot be the database. The log grows without bound, so restart replay gets slower forever, and answering a GET from a log would mean scanning history. Every log-structured engine therefore splits state in two:

• the memtable — an in-memory sorted map absorbing all fresh writes (paired with the WAL for crash safety), and
• flush — when the memtable gets big, serialize it to disk as an immutable sorted file (an SSTable, dissected next lesson), reset the memtable, and drop the now-redundant WAL prefix.

WAL (crash safety) --> memtable (newest data, in RAM)
                          |  flush at threshold
                          v
                       file 1   (newer)
                       file 0   (older)

LevelDB flushes at 4 MB of memtable by default; RocksDB also triggers on total WAL size and elapsed time. Production engines swap in a fresh memtable and flush the full one in the background as an immutable memtable, so writes never stall on disk I/O.

Deletes must survive the flush: tombstones

Here is the subtlety that breaks naive implementations. Say a=1 was flushed into file 0, and now the user deletes a. You cannot reach into file 0 — it is immutable. If DELETE merely removes a from the memtable dict, a later GET misses the memtable, falls through to file 0, and happily returns 1. The delete silently undoes itself.

The fix: DELETE writes a tombstone — a marker meaning "deleted as of now" — into the memtable, and flush persists it like any other entry:

Reads walk the layers newest-first

The order is the whole point: the memtable is newest; file 1 beats file 0. And a tombstone is a real answer ("deleted"), not a miss — finding one must end the search. LIST applies the same rule across every layer: the newest version of each key wins, and tombstoned keys are omitted.

Your exercise

Implement PUT, DELETE, GET, FLUSH, FILES, LIST. The grader-caught mistakes, from the real tests: (1) the undead delete — PUT a 1, FLUSH, DELETE a, GET a must print <nil>; deleting with del mem[key] instead of writing a tombstone makes GET fall through to file 0 and print 1; (2) exact tokens — FLUSH prints FLUSHED file=0 entries=2 (files number from 0, and tombstones count as entries, so flushing a lone DELETE prints entries=1), while FILES renders a tombstone as a=TOMBSTONE — the bare word, no angle brackets; (3) LIST across layers — after PUT a 1, PUT b 2, FLUSH, DELETE a, FLUSH, the hidden test expects LIST to print exactly one line, b=2.