SSTable Format

Flush produces a Sorted String Table — the on-disk file format at the heart of LevelDB, RocksDB, Cassandra, and Bigtable (whose paper coined the name). Three properties define it:

• Sorted by key — point lookups binary-search; range scans walk linearly.
• Immutable — written once, never edited. Updates land in newer files, compaction rewrites whole files, but an SSTable itself never changes — which makes caching and concurrent reads trivially safe.
• Self-describing — a footer points at the index and filters, so a reader needs no external metadata.

Real formats layer optimizations onto the sorted run: data is cut into ~4 KB blocks (with restart points every ~16 keys inside each block); a block index at the file's tail maps key ranges to block offsets and stays in memory after open; a Bloom filter (~10 bits per key for a ~1% false-positive rate — lesson 2.2 does the math) lets reads skip files that cannot contain the key; blocks are compressed independently with Snappy/LZ4/Zstd for 5–10x savings. This exercise strips all of that to the essence: one sorted array per file, binary search on GET.

The binary search the grader expects

Your GET must report compares=<n> — and the tests check that number exactly, so the algorithm is pinned down. Use the classic inclusive-bounds search, counting one compare per probe (a probe inspects one key; do not bill its == and < checks separately):

Trace it on the sorted file [a, b, c]: GET b probes index 1 — found, so it prints 2 compares=1. GET a probes b then a: 1 compares=2. GET d probes b, then c, then runs out: <nil> compares=2. Those are the visible test's exact expected lines. The half-open variant (hi = len(table), hi = mid) probes different midpoints — on a two-key file [a, b], it would probe b first and report compares=2 where the grader demands compares=1. Inclusive bounds only.

Scope quirks of this lesson

GET searches only the newest SSTable — not the memtable, and not older files (the full newest-first read path is the next lesson). So before any FLUSH there is nothing to search at all: GET a prints <nil> compares=0. KEY-COUNT totals entries across all SSTables, and SSTABLES summarizes each file as SSTABLE <n>: keys=<m> first=<k> last=<k> — first and last fall out of the sorted array for free.

Your exercise

Implement PUT, FLUSH, GET, KEY-COUNT, SSTABLES. The grader-caught mistakes, from the real tests: (1) compare counting — on the file [a, b, c, d], GET c must print 3 compares=2 (probe b, then c); billing == and < as two compares, or using exclusive-hi bounds, breaks the exact numbers; (2) the pre-flush GET — with zero SSTables, GET a prints <nil> compares=0, not an error; (3) sort on flush — PUT z 26, PUT a 1, PUT m 13, FLUSH, SSTABLES must print SSTABLE 0: keys=3 first=a last=z; flushing in insertion order breaks both the binary search and the first/last summary.