Consistent Hashing Explained

Consistent hashing is a technique that distributes data across servers in a way that minimizes redistribution when servers are added or removed. It solves the fundamental problem with modulo hashing: adding or removing a server remaps almost every key.

1. The Problem with Modulo Hashing

graph TD
    subgraph "Modulo Hashing: 4 servers"
        K1["key1 hash=7"] -->|"7 % 4 = 3"| S4["Server 4"]
        K2["key2 hash=12"] -->|"12 % 4 = 0"| S1["Server 1"]
        K3["key3 hash=19"] -->|"19 % 4 = 3"| S4
        K4["key4 hash=25"] -->|"25 % 4 = 1"| S2["Server 2"]
    end
    subgraph "Add Server 5 → Almost ALL keys remap"
        K1B["key1 hash=7"] -->|"7 % 5 = 2"| S3["Server 3"]
        K2B["key2 hash=12"] -->|"12 % 5 = 2"| S3
        K3B["key3 hash=19"] -->|"19 % 5 = 4"| S5["Server 5"]
        K4B["key4 hash=25"] -->|"25 % 5 = 0"| S1B["Server 1"]
    end

    style S4 fill:#F8D7DA,stroke:#DC3545
    style S3 fill:#D4EDDA,stroke:#28A745
    style S5 fill:#D4EDDA,stroke:#28A745

With modulo hashing (server = hash(key) % N), adding or removing a server changes the modulus, causing almost every key to remap. This means massive data migration : unacceptable at scale.

2. The Hash Ring Solution

graph TD
    Ring["Hash Ring
(0 to 2^32 - 1)"]
    S1["Server 1
hash position: 0"]
    S2["Server 2
hash position: 8"]
    S3["Server 3
hash position: 14"]
    K1["key1 hash=2
→ clockwise → Server 2"]
    K2["key2 hash=10
→ clockwise → Server 3"]
    K3["key3 hash=15
→ clockwise → Server 1 (wrap)"]

    Ring --> S1
    Ring --> S2
    Ring --> S3

    style Ring fill:#D97A2B,stroke:#B86418,color:#fff
    style S1 fill:#FAF6EE,stroke:#E8DFC8
    style S2 fill:#FAF6EE,stroke:#E8DFC8
    style S3 fill:#FAF6EE,stroke:#E8DFC8

Consistent hashing maps both keys and servers onto a circular ring (0 to 2^32 - 1). To find which server handles a key, hash the key and walk clockwise on the ring until you hit a server.

When a server is added, only the keys between the new server and its predecessor need to move. When a server is removed, only its keys need to move to the next server clockwise.

3. Implementation

class ConsistentHashRing {
  private ring: Map<number, string> = new Map();
  private sortedKeys: number[] = [];

  addServer(server: string) {
    const hash = this.hash(server);
    this.ring.set(hash, server);
    this.sortedKeys.push(hash);
    this.sortedKeys.sort((a, b) => a - b);
  }

  getServer(key: string): string {
    const hash = this.hash(key);
    // Find the first server clockwise
    for (const ringKey of this.sortedKeys) {
      if (ringKey >= hash) return this.ring.get(ringKey)!;
    }
    // Wrap around to first server
    return this.ring.get(this.sortedKeys[0])!;
  }
}

4. Virtual Nodes

graph TD
    subgraph "Without Virtual Nodes"
        Bad["Uneven distribution
Server 1: 70% of keys
Server 2: 20% of keys
Server 3: 10% of keys"]
    end
    subgraph "With 150 Virtual Nodes Each"
        Good["Even distribution
Server 1: 33% of keys
Server 2: 33% of keys
Server 3: 34% of keys"]
    end

    style Bad fill:#F8D7DA,stroke:#DC3545
    style Good fill:#D4EDDA,stroke:#28A745

The basic hash ring has uneven distribution : some servers get more keys than others. Virtual nodes solve this: each physical server gets multiple positions on the ring (e.g., 150 virtual nodes per server). This statistically guarantees even distribution.

More virtual nodes = better balance, at the cost of more memory for the ring data structure.

5. Adding/Removing Servers

graph LR
    Before["Before: 3 servers
keys spread across S1, S2, S3"]
    Add["Add Server 4"]
    After["After: 4 servers
Only keys between S3→S4 move
Everything else stays put"]

    Before --> Add --> After

    style Before fill:#FAF6EE,stroke:#E8DFC8
    style Add fill:#D97A2B,stroke:#B86418,color:#fff
    style After fill:#D4EDDA,stroke:#28A745

With consistent hashing, adding a server only moves the keys between the new server and its predecessor. With 3 servers and 1M keys, adding a 4th server moves ~250K keys (25%) instead of ~750K keys (75%) with modulo hashing.

6. Real-World Usage

• Amazon DynamoDB: Uses consistent hashing to distribute data across storage nodes.
• Apache Cassandra: Uses consistent hashing with virtual nodes for partition distribution.
• CDNs: Akamai and Cloudflare use consistent hashing to route requests to edge servers.
• Memcached: Client libraries use consistent hashing to distribute keys across cache nodes.
• Load balancers: Session affinity via consistent hashing of client IP.

7. Common Interview Mistakes

• Not using virtual nodes: Without them, data distribution is severely uneven, especially with a small number of servers.
• Using a poor hash function: Use MurmurHash3 or CityHash, not MD5 (too slow) or Java's default hashCode (poor distribution).
• Ignoring server weights: Not all servers have equal capacity. Virtual nodes should be proportional to server capacity.
• Forgetting about replication: Consistent hashing distributes data but doesn't replicate it. You need separate replication logic for fault tolerance.
• Not monitoring distribution: Track key count per server to detect imbalance early.

8. Summary