## Design a Concurrent Key-Value Store with Batch Writes Design the core implementation of an in-memory key-value store for concurrent callers. For this practice contract, support `get`, `put`, `delete`, and an all-or-nothing `batchWrite` containing ordered puts and deletes. Single operations and committed batches must appear linearizable; operations on the same key within a batch take effect in list order. The original interview summary mentions a basic implementation, locking, and batch writes but does not preserve exact method signatures or semantics. Treat the contract above as the practice version, not as an observed detail. ### Part 1 — Define State and API Semantics Specify missing-key behavior, value ownership, batch validation, and the point at which each operation takes effect. #### What This Part Should Cover - Exact behavior for `get`, `put`, and `delete` on present and absent keys. - Defensive copying or immutability rules for keys and values. - Ordered handling of repeated keys inside one batch. - Validation that cannot leave partial changes behind. ```hint Define one visible instant Linearizability becomes testable only when each operation or entire batch has a clear point between invocation and response at which it takes effect. ``` ### Part 2 — Choose a Locking Strategy Compare a simple global lock with finer-grained locking and select a design that preserves the batch contract. #### What This Part Should Cover - Read versus write synchronization and safe publication of values. - Lock ordering when a batch touches several keys. - Deadlock avoidance, starvation, and behavior under hot-key contention. - The complexity cost of moving beyond a single lock. ```hint Let the batch contract drive the locks Per-key locks improve concurrency only if the implementation can acquire every required lock without exposing half of a batch or creating a lock-order cycle. ``` ### Part 3 — Apply Batches Atomically Design validation, staging, commit, and result handling for a mixed list of puts and deletes. #### What This Part Should Cover - Rejection of malformed operations before mutation. - A staging or rollback strategy for failures during preparation. - One commit boundary visible to readers and writers. - Deterministic results for duplicate keys and empty batches. ```hint Prepare before publishing Construct the new state or rollback information before the commit boundary so validation and allocation failures do not expose a prefix. ``` ### Part 4 — Verify Concurrency and Evolution Explain complexity, tests, observability, and what changes if persistence or multi-process access is later required. #### What This Part Should Cover - Expected time and space for single operations and a batch of `b` operations. - Deterministic concurrency tests rather than timing-only tests. - Invariants and metrics for contention, batch size, and operation latency. - The boundary between an in-memory lock and durable or distributed transactions. ```hint Test forbidden histories The strongest test is not that threads finish; it is that no reader can observe a state that falls between two operations of one committed batch. ``` ### What a Strong Answer Covers - Explicit single-operation and all-or-nothing batch semantics. - A locking design whose ordering and publication rules are defensible. - Validation and staging before one atomic commit point. - Concurrency tests that detect partial visibility, lost updates, and deadlocks. ### Follow-up Questions 1. When would a global read-write lock outperform a striped-lock design? 2. How would you acquire striped locks for a batch without deadlock? 3. What happens if preparing a batch runs out of memory? 4. Which guarantees require a different design once the store must survive process failure?