Serialize and Restore an In-Memory Key-Value Store

Problem Statement

You are tasked with implementing a deterministic binary serialization and deserialization protocol for an in-memory key-value store where both keys and values are arbitrary UTF-8 strings.

Your implementation must be canonical (identical key-value pairs always produce the exact same byte representation) and defensive (corrupted, ambiguous, or malicious byte streams must be safely rejected by raising a ValueError).

Binary Format Specification

1. Entry Count: A 4-byte unsigned integer in big-endian format (>I), indicating the number of key-value pairs N.
2. Entries: N sequential key-value entries sorted in ascending lexicographical order by raw key bytes.
   • Key Length: 4-byte unsigned big-endian integer.
   • Key Bytes: Raw UTF-8 encoded bytes.
   • Value Length: 4-byte unsigned big-endian integer.
   • Value Bytes: Raw UTF-8 encoded bytes.

Validation Rules

The deserialize method must raise a ValueError if any of the following occur:

• Truncation / Unexpected EOF: The byte stream ends before all declared fields or entries are fully read.
• Trailing Bytes: Extraneous bytes remain after decoding all declared entries.
• Duplicate or Out-of-Order Keys: Keys are not strictly increasing lexicographically (this enforces uniqueness and canonical ordering).
• Size Limits: Any key length exceeds 64 KiB (65,536 bytes) or any value length exceeds 1 MiB (1,048,576 bytes).
• Malformed Encoding: Key or value bytes are not valid UTF-8.

Class Interface

class KVStoreSerializer:
    MAX_KEY_SIZE: int = 65_536       # 64 KiB
    MAX_VALUE_SIZE: int = 1_048_576  # 1 MiB

    def serialize(self, store: dict[str, str]) -> bytes:
        """Serializes a dictionary of string keys and values into bytes."""
        pass

    def deserialize(self, data: bytes) -> dict[str, str]:
        """Restores a dictionary from bytes. Raises ValueError if invalid."""
        pass

Examples

Example 1: Empty Store

• Input: {}
• Serialized: b'\x00\x00\x00\x00' (4 bytes, count = 0)
• Deserialized: {}

Example 2: Single Entry

• Input: {"a": "b"}
• Serialized: b'\x00\x00\x00\x01\x00\x00\x00\x01a\x00\x00\x00\x01b'
  • Count = 1 (\x00\x00\x00\x01)
  • Key len = 1 (\x00\x00\x00\x01), Key = 'a'
  • Value len = 1 (\x00\x00\x00\x01), Value = 'b'
• Deserialized: {"a": "b"}