When the memtable fills, flush it to an SSTable file: sorted key-value pairs, often with a block index and bloom filter footer. LevelDB's format is the reference students copy. Immutability makes concurrent reads safe without locks.
File Layout
Data blocks, index block mapping key ranges to offsets, magic footer.
c
Loading…
Flush sorts in memory before write for sequential I/O
Each SSTable is read-only after creation
Filename encodes level and sequence number in real engines
Compression per block optional (Snappy, Zstd)
Working Through the Exercise
Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.
Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest
Why for this exercise
You will flush a sorted memtable array to a simple SSTable file format on disk. This exercise asks you to write length-prefixed records and an index entry per block.
Document one invariant you will assert in tests and how you would detect its violation from observable symptoms.
Write a C program that flushes a memtable to a sorted SSTable and answers point lookups against it.
Input (stdin):
First line: n, the number of memtable writes
Next n lines: "key value tomb" (tomb=1 marks the write as a tombstone/delete)
Next line: q, the number of lookups
Next q lines: one key per line
Semantics:
The memtable is keyed by key: a later write to the same key overwrites the earlier value/tombstone (last write wins). Keys arrive in arbitrary write order.
A tombstone is a delete marker: it must survive the flush as a TOMBSTONE entry (a real flush cannot know whether older SSTables still hold the key).
The flush emits entries sorted by key.
Output:
"FLUSHED n"
One line per surviving entry, sorted by key: "PUT key value" or "TOMBSTONE key"
"INDEX c" where c = number of index entries (every 3rd entry, 0-based, qualifies)
One line per lookup: "QUERY key FOUND value" | "QUERY key DELETED" (entry is a tombstone) | "QUERY key NOT_FOUND" (no entry)
Use binary search for lookups; a linear scan per query is the exact anti-pattern this format exists to avoid.