Key-Value Store Persistence: Length-Prefixed Bytes, Size-Capped Chunks, Thread Safety

Implement an in-memory key-value store whose contents survive a restart. While the program runs, the store serves reads and writes from memory. When `shutdown()` is called, it writes its contents to disk; when the store starts again, it restores exactly the same contents. The exact interface was not reported. A reasonable starting point: ```python class KVStore: def __init__(self, path: str) -> None: ... # restore from disk if a saved store exists def get(self, key: str) -> str | None: ... def set(self, key: str, value: str) -> None: ... def shutdown(self) -> None: ... # persist everything to disk ``` ### Constraints and Clarifications - Assume keys and values may contain any characters, including newlines, spaces and non-ASCII text. - In Parts 1 and 2, data is written only on `shutdown()`; nothing needs to be persisted on each `set`. ### Clarifying Questions - Are keys and values always strings, or can they be arbitrary bytes? Is there a maximum length for either? - Is there a `delete` operation, and must deletions survive a restart? - Must the store survive only a clean `shutdown()`, or also a crash at any moment? - If the saved data is missing or damaged at start-up, should the store start empty or refuse to start? ### Part 1 — Serialize keys, values and their lengths to bytes On `shutdown()`, convert every key, every value and the length of each into bytes and write them to disk. On start-up, read the bytes back and rebuild the store. ```hint Count the right thing Decide what unit each length measures and how many bytes the length itself occupies, so the reader never has to guess where a number ends or how much data follows it. ``` #### What This Part Should Cover - A byte layout for each record: how lengths are encoded (width, byte order) and what they count - Text encoding of keys and values, and byte length versus character length - An exact round trip, including empty strings and an empty store - Behavior when the saved file is missing, truncated or corrupt ### Part 2 — Split the saved data into chunks of a given size You are now also given a size. The saved data must be split into chunks no larger than that size before being written to disk. Restoring must reassemble the chunks and rebuild the same store. ```hint Reassembly needs its own information Whoever restores the store must know which chunks belong to the latest save, in what order, and whether the set is complete. Decide where that information lives and when it is written. ``` #### Clarifying Questions for this Part - Does the size limit apply to each chunk file, including any header you add to it? - May one key-value record be split across two chunks, or must every record fit inside a single chunk? What if one record is larger than the size? - Should each chunk be written as a separate file? #### What This Part Should Cover - Chunking strategy: slicing one byte stream versus packing whole records - Chunk naming, ordering, and the metadata needed for reassembly - Validation on restore: missing or damaged chunks, and leftovers from an earlier, larger save - Keeping the previous save intact if writing many chunks is interrupted ### Part 3 — Make the existing code safe for multiple threads (discussion only) The store is now used by several threads at once. Without writing code, discuss what can go wrong in the current implementation and how you would support concurrent `get`, `set` and `shutdown` calls. ```hint Shutdown is the hard case Single reads and writes are only part of the problem. Think about what `shutdown` sees if another thread calls `set` while it is serializing, and what should happen to a `set` that arrives afterwards. ``` #### What This Part Should Cover - Which operations race in the current code, and what the failures look like - Locking options (one lock, reader-writer lock, lock striping) and their trade-offs - A consistent snapshot for persistence without holding a lock during disk I/O - Behavior of calls that arrive during or after shutdown ### What a Strong Answer Covers - A precise byte format that round-trips arbitrary keys and values, with lengths measured in bytes - Restore that rejects truncated or corrupt data instead of loading part of it - Chunking that preserves order and lets the reader detect an incomplete save - A concurrency design built around a consistent snapshot and a clear shutdown cut-off - Tests for edge cases: empty strings, separator-like characters inside data, multi-byte characters, records larger than the chunk size ### Follow-up Questions - The store is too large to hold a second, encoded copy in memory during shutdown. How do you stream the save? - A crash happens halfway through `shutdown`. How do you make sure the previous save is not destroyed? - How would you make every `set` durable immediately, so that a crash at any moment loses nothing? - Most operations are reads from many threads. How does that change your locking choice, and what difference does Python's global interpreter lock make?