Objective
Design and implement an efficient and fault-tolerant key-value store in Rust that persists data to disk using append-only log containers , maintains an in-memory index for fast lookups, supports crash recovery , and guarantees atomic updates . Bonus: implement log compaction .
Part 1: Core File-Based Storage
Implement a key-value store API with:
All write operations ( set and delete ) must be appended to a log container file .
Maintain an in-memory index mapping keys to their file offsets for efficient reads.
On startup, reconstruct the in-memory index by replaying the log file .
Ensure proper handling of file errors and edge cases.
Correctness of read and write operations.
Proper log replay and recovery.
Efficient file handling and memory usage.
Part 2: Atomic Writes and Crash Consistency
Ensure that every log write is atomic : either fully written or not written at all.
Implement crash recovery to detect and discard partial or invalid writes at the end of the log.
Flush writes to disk to guarantee durability.
Demonstrate a strategy for atomic append writes.
Ensure the solution works correctly under simulated crashes (e.g., manually interrupting writes).
Understanding of atomicity and durability in file systems.
Correct handling of partial or corrupted log entries .
Robustness of recovery logic.
Part 3: Concurrency and Thread Safety
Extend the key-value store to be safe for multi-threaded access .
Ensure concurrent reads and writes do not corrupt the log or in-memory index.
Implement safe and correct locking mechanisms.
Avoid deadlocks and race conditions.
Demonstrate thread-safe reads and writes in a test scenario.
Correct use of Rust concurrency primitives.
Thread-safe file access and index updates.
Efficiency under concurrent access.
Part 4: Log Compaction (Optional / Bonus)
Implement a compaction process to reduce log size:
Only retain the latest value for each key.
Discard deleted keys.
Ensure no data is lost during compaction.
Demonstrate that atomic replacement prevents partial compaction from corrupting the store.
Correctness of compaction logic.
Atomic replacement strategy.
Performance and durability considerations.
Discussion / Design Questions
How would you handle very large logs or values efficiently?
How could this system be extended to support secondary indexes ?
What strategies would you use to optimize recovery time for extremely large logs?