Quick Overview

This question evaluates understanding of persistent storage and file-based sharding, including on-disk layout, record serialization, indexing strategies for locating the latest value per key, shard rollover, and recovery from partial or corrupt tails.

Implement a persistent sharded key-value store

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

## Problem Implement a simple **key–value store** that persists data on disk. You must store the data in **fixed-size shards**, where each shard is saved in **one file**. If a shard file reaches its maximum size, new writes must go into a **new shard file**. The store must support **shutdown (persist)** and **restore (recover)**. You are given helper functions: - `encode(key, value) -> bytes` to serialize a key/value record - `decode(bytes) -> (key, value)` to deserialize a record Assume keys and values are strings (or byte arrays), and `encode/decode` are inverses for valid records. ## Required API Design and implement (language-agnostic) functions/methods equivalent to: - `put(key, value)` - Insert or overwrite the value for `key`. - `get(key) -> value | null` - Return the current value for `key`, or `null`/`None` if missing. - `delete(key)` (optional if you want to support removals) - Remove `key` if it exists. - `shutdown()` - Ensure all in-memory state is persisted so the store can be restored later. - `restore(directory_path)` (or constructor-based restore) - Load persisted data from disk and make the store usable again. ## Storage requirements - Data is stored across **one or more files** in a directory. - Each file is a **shard** with a configurable maximum size `SHARD_SIZE_BYTES`. - Writes append records to the current shard until it would exceed the shard size; then create a new shard file. ## What to discuss / clarify - Your on-disk layout (file naming, record boundaries, handling partial/corrupt tail). - How you locate the latest value for a key after many overwrites. - What metadata or in-memory index (if any) you maintain. - Complexity of `put/get` and `restore`. - Edge cases: empty store, large values, shard rollover, overwrite semantics, optional delete semantics.

Overview: This question evaluates understanding of persistent storage and file-based sharding, including on-disk layout, record serialization, indexing strategies for locating the latest value per key, shard rollover, and recovery from partial or corrupt tails.

Simulate a **persistent, log-structured sharded key-value store**. Instead of real files, each shard "file" is represented by a Python string, and the full set of shards is a list of such strings. You are given a `shard_size` and a list of `operations`. Process the operations in order, maintaining both the persisted shard strings and a live in-memory key→value map, then return what the `get` operations saw together with the final shard contents. ## What to implement ```python def solution(shard_size, operations): ... ``` - `shard_size` — the maximum allowed length of any single shard string. - `operations` — a list of operation tuples (described below). ## Operations Each operation is a tuple whose first element names the operation: - **`('put', key, value)`** — write a **put record** for `key`, then set the current value of `key` to `value` (overwriting any existing value). - **`('get', key)`** — read the current value of `key`. Append the result to the list of get-results: the stored value if the key exists, otherwise `None`. - **`('delete', key)`** — if `key` currently exists, write a **delete record** for it and remove it from the live map. If `key` does not exist, **do nothing** (no record is written). - **`('shutdown',)`** — a no-op, included only for API completeness. Every write is already persisted to the shard strings, so there is nothing to flush. - **`('restore',)`** — discard the entire in-memory map and rebuild it by **replaying the shard contents from the first shard to the last** (see *Restore* below). ## Record encoding Each `put` and `delete` is encoded as a single semicolon-terminated record: - **Put record:** `P|key|value;` - **Delete record:** `D|key;` The **size of a record** is its string length. Keys and values are ASCII (letters and digits only), so a character equals one byte, and keys/values never contain `|` or `;`. ## Sharding rule (where each new record is written) Maintain shards as an ordered list, appended to in creation order. When a new record must be written: - If appending it to the **last** shard would keep that shard's length **at most** `shard_size`, append it there (the last shard's new length must be `≤ shard_size`). - Otherwise (appending would make the last shard's length exceed `shard_size`), **create a new shard** and write the record into it. If there are no shards yet, the first record creates the first shard. Because every individual record's encoded length is at most `shard_size`, a record always fits in a fresh shard. If no records are ever written, the shard list is empty (`[]`). ## Restore rule (replaying shards) On `('restore',)`, throw away the current in-memory map and rebuild it from scratch by scanning the shards **in creation order** (first to last): - Split each shard on the `;` terminator and replay each complete record in order. - A `P|key|value;` record sets `key` to `value`. - A `D|key;` record removes `key`. - If a shard ends with an **incomplete fragment that is not terminated by `;`**, ignore that trailing fragment. Because records are replayed in order, the **last write to a key wins**, so the rebuilt map matches the live state that produced the shards. ## Return value Return a tuple **`(get_results, shards)`** where: - `get_results` is the list of results from every `get` operation, in the order they occurred (each entry is a value string or `None`). - `shards` is the final list of shard strings. ## Constraints - `0 <= len(operations) <= 20000` - `1 <= shard_size <= 10000` - Keys and values are non-empty ASCII strings of letters and digits only, so they never contain `|` or `;`. - The encoded length of every single put or delete record is at most `shard_size`.

Constraints

  • 0 <= len(operations) <= 20000
  • 1 <= shard_size <= 10000
  • Keys and values are non-empty ASCII strings containing only letters and digits, so they never contain '|' or ';'
  • The encoded length of every single put or delete record is at most shard_size

Examples

Input: (10, [('put', 'a', '1'), ('put', 'b', '22'), ('get', 'a'), ('put', 'a', '333'), ('get', 'a'), ('restore',), ('get', 'b')])

Expected Output: (['1', '333', '22'], ['P|a|1;', 'P|b|22;', 'P|a|333;'])

Explanation: Each write would overflow the current shard, so three shards are created. After restore, the latest value of 'a' is '333' and 'b' is still '22'.

Input: (20, [('put', 'ab', 'x'), ('put', 'c', 'yz'), ('delete', 'ab'), ('get', 'ab'), ('restore',), ('get', 'c'), ('get', 'ab')])

Expected Output: ([None, 'yz', None], ['P|ab|x;P|c|yz;D|ab;'])

Explanation: All records fit in one shard. The delete operation writes a tombstone for 'ab', so it is missing both before and after restore.

Hints

  1. Use an in-memory hash map for the current state so that each get is O(1) on average.
  2. Treat the shard contents as an append-only log. On restore, replay records from the first shard to the last; the latest record for a key wins.

Community answers

Answer by EL

This is a production-grade implementation. It utilizes a Log-Structured Hash Table (Bitcask-inspired) design. It uses pathlib for modern path handling, struct.Struct for high-performance binary serialization, and zlib for data integrity via CRC32 checksums. import os import zlib import struct from pathlib import Path from typing import Dict, Optional, Tuple, Union --- Provided Helper Functions --- In a real interview, these are given. I'll provide standard implementations here. def encode(key: str, value: Optional[str]) -> bytes: """Serializes a key/value pair. A value of None represents a tombstone (delete).""" import json return json.dumps({"k": key, "v": value}).encode('utf-8') def decode(data: bytes) -> Tuple[str, Optional[str]]: """Deserializes a record back into a (key, value) tuple.""" import json obj = json.loads(data.decode('utf-8')) return obj['k'], obj['v'] class StorageError(Exception): """Custom exception for storage-related failures (e.g., corruption).""" pass class ShardedKVStore: """ A persistent Key-Value store using append-only sharded logs and an in-memory index. """ # Header: Checksum (Unsigned Int, 4B) + Data Length (Unsigned Int, 4B) = 8 Bytes HEADER = struct.Struct(" (shard_id, offset, total_record_size) self.index: Dict[str, Tuple[int, int, int]] = {} self.current_shard_id = 0 self.active_file = None self.current_offset = 0 # Ensure storage directory exists self.directory.mkdir(parents=True, exist_ok=True) # Recover state from disk self.restore() def _

Loading coding console...

Show the approach

Approach

The solution simulates a log-structured sharded key-value store by keeping two things in sync: a list of shard strings (shards, the "persisted" data) and an in-memory dict (index, the live key→value map).

Writing records. Every put/delete is encoded as a terminated record — P|key|value; or D|key; — and routed through append_record. It appends the record to the last shard unless doing so would push that shard's length past shard_size; in that case it opens a fresh shard and writes the record there. Because the problem guarantees each record's length is at most shard_size, a record always fits in a new shard.

Operation dispatch.

  • put: append the record and set index[key] = value.
  • get: append index.get(key) (returns None for a missing key) to get_results.
  • delete: only writes a D|...; record (and removes the key) if the key currently exists, matching the "if missing, do nothing" rule.
  • shutdown: no-op, since every write was already persisted.
  • restore: discard index and rebuild it from the shards via rebuild_index.

Replaying on restore. rebuild_index walks shards in creation order. For each shard it does shard.split(';')[:-1] — splitting on the terminator and dropping the final fragment, which is the empty string after a trailing ; (or an unterminated partial record), elegantly implementing the "ignore incomplete trailing fragment" rule. Each P| record re-sets the key; each D| record pops it. Replaying in order makes the last write to a key win, so the rebuilt map exactly matches the live state.

The function returns (get_results, shards).

Time complexity:
O(n + B), where n is the number of operations and B is the total number of bytes across all shards. Each put/delete does an amortized O(record length) append and a restore scans every shard byte once (proportional to B).
Space complexity:
O(B + k), where B is the total bytes stored in the shard strings and k is the number of live keys held in the index dict.