Verification — SSTable Format

V1: empty build

build from an empty MemTable produces a 36-byte file ending in SST1\0\0\0\0 with index_offset=0, index_size=4, num_blocks=0.

V2: single-entry build

add("k", Value("v")) → finish yields a file that:

  • contains exactly one data block,
  • has one index entry with key "k",
  • round-trips: iter returns [("k", Value("v"))], get("k") returns the value, get("missing") returns None.

V3: tombstones survive

A tombstone added during build is reported as Some(Entry::Tombstone) by get and as T <hex-key> by iter.

V4: ascending-key precondition

Calling add with a key that is not strictly greater than the previous added key MUST return Unsorted and leave no partial output.

V5: block-boundary rule

With target_block_size = 64 and inputs whose encoded sizes are known, the writer flushes the running block as soon as adding the next entry would push its size strictly greater than 64 bytes. A test inserts entries crafted so that the second insert is the boundary-crossing one and asserts the resulting file has exactly two data blocks and two index entries.

For any file produced by finish:

  • the last 32 bytes parse as a Footer,
  • magic == "SST1\0\0\0\0",
  • index_offset + index_size + 32 == file_size,
  • num_blocks matches the count of index entries.

V7: bulk round-trip vs MemTable

Take a MemTable populated by bulk 100 + put key50 REPLACED + del key10 + put "" empty-key-value + del key99, build an SSTable from it, then verify that iter-over-SSTable returns the exact same (key, entry) sequence as iter-over-MemTable. Per-key get agrees too.

V8: floor lookup correctness

For a multi-block SSTable, get(target) returns the matching entry when present and None when the target falls between blocks, even though the index entry it lands on belongs to the preceding block.

V9: reader rejects bad magic

A file with the last 8 bytes mutated away from SST1\0\0\0\0 MUST return BadMagic on open.

V10: reader rejects out-of-range index pointer

A file whose footer claims index_offset >= file_size - 32 MUST return IndexOutOfRange on open (caught before any block read).