Implement a persistent sharded key-value store

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.

Simulate a Persistent Sharded Key-Value Store

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

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.

Examples

Example 1

Input: (10, [('put', 'a', '1'), ('put', 'b', '22'), ('get', 'a'), ('put', 'a', '333'), ('get', 'a'), ('restore',), ('get', 'b')])
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'.

Example 2

Input: (20, [('put', 'ab', 'x'), ('put', 'c', 'yz'), ('delete', 'ab'), ('get', 'ab'), ('restore',), ('get', 'c'), ('get', 'ab')])
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.

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.