Design: Scale a Single-Node LRU Cache to a Distributed Cache

Assume you are upgrading a single-node, in-memory LRU cache to a distributed cache to support high read throughput (10^5–10^6 QPS), moderate writes, millions of keys, and sub-millisecond p50 latency within a single region. Keys and values are arbitrary byte strings; items have TTLs and are evicted by LRU when memory is full. Availability target is 99.9%+.

Design the system and address the following:

1. Sharding

• Describe how to shard keys across nodes using consistent hashing with virtual nodes (vnodes). Include how you map a key to its primary node and to replicas, and how you handle weighted nodes.

2. Rebalancing

• Explain what happens during node joins and leaves (graceful and failures). Include data movement, ownership changes, and how to rate-limit rebalancing to protect tail latency.

3. Hot Keys

• Propose techniques to mitigate hot keys and stampedes (e.g., heavy hitters, thundering herds).

4. Replication

• Specify replication factor, placement, write propagation (sync/async), conflict resolution/versioning, and replica read preferences.

5. Failure Detection

• Describe how nodes detect membership changes (e.g., gossip, heartbeats, thresholds) and how that integrates with routing.

6. Request Routing

• Compare client-side routing vs proxy/sidecar. Explain how a client locates the right node(s) and handles failures/blacklisting.

7. Read/Write Paths

• Provide read and write flows for: cache hit, miss + fill, and write-through/write-back/write-around policies.

8. Consistency & Invalidation

• Discuss TTL handling (soft/hard TTL), write-through/back, cache invalidations (push vs pull), and dogpile prevention.

9. Fault Tolerance & Partitions

• Explain behavior under node failures and network partitions. State the consistency-availability trade-offs you choose and why.

10. Monitoring & Capacity Planning

• List the key metrics, SLOs, and an approach to plan capacity (memory, network, QPS). Include simple sizing formulas.

11. Trade-offs & Performance

• Summarize trade-offs among consistency, availability, latency, and cost. Provide expected latency/throughput numbers and rebalancing cost at scale.