Consistent hashing in HLD - System Design Exercise

Design: Consistent Hashing System

Design the consistent hashing mechanism and its integration with nodes for key distribution. Out of scope: detailed node internals, network protocols, and client-side caching.

Functional Requirements

FR1: Distribute keys evenly across multiple nodes (servers).

FR2: Minimize key remapping when nodes are added or removed.

FR3: Support dynamic scaling of nodes without major data reshuffling.

FR4: Handle node failures gracefully with minimal impact on key distribution.

FR5: Provide a way to locate the node responsible for a given key efficiently.

Non-Functional Requirements

NFR1: System should handle up to 10,000 nodes.

NFR2: Key lookup latency should be under 5 milliseconds.

NFR3: System availability target is 99.9% uptime.

NFR4: Memory usage per node should be optimized to handle millions of keys.

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

Hash function module

Hash ring data structure

Node manager for adding/removing nodes

Virtual node implementation

Failure detection and recovery mechanism

Client lookup interface

Design Patterns

Consistent hashing ring

Virtual nodes for load balancing

Hashing with rendezvous (highest random weight) as alternative

Replication strategies for fault tolerance

Reference Architecture

Client
  |
  v
+-------------------+
| Consistent Hashing |
|       Ring        |
+-------------------+
  |        |        |
  v        v        v
Node1    Node2    Node3
(Physical nodes with virtual nodes mapped on ring)

Components

Hash Function

MurmurHash3 or SHA-256

Generate uniform hash values for keys and nodes.

Consistent Hash Ring

Sorted data structure (e.g., balanced tree or sorted array)

Map hash values of nodes and keys on a circular ring.

Virtual Nodes

Multiple hash points per physical node

Improve key distribution and balance load across nodes.

Node Manager

Service or module managing node lifecycle

Add or remove nodes and update the hash ring accordingly.

Client Lookup Interface

API or library

Given a key, find the responsible node by hashing and ring traversal.

Failure Detection

Heartbeat or health checks

Detect node failures and trigger ring updates.

Request Flow

1. Client wants to store or retrieve a key.

2. Client hashes the key using the hash function.

3. The hash value is located on the consistent hash ring.

4. Traverse clockwise on the ring to find the first node hash greater than or equal to the key hash.

5. The corresponding physical node owning that virtual node is selected.

6. Client sends request to the selected node.

7. If nodes are added or removed, Node Manager updates the ring with minimal key remapping.

Database Schema

Not applicable as consistent hashing is a data distribution technique rather than a database schema. Key entities: Node (id, virtual node hashes), Key (hashed value), Hash Ring (sorted list of virtual node hashes mapped to physical nodes).

Scaling Discussion

Bottlenecks

Hash ring lookup latency increases with very large number of nodes.

Uneven key distribution if virtual nodes are insufficient.

Node failure detection delay causing stale ring state.

Memory overhead for storing many virtual nodes per physical node.

Solutions

Use efficient data structures like balanced binary search trees or skip lists for ring lookup to keep O(log N) complexity.

Increase number of virtual nodes per physical node to improve balance.

Implement fast failure detection mechanisms like gossip protocols or heartbeat intervals.

Tune virtual node count to balance memory usage and distribution quality.

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing the consistent hashing ring and components, 10 minutes discussing scaling and failure handling, 5 minutes summarizing.

Explain the problem of key distribution and why consistent hashing helps.

Describe how the hash ring works and the role of virtual nodes.

Discuss how node addition/removal affects key remapping.

Mention failure detection and recovery strategies.

Talk about scaling challenges and how to mitigate them.