Design a Distributed LRU Cache

Problem and Scope

Design a distributed Least-Recently-Used cache that supports low-latency reads and writes across multiple cache servers while preserving clearly defined eviction semantics through scaling and failures.

Start by confirming the core user journey, exclusions, success criteria, and the constraints that materially affect the architecture.

Requirements to Clarify

A strong answer should establish scope before choosing components.

Functional requirements:

• PUT(key, value): insert/update an item.
• GET(key): retrieve an item; moves item to MRU.
• DELETE(key): optional remove.
• Eviction: global LRU per shard with capacity limits.

Non-functional requirements:

• High availability and low latency (ms).
• Horizontal scalability (add/remove nodes with minimal disruption).
• Configurable consistency (strong vs eventual trade-offs).
• Monitoring and operational observability.
• Cache capacity per node is bounded.
• Network partitions and node failures must be handled gracefully.
• Acceptable to return slightly stale reads in return for availability unless strict consistency is requested.

Scale and Capacity

Use the workload to justify storage, partitioning, caching, and reliability decisions. Clarify or challenge these assumptions rather than treating them as unquestionable facts:

• Sustain roughly 50,000 reads and 5,000 writes per second before peak headroom
• Maintain about 200 million hot keys with an average value size near 5 KB, or roughly 1 TB before metadata and replication
• A 64 GB node holds roughly 10-12 million 5 KB values after reserving memory for metadata and fragmentation
• Capacity planning must include replication, failover headroom, hot-key skew, and rebalancing traffic

Architecture Discussion

Walk through the important read and write paths, identify ownership boundaries, and explain how the design behaves when dependencies fail. Cover these areas explicitly:

• Precise GET, PUT, DELETE, TTL, and eviction semantics
• O(1) local LRU data structures and thread-safe mutation
• Client-side or proxy routing with consistent hashing and bounded remapping
• Per-shard versus global eviction semantics and their feasibility
• Replication, consistency, failover, and recovery of cache state
• Hot-key mitigation, admission control, memory accounting, and observability

Follow-up Questions

Expect the interviewer to test the consequences of your choices. Practise answering these questions with a concrete decision, its benefit, and its cost:

• Is the cache read-heavy or write-heavy? (Typical caches are read-heavy.)
  • Focus: Assess the candidate's answer to "Is the cache read-heavy or write-heavy? (Typical caches are read-heavy.)" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Are keys fixed-size strings/IDs and are values blobs with size limits?
  • Focus: Assess the candidate's answer to "Are keys fixed-size strings/IDs and are values blobs with size limits" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Should the cache provide strong consistency, read-your-writes, or eventual consistency?
  • Focus: Assess the candidate's answer to "Should the cache provide strong consistency, read-your-writes, or eventual consistency" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Expected QPS, number of unique keys, and average object size (to estimate capacity)?
  • Focus: Assess the candidate's answer to "Expected QPS, number of unique keys, and average object size (to estimate capacity)" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Multi-region availability requirements and acceptable staleness on failover?
  • Focus: Assess the candidate's answer to "Multi-region availability requirements and acceptable staleness on failover" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Do we need TTLs, eviction metrics, or transactionality across multiple keys?
  • Focus: Assess the candidate's answer to "Do we need TTLs, eviction metrics, or transactionality across multiple keys" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Provide TTL-based expiry alongside LRU and combined eviction policies.
  • Focus: Assess the candidate's answer to "Provide TTL-based expiry alongside LRU and combined eviction policies." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Support multi-key atomic operations (compare-and-swap, transactions) and implications for consistency.
  • Focus: Assess the candidate's answer to "Support multi-key atomic operations (compare-and-swap, transactions) and implications for consistency." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Hot-key mitigation strategies (client-side sharding, request batching, or adaptive replication).
  • Focus: Assess the candidate's answer to "Hot-key mitigation strategies (client-side sharding, request batching, or adaptive replication)." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Integrate with CDN or edge caches for geo-distribution.
  • Focus: Assess the candidate's answer to "Integrate with CDN or edge caches for geo-distribution." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Cache invalidation strategies for updates in the origin datastore.
  • Focus: Assess the candidate's answer to "Cache invalidation strategies for updates in the origin datastore." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Advanced routing: client-side consistent hashing vs centralized proxying and pros/cons.
  • Focus: Assess the candidate's answer to "Advanced routing: client-side consistent hashing vs centralized proxying and pros/cons." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Security: authentication, encryption in transit, and multi-tenant isolation.
  • Focus: Assess the candidate's answer to "Security: authentication, encryption in transit, and multi-tenant isolation." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.

Evaluation Rubric

MockMe evaluates the answer across the following dimensions. A complete answer should connect claims to requirements and explain consequential trade-offs.

• Requirements and scope (15%): Clarifies and prioritizes the required behavior for PUT(key, value): insert/update an item; GET(key): retrieve an item; moves item to MRU; DELETE(key): optional remove. Establishes the constraints that materially affect Design a Distributed LRU Cache, including High availability and low latency (ms); Horizontal scalability (add/remove nodes with minimal disruption). Strong evidence includes Separates the critical path from secondary features and resolves ambiguous requirements before choosing components.
• Architecture and interfaces (20%): Presents coherent ownership boundaries and end-to-end flows covering Precise GET, PUT, DELETE, TTL, and eviction semantics; O(1) local LRU data structures and thread-safe mutation; Client-side or proxy routing with consistent hashing and bounded remapping; Per-shard versus global eviction semantics and their feasibility. Strong evidence includes Defines interfaces and traces important success, retry, and failure paths across the proposed components.
• Data and scaling (25%): Uses workload assumptions such as Sustain roughly 50,000 reads and 5,000 writes per second before peak headroom; Maintain about 200 million hot keys with an average value size near 5 KB, or roughly 1 TB before metadata and replication to justify capacity and partitioning decisions. Explains the data, state, or model strategy for O(1) local LRU data structures and thread-safe mutation; Per-shard versus global eviction semantics and their feasibility; Replication, consistency, failover, and recovery of cache state. Strong evidence includes Quantifies a dominant workload, identifies the first bottleneck, and explains how the design evolves as that workload grows.
• Reliability, correctness, and safety (20%): Explains concrete failure behavior, recovery, and operational safeguards for Client-side or proxy routing with consistent hashing and bounded remapping; Replication, consistency, failover, and recovery of cache state; High availability and low latency (ms). Strong evidence includes States the required correctness or consistency boundary and covers retries, partial failure, observability, and safe degradation.
• Communication and trade-offs (20%): Drives a structured discussion and compares consequential alternatives for Per-shard versus global eviction semantics and their feasibility; Replication, consistency, failover, and recovery of cache state; Hot-key mitigation, admission control, memory accounting, and observability. Strong evidence includes Makes assumptions explicit, answers the question asked, and explains both the benefit and cost of major decisions.