Build a Crash-Consistent Single-Server Key-Value Store

Problem Statement

Implement an embedded, log-structured key-value store (LogKV) for arbitrary byte keys and byte values. The store persists data to an append-only log file on a local filesystem and maintains an in-memory index for fast point lookups.

The system must guarantee crash consistency: in the event of an abrupt process crash, power loss, or torn write mid-record, the recovery mechanism must restore the database to the last clean, uncorrupted record state.

Requirements

1. Record Framing & Integrity:
   • Each record written to the append-only log must contain a fixed-width header followed by the payload.
   • Header format (13 bytes total, big-endian):
     • crc32 (4 bytes, unsigned int): Checksum computed over flags + key_len + val_len + key + value.
     • flags (1 byte): Record type (0x01 for PUT, 0x02 for TOMBSTONE / deletion).
     • key_len (4 bytes, unsigned int): Length of the key in bytes.
     • val_len (4 bytes, unsigned int): Length of the value in bytes (0 for tombstones).
   • Payload: key bytes immediately followed by value bytes.
2. Operations:
   • put(key, value): Append a PUT record, flush/sync to disk, and update the in-memory index.
   • get(key): Retrieve the latest value from the in-memory index or disk. Return None if the key does not exist or was deleted.
   • delete(key): Append a TOMBSTONE record, flush/sync to disk, and remove the key from the in-memory index. Return True if key existed, False otherwise.
   • recover(): Invoked at initialization. Scans the log from offset 0, validates CRC checksums, discards corrupt/partial trailing writes by truncating the file to the last valid boundary, and rebuilds the index.
3. Concurrency:
   • Thread-safe for concurrent readers and writers.

Class Interface

class LogKV:
    def __init__(self, filepath: str):
        """
        Initialize the store at the given file path.
        Must call recover() if the file already exists.
        """
        pass

    def put(self, key: bytes, value: bytes) -> None:
        """Persist key-value pair and update index."""
        pass

    def get(self, key: bytes) -> bytes | None:
        """Return value for key, or None if not found or deleted."""
        pass

    def delete(self, key: bytes) -> bool:
        """Append tombstone and remove key from index. Return True if existed."""
        pass

    def recover(self) -> None:
        """Scan log, validate records, truncate corrupted tail, and rebuild index."""
        pass

    def close(self) -> None:
        """Flush buffers and close underlying file descriptors."""
        pass

Example

store = LogKV("data.db")
store.put(b"user:101", b"Alice")
store.put(b"user:102", b"Bob")
assert store.get(b"user:101") == b"Alice"

store.delete(b"user:101")
assert store.get(b"user:101") is None

store.close()

# Simulate crash recovery on reopen
reopened_store = LogKV("data.db")
assert reopened_store.get(b"user:101") is None
assert reopened_store.get(b"user:102") == b"Bob"

Constraints & Edge Cases

• 1 <= len(key) <= 65,536 bytes.
• 0 <= len(value) <= 10,485,760 (10 MB) bytes.
• Recovery must handle torn writes (e.g., partial header, header present but payload truncated, or CRC mismatch due to corrupted bits). Once an invalid record is encountered, the log must be truncated at that exact record boundary, discarding all subsequent bytes.
• Handle empty log files gracefully.
• Deleting a non-existent key must return False without writing an unnecessary tombstone.