Bird
Raised Fist0

Hash Ring - Virtual Nodes, Token Assignment, Node Addition and Removal

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Hash Ring - Virtual Nodes, Token Assignment, Node Addition and Removal
Design a scalable consistent hashing system with virtual nodes for balanced token assignment and smooth node addition/removal
mediumConsistent HashingFreq: common
Prerequisites:Distributed Systems BasicsHashing
⚙️
Functional Requirements
  • Distribute keys (tokens) evenly across nodes using consistent hashing with virtual nodes
  • Support dynamic addition of nodes with minimal data reshuffling
  • Support removal of nodes with minimal impact on key distribution
  • Map arbitrary keys to nodes efficiently with O(log N) or better lookup
  • Maintain balanced load across nodes to avoid hotspots
  • Provide APIs to query node ownership for a given key
📊
Non-Functional Requirements
  • Handle 2 billion daily active users generating 40 keys per user per day
  • Ensure 99.99% availability for key-to-node mapping queries
  • Achieve 100ms P99 latency for key lookups
  • Support scaling to 10,000+ nodes without significant performance degradation
  • Minimize data movement during node addition/removal to under 5% of total keys
❓
Clarifying Questions to Ask
  • What is the expected number of nodes in the cluster initially and at peak?
  • Are virtual nodes fixed per physical node or dynamically adjustable?
  • What is the key space size and hash function used?
  • Is the system read-heavy or write-heavy for key lookups?
  • How frequently do nodes join or leave the cluster?
  • Is there a requirement for consistent hashing ring state synchronization across clients?
Out of Scope
✗ Data storage or replication of actual key-value data
✗ Security and authentication of API calls
✗ Detailed network partition handling beyond node addition/removal
✗ Physical hardware provisioning and deployment
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user generates 40 keys (messages/operations) per day
  • Average key size is 100 bytes
  • Cluster size is 1000 physical nodes initially
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 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 storage2B × 40 × 100 bytes = 8,000 TB/day (8 PB/day)
retention days7
total storage8 PB × 7 = 56 PB
with replicationReplication factor 3 → 56 PB × 3 = 168 PB
🖥️
Server Estimate
hash ring manager100 nodes running hash ring service, each handling ~10K QPS
metadata store3-node Apache Zookeeper ensemble for ring state coordination
🏗️
Architecture Diagram
Architecture Diagram
          +----------------------+
          |  Client / Application |
          +----------+-----------+
                     | Key Lookup / Mapping
                     v
          +----------------------+
          |  Hash Ring Service   |
          | (Virtual Nodes Logic)|
          +----------+-----------+
                     | Reads/Writes Ring State
                     v
          +----------------------+
          |  Metadata Store      |
          | (Apache Zookeeper)   |
          +----------+-----------+
                     | Node Join/Leave Events
                     v
          +----------------------+
          |  Physical Nodes Pool  |
          | (Storage / Compute)   |
          +----------------------+
🧩
Components
Hash Ring Service
Maintains consistent hash ring with virtual nodes, handles key-to-node mapping
Why thisImplements virtual nodes to evenly distribute load and minimize data movement on node changes using consistent hashing
Why notSimple modulo hashing causes hotspots and full remapping on node changes; consistent hashing with virtual nodes avoids this
Metadata Store (Apache Zookeeper)
Stores ring state, node membership, and coordinates node addition/removal
Why thisZookeeper provides strong consistency and watches for cluster state changes with low latency
Why notEtcd or Consul have higher latencies or weaker consistency guarantees at this scale
Physical Nodes Pool
Actual nodes that store or process data, assigned tokens from the hash ring
Why thisPhysical nodes represent real resources; virtual nodes map tokens to these physical nodes
Why notUsing only virtual nodes without physical node abstraction complicates resource management
Client / Application
Queries hash ring service to find node responsible for a given key
Why thisDecouples key lookup logic from data storage, enabling scalability and flexibility
Why notEmbedding ring logic in clients leads to inconsistent views and complex client updates
Ring State Updater
Handles node addition/removal events, reassigns tokens, and updates metadata store
Why thisCentralizes ring updates to ensure consistent token assignment and minimal key movement
Why notDecentralized updates risk inconsistent ring views and data loss
🔄
Data Flow
1
Client → Hash Ring Service
Send key lookup request
Client queries which node owns the key
2
Hash Ring Service → Metadata Store
Read ring state and virtual node mapping
Fetch current token assignments and node membership
3
Hash Ring Service → Client
Return physical node responsible for key
Uses consistent hashing with virtual nodes for balanced mapping
4
Ring State Updater → Metadata Store
Update ring state on node addition/removal
Assigns tokens to new nodes and rebalances virtual nodes
5
Metadata Store → Hash Ring Service
Notify ring state change
Triggers ring service to refresh token assignments
6
Hash Ring Service → Physical Nodes Pool
Redirect client requests to correct physical node
Ensures requests are routed to nodes owning the key

Practice

(1/5)
1. A web crawler must efficiently avoid re-crawling the same URLs too frequently while ensuring freshness. Which component best handles URL scheduling and politeness constraints?
easy
A. Implement a URL Frontier with priority queues and politeness policies
B. Use a distributed key-value store to store page content for freshness checks
C. Rely on the PageRank component to prioritize URLs for crawling
D. Use a message queue to distribute URLs randomly among crawler workers

Solution

  1. Step 1: Identify URL scheduling role

    The URL Frontier manages which URLs to crawl next, enforcing politeness and freshness constraints.

  2. Step 2: Evaluate other components

    PageRank ranks pages post-crawl, not for scheduling. Distributed KV stores hold content but don't schedule. Random distribution ignores politeness.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    URL Frontier enforces crawl politeness and freshness [check]
Hint: URL Frontier schedules URLs with politeness [check]
Common Mistakes:
2. In a primary-replica system, what exactly breaks if the replication log (WAL) on the primary is lost before being sent to replicas?
medium
A. Replicas request full data snapshot from primary, causing high load and delayed recovery
B. Primary blocks all writes until WAL is restored, causing system-wide write unavailability
C. Primary loses committed transactions permanently, causing data loss and inconsistency
D. Replicas continue serving stale reads but cannot apply new writes, causing data divergence

Solution

  1. Step 1: Understand WAL role in replication

    WAL is the source of truth for replicas to catch up incrementally.

  2. Step 2: Trace failure impact

    If WAL is lost, replicas cannot catch up incrementally and must request full snapshot, causing load and delay.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Lost WAL -> replicas request full snapshot -> recovery delay [check]
Hint: Lost WAL -> full snapshot fetch delays recovery [check]
Common Mistakes:
3. At 10x scale, which component in the notification system is most likely to fail first and why?
hard
A. The Delivery Workers, because they cannot horizontally scale beyond a fixed number of threads per machine
B. The push notification gateway, because mobile platform rate limits throttle outgoing messages
C. The relational database storing user preferences, due to increased read/write contention
D. The presence cache, because it is stateful and cannot be sharded easily across many servers

Solution

  1. Step 1: Analyze Delivery Worker scalability

    Delivery Workers are CPU and thread-bound; increasing scale requires more workers, but thread limits and resource contention cause bottlenecks.

  2. Step 2: Compare other components

    Relational DB (A) can be sharded; push gateways (C) are rate-limited but can be scaled with multiple credentials; presence cache (D) can be sharded with consistent hashing.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Delivery Workers hit thread and CPU limits first at 10x scale [check]
Hint: Delivery Workers hit thread limits before other components [check]
Common Mistakes:
4. At 10x scale, which component in the News Feed system is most likely to fail first and why?
hard
A. The database, because it cannot handle the increased write volume for posts
B. The Delivery Workers, because they cannot process the exponentially larger fan-out queues fast enough
C. The cache layer, because cache invalidation traffic grows superlinearly with user count
D. The fan-out message queue (Kafka), because partition count limits prevent scaling beyond a threshold

Solution

  1. Step 1: Analyze bottlenecks at 10x scale

    Database (A) can be sharded; cache (C) scales horizontally; Kafka (D) can add partitions but has limits.

  2. Step 2: Delivery Workers face exponential fan-out growth

    Fan-out queues grow with followers; Delivery Workers must push updates to millions more followers, causing processing lag and backlog.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Delivery Workers bottleneck due to fan-out processing load [check]
Hint: Delivery Workers bottleneck on fan-out processing at scale [check]
Common Mistakes:
5. At 10x scale, which component in a system using TLS for encryption in transit is most likely to become the bottleneck first, and why?
hard
A. The TLS termination proxy, because it must handle CPU-intensive handshake operations for all new connections
B. The Application Servers, because they decrypt and encrypt all traffic themselves causing CPU exhaustion
C. The Network Load Balancer, because it cannot scale beyond a fixed number of connections
D. The Database, because encrypted queries increase query processing time

Solution

  1. Step 1: Identify TLS termination proxy role

    It handles all TLS handshakes which are CPU-intensive, especially at high connection rates.

  2. Step 2: Compare other components

    Application servers offload encryption to TLS proxy; load balancer scales horizontally; database impact is unrelated to TLS termination.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    TLS proxy CPU-bound on handshakes -> first bottleneck at scale [check]
Hint: TLS handshake CPU load hits termination proxy first [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