Bird
Raised Fist0

Distributed Cache Design - Consistent Hashing for Cache Node Assignment

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Distributed Cache Design - Consistent Hashing for Cache Node Assignment
45 min · senior
senior

You are designing a distributed caching layer for a startup with 50 million daily active users (DAU). The cache must support low-latency reads and writes with a P99 latency under 200ms. The system must handle dynamic cache node membership (nodes joining/leaving) without significant cache misses or hotspots. Data encryption at rest and in transit is mandatory due to compliance requirements. The cache should support offline delivery of data updates to clients when they reconnect. The system must scale horizontally to handle peak loads of up to 1 million requests per second.

Constraints
  • P99 latency under 200ms for cache operations
  • Encryption required for data at rest and in transit
  • Support dynamic cache node membership with minimal cache misses
  • Offline delivery of cache updates to clients on reconnect
  • Scale to 1 million requests per second peak load
📋
Guided Steps
1/5
Step 1
Choosing the Cache Node Assignment Strategy
How would you assign keys to cache nodes to ensure even load distribution and minimal cache misses during node membership changes?
💡 Hint
Consider a hashing technique that minimizes key remapping when nodes join or leave.
Key Decision
Use consistent hashing with virtual nodes implemented via Ketama hashing algorithm to assign keys to Redis cluster nodes, minimizing key remapping and hotspots during node membership changes.
Interviewer Expectation
Mid-level: Names consistent hashing for load distribution. Senior: Explains virtual nodes in consistent hashing reduce uneven load and key remapping during node churn.
⚠️Common Wrong Answer
Using modulo-based hashing on node count - causes massive cache misses and rebalancing on node changes, leading to high latency spikes.
Step 2
Handling Cache Node Failures and Data Replication
How will you ensure cache availability and data durability when cache nodes fail or restart?
💡 Hint
Think about replication strategies and failover mechanisms in distributed caches like Redis.
Key Decision
Use Redis Cluster with asynchronous replication and Redis Sentinel for automatic failover, ensuring availability and eventual consistency without blocking writes.
Interviewer Expectation
Mid-level: Mentions Redis replication or Sentinel. Senior: Details async replication trade-offs, failover detection latency, and impact on P99 latency under failover.
⚠️Common Wrong Answer
Relying on single Redis instance per node without replication - leads to data loss and cache unavailability during node failures.
Step 3
Ensuring Data Encryption at Rest and In Transit
How will you implement encryption to meet compliance requirements for data at rest and in transit in the cache system?
💡 Hint
Consider TLS for network encryption and disk encryption or encrypted memory for stored data.
Key Decision
Enable TLS 1.3 for all Redis client-server and inter-node communication, and use OS-level disk encryption (e.g., LUKS) on cache nodes to secure data at rest.
Interviewer Expectation
Mid-level: Mentions TLS for in-transit encryption. Senior: Explains TLS version choice, key rotation, and OS-level disk encryption trade-offs for performance and compliance.
⚠️Common Wrong Answer
Encrypting only in transit but not at rest - violates compliance and risks data exposure on node compromise.
Step 4
Supporting Offline Delivery and Client Synchronization
How will clients synchronize cache updates after being offline, ensuring they receive missed updates efficiently?
💡 Hint
Think about versioning, update logs, or message queues to track changes for offline clients.
Key Decision
Maintain a Kafka topic per cache key prefix with update events; clients consume from their last committed offset to sync missed updates upon reconnect.
Interviewer Expectation
Mid-level: Suggests client polling or full cache reload. Senior: Explains Kafka partitioning by key prefix for ordered updates and offset management for efficient offline sync.
⚠️Common Wrong Answer
Clients reload entire cache on reconnect - causes high load and latency spikes, violating P99 latency SLA.
Step 5
API Design for Cache Operations and Offline Sync
Design 3 core API endpoints that clients will use to interact with the distributed cache and support offline delivery.
💡 Hint
Consider endpoints for write/update, sync after offline, and acknowledgement of updates.
Key Decision
Define POST /cache/write for writes, GET /cache/sync?since=offset for incremental sync, and POST /cache/ack for clients to acknowledge received updates, enabling efficient state management.
Interviewer Expectation
Mid-level: Names basic CRUD endpoints. Senior: Explains incremental sync with offsets and acknowledgements to avoid redundant data transfer and ensure consistency.
⚠️Common Wrong Answer
Only providing basic get/set endpoints without sync or ack - leads to inefficient offline recovery and inconsistent cache state.
🔌
API Design Challenge
Sketch 3 core API endpoints for the distributed cache system that support client cache operations and offline delivery.
Hints
  • How does the client send cache write/update requests?
  • How does the client synchronize cache state after offline periods?
  • How does the client acknowledge receipt of cache updates?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Consistent hashing with virtual nodes to minimize cache misses during node changes
  • Replication and failover strategy using Redis Cluster and Sentinel
  • Encryption in transit (TLS) and at rest (disk encryption) for compliance
  • Offline delivery support via Kafka-based update logs and client offset tracking
  • API design supporting incremental sync and acknowledgements
Good to Have - 30%
  • Use of Redis TTL and heartbeats for node liveness detection
  • Monitoring with Prometheus and Grafana for latency and health metrics
  • Discussion of trade-offs between synchronous vs asynchronous replication
  • Consideration of cache warming strategies after node addition
Bonus - 10%
  • Advanced failure mode analysis with step-by-step failure tracing
  • Use of client-side caching and local fallback strategies
  • Integration with service mesh for secure inter-node communication
Anti-patterns to Avoid
Modulo hashing on node count causing massive cache misses and hotspots during node churn, leading to high latency spikes and cache instability
Single Redis instance without replication leading to data loss and downtime during node failures, causing cache unavailability
Encrypting only in transit but not at rest, violating compliance and risking data exposure on node compromise
Clients performing full cache reload on reconnect causing high load and latency spikes, violating P99 latency SLA and degrading user experience
✅
Model Answer
▼ Reveal

This design uses consistent hashing with virtual nodes (Ketama) to assign keys evenly across Redis cluster nodes, minimizing remapping during node changes. Redis Cluster with asynchronous replication and Sentinel ensures high availability and durability. TLS 1.3 secures data in transit, while OS-level disk encryption protects data at rest. Kafka topics partitioned by cache key prefix track update events, enabling clients to synchronize missed updates efficiently after offline periods. The API supports incremental sync and acknowledgements to optimize data transfer and consistency.

Key Decisions
  • Use Ketama consistent hashing with virtual nodes to minimize cache misses during node membership changes
  • Implement Redis Cluster with asynchronous replication and Sentinel for failover to maintain availability and eventual consistency
  • Enable TLS 1.3 for all client-server and inter-node communication to meet compliance and security requirements
  • Apply OS-level disk encryption (e.g., LUKS) on cache nodes to secure data at rest
  • Use Kafka topics partitioned by cache key prefix to track cache update events, allowing clients to consume missed updates efficiently
  • Design client APIs to support incremental synchronization using offsets and acknowledgements to reduce redundant data transfer and ensure cache consistency
  • Consistent hashing with virtual nodes (Ketama) for balanced key distribution and minimal remapping
  • Redis Cluster with asynchronous replication and Sentinel for failover and high availability
  • TLS 1.3 enabled for all client-server and inter-node communication to secure data in transit
  • OS-level disk encryption (e.g., LUKS) on cache nodes to secure data at rest
  • Kafka topics partitioned by cache key prefix to track update events for offline client synchronization
  • Client APIs supporting incremental sync via offsets and acknowledgements to minimize data transfer and ensure consistency
  • Use of Redis TTL and heartbeats to detect node liveness and trigger rebalancing
  • Monitoring and alerting integrated with Prometheus and Grafana to track latency and node health

Practice

(1/5)
1. A web application needs to ensure that cache entries are updated immediately after every write to the database to prevent stale reads. Which caching pattern best fits this requirement?
easy
A. Cache Aside, where the application updates the cache only on cache misses
B. Write-Through, where writes go through the cache and update the database synchronously
C. Read-Through, where the cache loads data on reads but writes bypass the cache
D. Write-Behind, where writes are buffered and asynchronously flushed to the database

Solution

  1. Step 1: Identify cache update timing

    Write-Through updates cache and database synchronously, ensuring cache is always fresh.

  2. Step 2: Eliminate other patterns

    Cache Aside updates cache only on misses, risking stale cache after writes; Read-Through only loads on reads; Write-Behind delays DB update, risking stale cache.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Write-Through synchronously updates cache and DB [check]
Hint: Write-Through syncs cache and DB on writes [check]
Common Mistakes:
2. In a code repository system, which component is best suited to efficiently store and retrieve file diffs to minimize storage space while allowing fast access for merges?
easy
A. Use a relational database with BLOB columns to store entire file versions
B. Use a distributed cache like Redis to store diffs temporarily for quick access
C. Use a content-addressable storage system that stores objects by hash and reuses identical content
D. Use a simple file system directory structure with full copies of each file version

Solution

  1. Step 1: Identify storage needs for diffs

    Storing diffs efficiently requires deduplication and immutability; content-addressable storage (CAS) stores objects by their hash, enabling reuse of identical content and saving space.

  2. Step 2: Evaluate other options

    Relational DB with BLOBs stores full versions, wasting space; Redis is volatile and not durable for persistent storage; file system copies waste space and slow for merges.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    CAS stores objects by hash -> deduplication and fast retrieval [check]
Hint: Content-addressable storage deduplicates by hash [check]
Common Mistakes:
3. A system must match riders with nearby drivers in under 2 seconds while handling millions of concurrent requests. Which component is best suited to efficiently index and query driver locations in real-time?
easy
A. An in-memory spatial index like an R-tree or geohash-based Redis module
B. A relational database with geospatial extensions for location queries
C. A distributed log system like Kafka to stream location updates
D. A batch processing system like Hadoop to periodically update driver locations

Solution

  1. Step 1: Identify location query requirements

    Real-time matching requires low-latency spatial queries on dynamic driver locations.

  2. Step 2: Evaluate component suitability

    Relational DBs (A) have high latency for frequent updates; Kafka (C) streams data but doesn't index locations; Hadoop (D) is batch-oriented and too slow. In-memory spatial indexes (B) provide fast nearest-neighbor queries and frequent updates.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    In-memory spatial index enables fast real-time location queries [check]
Hint: Real-time location needs fast spatial index, not batch or logs [check]
Common Mistakes:
4. A faceted search system must support sub-second response times for queries combining multiple filters on billions of documents. Which component is best suited to handle the inverted index lookups efficiently under this constraint?
easy
A. A key-value store like Redis storing precomputed filter results
B. A relational database with composite indexes on all filter fields
C. A distributed inverted index engine like Elasticsearch or Solr
D. A message queue system to asynchronously process filter queries

Solution

  1. Step 1: Identify the role of inverted index engine

    Distributed inverted index engines like Elasticsearch are optimized for multi-dimensional filtering and fast lookups on large datasets, supporting sub-second query latency.

  2. Step 2: Eliminate other options based on constraints

    Relational DBs with composite indexes do not scale well for high-cardinality multi-facet queries; Redis is fast but storing precomputed results for all filter combinations is infeasible; message queues are for async processing, not low-latency queries.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Distributed inverted index -> fast multi-facet filtering [check]
Hint: Inverted index engines excel at multi-filter fast lookups [check]
Common Mistakes:
5. In a rate-limited API request flow, at Step 4 the Rate Limiter component checks the client's request count against the quota. What happens if the quota is exceeded at this step?
easy
A. The request is immediately rejected with a 429 Too Many Requests response
B. The request is forwarded to backend but marked for delayed processing
C. The request is queued for later processing until quota resets
D. The request bypasses the limiter if the client has a valid API key

Solution

  1. Step 1: Understand Rate Limiter behavior at Step 4

    Rate limiter checks quota; if exceeded, it must prevent further load by rejecting requests immediately.

  2. Step 2: Eliminate incorrect behaviors

    Queuing (A) delays overload but doesn't prevent it; forwarding with delay (C) risks backend overload; bypassing (D) violates rate limiting rules.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Quota exceeded -> immediate 429 rejection [check]
Hint: Quota exceeded triggers immediate 429 rejection [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