Bird
Raised Fist0

Design a Distributed Cache - Consistent Hashing, Eviction, Replication

HLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Design a Distributed Cache with Consistent Hashing, Eviction, and Replication
45 min · senior
senior

You are designing a distributed caching layer for a startup with 50 million daily active users (DAU). The cache must serve low-latency reads and writes with P99 latency under 200ms. Data must be encrypted both at rest and in transit due to compliance requirements. The cache should scale horizontally, handle node failures gracefully, and support configurable eviction policies to manage memory. Replication is required to ensure availability and durability. The system will be used as a front layer for a high-throughput backend database.

Constraints
  • Support 50M DAU with peak QPS of 1M requests/sec
  • P99 latency under 200ms for reads and writes
  • Data encryption at rest and in transit (TLS + disk encryption)
  • Configurable eviction policies (LRU, LFU) per cache node
  • Replication factor of 3 for fault tolerance
  • Strong consistency for critical keys, eventual consistency acceptable for others
📋
Guided Steps
1/5
Step 1
Key Distribution and Node Scalability
How will you distribute keys across cache nodes to ensure even load and easy scaling?
💡 Hint
Consider consistent hashing to minimize key remapping when nodes join or leave.
Key Decision
Use consistent hashing with a ring-based algorithm and virtual nodes to evenly distribute keys across Redis Cluster nodes, minimizing key remapping during scaling events.
Interviewer Expectation
Mid-level: Names consistent hashing and Redis Cluster. Senior: Explains virtual nodes reduce load imbalance and how consistent hashing avoids full key redistribution on node changes.
⚠️Common Wrong Answer
Using modulo-based key partitioning - causes massive cache invalidation and data reshuffling on node addition/removal, leading to high latency spikes.
Step 2
Eviction Policy Implementation
How will you implement eviction policies to manage memory usage on each cache node?
💡 Hint
Explore Redis eviction modes and how to support configurable policies per node.
Key Decision
Leverage Redis's built-in eviction policies (volatile-lru, allkeys-lfu) configurable per node, enabling dynamic memory management based on workload characteristics.
Interviewer Expectation
Mid-level: Mentions Redis eviction policies. Senior: Details trade-offs between LRU and LFU, how eviction impacts cache hit ratio, and how to tune policies per workload.
⚠️Common Wrong Answer
Implementing eviction at the client side - leads to inconsistent cache states and increased complexity, causing stale data and cache pollution.
Step 3
Replication and Fault Tolerance
How will you replicate cache data to ensure availability and durability in case of node failures?
💡 Hint
Consider Redis Sentinel or Redis Cluster replication with quorum-based failover.
Key Decision
Use Redis Cluster with asynchronous replication and Redis Sentinel for monitoring and automatic failover, maintaining a replication factor of 3 to ensure availability and durability.
Interviewer Expectation
Mid-level: Names Redis Sentinel and replication. Senior: Explains asynchronous replication trade-offs, failover detection latency, and how quorum-based election prevents split-brain.
⚠️Common Wrong Answer
Synchronous replication on every write - severely increases write latency beyond 200ms P99, reducing throughput.
Step 4
Data Encryption and Security
How will you ensure data encryption at rest and in transit for compliance requirements?
💡 Hint
Look into TLS for network encryption and disk encryption options for Redis nodes.
Key Decision
Enable TLS encryption for all client-server and inter-node communication using Redis TLS support, and use OS-level disk encryption (e.g., LUKS) on cache nodes for data at rest.
Interviewer Expectation
Mid-level: Mentions TLS and disk encryption. Senior: Details key management, certificate rotation, and performance impact mitigation strategies.
⚠️Common Wrong Answer
Relying only on network perimeter security - exposes data to insider threats and violates compliance.
Step 5
Consistency Model and Cache Coherency
How will you handle consistency guarantees and cache invalidation to avoid stale reads?
💡 Hint
Consider strong consistency for critical keys and eventual consistency for others, with cache invalidation or write-through strategies.
Key Decision
Implement a hybrid consistency model: use Redis write-through caching for critical keys with synchronous backend writes, and asynchronous replication with TTL-based eviction for less critical data to balance latency and consistency.
Interviewer Expectation
Mid-level: Describes write-through caching. Senior: Explains trade-offs between write-through and write-back, how to handle race conditions, and cache stampede prevention.
⚠️Common Wrong Answer
Using only eventual consistency without invalidation - leads to stale data and inconsistent application behavior.
🔌
API Design Challenge
Sketch 3 core API endpoints for the distributed cache system that clients will use.
Hints
  • How does the client write data to the cache and specify TTL or eviction hints?
  • How does the client read data and handle cache misses or stale data?
  • How does the client acknowledge or invalidate cache entries after updates?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Consistent hashing with virtual nodes for key distribution
  • Configurable eviction policies implemented per cache node
  • Replication with automatic failover to ensure availability
  • Encryption at rest and in transit for compliance
  • API design covering core cache operations
Good to Have - 30%
  • Hybrid consistency model balancing latency and correctness
  • Monitoring and alerting for operational visibility
  • Seamless scaling with slot migration and resharding
Bonus - 10%
  • Cache stampede prevention techniques
  • Dynamic eviction policy tuning based on workload
Anti-patterns to Avoid
Modulo-based key partitioning causing massive cache invalidation on node changes, leading to high latency spikes and degraded user experience
Client-side eviction causing inconsistent cache states and stale data, increasing complexity and reducing cache effectiveness
Synchronous replication on every write increasing write latency beyond SLA, severely impacting throughput and user latency
Relying solely on network perimeter security exposes data to insider threats and violates compliance requirements, risking data breaches
✅
Model Answer
▼ Reveal

This design uses Redis Cluster with consistent hashing and virtual nodes for even key distribution and easy scaling. Each cache node uses configurable eviction policies like volatile-lru or allkeys-lfu to manage memory efficiently. Replication is handled asynchronously with Redis Sentinel monitoring and automatic failover, maintaining a replication factor of 3 for fault tolerance. TLS encrypts all network traffic, and OS-level disk encryption secures data at rest. A hybrid consistency model balances strong consistency for critical keys with eventual consistency for others. The API exposes Set, Get, and Invalidate endpoints to clients. Monitoring with Prometheus and Grafana ensures operational visibility, and Redis Cluster's slot migration supports seamless scaling.

Key Decisions
  • Use Redis Cluster's ring-based consistent hashing with virtual nodes to minimize key remapping during scaling
  • Configure eviction policies per node using Redis's volatile-lru and allkeys-lfu modes to optimize memory usage
  • Implement asynchronous replication with Redis Sentinel for automatic failover and maintain replication factor of 3
  • Enable TLS for all client-server and inter-node communication and use OS-level disk encryption for data at rest
  • Adopt a hybrid consistency model with write-through caching for critical keys and TTL-based eviction for others
  • Design API with Set(key, value, ttl) to write data with TTL, Get(key) to read data handling cache misses, and Invalidate(key) to maintain cache coherency
  • Consistent hashing with virtual nodes implemented via Redis Cluster to evenly distribute keys and minimize remapping on scaling
  • Redis eviction policies (volatile-lru, allkeys-lfu) configured per node to optimize memory usage and cache hit ratio
  • Redis asynchronous replication with Sentinel for automatic failover and maintaining replication factor of 3 for fault tolerance
  • TLS encryption enabled for all client and inter-node communication, combined with OS-level disk encryption (e.g., LUKS) for data at rest
  • Hybrid consistency model using write-through caching for critical keys and TTL-based eviction for less critical data to balance latency and consistency
  • API design includes Set(key, value, ttl), Get(key), and Invalidate(key) endpoints to support client cache operations and coherency
  • Monitoring and alerting integrated with Prometheus and Grafana to track cache hit ratio, latency, and node health
  • Use of Redis Cluster's slot migration and resharding tools to support seamless scaling and maintenance

Practice

(1/5)
1. In the request flow, at Step 4 the load balancer's health check worker receives no response from a backend server. What state does the health check worker mark for that server at this step?
easy
A. Server marked as healthy but with increased latency metric
B. Server marked as unhealthy and removed from active pool
C. Server marked as temporarily overloaded but still active
D. Server marked as unknown and kept in rotation until next check

Solution

  1. Step 1: Trace health check worker behavior at Step 4

    When no response is received, the server is marked unhealthy to prevent routing traffic to it.

  2. Step 2: Exclude other states

    Latency increase implies response received; overloaded means server responded; unknown state would not remove server immediately.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    No response -> mark server unhealthy and remove [check]
Hint: No response means unhealthy, remove from pool immediately [check]
Common Mistakes:
2. In the SLO error budget tracking system, at step 4 the Error Budget Calculator receives aggregated error counts and total request counts. What state does it maintain immediately after processing these inputs?
easy
A. It resets the error budget to full capacity regardless of recent errors
B. It discards error counts if the total request count is below a threshold
C. It queues the error counts for asynchronous processing by the alerting system
D. It updates the current error budget remaining by subtracting recent error rate from total budget

Solution

  1. Step 1: Understand the role of the Error Budget Calculator at step 4

    It updates the remaining error budget by subtracting the recent error rate from the total allowed errors, reflecting current SLO compliance.

  2. Step 2: Exclude other states that contradict error budget tracking logic

    Resetting the budget ignores recent errors; queuing is done later by alerting; discarding counts would lose accuracy.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Error Budget Calculator updates remaining budget after aggregation [check]
Hint: Error budget updates subtract recent errors, not reset or discard [OK]
Common Mistakes:
3. If the quorum coordinator fails immediately after receiving write acknowledgments from a majority but before sending success to the client, what is the exact failure mode observed by the client?
medium
A. Client experiences a timeout and retries, risking duplicate writes
B. Client blocks indefinitely waiting for acknowledgment
C. Client receives duplicate success acknowledgments causing confusion
D. Client receives failure response despite successful write

Solution

  1. Step 1: Trace quorum coordinator failure after majority ack

    Coordinator crashes before responding, client waits but eventually times out.

  2. Step 2: Client retries write causing potential duplicates

    Client retries due to timeout; duplicates possible if write was committed.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Timeout triggers retry risking duplicate writes [check]
Hint: Coordinator crash before ack -> client timeout and retry risk [check]
Common Mistakes:
4. At 10x current scale, which component is most likely to fail first in Instagram's real-time feed delivery, and why?
hard
A. The relational database storing user profiles, due to increased read/write contention
B. The feed cache layer, because cache invalidation traffic grows exponentially with user base
C. The WebSocket servers handling live feed updates, due to stateful connections limiting horizontal scaling
D. The photo storage service, because object storage bandwidth saturates under heavy upload load

Solution

  1. Step 1: Identify stateful components limiting scale

    WebSocket servers maintain persistent connections per user, which are stateful and bound to server memory.

  2. Step 2: Analyze scaling challenges

    At 10x scale, adding servers doesn't migrate existing WebSocket connections, causing uneven load and resource exhaustion. Relational DB (A) can be sharded, cache (B) can be scaled with TTL tuning, storage (D) scales with cloud object storage.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Stateful WebSocket connections limit horizontal scaling [check]
Hint: Stateful WebSocket servers bottleneck horizontal scaling [check]
Common Mistakes:
5. At 10x scale, which component in a Redis-based centralized rate limiter is most likely to fail first and why?
hard
A. Network bandwidth, because of increased data transfer between servers
B. API servers, because they cannot handle increased request volume
C. Redis server, due to single-threaded command processing becoming a bottleneck
D. Client applications, due to increased latency causing timeouts

Solution

  1. Step 1: Identify Redis command processing model

    Redis processes commands single-threaded, limiting throughput regardless of hardware.

  2. Step 2: Analyze scaling impact

    At 10x scale, Redis becomes the bottleneck as it cannot process atomic increments fast enough.

  3. Step 3: Evaluate other components

    API servers can be scaled horizontally; network and clients are less likely to fail first.

  4. Final Answer:

    Option C -> Option C

  5. Quick Check:

    Redis single-threaded processing limits throughput at high scale [check]
Hint: Redis single-threaded limits throughput at scale [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard