## Build a Crash-Consistent Single-Server Key-Value Store Implement and explain a key-value store that runs in one server process and persists byte-string keys and values on its local filesystem. The public operations are `put(key, value)`, `get(key)`, and `delete(key)`. Multiple threads may call the store concurrently. A completed write must survive a process restart, and deletion must be represented by a tombstone rather than by rewriting old records in place. ### Constraints & Assumptions - Keys and values are arbitrary byte strings; records therefore need explicit lengths rather than delimiter-only encoding. - The store may divide data into several local shards, but no operation spans more than one key. - The filesystem can return short reads or writes, and a crash can leave a partial final record. - State the exact point at which `put` or `delete` is acknowledged as durable. - Do not assume a data volume, durability latency, or read/write ratio; identify which values affect the layout and synchronization choices. ### Part 1 — Define the On-Disk Record and Basic Operations Specify a record format and show how startup, `put`, `get`, and `delete` use it. Explain how byte keys and values are distinguished from metadata and how a tombstone changes later reads. #### What This Part Should Cover - Length-prefixed records with an operation type and integrity check. - An in-memory index from key to the latest durable record location. - Append behavior for updates and tombstones for deletes. - Detection and truncation or rejection of a partial tail during recovery. ```hint Make the final record recognizable Recovery needs enough framing information to distinguish a complete append from bytes left by a crash. ``` ### Part 2 — Make Concurrent Access and Durability Correct Describe the synchronization around the file, index, and acknowledgement path. Include two writers to the same key, a reader racing with a delete, and a crash between appending a record and updating memory. #### What This Part Should Cover - A consistent serialization point for each key update. - Lock scope and the state protected by each lock. - A write-ahead or append-log rule that persists intent before publishing it in memory. - Full-write loops, flush versus durable sync, and error propagation. ```hint Choose one publication order If disk and the in-memory index disagree after a crash, recovery must have one authoritative sequence to replay. ``` ### Part 3 — Shard, Recover, and Test the Store Explain how keys map to local shards, how each shard recovers, and how stale records are eventually reclaimed. Give tests that expose locking, race, tombstone, and write-ahead-log defects. #### What This Part Should Cover - Deterministic key-to-shard routing and independent shard state. - Recovery that replays complete records in log order. - Compaction that does not resurrect deleted or overwritten values. - Crash-injection and concurrent-operation tests with stated invariants. ```hint Treat compaction as another writer A compacted file should become visible atomically and only after it contains the latest live state for that shard. ``` ### What a Strong Answer Covers - Connects byte-safe encoding, append order, synchronization, and recovery into one coherent implementation. - Defines the durability acknowledgement boundary instead of treating every buffered write as durable. - Handles same-key races and partial I/O without corrupting the index. - Explains how sharding improves concurrency while preserving one-key semantics. ### Follow-up Questions 1. How would checksums and sequence numbers help distinguish corruption from a partial tail? 2. What changes if two processes, rather than two threads, open the same shard? 3. How can compaction swap files without losing writes that arrive during the copy? 4. Which guarantee changes if the store acknowledges after a buffered write but before a durable sync?