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
Understanding the limitations of modular hashing and the advantages of consistent hashing in distributed systems
mediumConsistent HashingFreq: common
Prerequisites:Distributed Systems BasicsHashing
⚙️
Functional Requirements
  • Distribute keys uniformly across N nodes to balance load
  • Minimize data movement when nodes are added or removed
  • Support dynamic scaling of nodes without downtime
  • Ensure efficient key lookup with minimal latency
  • Handle node failures gracefully without large-scale remapping
📊
Non-Functional Requirements
  • Support 2 billion daily active users generating 40 messages each per day
  • Achieve 99.99% availability for key lookups
  • Maintain 100ms P99 latency for read/write operations
  • Handle peak write QPS of approximately 925,000 messages per second
  • Ensure data redistribution on node changes affects less than 5% of keys
❓
Clarifying Questions to Ask
  • What is the expected number of nodes in the cluster initially and at peak scale?
  • Are keys uniformly distributed or do we expect hotspots?
  • What is the acceptable downtime or performance degradation during node addition/removal?
  • Is the system read-heavy, write-heavy, or balanced?
  • What failure scenarios must be tolerated (node crash, network partition)?
  • Is data replication handled separately or integrated with partitioning?
Out of Scope
✗ Data replication and consistency protocols
✗ Detailed storage engine internals
✗ Security and encryption mechanisms
✗ Client-side caching strategies
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user generates 40 messages per day
  • Average message size is 100 bytes
  • Cluster initially has 100 nodes
⚡
QPS Calculation
write qps2,000,000,000 × 40 / 86,400 ≈ 925,926 writes/sec
peak write qpsAssuming 2× peak factor → 1,851,852 writes/sec
read qpsAssuming 5 reads per write → 4,629,630 reads/sec
💾
Storage Estimate
daily storage2,000,000,000 × 40 × 100 bytes = 8,000,000,000,000 bytes ≈ 7.28 TB/day
retention days7
total storage7.28 TB × 7 = 50.96 TB
with replicationAssuming 3 replicas → 50.96 TB × 3 = 152.88 TB
🖥️
Server Estimate
storage nodesAssuming 1 TB usable per node → 153 nodes needed for storage
load balancersAt least 10 nodes to handle 6.5M QPS (read+write) with 650K QPS per node
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |   Client App   |
          +-------+--------+
                  |
                  v
          +-------+--------+
          |  Load Balancer |
          +-------+--------+
                  |
                  v
          +-------+--------+
          | Partitioning   |
          | Service       |
          | (Consistent   |
          |  Hashing)     |
          +-------+--------+
                  |
        +---------+---------+
        |         |         |
   +----v----+ +--v----+ +--v----+
   | Node 1  | | Node 2 | | Node N|
   +---------+ +--------+ +-------+
🧩
Components
Load Balancer
Distributes incoming client requests evenly across partitioning service instances
Why thisNginx with consistent hashing module supports sticky sessions and high throughput
Why notAWS ELB lacks fine-grained control over hashing and session affinity at scale
Partitioning Service
Implements consistent hashing ring to map keys to nodes dynamically
Why thisCustom consistent hashing implementation allows minimal key remapping on node changes
Why notModular hashing (key % N) requires full remapping on node count change, causing massive data movement
Storage Nodes (Cassandra)
Stores key-value data partitioned by consistent hashing ring segments
Why thisCassandra supports tunable replication, linear scalability, and partition key-based data distribution
Why notPostgreSQL requires manual sharding and does not scale linearly at 1M+ writes/sec
Metadata Service (ZooKeeper)
Maintains cluster membership and consistent hashing ring state
Why thisZooKeeper provides reliable distributed coordination and watches for node changes
Why notEtcd has higher latency and less mature client libraries in this environment
Monitoring & Alerting (Prometheus + Grafana)
Tracks node health, request latencies, and data distribution metrics
Why thisPrometheus supports high cardinality metrics and Grafana provides rich visualization
Why notCloudWatch lacks granularity and custom metric support for internal ring state
🔄
Data Flow
1
Client App → Load Balancer
Client sends key-based request (read/write)
Load balancer evenly distributes requests to partitioning service
2
Load Balancer → Partitioning Service
Forward request with key metadata
Partitioning service uses consistent hashing to find target node
3
Partitioning Service → Metadata Service
Fetch current consistent hashing ring state
Ensures up-to-date node membership and ring mapping
4
Partitioning Service → Storage Node
Route request to node responsible for key's hash range
Only affected nodes handle the request, minimizing cross-node traffic
5
Storage Node → Partitioning Service
Return read/write response
Partitioning service forwards response back to client
6
Metadata Service → Partitioning Service
Notify on node addition/removal
Partitioning service updates ring and triggers minimal key remapping

Practice

(1/5)
1. In the request flow for generating a user's feed, at step 5 the Feed Aggregator receives multiple candidate posts from different microservices. What does the Feed Aggregator do at this step before sending the feed to the user?
easy
A. It merges, deduplicates, and ranks posts based on relevance scores before returning
B. It immediately returns the raw posts without filtering or ranking
C. It stores all posts in a persistent database before responding to the user
D. It sends posts to the notification service to alert the user before aggregation

Solution

  1. Step 1: Understand Feed Aggregator's role at Step 5

    The Feed Aggregator must combine posts from multiple sources, remove duplicates, and rank them to personalize the feed.

  2. Step 2: Eliminate incorrect options

    It immediately returns the raw posts without filtering or ranking skips ranking, leading to poor UX. It stores all posts in a persistent database before responding to the user delays response unnecessarily. It sends posts to the notification service to alert the user before aggregation misplaces notification logic before feed aggregation.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Feed Aggregator merges and ranks posts -> personalized feed [check]
Hint: Aggregate, dedupe, rank before sending feed [OK]
Common Mistakes:
2. In a multi-CDN request flow, at Step 4 the Global Traffic Manager receives a health check failure from CDN Provider A. What is the immediate action taken by the Global Traffic Manager at this step?
easy
A. It marks CDN Provider A as unhealthy and temporarily stops routing new requests to it
B. It sends a notification to the origin server to stop sending content to CDN Provider A
C. It immediately reroutes all new user requests to CDN Provider B without delay
D. It caches the last successful response from CDN Provider A to serve future requests

Solution

  1. Step 1: Understand Global Traffic Manager health check handling

    Upon receiving a health check failure, the manager marks the CDN as unhealthy to prevent routing new requests to it.

  2. Step 2: Eliminate other options

    Immediate rerouting (A) may cause abrupt traffic shifts without grace. Origin server notifications (C) are not part of traffic management. Caching responses (D) is unrelated to health check handling.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Health check failure -> mark CDN unhealthy, stop routing new requests [check]
Hint: Health check failure -> mark CDN unhealthy, pause routing [OK]
Common Mistakes:
3. For a video calling system targeting mobile clients with intermittent connectivity, which architecture best balances latency and reliability for media delivery?
medium
A. Use a multipoint control unit (MCU) media server that mixes all streams into one
B. Use a fully peer-to-peer WebRTC connection with no media server relay
C. Use a selective forwarding unit (SFU) media server to relay streams only when needed
D. Use HTTP Live Streaming (HLS) for media delivery to ensure reliability

Solution

  1. Step 1: Evaluate architectures for mobile intermittent connectivity

    Pure peer-to-peer (A) suffers from connectivity issues; MCU (C) adds latency and CPU overhead; HLS (D) is high latency and not real-time.

  2. Step 2: SFU (B) relays streams selectively, reducing latency and handling network variability well.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    SFU balances latency and reliability for mobile intermittent networks [check]
Hint: SFU relays selectively, best for mobile intermittent connectivity [check]
Common Mistakes:
4. If the Key Management Service (KMS) becomes unavailable, what exactly breaks in the system's encryption-at-rest workflow?
medium
A. New encryption keys cannot be generated, but existing data remains accessible and decryptable
B. Data encryption stops, causing all writes to fail immediately
C. Decryption of existing data fails, causing read operations to block or error out
D. The system falls back to unencrypted storage, risking data exposure

Solution

  1. Step 1: Understand KMS role in key lifecycle

    KMS generates and manages encryption keys; if unavailable, new keys can't be created but existing keys cached locally allow decryption.

  2. Step 2: Eliminate incorrect failure modes

    Encryption doesn't stop immediately; decryption continues with cached keys; system does not fallback to unencrypted storage automatically.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    KMS outage blocks new key generation, existing keys still usable [check]
Hint: KMS down -> no new keys, existing keys still decrypt [check]
Common Mistakes:
5. At 10x scale, which component in the recommendation system is most likely to fail first due to stateful connection limits, and why?
hard
A. The Kafka cluster, because partition count limits throughput and causes producer backpressure
B. The recommendation API servers, because maintaining user session state for personalized recommendations exhausts memory
C. The embedding storage database, because it cannot shard embeddings by user ID efficiently
D. The embedding service, because it holds in-memory caches that grow unbounded with user scale

Solution

  1. Step 1: Identify bottleneck at 10x scale

    Kafka partitions limit throughput; increasing partitions is complex and causes rebalancing overhead.

  2. Step 2: Evaluate other components

    Embedding DB (A) can shard by user ID; API servers (C) are typically stateless or use external session stores; embedding service caches (D) can be evicted or sharded. Kafka's partition limit causes producer backpressure and stalls event flow first.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Kafka partition limit -> throughput bottleneck -> backpressure [check]
Hint: Kafka partitions limit throughput first 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