Single-Machine Cache with WAL Persistence, Sharded Locks and LRU

A web service handles requests and needs a cache. Design a single-machine cache and write pseudocode for it. An in-memory map is enough for storage; if the cache must be persistent, use a write-ahead log (WAL). You will also be asked how to scale it on one machine and which eviction policy to use, and you will be questioned in detail on how to optimize its locking. ### Clarifying Questions - Which operations are needed: only `get`, `put` and `delete`, or also multi-key or conditional operations? - Must a `put` be durable before it is acknowledged, or is losing the last few writes in a crash acceptable? - Is capacity bounded by entry count or by bytes, and how large are typical values? - What is the read/write ratio, and how skewed is key popularity? - Must a reader never see a value that could still be lost in a crash? ### Part 1 — Core cache and pseudocode Write pseudocode for thread-safe `get`, `put` and `delete` operations over an in-memory map with a capacity bound. ```hint Start simple, then earn complexity A single lock around a map is a legitimate baseline. Be explicit about what it serializes, because the later parts attack exactly that. ``` #### What This Part Should Cover - Data structures and the exact steps of each operation - Where the lock is taken and released - Behavior when the capacity bound is reached ### Part 2 — Persistence with a write-ahead log Make the cache survive a process restart by using a WAL. ```hint Order is the contract Decide what must reach the log before an operation is acknowledged, and what a restart replays. ``` #### What This Part Should Cover - WAL record contents, when records are written and synced, and when a write is acknowledged - Recovery by replay, plus checkpoints or compaction so the log does not grow forever - Keeping log order consistent with the order in which updates are applied in memory ### Part 3 — Scaling on one machine and fine-grained locking Scale the design to many concurrent requests. Use sharding to avoid lock contention, then keep going: can each critical section be made smaller? Walk through your own pseudocode and find every place where two threads could deadlock. ```hint Look inside the lock For each critical section, list which work actually needs mutual exclusion and which (hashing, serialization, disk I/O, waiting) could happen before or after it. ``` #### What This Part Should Cover - The sharding scheme, and how a key maps to a shard lock - Moving work out of critical sections, especially log syncs - Lock-ordering rules, and concrete deadlocks the design avoids ### Part 4 — Eviction Choose an eviction policy. You do not need to implement LRU, but explain how you would build it (a linked list plus a map) and how it interacts with sharding and locking. ```hint Reads become writes Consider what an LRU structure must do on every successful read, and what that implies for the lock a reader needs. ``` #### What This Part Should Cover - The LRU data structures and their O(1) operations - Why exact global LRU conflicts with sharding and read concurrency, and which approximations are acceptable - How evictions interact with the WAL ### What a Strong Answer Covers - Correct pseudocode before any optimization, followed by deliberate refinements - A clear durability contract and a WAL design that matches it - Shard-level concurrency with minimal critical sections and no I/O under hot locks - An explicit lock hierarchy, and the ability to spot deadlocks by reading code - Eviction that works per shard without a global bottleneck ### Follow-up Questions - How would you add per-entry TTL expiry without a background thread scanning everything? - A single key is extremely hot. What does sharding do for it, and what else could help? - How would you take a consistent snapshot for compaction while writes continue?