Katkat
Back

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

DatabricksSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

Design and write pseudocode for a single-machine in-memory cache behind a web service, then add write-ahead-log persistence, shard it to cut lock contention, shrink critical sections, find deadlocks by inspection, and explain LRU eviction built from a linked list and a hash map.

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.

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.

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.

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.

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

Hints

Hint 1

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.

Hint 2

Order is the contract: Decide what must reach the log before an operation is acknowledged, and what a restart replays.

Hint 3

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.

Hint 4

Reads become writes: Consider what an LRU structure must do on every successful read, and what that implies for the lock a reader needs.

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?