Append, don't overwrite

Goal

Store changes as records in an append-only log, see the exact bytes of each record, and play with Stash by hand.

A log of changes

Instead of rewriting the file, Stash adds one record to the end for every change. A new value for a key is a new record. A delete is a record too, called a tombstone. Old records are never touched, so a crash can only ever damage the record being written.

Each record has the same shape, from lab/stash/record.py:

    +--------+---------+-----------+-----+-------+
    | crc32  | key len | value len | key | value |
    | 4 B    | 4 B     | 4 B       |     |       |
    +--------+---------+-----------+-----+-------+

The two lengths tell a reader where the record ends. The checksum comes in chapter 04. Encoding a record is four lines:

def encode(key: bytes, value: bytes | None) -> bytes:
    size = TOMBSTONE if value is None else len(value)
    body = struct.pack("<II", len(key), size) + key + (value or b"")
    return struct.pack("<I", zlib.crc32(body)) + body

<II packs two unsigned 32-bit numbers in little-endian order. A tombstone has a value length of 0xFFFFFFFF and no value.

Play with it

uv run python -m stash shell

stash> set acorn:1 under the oak
ok
stash> set acorn:2 behind the shed
ok
stash> set acorn:1 in the flower pot
ok
stash> del acorn:2
deleted
stash> get acorn:1
in the flower pot
stash> quit

Look inside

uv run python -m stash inspect

  offset  size  key         value
       0    32  acorn:1     under the oak
      32    34  acorn:2     behind the shed
      66    36  acorn:1     in the flower pot
     102    19  acorn:2     (deleted)
4 records, 121 bytes

Four changes, four records. acorn:1 is in the file twice, and only the last one counts. acorn:2 is in the file even though it is deleted: the tombstone says so. Check the first size: 12 bytes of header, 7 for acorn:1, 13 for under the oak. That makes 32.

Check it works

• inspect shows one record per change, including the tombstone.
• You can explain every number in the size column.

Exercise

Run del acorn:99 in the shell for a key that was never set. Does Stash write a tombstone? Read delete in lab/stash/store.py to check, and decide whether that is the right call.

More to try

• Look at the raw bytes with python -c "print(open('data/nuts.stash','rb').read())". Find the four acorn keys.
• What does a record cost for a 3-byte key and a 3-byte value? What fraction is header?