Consistent Hashing: Scalable Routing for Distributed Caches and Storage

In distributed caching and storage clusters, incoming keys must be partitioned across multiple server nodes. A naive approach maps keys to servers using the modulo hash formula: `server_index = hash(key) % N`, where N is the number of active server nodes.

However, if a server node crashes or the cluster scales horizontally by adding a new server (changing N to N + 1 or N - 1), almost every existing key remaps to a completely different server index. In a production cache cluster, this triggers a catastrophic cache stampede (thundering herd), collapsing backend databases under sudden load.

Consistent Hashing—introduced by David Karger et al. in 1997—solves this fundamental scalability challenge by ensuring that when a node is added or removed, only `K / N` keys need to be remapped on average (where K is the total number of keys and N is the number of servers).

The Hash Ring (Circle) Architecture

Consistent Hashing maps both data keys and server nodes onto a circular continuum known as a Hash Ring:

• Uniform Hash Range: Assume a 32-bit hash function (such as Murmur3 or MD5) whose output space spans the integer range [0, 2^32 - 1]. The end of the range wraps seamlessly back to 0, forming a continuous circle.
• Mapping Server Nodes: Each server's unique identifier (e.g., its IP address or hostname) is hashed to place the node at a fixed coordinate on the ring.
• Mapping Data Keys: Incoming data keys are hashed using the exact same hash function to locate their position on the perimeter.
• Clockwise Routing: To determine which server stores a given key, start at the key's position on the ring and traverse clockwise until the first server node is encountered. That node becomes the owner of the key.

Handling Node Additions and Removals

1. Adding a New Node

When Node X is placed onto the ring between Node A and Node B, it intercepts only those keys situated along the ring arc between Node A and Node X. All other keys on the rest of the ring remain unaffected and continue routing to their existing server nodes.

2. Removing / Failure of a Node

If Node B crashes, only the keys previously owned by Node B fall forward to its immediate clockwise successor (Node C). The remaining partitions across all other nodes stay undisturbed.

Virtual Nodes (Vnodes): Preventing Non-Uniform Data Skew

A basic Consistent Hash Ring with only a few physical nodes suffers from two major problems: non-uniform partition distribution (some nodes own vast segments of the ring while others hold slivers) and heterogeneous server capacity mismatches.

The solution is Virtual Nodes (Vnodes). Instead of hashing a physical server once, the system hashes each physical server multiple times using distinct labels (e.g., `Server1#1`, `Server1#2`, ..., `Server1#150`):

• Uniform Distribution: By allocating 100 to 256 virtual nodes per physical machine, ownership slices become evenly interleaved across the entire 360-degree perimeter.
• Graceful Cascades: When a physical node fails, its many virtual nodes disappear across various points on the ring, spreading the migration load evenly across all remaining machines instead of overwhelming a single neighbor.
• Weighted Heterogeneity: High-capacity servers with more RAM/CPU can simply be assigned more virtual node tokens than smaller machines.

C++ Implementation Blueprint

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <sstream>

class ConsistentHashRing {
private:
    int num_replicas; // Virtual nodes per physical node
    std::map<size_t, std::string> ring; // Sorted map for O(log N) binary search lookup

    size_t hash(const std::string& key) const {
        return std::hash<std::string>{}(key);
    }

public:
    ConsistentHashRing(int replicas = 100) : num_replicas(replicas) {}

    void addServer(const std::string& server) {
        for (int i = 0; i < num_replicas; ++i) {
            std::stringstream ss;
            ss << server << "#vnode_" << i;
            size_t token = hash(ss.str());
            ring[token] = server;
        }
    }

    void removeServer(const std::string& server) {
        for (int i = 0; i < num_replicas; ++i) {
            std::stringstream ss;
            ss << server << "#vnode_" << i;
            size_t token = hash(ss.str());
            ring.erase(token);
        }
    }

    std::string getServer(const std::string& key) const {
        if (ring.empty()) return "";
        
        size_t key_hash = hash(key);
        // std::map::lower_bound executes binary search for clockwise successor in O(log N)
        auto it = ring.lower_bound(key_hash);
        
        // If key_hash is greater than all tokens, wrap around to the first node on the ring
        if (it == ring.end()) {
            it = ring.begin();
        }
        return it->second;
    }
};

Real-World Distributed Systems Applications

1. Amazon DynamoDB & Apache Cassandra: Partitioning primary partition keys across storage cluster rings to determine read/write quorum replicas without centralized coordinators.
2. Ketama Client Algorithm (Memcached): Standardizing consistent hashing implementations across client libraries to prevent multi-server cache invalidation on cluster resizing.
3. Reverse Proxies & L7 Load Balancers (HAProxy, NGINX, Envoy): Sticky session management and connection pooling routing client IP sessions to upstream backends.
4. Peer-to-Peer Networks (Chord DHT): Distributed lookup protocols mapping cryptographic SHA-1 identifiers to peers across decentralized networks.