Consistent Hashing

Consistent hashing is a distributed hashing algorithm that enables efficient data partitioning across a dynamic set of nodes, minimizing data movement when nodes are added or removed from the system.

The Problem: Traditional Hashing Doesn’t Scale

Modulo Arithmetic's Hidden Cost

The innocuous % operator in traditional hashing creates catastrophic data movement when clusters grow—a single node addition reshuffles 80% of all keys.

Traditional hashing uses modulo arithmetic: node = hash(key) % N where N is the number of nodes.

Fatal flaw: When N changes (node added/removed), almost all keys need to be remapped:

• Adding a node: hash(key) % 4 → hash(key) % 5 changes mapping for ~80% of keys
• Removing a node: hash(key) % 5 → hash(key) % 4 changes mapping for ~75% of keys

This causes massive data movement and service disruption in distributed systems.

The Algorithm: Hash Ring Model

Consistent hashing maps both keys and nodes onto a circular hash space (typically 0 to 2^160 - 1).

graph TB
    subgraph "Hash Ring (0° to 360°)"
        direction LR
        A[Node A<br/>hash: 45°]
        B[Node B<br/>hash: 135°]
        C[Node C<br/>hash: 225°]
        D[Node D<br/>hash: 315°]

        K1[Key K1<br/>hash: 20°]
        K2[Key K2<br/>hash: 100°]
        K3[Key K3<br/>hash: 180°]
        K4[Key K4<br/>hash: 270°]
    end

    K1 -->|Walk clockwise| A
    K2 -->|Walk clockwise| B
    K3 -->|Walk clockwise| C
    K4 -->|Walk clockwise| D

Key Assignment Algorithm

1. Hash each node to a position on the ring: position = hash(node_id)
2. For a given key, compute its hash: position = hash(key)
3. Walk clockwise from the key’s position until you find the first node
4. That node is responsible for the key

Minimal Disruption Property

When a node is added or removed, only keys in one segment of the ring are affected:

Adding Node X (between A and B):

• Keys that previously mapped to B but hash before X now map to X
• All other keys remain unchanged
• On average, only K/N keys move (where K = total keys, N = number of nodes)

Removing Node B:

• Only keys that mapped to B are affected
• They remap to the next node clockwise (C)
• All other keys remain unchanged

This is the core advantage: O(K/N) keys move versus O(K) in traditional hashing.

graph LR
    subgraph Before Adding Node X
        A1[Node A] --- B1[Node B] --- C1[Node C] --- A1
    end

    subgraph After Adding Node X
        A2[Node A] --- X[Node X] --- B2[Node B] --- C2[Node C] --- A2
    end

    B1 -.->|Only keys between<br/>A and X move| X

Load Distribution Challenge

With random node placement, the variance in load can be significant. Some nodes might receive 2x the average load, while others receive 0.5x.

The probability that a node receives a load outside the range [0.5 * K/N, 2 * K/N] is non-negligible with small numbers of nodes.

Why this happens: Random placement creates uneven spacing between nodes on the ring, leading to different-sized hash ranges per node.

Randomness Creates Predictability

Virtual nodes harness the law of large numbers—introducing more randomness at the virtual level produces more uniform distribution at the physical level.

Solution: Virtual Nodes

Virtual nodes solve the load distribution problem by mapping each physical node to multiple positions on the ring. This is the key innovation that makes consistent hashing practical for production systems like Dynamo.

Use Cases

Distributed Caches

Systems like Memcached use consistent hashing to distribute cache entries across servers. When a cache server fails, only its entries need to be refetched—other servers continue serving their data.

Content Delivery Networks (CDNs)

Content is distributed across edge servers using consistent hashing. Adding a new edge location only requires moving a small fraction of content.

Distributed Databases

Dynamo, Cassandra, and Riak use consistent hashing to partition data. This enables incremental scalability—adding one node at a time without massive reorganization.

Load Balancing

Requests can be consistently routed to backend servers. Sticky sessions naturally emerge: the same user consistently hits the same server (until topology changes).

Implementation Considerations

Hash Function Choice

Requirements:

• Uniform distribution: Keys should spread evenly across the hash space
• Fast computation: Hash is computed frequently
• Deterministic: Same input always produces same output

Common choices: MD5, SHA-1, MurmurHash

Ring Data Structure

Efficient implementations use sorted data structures:

• Sorted array with binary search: O(log N) lookups
• Balanced tree (Red-Black, AVL): O(log N) lookups and updates
• Skip list: O(log N) expected time, simpler implementation

Replication Integration

Consistent hashing naturally supports replication strategies in distributed systems:

• After finding the coordinator node for a key, continue walking clockwise to find N successor nodes
• These N nodes form the replication set (preference list in Dynamo)
• Ensures replicas are distributed across different parts of the ring

Limitations

Hot spots: If keys are not uniformly distributed (e.g., popular items accessed frequently), some nodes become hotspots even with perfect hashing. Virtual nodes help but don’t fully solve this.

Zone awareness: Basic consistent hashing doesn’t account for physical topology (racks, datacenters). Enhanced versions assign virtual nodes to ensure replicas span multiple failure domains.

Rebalancing cost: While minimal compared to traditional hashing, moving O(K/N) keys during node changes still requires network bandwidth and can impact performance.

Key Insight

Consistent hashing transforms system design by making distributed systems elastic. The ability to add or remove nodes with minimal disruption enables:

• Incremental scaling (add capacity gradually)
• Graceful handling of failures (remove failed nodes without chaos)
• Cost optimization (scale down during low-traffic periods)

The algorithm demonstrates that small changes to how we think about partitioning—using a ring instead of modulo arithmetic—can dramatically improve system properties. When combined with virtual nodes, it becomes the foundation for highly scalable data persistence systems.