Observation — db-05 LSM MemTable

Hex layout of a tiny dump

Three operations: put alpha first, put beta second, del beta.

hexdump -C m.bin

00000000  4d 4d 54 31 02 00 00 00  05 00 00 00 05 00 00 00  |MMT1............|
00000010  00 61 6c 70 68 61 66 69  72 73 74 04 00 00 00 00  |.alphafirst.....|
00000020  00 00 00 01 62 65 74 61                          |....beta|

Annotated:

Total: 40 bytes; matches size_bytes() = 8 + (9+5+5) + (9+4+0) = 40.

Cross-language byte equality

scripts/cross_test.sh produces three files rust.bin, go.bin, cpp.bin. With the verify script in this lab:

$ shasum -a 256 *.bin
b67…  rust.bin
b67…  go.bin
b67…  cpp.bin

If any one of the three differs we either have endianness disagreement, key ordering disagreement, or someone wrote the type byte in a different position.

Memory layout intuition

key                          entry
"abc"  ──►  Entry::Value("..."  10 bytes)
"abd"  ──►  Entry::Tombstone
"abz"  ──►  Entry::Value(""      0 bytes)   # empty value is legal and ≠ tombstone
"zz"   ──►  Entry::Value("..."  4096 bytes)

Notes:

• The key length is not stored alongside the in-memory entry — only at encode time.
• An empty value ("") is a valid value, distinct from Tombstone. The type byte is what discriminates them.

size_bytes() table

For a MemTable with n entries of average key length k̄ and average value length v̄, with a fraction f being tombstones:

$$ \text{size_bytes}(n, k̄, v̄, f) = 8 + n \cdot (9 + k̄) + n(1-f) \cdot v̄ $$

For default LSM tunings:

(Compare to a real LevelDB write_buffer_size of 4 MiB or RocksDB's 64 MiB default — the table above shows you'd flush a 10K-entry buffer at about a megabyte.)

What an empty MemTable looks like

hexdump -C empty.bin
00000000  4d 4d 54 31 00 00 00 00                           |MMT1....|

8 bytes. size_bytes() returns 8. len() returns 0.

Iteration order corner cases

keys = ["", "\x00", "\x00\x00", "a", "ab", "b"]

Sorted byte-lex order:

""         (empty key — sorts first)
"\x00"
"\x00\x00"
"a"
"ab"
"b"

Empty keys are legal in this design (klen = 0). They are useful when the key is something like a single byte tag followed by an optional suffix.