Bird
Raised Fist0

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

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
▶
Request Trace
Step 1/6
Client / Application

Sends token assignment request

Client requests token assignment for a new data shard

Protocol:WebSocket
BeforeClient has data shard needing node assignment
AfterRequest sent to Hash Ring Service for token assignment
Hash Ring Service

Processes token assignment request

Calculates virtual node tokens and maps to physical nodes

Protocol:Internal RPC
BeforeRing state cached but may be stale due to recent node changes
AfterToken assignment computed and response prepared
Ring State Updater

Detects node addition event

Receives notification of new physical node joining pool

Protocol:Internal RPC
BeforeRing state reflects old node set without new node
AfterTriggers ring state update to include new node tokens
Metadata Store (Apache Zk)

Stores updated ring state

Persists new token assignments and virtual node mappings

Protocol:Zk API
BeforeRing state stored without new node tokens
AfterRing state updated with new tokens and node info
Hash Ring Service

Receives ring state update notification

Refreshes cached ring state from Zookeeper

Protocol:Watch/Notify
BeforeCached ring state outdated, missing new node tokens
AfterCached ring state refreshed with new node tokens
Client / Application

Receives token assignment response

Gets assigned tokens mapped to physical nodes including new node

Protocol:WebSocket
BeforeClient waiting for token assignment response
AfterClient knows token assignment including new physical node
🏗️
Architecture Diagram
Architecture Diagram
┌───────────────────────┐
│   Client / Application │
└─────────────┬─────────┘
              │ WebSocket
              ▼
┌───────────────────────┐
│    Hash Ring Service   │
│  (virtual nodes, token │
│   assignment logic)    │
└─────────────┬─────────┘
              │ Internal RPC
              ▼
┌───────────────────────┐
│   Ring State Updater   │
│ (detects node changes, │
│  updates ring state)   │
└─────────────┬─────────┘
              │ Zk API
              ▼
┌────────────────────────┐
│ Metadata Store (Apache  │
│ Zk)                    │
│ (stores ring state,    │
│ tokens)                │
└─────────────┬──────────┘
              │ Watch/Notify
              ▼
┌───────────────────────┐
│  Physical Nodes Pool   │
│ (actual physical nodes)│
└───────────────────────┘
Design Rationale

This architecture shows a vertical flow starting from the Client / Application sending a token assignment request to the Hash Ring Service. The Hash Ring Service calculates virtual node tokens and maps them to physical nodes. When a new physical node is added, the Ring State Updater detects this event and updates the ring state in the Metadata Store (Apache Zookeeper). The Hash Ring Service watches for these updates and refreshes its cached ring state accordingly. This design ensures consistent token assignment with virtual nodes and supports dynamic node addition by leveraging Zookeeper's strong consistency and watch notifications. The Physical Nodes Pool represents the actual nodes mapped by tokens on the ring, completing the flow from client request to updated node assignment.

Primary Focus

✓

Practice

(1/5)
1. You need to quickly outline a system design answer in 45 minutes that ensures clarity and completeness. Which component of your approach best handles organizing the problem scope and constraints?
easy
A. Start by immediately designing the database schema to save time
B. Focus on coding a prototype to demonstrate feasibility
C. Begin with clarifying requirements and constraints to define scope
D. Jump directly to choosing technologies based on personal preference

Solution

  1. Step 1: Identify the importance of requirements gathering

    Clarifying requirements and constraints defines the problem scope, preventing wasted effort on irrelevant details.

  2. Step 2: Eliminate premature design steps

    Starting with database design or coding ignores the need to understand what to build, risking misaligned solutions.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Clarify scope first -> focused design [check]
Hint: Clarify scope before design [check]
Common Mistakes:
2. For a ChatGPT-like system requiring real-time token streaming to mobile clients with intermittent connectivity, which architecture best balances latency and client compatibility?
medium
A. Use gRPC streaming for continuous token delivery
B. Use WebSocket connections with custom heartbeat and reconnection logic
C. Use long polling over HTTP/1.1 to simulate streaming
D. Use HTTP/2 server-sent events (SSE) for token streaming with automatic reconnection

Solution

  1. Step 1: Analyze client compatibility and connectivity constraints

    Mobile clients often have intermittent connectivity and limited support for gRPC streaming.

  2. Step 2: Evaluate streaming options

    gRPC streaming (A) has limited mobile support; WebSockets (C) require complex reconnection; long polling (D) adds latency and overhead. SSE (B) supports automatic reconnection and is widely supported on mobile.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    HTTP/2 SSE balances latency and mobile client compatibility [check]
Hint: SSE auto-reconnects, suits mobile better than gRPC or WebSocket [check]
Common Mistakes:
3. For a real-time ML inference system requiring minimal latency and high availability during model updates, which architecture is preferable and why?
medium
A. Monolithic model server that loads new models sequentially, blocking requests during reload
B. Single model server with periodic batch reloads and request queueing during reload
C. Blue-green deployment with two identical model serving clusters switching traffic atomically
D. Client-side model loading with periodic updates pushed to clients

Solution

  1. Step 1: Evaluate architectures for latency and availability

    Monolithic (A) and single server batch reload (C) block requests during reload, increasing latency. Client-side loading (D) adds complexity and inconsistent versions.

  2. Step 2: Understand blue-green deployment benefits

    Blue-green (B) runs two clusters; new model loads on inactive cluster, then traffic switches atomically, ensuring zero downtime and minimal latency impact.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Blue-green enables atomic switch with zero downtime [check]
Hint: Blue-green switches traffic atomically, avoiding reload blocking [OK]
Common Mistakes:
4. At 10x scale, which component of a Bloom filter system is most likely to fail first and why?
hard
A. The client application, due to increased latency in membership queries
B. The bit array storage, because increased insertions cause saturation and higher false positive rates
C. The hash functions, because their computation time grows linearly with scale
D. The network bandwidth, due to Bloom filter synchronization overhead

Solution

  1. Step 1: Identify scaling impact on Bloom filter components

    At very high scale, hash function computation cost increases linearly with insertions, becoming a CPU bottleneck.

  2. Step 2: Evaluate other components

    Bit array saturation affects false positives but does not cause immediate failure; network and client latency scale better.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Hash function CPU cost grows linearly, causing first failure at scale [check]
Hint: Hash function CPU cost grows linearly at scale [check]
Common Mistakes:
5. At 10x scale, which component in the payment gateway architecture is most likely to fail first due to stateful connection limits, and why?
hard
A. The relational database, because increased writes cause lock contention and slow queries
B. The webhook delivery workers, because retry queues grow unbounded causing memory exhaustion
C. The API gateway servers, because they maintain stateful TLS sessions and cannot shard connections easily
D. The payment processor adapters, because external API rate limits cause cascading failures

Solution

  1. Step 1: Identify stateful components limiting scale

    API gateway servers maintain stateful TLS sessions per client, limiting horizontal scaling.

  2. Step 2: Compare with other components

    Databases can be scaled with sharding; retry queues are bounded; external API limits cause delays but not immediate failure.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Stateful TLS sessions limit API gateway horizontal scaling [check]
Hint: Stateful TLS sessions bottleneck API gateway scaling [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