~/problems / Streams & durability / Serialization and durability

Basics: length-prefixed encoding of a list of strings

easy basics ~10 min

To save a list of strings as bytes and get exactly the same list back, you can't just join them with a separator: the strings might contain the separator. The standard fix is to write each string's length first, so the reader knows how many bytes to take.

Implement two functions:

  • encode(strings: list[str]) -> bytes
  • decode(data: bytes) -> list[str]

such that decode(encode(xs)) == xs for every list of strings, including empty strings, newlines, commas, NUL characters and non-ASCII text.

Use this exact format so other programs could read it. For each string, in order:

  1. Encode the string as UTF-8.
  2. Write the number of bytes (not characters) as a 4-byte big-endian unsigned integer: struct.pack(">I", n).
  3. Write the UTF-8 bytes.

Nothing else: no header and no count of strings.

encode(["hi", ""])        # b"\x00\x00\x00\x02hi" + b"\x00\x00\x00\x00"
encode(["é"])             # b"\x00\x00\x00\x02\xc3\xa9"   ("é" is 1 character but 2 bytes)
decode(encode(["a,b", "line\nbreak"]))   # ["a,b", "line\nbreak"]
decode(b"")               # []

If data ends in the middle of a length or a string (a truncated file), decode must raise ValueError rather than return a partial result.

Show hint

decode walks an offset through the bytes: read 4 bytes with struct.unpack_from(">I", data, offset), then slice exactly that many bytes, and check there really are that many left.

Topic: Serialization and durability. Length-prefixed encodings, write-ahead logs, checkpoints and recovery.

0:00
Ctrl ' run · Ctrl ↵ submit
esc