In-Memory Cache with WAL

Design an in-memory key-value cache that supports fast reads and writes, bounded size, LRU eviction, and crash recovery. The cache must provide get(key) and put(key, value) operations with O(1) average latency under high concurrency. To survive process crashes, every mutating operation must first be recorded in a Write-Ahead Log (WAL) file on local disk before it is applied to the in-memory map. On restart the WAL is replayed to reconstruct the exact cache state. To prevent unbounded WAL growth, implement periodic checkpointing: snapshot the entire in-memory map to disk, then truncate the WAL up to that snapshot’s sequence number. During recovery load the latest snapshot and replay only the subsequent WAL entries. Support concurrent clients by using fine-grained locking: partition the hash table into hundreds of segments each with its own read-write lock and manage the LRU list with a separate lock or a lock-free scheme. Target a single-node deployment handling 1 M ops/s with < 5 ms p99 latency on commodity SSDs.