Consistent Hashing

The Problem with Traditional Hashing

In distributed systems, we need to map keys (like cache keys, database shard keys, or request IDs) to nodes (servers, cache instances, or database shards). Traditional hashing uses a simple modulo operation:

Traditional Approach:

node = hash(key) % num_nodes

The Problem:

• Adding one node requires remapping all keys
• Removing one node loses all keys mapped to that node
• This causes massive data migration and cache invalidation

Real-World Impact: Imagine a distributed cache with 1 million keys. Adding one server means remapping all 1 million keys, causing cache misses, database load spikes, and degraded performance.

What is Consistent Hashing?

Consistent hashing is a distributed hashing scheme that minimizes the number of keys that need to be remapped when nodes are added or removed. Instead of using modulo, it uses a hash ring - a circular space where both keys and nodes are mapped.

The Core Concept

Think of consistent hashing like a clock face:

• The ring represents values from 0 to 2^32-1 (or 2^64-1)
• Both keys and nodes are hashed to positions on this ring
• A key is assigned to the first node encountered when moving clockwise from the key’s position

Key Properties:

• Minimal rehashing: Only keys between the old and new node positions need remapping
• Load balancing: Keys are distributed evenly across nodes (with virtual nodes)
• Fault tolerance: Node removal only affects keys mapped to that node
• Horizontal scaling: Adding nodes is efficient

How It Works

1. Create hash ring: Define a circular space (typically 0 to 2^32-1)
2. Hash nodes: Map each node to one or more positions on the ring
3. Hash keys: Map each key to a position on the ring
4. Assign keys: Each key belongs to the first node encountered clockwise from its position

When a node is added:

• Only keys between the previous node and the new node need remapping
• On average, only k/n keys need remapping (where k = number of keys, n = number of nodes)

When a node is removed:

• Keys mapped to that node are reassigned to the next node clockwise
• Other keys remain unchanged

Virtual Nodes

Virtual nodes (vnodes) are multiple hash positions for a single physical node. This improves load distribution and handles nodes with different capacities.

Why Virtual Nodes Matter:

Without virtual nodes, if nodes are hashed to positions that cluster together, some nodes get many keys while others get few. Virtual nodes spread each physical node across multiple positions on the ring, ensuring more even distribution.

Example:

• Physical node “Server-1” might have virtual nodes at positions: 1000, 50000, 100000, 200000
• Physical node “Server-2” might have virtual nodes at positions: 25000, 75000, 150000, 250000
• This spreads the load more evenly

Consistent Hashing Implementation

💡 Tip: Click dropdown to switch between languages

Python

Python

"consistent_hashing.py

import hashlib
from typing import List, Optional, Dict
from bisect import bisect_right

class ConsistentHashRing:
    """Consistent hash ring implementation"""

    def __init__(self, virtual_nodes_per_node: int = 150):
        self.virtual_nodes_per_node = virtual_nodes_per_node
        self.ring: Dict[int, str] = {}  # position -> node_name
        self.sorted_positions: List[int] = []
        self.nodes: set = set()

    def _hash(self, key: str) -> int:
        """Hash key to position on ring (0 to 2^32-1)"""
        return int(hashlib.md5(key.encode()).hexdigest(), 16) % (2**32)

    def add_node(self, node_name: str):
        """Add node to hash ring with virtual nodes"""
        if node_name in self.nodes:
            return

        self.nodes.add(node_name)

        # Create virtual nodes
        for i in range(self.virtual_nodes_per_node):
            virtual_node_key = f"{node_name}:{i}"
            position = self._hash(virtual_node_key)

            # Handle collision (unlikely but possible)
            while position in self.ring:
                position = (position + 1) % (2**32)

            self.ring[position] = node_name
            self.sorted_positions.append(position)

        # Keep positions sorted for efficient lookup
        self.sorted_positions.sort()

    def remove_node(self, node_name: str):
        """Remove node from hash ring"""
        if node_name not in self.nodes:
            return

        self.nodes.remove(node_name)

        # Remove all virtual nodes
        positions_to_remove = [
            pos for pos, node in self.ring.items()
            if node == node_name
        ]

        for position in positions_to_remove:
            del self.ring[position]
            self.sorted_positions.remove(position)

    def get_node(self, key: str) -> Optional[str]:
        """Get node responsible for key"""
        if not self.ring:
            return None

        key_position = self._hash(key)

        # Find first node clockwise from key position
        # Use binary search for efficiency
        idx = bisect_right(self.sorted_positions, key_position)

        # Wrap around if key is after all nodes
        if idx == len(self.sorted_positions):
            idx = 0

        position = self.sorted_positions[idx]
        return self.ring[position]

    def get_nodes(self) -> List[str]:
        """Get all node names"""
        return list(self.nodes)

# Usage
ring = ConsistentHashRing(virtual_nodes_per_node=150)

# Add nodes
ring.add_node("server-1")
ring.add_node("server-2")
ring.add_node("server-3")

# Get node for key
node = ring.get_node("user-123")
print(f"Key 'user-123' mapped to: {node}")

# Add new node (minimal rehashing)
ring.add_node("server-4")

# Remove node
ring.remove_node("server-2")

Java

"ConsistentHashRing.java

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;

public class ConsistentHashRing {
    private final int virtualNodesPerNode;
    private final TreeMap<Long, String> ring; // position -> node_name
    private final Set<String> nodes;

    public ConsistentHashRing(int virtualNodesPerNode) {
        this.virtualNodesPerNode = virtualNodesPerNode;
        this.ring = new TreeMap<>();
        this.nodes = new HashSet<>();
    }

    private long hash(String key) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[] digest = md.digest(key.getBytes());
            long hash = 0;
            for (int i = 0; i < 8; i++) {
                hash = (hash << 8) | (digest[i] & 0xFF);
            }
            return hash & 0xFFFFFFFFL; // 32-bit hash
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException(e);
        }
    }

    public void addNode(String nodeName) {
        if (nodes.contains(nodeName)) {
            return;
        }

        nodes.add(nodeName);

        // Create virtual nodes
        for (int i = 0; i < virtualNodesPerNode; i++) {
            String virtualNodeKey = nodeName + ":" + i;
            long position = hash(virtualNodeKey);

            // Handle collision
            while (ring.containsKey(position)) {
                position = (position + 1) % (1L << 32);
            }

            ring.put(position, nodeName);
        }
    }

    public void removeNode(String nodeName) {
        if (!nodes.contains(nodeName)) {
            return;
        }

        nodes.remove(nodeName);

        // Remove all virtual nodes
        ring.entrySet().removeIf(entry -> entry.getValue().equals(nodeName));
    }

    public String getNode(String key) {
        if (ring.isEmpty()) {
            return null;
        }

        long keyPosition = hash(key);

        // Find first node clockwise from key position
        Map.Entry<Long, String> entry = ring.ceilingEntry(keyPosition);

        // Wrap around if key is after all nodes
        if (entry == null) {
            entry = ring.firstEntry();
        }

        return entry.getValue();
    }

    public List<String> getNodes() {
        return new ArrayList<>(nodes);
    }
}

// Usage
ConsistentHashRing ring = new ConsistentHashRing(150);

ring.addNode("server-1");
ring.addNode("server-2");
ring.addNode("server-3");

String node = ring.getNode("user-123");
System.out.println("Key 'user-123' mapped to: " + node);

ring.addNode("server-4");
ring.removeNode("server-2");

TypeScript

consistent-hashing.ts

import * as crypto from 'crypto';

class ConsistentHashRing {
    // Consistent hash ring implementation
    private virtualNodesPerNode: number;
    private ring: Map<number, string>; // position -> node_name
    private sortedPositions: number[];
    private nodes: Set<string>;

    constructor(virtualNodesPerNode: number = 150) {
        this.virtualNodesPerNode = virtualNodesPerNode;
        this.ring = new Map();
        this.sortedPositions = [];
        this.nodes = new Set();
    }

    private hash(key: string): number {
        // Hash key to position on ring (0 to 2^32-1)
        const hash = crypto.createHash('md5').update(key).digest();
        // Convert first 4 bytes to 32-bit integer
        return hash.readUInt32BE(0);
    }

    addNode(nodeName: string): void {
        // Add node to hash ring with virtual nodes
        if (this.nodes.has(nodeName)) {
            return;
        }

        this.nodes.add(nodeName);

        // Create virtual nodes
        for (let i = 0; i < this.virtualNodesPerNode; i++) {
            const virtualNodeKey = `${nodeName}:${i}`;
            let position = this.hash(virtualNodeKey);

            // Handle collision
            while (this.ring.has(position)) {
                position = (position + 1) % (2 ** 32);
            }

            this.ring.set(position, nodeName);
            this.sortedPositions.push(position);
        }

        // Keep positions sorted for efficient lookup
        this.sortedPositions.sort((a, b) => a - b);
    }

    removeNode(nodeName: string): void {
        // Remove node from hash ring
        if (!this.nodes.has(nodeName)) {
            return;
        }

        this.nodes.delete(nodeName);

        // Remove all virtual nodes
        const positionsToRemove: number[] = [];
        this.ring.forEach((node, position) => {
            if (node === nodeName) {
                positionsToRemove.push(position);
            }
        });

        positionsToRemove.forEach(position => {
            this.ring.delete(position);
            const index = this.sortedPositions.indexOf(position);
            if (index > -1) {
                this.sortedPositions.splice(index, 1);
            }
        });
    }

    getNode(key: string): string | null {
        // Get node responsible for key
        if (this.ring.size === 0) {
            return null;
        }

        const keyPosition = this.hash(key);

        // Find first node clockwise from key position
        // Use binary search for efficiency
        let idx = this.sortedPositions.findIndex(pos => pos >= keyPosition);

        // Wrap around if key is after all nodes
        if (idx === -1) {
            idx = 0;
        }

        const position = this.sortedPositions[idx];
        return this.ring.get(position) || null;
    }

    getNodes(): string[] {
        // Get all node names
        return Array.from(this.nodes);
    }
}

// Usage
const ring = new ConsistentHashRing(150);

ring.addNode("server-1");
ring.addNode("server-2");
ring.addNode("server-3");

const node = ring.getNode("user-123");
console.log(`Key 'user-123' mapped to: ${node}`);

ring.addNode("server-4");
ring.removeNode("server-2");

C++

consistent_hashing.cpp

#include <string>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <openssl/md5.h>
#include <cstring>

class ConsistentHashRing {
private:
    int virtualNodesPerNode;
    std::map<uint32_t, std::string> ring; // position -> node_name
    std::vector<uint32_t> sortedPositions;
    std::set<std::string> nodes;

    uint32_t hash(const std::string& key) {
        // Hash key to position on ring (0 to 2^32-1)
        unsigned char digest[MD5_DIGEST_LENGTH];
        MD5((unsigned char*)key.c_str(), key.length(), digest);

        // Convert first 4 bytes to 32-bit integer
        uint32_t hashValue = 0;
        for (int i = 0; i < 4; i++) {
            hashValue = (hashValue << 8) | digest[i];
        }
        return hashValue;
    }

public:
    ConsistentHashRing(int virtualNodesPerNode = 150)
        : virtualNodesPerNode(virtualNodesPerNode) {}

    void addNode(const std::string& nodeName) {
        // Add node to hash ring with virtual nodes
        if (nodes.find(nodeName) != nodes.end()) {
            return;
        }

        nodes.insert(nodeName);

        // Create virtual nodes
        for (int i = 0; i < virtualNodesPerNode; i++) {
            std::string virtualNodeKey = nodeName + ":" + std::to_string(i);
            uint32_t position = hash(virtualNodeKey);

            // Handle collision
            while (ring.find(position) != ring.end()) {
                position = (position + 1) % (1ULL << 32);
            }

            ring[position] = nodeName;
            sortedPositions.push_back(position);
        }

        // Keep positions sorted for efficient lookup
        std::sort(sortedPositions.begin(), sortedPositions.end());
    }

    void removeNode(const std::string& nodeName) {
        // Remove node from hash ring
        if (nodes.find(nodeName) == nodes.end()) {
            return;
        }

        nodes.erase(nodeName);

        // Remove all virtual nodes
        std::vector<uint32_t> positionsToRemove;
        for (const auto& pair : ring) {
            if (pair.second == nodeName) {
                positionsToRemove.push_back(pair.first);
            }
        }

        for (uint32_t position : positionsToRemove) {
            ring.erase(position);
            sortedPositions.erase(
                std::remove(sortedPositions.begin(), sortedPositions.end(), position),
                sortedPositions.end()
            );
        }
    }

    std::string getNode(const std::string& key) {
        // Get node responsible for key
        if (ring.empty()) {
            return "";
        }

        uint32_t keyPosition = hash(key);

        // Find first node clockwise from key position
        auto it = std::lower_bound(sortedPositions.begin(), sortedPositions.end(), keyPosition);

        // Wrap around if key is after all nodes
        if (it == sortedPositions.end()) {
            it = sortedPositions.begin();
        }

        uint32_t position = *it;
        return ring[position];
    }

    std::vector<std::string> getNodes() {
        // Get all node names
        return std::vector<std::string>(nodes.begin(), nodes.end());
    }
};

// Usage
int main() {
    ConsistentHashRing ring(150);

    ring.addNode("server-1");
    ring.addNode("server-2");
    ring.addNode("server-3");

    std::string node = ring.getNode("user-123");
    std::cout << "Key 'user-123' mapped to: " << node << std::endl;

    ring.addNode("server-4");
    ring.removeNode("server-2");

    return 0;
}

C#

ConsistentHashRing.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;

public class ConsistentHashRing {
    // Consistent hash ring implementation
    private readonly int virtualNodesPerNode;
    private readonly SortedDictionary<uint, string> ring; // position -> node_name
    private readonly HashSet<string> nodes;

    public ConsistentHashRing(int virtualNodesPerNode = 150) {
        this.virtualNodesPerNode = virtualNodesPerNode;
        this.ring = new SortedDictionary<uint, string>();
        this.nodes = new HashSet<string>();
    }

    private uint Hash(string key) {
        // Hash key to position on ring (0 to 2^32-1)
        using (var md5 = MD5.Create()) {
            byte[] hash = md5.ComputeHash(Encoding.UTF8.GetBytes(key));
            // Convert first 4 bytes to 32-bit integer
            return BitConverter.ToUInt32(hash, 0);
        }
    }

    public void AddNode(string nodeName) {
        // Add node to hash ring with virtual nodes
        if (nodes.Contains(nodeName)) {
            return;
        }

        nodes.Add(nodeName);

        // Create virtual nodes
        for (int i = 0; i < virtualNodesPerNode; i++) {
            string virtualNodeKey = $"{nodeName}:{i}";
            uint position = Hash(virtualNodeKey);

            // Handle collision
            while (ring.ContainsKey(position)) {
                position = (position + 1) % (1U << 32);
            }

            ring[position] = nodeName;
        }
    }

    public void RemoveNode(string nodeName) {
        // Remove node from hash ring
        if (!nodes.Contains(nodeName)) {
            return;
        }

        nodes.Remove(nodeName);

        // Remove all virtual nodes
        var positionsToRemove = ring
            .Where(pair => pair.Value == nodeName)
            .Select(pair => pair.Key)
            .ToList();

        foreach (uint position in positionsToRemove) {
            ring.Remove(position);
        }
    }

    public string GetNode(string key) {
        // Get node responsible for key
        if (ring.Count == 0) {
            return null;
        }

        uint keyPosition = Hash(key);

        // Find first node clockwise from key position
        var entry = ring.FirstOrDefault(pair => pair.Key >= keyPosition);

        // Wrap around if key is after all nodes
        if (entry.Key == 0 && entry.Value == null) {
            entry = ring.First();
        }

        return entry.Value;
    }

    public List<string> GetNodes() {
        // Get all node names
        return nodes.ToList();
    }
}

// Usage
var ring = new ConsistentHashRing(150);

ring.AddNode("server-1");
ring.AddNode("server-2");
ring.AddNode("server-3");

string node = ring.GetNode("user-123");
Console.WriteLine($"Key 'user-123' mapped to: {node}");

ring.AddNode("server-4");
ring.RemoveNode("server-2");

Use Cases

Distributed Caching

Consistent hashing is widely used in distributed caches like Memcached and Redis Cluster. When a cache node is added or removed, only a fraction of keys need to be remapped, minimizing cache misses.

Example: A cache cluster with 10 nodes. Adding one node remaps only ~10% of keys instead of 100%.

Load Balancing

Load balancers use consistent hashing to route requests to backend servers. This ensures:

• Session affinity: Same user always routed to same server (if using user ID as key)
• Minimal disruption: Adding/removing servers doesn’t affect most requests

Database Sharding

Distributed databases use consistent hashing to determine which shard stores a record. This enables:

• Horizontal scaling: Add shards without massive data migration
• Fault tolerance: Remove failed shards with minimal impact

CDN Content Routing

Content delivery networks use consistent hashing to route requests to edge servers. Ensures content is served from the same server for cache efficiency.

Trade-offs

Advantages:

• Minimal rehashing when nodes change
• Good load distribution (with virtual nodes)
• Handles node failures gracefully
• Scales horizontally

Disadvantages:

• More complex than simple hashing
• Requires sorted data structure for efficient lookup
• Virtual nodes increase memory usage
• Can have uneven distribution without virtual nodes

Key Takeaways

Minimal Rehashing

Only k/n keys need remapping when k nodes are added. Much better than traditional hashing where all keys remap.

Hash Ring

Circular space where keys and nodes are mapped. Keys assigned to first node clockwise from their position.

Virtual Nodes

Multiple hash positions per physical node improve load distribution and handle different node capacities.

Efficient Lookup

Use sorted data structure (TreeMap, sorted array) with binary search for O(log n) key lookup.

---

Next Steps

• Learn Distributed Caching - consistent hashing used in cache clusters
• Master Database Sharding - consistent hashing for shard selection
• Understand Load Balancing - consistent hashing for request routing