Consistent Hashing

Consistent Hashing is a foundational algorithm in distributed systems used to distribute request traffic and data across a dynamically scaling cluster of servers. Whether you are building a distributed cache, sharding a database, or routing traffic across proxy tiers, consistent hashing solves a fundamental challenge: how to minimize data movement when servers join or leave the network.

The Five Step System Design Framework

When approaching infrastructure questions in a system design interview, follow these five structured steps to navigate complex distributed systems choices:

1. Define Requirements and Estimations: Clarify functional expectations, throughput scale, and availability goals.
2. Identify Core Entities: Design database tables, memory representations, and server token structures.
3. Design the API: Define explicit HTTP or RPC contracts between clients, routers, and storage nodes.
4. High Level Design: Draw overall system component layouts and write detailed diagram generation prompts.
5. Deep Dives and Production Case Studies: Explore algorithmic edge cases, trade offs, virtual nodes, hot spot salting, and real world production implementations.

Step 1: Requirements and Estimations

Functional Requirements

• Dynamic Node Registration: Support adding new storage or cache servers to the active cluster without manual reindexing.
• Graceful Node Removal: Handle intentional decommissioning or unexpected crashes of database instances seamlessly.
• Deterministic Key Lookup: Given a request key, deterministically compute and resolve the exact target server node holding that data.
• Minimal Data Movement: Ensure that adding or removing a single node redistributes only a minimal fraction of total cached keys.

Non Functional Requirements

• High Availability: Target zero downtime during cluster rebalancing or server node additions.
• Sub Millisecond Lookup Latency: Key resolution at the router proxy tier must execute in under 1 millisecond.
• Uniform Distribution: Keys must be evenly partitioned across all active physical nodes to prevent storage imbalance.
• Fault Tolerance: The system must maintain operation even when individual cluster nodes become unavailable.

Capacity Estimations

• Key Scale: 100 million active keys stored across a distributed caching layer.
• Cluster Size: 100 physical cache servers deployed in the active infrastructure pool.
• Virtual Nodes: Each physical server operates 200 virtual nodes to ensure balanced keyspace distribution.
• Ring Tokens: The hash ring manages 20,000 total virtual points across a 32 bit unsigned integer space (0 to 4,294,967,295).
• Router Memory Footprint: Storing 20,000 token mappings in memory requires less than 1 megabyte of memory per router instance, making client side routing lightweight.

Step 2: Core Entities and Schema

To support consistent hashing across an infrastructure cluster, define clear data structures for physical servers, virtual nodes, and key partitions.

1. PhysicalNode Entity

• node_id (String, Unique identifier like cache-prod-01)
• ip_address (String, Network address for direct node communication)
• port (Integer, Service port for connection pooling)
• status (Enum: ACTIVE, DRAINING, OFFLINE)
• weight (Integer, Capacity multiplier for heterogeneous hardware sizing)

2. VirtualNode Entity

• vnode_id (String, Synthetic label such as cache-prod-01-vn42)
• physical_node_id (Foreign Key referencing PhysicalNode.node_id)
• hash_token (Unsigned 32 bit Integer, Exact point location on the ring circle)

3. KeyMapping Entity (Logical Partition Concept)

• key_hash (Unsigned 32 bit Integer, Hash code generated from key identifier)
• target_vnode_id (Foreign Key referencing VirtualNode.vnode_id)
• target_physical_node_id (Foreign Key referencing PhysicalNode.node_id)

Step 3: API Design

Define explicit management and query contracts between client proxies and cluster coordinator nodes.

1. Add Server Node to Cluster

POST /api/v1/cluster/nodes
Content-Type: application/json

Request Body:

{
  "nodeId": "cache-prod-101",
  "ipAddress": "10.0.4.15",
  "port": 6379,
  "vnodeCount": 200
}

Response Body (201 Created):

{
  "status": "SUCCESS",
  "assignedTokens": 200,
  "rebalanceRangeCount": 200
}

2. Remove Server Node from Cluster

DELETE /api/v1/cluster/nodes/cache-prod-101

Response Body (200 OK):

{
  "status": "DRAINING",
  "keysMigrated": 1000000,
  "targetNodes": ["cache-prod-02", "cache-prod-14"]
}

3. Lookup Destination Server for Key

GET /api/v1/keys/route?key=user_session_98421

Response Body (200 OK):

{
  "key": "user_session_98421",
  "keyHash": 2847192041,
  "targetNodeId": "cache-prod-42",
  "ipAddress": "10.0.2.88",
  "port": 6379
}

Step 4: High Level Design

At a high level, consistent hashing coordinates traffic routing between incoming client requests, routing proxies, and distributed storage tiers:

Architecture Diagram Generation Prompt: A clean distributed systems architecture diagram illustrating consistent hashing routing flow. At the top, multiple Client applications send read and write requests. Below them sits a Stateless Routing Proxy Tier running a local Hash Ring Routing Table. To the right, an External Cluster Coordinator (such as Apache ZooKeeper or HashiCorp Consul) monitors Node Health via heartbeat signals and broadcasts Membership Updates to all proxy nodes. Below the proxy tier is a circular Hash Ring diagram ranging from 0 to 2^32 - 1. Physical database nodes DB1, DB2, DB3, and DB4 are mapped to multiple Virtual Nodes scattered around the ring perimeter. Client key requests are hashed, placed on the ring circle, and routed clockwise to the first encountered virtual node. Sub diagrams illustrate node addition where only adjacent key segments are transferred, leaving all other node assignments completely unaffected.

• Client Request Flow: Incoming requests pass into stateless routing proxies. The proxy hashes the incoming key string to determine its numeric position on the ring circle.
• Ring Evaluation: The proxy walks clockwise around the ring to identify the first virtual node token whose value is greater than or equal to the key hash.
• Cluster Coordination: A distributed coordinator cluster monitors physical server health using background heartbeats. When node topology updates occur, the coordinator broadcasts updated token arrays to all routing proxies.

Step 5: Deep Dives and Real World Production Case Studies

1. The Flaw of Simple Modulo Hashing

The naive method for distributing items across multiple storage nodes relies on basic modulo arithmetic:

target_server_id = hash(key) % total_servers

While simple modulo hashing works well when the cluster size remains static, it fails dramatically in dynamic environments. Suppose you have 4 cache servers and wish to add a 5th server to handle growing traffic.

When total_servers changes from 4 to 5, the mathematical result of hash(key) % N changes for nearly every key in the database. Specifically, statistical analysis shows that N / (N + 1) of all cached items (80 percent when scaling from 4 to 5 nodes) suddenly map to completely different servers.

This causes massive cache invalidation across your entire cluster, triggering a massive cache stampede where requests overwhelm underlying backend databases simultaneously, leading to widespread system outages.

2. Hash Ring Mechanics and Ring Traversal

Consistent hashing eliminates mass cache invalidation by mapping both data keys and server nodes onto a shared conceptual ring.

• The Keyspace Ring: Imagine an integer range from 0 to 2^32 - 1 mapped onto a continuous circle, where position 0 connects seamlessly back to 2^32 - 1.
• Server Placement: Physical server identifiers (or IP addresses) are passed through a uniform cryptographic hash function like MD5 or MurmurHash3 to produce integer points along the circle.
• Key Routing: When a request arrives for a key, the router hashes the key identifier to obtain an integer point on the circle. The router then walks clockwise around the perimeter until it encounters the first server position. That server is the designated destination owner for the key.

[ 0 / 2^32-1 ]
               . - - - - - - - - .
           .                       .
         .   DB1 (Token: 500M)       .
       .                               .
      .                                 .  Key A (Hash: 800M)
     .                                   . ----> Routes Clockwise to DB2
     .   DB4 (Token: 3.2B)               .
      .                                 .
       .                               .   DB2 (Token: 1.2B)
         .                           .
           .                       .
               . - - - - - - - - .
                  DB3 (Token: 2.1B)

To implement clockwise ring traversal efficiently in memory, routing proxies store sorted arrays of server tokens. Using binary search algorithms like Java TreeMap ceilingKey or C++ std::upper_bound, proxies locate target nodes in logarithmic time O(log K), where K represents the total number of ring tokens.

3. Virtual Nodes for Uniform Load Distribution

Pure consistent hashing with single server tokens introduces two critical operational problems:

1. Non Uniform Key Distribution: Random cryptographic hashing can leave large empty gaps on the ring, causing some servers to own massive segments while others receive minimal traffic.
2. Cascading Failure Oversupply: When a single physical server crashes, all of its assigned keys cascade directly onto its immediate clockwise neighbor. That neighbor can quickly become overwhelmed by double load, crashing in turn and cascading failures throughout the entire cluster.

To solve both issues, distributed systems implement Virtual Nodes (vnodes). Instead of placing a physical server at just one point, each physical database instance is assigned multiple synthetic tokens across the ring perimeter (for example, 100 to 250 virtual tokens per physical node).

# Generating virtual node positions for a physical server
def generate_vnode_tokens(physical_node_id, vnode_count):
    tokens = []
    for i in range(vnode_count):
        vnode_key = f"{physical_node_id}-vnode-{i}"
        token = murmurhash3_32(vnode_key)
        tokens.append((token, physical_node_id))
    return tokens

With virtual nodes, when a physical server fails, its virtual nodes are scattered interleaved across the entire circle perimeter. Consequently, its lost request load redistributes evenly across all remaining cluster servers rather than crushing a single adjacent neighbor.

4. Hot Spot Mitigation Strategies

While virtual nodes ensure structural balance (an equal count of keys per server), they do not solve traffic hotspots created by popular individual keys. For instance, in a ticketing application, an event page for a major concert receives millions of read requests per minute, creating a massive hotspot on whichever node holds that specific key.

System design engineers use three complementary techniques to neutralize traffic hotspots:

• Read Replicas: Replicate popular key data across multiple secondary nodes and load balance read queries across the replica group.
• Key Space Salting: Append random numeric suffixes to hot keys during write operations (for example, taylor_swift_concert_0 through taylor_swift_concert_9). This splits write and read operations across multiple distinct hash ring positions. Client queries scatter read requests across all salted variants and aggregate results.
• Adaptive Dynamic Rebalancing: Real time monitoring proxies detect traffic spikes on specific key partitions dynamically, automatically splitting and migrating hot token ranges off overloaded servers onto idle instances.

5. Data Movement and Synchronization in Production

When adding a new node to a consistent hash ring, only a fraction of keys need to move. If a cluster has N active physical nodes and introduces 1 new node, approximately 1 / (N + 1) of total keys are transferred.

During node addition, the new node connects to its clockwise neighbor, identifies the specific key range segment it is inheriting, and streams that data background segment asynchronously. Client reads fall back to the old owner until data streaming completes, ensuring zero service disruption during cluster scaling.

6. Real World Production Case Studies

Apache Cassandra

Apache Cassandra uses a consistent hashing ring to manage partitioned data across peer to peer cluster nodes. Cassandra configures Murmur3Partitioner to assign 64 bit integer tokens across nodes. Modern Cassandra deployments utilize virtual nodes (vnodes) by default, allowing seamless node replacement, automated repair streaming, and proportional data distribution based on heterogeneous disk capacity.

Amazon DynamoDB

Amazon DynamoDB relies on consistent hashing principles within its internal request routing layer. DynamoDB storage nodes are partitioned across internal rings. As tables grow in storage volume or throughput capacity, DynamoDB partition split coordinators dynamically split token ranges and reassign storage segments without impacting application request latency.

Redis Cluster (Fixed Hash Slots Comparison)

Unlike pure consistent hashing, Redis Cluster uses a fixed hash slot model. Redis Cluster divides the entire key space into exactly 16,384 fixed slots using the formula CRC16(key) mod 16384. These 16,384 slots are distributed among physical cluster nodes. While consistent hashing allows dynamic continuous token placement, Redis chose fixed hash slots because explicit slot assignments make operational rebalancing, cluster resharding, and cluster state broadcasting significantly simpler to manage in memory.

Content Delivery Networks (CDNs)

Global CDNs employ consistent hashing within edge caching proxy tiers. When web requests hit edge points of presence, edge routers hash incoming URL strings to select specific caching proxy servers. Consistent hashing ensures that when an edge caching proxy is restarted or replaced, only a tiny fraction of cached web assets are invalidated, keeping cache hit ratios high across global networks.

You have mastered Consistent Hashing! Apply these architectural patterns in your next system design interview to build scalable, resilient distributed systems.