Bird
Raised Fist0

Why Consistent Hashing and What Modular Hashing Cannot Handle

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Why Consistent Hashing and What Modular Hashing Cannot Handle
45 min · senior
senior

You are designing a distributed key-value storage system for a startup with 50 million daily active users (DAU). The system must handle dynamic scaling of storage nodes without significant data reshuffling, maintain low latency (P99 < 200ms), and ensure encrypted data storage and transmission. The system should also support offline data delivery to clients with intermittent connectivity.

Constraints
  • Support dynamic addition and removal of storage nodes with minimal data movement
  • Ensure end-to-end encryption for data at rest and in transit
  • Maintain P99 latency under 200ms for read/write operations
  • Support offline data delivery with eventual consistency
  • Handle 50 million DAU with expected peak QPS of 500K
  • Avoid hotspots and uneven load distribution across nodes
📋
Guided Steps
1/5
Step 1
Choosing the Hashing Strategy for Node Assignment
How would you assign keys to storage nodes to ensure minimal data movement when nodes are added or removed?
💡 Hint
Consider how modular hashing causes large-scale remapping of keys on node changes.
Key Decision
Use Consistent Hashing with a ring structure implemented via Ketama to map keys to nodes, minimizing key remapping on node changes.
Interviewer Expectation
Mid: Names consistent hashing with Ketama as a solution. Senior: Explains how modular hashing (key % N) causes O(N) remapping, while consistent hashing limits remapping to O(1/N) keys using Ketama's ring.
⚠️Common Wrong Answer
Using modular hashing (key % number_of_nodes) which causes massive data reshuffling and downtime during scaling.
Step 2
Handling Load Imbalance and Hotspots
How would you prevent uneven load distribution and hotspots in the consistent hashing ring?
💡 Hint
Think about virtual nodes or replicas to smooth out key distribution.
Key Decision
Implement virtual nodes (vnodes) per physical node in the Ketama consistent hashing ring to evenly distribute keys and balance load.
Interviewer Expectation
Mid: Mentions virtual nodes improve distribution. Senior: Quantifies vnode count impact on load balance and explains trade-offs in vnode count vs. metadata overhead.
⚠️Common Wrong Answer
Assigning one hash point per node, leading to uneven key distribution and hotspots.
Step 3
Ensuring Low Latency and Fault Tolerance
How would you design the system to maintain P99 latency < 200ms and tolerate node failures without client impact?
💡 Hint
Consider replication strategies and client-side routing awareness.
Key Decision
Use consistent hashing with replication factor of 3 and client-side routing logic to try alternate replicas on failure, leveraging gRPC for low-latency communication.
Interviewer Expectation
Mid: Describes replication for fault tolerance. Senior: Explains how consistent hashing ring locates replicas and how client retries reduce failover latency using gRPC.
⚠️Common Wrong Answer
Single replica per key causing data loss and high latency on node failure.
Step 4
Supporting Encrypted Data and Offline Delivery
How would you ensure data encryption at rest and in transit, and support offline data delivery with eventual consistency?
💡 Hint
Think about encryption libraries and client-side caching with sync protocols.
Key Decision
Use TLS for in-transit encryption, AES-256 for at-rest encryption on storage nodes, and implement client-side local cache with CRDTs or version vectors for offline sync.
Interviewer Expectation
Mid: Mentions TLS and AES-256 encryption at rest. Senior: Details encryption key management, zero-trust principles, and offline sync conflict resolution mechanisms using CRDTs or version vectors.
⚠️Common Wrong Answer
Ignoring encryption or offline sync, risking data breaches and poor user experience.
Step 5
API Design for Client Interaction
Design 3 core API endpoints that leverage consistent hashing for routing and support offline scenarios.
💡 Hint
Consider endpoints for write, read, and sync acknowledgments with routing info embedded.
Key Decision
Define APIs: (1) PUT /store/{key} with client-side consistent hashing (Ketama) to route to correct node, (2) GET /store/{key} for reads with fallback to replicas, (3) POST /sync/ack to confirm offline data sync and resolve conflicts using CRDTs.
Interviewer Expectation
Mid: Lists basic CRUD endpoints. Senior: Explains how client uses consistent hashing to route requests, handles retries, and sync acknowledgments for offline support.
⚠️Common Wrong Answer
Generic REST endpoints without routing logic, causing inefficient request handling and inconsistent data.
🔌
API Design Challenge
Sketch 3 core API endpoints for the distributed key-value store that leverage consistent hashing for routing requests.
Hints
  • How does the client determine which node to contact for a given key?
  • How does the system handle node addition/removal transparently to clients?
  • How does the client confirm successful writes and handle offline scenarios?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Explain why modular hashing fails at scale due to O(N) key remapping
  • Use consistent hashing with virtual nodes for balanced load
  • Replication and client-side routing for fault tolerance and latency
  • Encryption in transit and at rest with key management
  • API design that leverages consistent hashing for routing
Good to Have - 30%
  • Offline data delivery with conflict resolution using CRDTs or version vectors
  • Dynamic ring membership updates via gossip protocol
  • Use of gRPC or similar for low-latency communication
Bonus - 10%
  • Quantitative analysis of vnode count impact on load distribution
  • Detailed failure mode analysis of node removal and data reshuffling
  • Security considerations for encryption key rotation and zero-trust
Anti-patterns to Avoid
Modular hashing causing full data reshuffle on node changes, leading to downtime and service unavailability during scaling events
Single hash point per node causing load imbalance and hotspots, resulting in uneven resource utilization and potential node overload
No replication causing data loss and high latency on node failure, degrading system reliability and user experience
Ignoring encryption leading to data breaches and compliance violations, risking user trust and legal penalties
Stateless clients without routing logic causing inefficient request routing, increasing latency and load on the system
Polling-based offline sync causing excessive load and stale data, leading to poor scalability and user experience
✅
Model Answer
▼ Reveal

Consistent hashing with virtual nodes is essential to minimize data movement and balance load in a 50M DAU distributed key-value store. Modular hashing fails due to massive reshuffling on node changes. Replication and client-side routing ensure fault tolerance and low latency, while encryption and offline sync support meet security and availability constraints.

Key Decisions
  • Use Ketama consistent hashing ring with virtual nodes to minimize key remapping and balance load
  • Implement replication factor of 3 with client-side routing logic to handle failover and maintain P99 latency < 200ms
  • Encrypt data in transit using TLS and at rest using AES-256 with robust key management and zero-trust principles
  • Support offline data delivery with client-side caching and conflict resolution using CRDTs or version vectors
  • Design APIs (PUT /store/{key}, GET /store/{key}, POST /sync/ack) embedding consistent hashing routing and offline sync support
  • Use gRPC for communication to achieve low latency and efficient retries
  • Manage dynamic node membership and ring updates using a gossip protocol to ensure consistent routing information
  • Consistent Hashing (Ketama) to minimize key remapping on node changes
  • Virtual Nodes to evenly distribute load and prevent hotspots
  • Replication factor of 3 with client-side routing for fault tolerance and low latency
  • TLS for in-transit encryption and AES-256 for at-rest encryption on storage nodes
  • Client-side local cache with CRDTs or version vectors for offline data delivery and conflict resolution
  • gRPC for efficient, low-latency communication between clients and storage nodes
  • API design embedding consistent hashing logic for routing and offline sync support
  • Dynamic membership management with a gossip protocol to update consistent hashing ring state

Practice

(1/5)
1. In the TLS handshake trace, at step 4 the server sends its certificate chain to the client. What does the client do immediately after receiving this chain at step 5?
easy
A. The client closes the connection if the certificate is expired without any retries
B. The client immediately sends encrypted application data without verification
C. The client requests a new certificate from the server
D. The client verifies the certificate chain against trusted root CAs

Solution

  1. Step 1: Understand client certificate validation

    After receiving the server's certificate chain, the client validates it against its trusted root certificate authorities to ensure authenticity.

  2. Step 2: Eliminate incorrect options

    The client immediately sends encrypted application data without verification is wrong because the client must verify before sending encrypted data. The client requests a new certificate from the server is incorrect; clients do not request certificates from servers. The client closes the connection if the certificate is expired without any retries is partially true but the client may attempt other steps like checking revocation before closing.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Client verifies certificate chain before proceeding [check]
Hint: Client verifies certificate chain before encrypted data [check]
Common Mistakes:
2. You must design a multi-primary replication system for a geo-distributed database with low write latency and conflict detection. Which approach is best?
medium
A. Use asynchronous replication with vector clocks for conflict detection and resolution
B. Use a single global primary with read replicas in each region
C. Use synchronous replication between primaries to ensure consistency
D. Use asynchronous replication with last-write-wins conflict resolution

Solution

  1. Step 1: Analyze latency and conflict requirements

    Low write latency requires asynchronous replication; conflict detection needs metadata like vector clocks.

  2. Step 2: Evaluate options

    Synchronous replication (A) adds latency; single primary (C) violates multi-primary requirement; last-write-wins (D) ignores conflicts.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Async replication + vector clocks -> low latency + conflict detection [check]
Hint: Vector clocks detect conflicts in async multi-primary [check]
Common Mistakes:
3. For a chat system requiring low latency and fault tolerance, which architecture is best when mobile clients have intermittent connectivity?
medium
A. Use gRPC streaming for persistent connections to push messages instantly
B. Use a message queue with client-side polling and exponential backoff
C. Use WebSocket connections with server-side buffering and reconnection logic
D. Use HTTP long polling with immediate retries on failure

Solution

  1. Step 1: Evaluate client connectivity constraints

    Mobile clients have intermittent connectivity; gRPC streaming (A) requires persistent connections, which mobile networks may not support well. HTTP long polling (D) causes overhead and latency.

  2. Step 2: Compare WebSocket with server buffering vs polling

    WebSocket with server-side buffering and reconnection (C) balances low latency and fault tolerance better than client polling (B), which increases latency and load.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    WebSocket + buffering + reconnection -> best for intermittent mobile [check]
Hint: WebSocket buffers and reconnects for flaky mobile networks [check]
Common Mistakes:
4. At 10x traffic scale, which API Gateway component is most likely to become the bottleneck first, and why?
hard
A. Rate limiting store, because centralized counters cause contention and latency spikes
B. Authentication service, because token validation is CPU-intensive and stateful
C. API Gateway routing logic, because routing tables grow exponentially with services
D. Backend microservices, because they cannot horizontally scale as easily as the gateway

Solution

  1. Step 1: Identify scaling challenges

    Rate limiting often relies on centralized counters or stores (e.g., Redis) that become contention points under high request rates.

  2. Step 2: Eliminate other options

    Backend microservices, because they cannot horizontally scale as easily as the gateway is incorrect as backend services typically scale horizontally. API Gateway routing logic, because routing tables grow exponentially with services is unlikely as routing tables are cached and optimized. Authentication service, because token validation is CPU-intensive and stateful is less likely as token validation is stateless and can be cached.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Centralized rate limiting store bottlenecks first at scale [check]
Hint: Centralized counters bottleneck rate limiting at scale [check]
Common Mistakes:
5. At 10x traffic scale, which component is most likely to fail first in a system without rate limiting, and why?
hard
A. The backend cache, because its memory fills up causing evictions and cache misses
B. The database, due to increased write load causing slow queries and deadlocks
C. The network load balancer, as it cannot handle the increased number of TCP connections
D. The API servers, because they maintain stateful connections that cannot be easily sharded

Solution

  1. Step 1: Analyze component scalability at 10x traffic

    Databases (A) and caches (D) can be scaled horizontally or sharded; load balancers (C) can be scaled or replaced with L4/L7 solutions.

  2. Step 2: Identify API servers as bottleneck

    API servers maintaining stateful connections (e.g., WebSockets) are hard to shard or move; connection limits cause saturation and failure first.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Stateful API servers hit connection limits first at scale [check]
Hint: Stateful API servers fail first due to connection limits [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