Problem Overview

You are building a persistent key-value storage system for a distributed data platform. The system must survive crashes and restarts while handling concurrent access from multiple threads. This is critical infrastructure that powers data pipelines and analytics workloads.

The key challenges are:

• Durability: All writes must survive crashes using Write-Ahead Logging (WAL)

• Concurrency: Multiple threads reading and writing simultaneously

• Recovery: Fast restart after crashes by replaying WAL entries

• Performance: Minimize lock contention for high-throughput workloads

Architecture Overview

` ┌─────────────────────────────────────────┐ │ DurableKVStore │ ├─────────────────────────────────────────┤ │ In-Memory Map (HashMap) │ │ + ReadWriteLock │ └──────────┬─────────────────┬────────────┘ │ │ ┌──────▼──────┐ ┌─────▼──────────┐ │ WAL File │ │ Snapshot File │ │ (append) │ │ (periodic) │ └─────────────┘ └────────────────┘

Write Path: WAL → flush → Memory Recovery: Snapshot → WAL replay → Memory `

Requirements

• Durability: All writes must survive crashes (WAL before memory update)

• Thread Safety: Support concurrent reads and writes with fine-grained locking

• Crash Recovery: Recover from snapshot + WAL replay after crash

• Performance: Optimize for read-heavy workloads using ReadWriteLock

The critical insight: Write to WAL before updating memory.

` def put(self, key: str, value: str): # Step 1: Write to WAL FIRST (durability) self.wal_lock.acquire() try: self.wal_file.write(f"PUT|{timestamp}|{key}|{value}\n") self.wal_file.flush() # Force to disk finally: self.wal_lock.release()

# Step 2: Update in-memory map (visibility)
self.store_lock.acquire_write()
try:
    self.store[key] = value
finally:
    self.store_lock.release_write()

` Why this ordering matters:

• If crash happens between WAL write and memory update: safe (replay restores data)

• If crash happens before WAL write: safe (write never promised durability)

• Never update memory before WAL - would violate durability guarantee

Hint: Separate Locks for PerformanceUse separate locks for WAL and in-memory store to maximize concurrency:

` self.store = {} # In-memory storage self.store_lock = ReadWriteLock() # Multiple readers OR single writer self.wal_lock = Lock() # Serializes WAL writes only

Read path (high concurrency)

def get(self, key: str): self.store_lock.acquire_read() try: return self.store.get(key) finally: self.store_lock.release_read() ` Benefits:

• Multiple concurrent readers (ReadWriteLock)

• Writes don't block reads (separate locks)

• 10x+ performance improvement for read-heavy workloads

Hint: File FormatsWAL Format:

PUT|timestamp|key|value DELETE|timestamp|key Snapshot Format:

SNAPSHOT|timestamp key1|value1 key2|value2 During recovery:

• Load snapshot (if exists)

• Replay WAL entries with timestamp > snapshot timestamp

• This gives you the complete state

• get(key): O(1) average

• put(key, value): O(1) average + disk I/O

• delete(key): O(1) average + disk I/O

• create_snapshot(): O(N) where N is number of keys

• Recovery: O(N + W) where W is WAL entries

Space complexity: O(N) for in-memory storage plus O(W) for WAL

• WAL-first ordering ensures durability

• ReadWriteLock allows multiple concurrent readers (9.5x improvement for read-heavy workloads)

• Separate locks prevent WAL writes from blocking reads

• Timestamp filtering during recovery avoids replaying already-snapshotted entries