Consistent Hashing: How Distributed Systems Route Traffic

Consistent hashing is one of the most commonly asked system design concepts at big tech companies. You will almost certainly encounter it when designing distributed caches, databases, or content delivery networks. The question often sounds like: “You have a cluster of cache servers. How do you decide which server stores which key — and what happens when you add or remove a server?”

Strategy

Before jumping to the solution, show the interviewer you understand why naïve approaches fail. Start with the obvious answer and build up from there.

Naïve approach: server_index = hash(key) % num_servers

This works fine when the number of servers never changes. But if you add a server, num_servers changes and almost every key remaps to a different server. For a cache, that means a thundering herd of cache misses all at once. For a database with data partitioned by key, it means you need to migrate nearly all your data.

The question consistent hashing answers: how do we distribute keys so that adding or removing a node only remaps a small fraction of keys?

Solution

The Hash Ring

Imagine a ring (a circle) with positions from 0 to 2³²−1 (or any large number). You hash both server identifiers and keys onto this ring.

Hash each server name/IP to a position on the ring: hash("server-A") → 12, hash("server-B") → 45, hash("server-C") → 78.
To look up a key, hash it to a position, then walk clockwise around the ring until you hit a server.

        hash("server-B") = 45
               ↑
0──────12──────45──────78──────(back to 0)
        ↑               ↑
hash("server-A")   hash("server-C")

If hash("my-key") = 30, walking clockwise from 30 hits server-B at 45. That’s where the key lives.

Adding a Server

Add server-D at position 60. Keys that were walking from 46 to 78 and landing on server-C now land on server-D instead. Only those keys move — everything else stays put. On average you only need to remap 1/n of keys when adding the nth server.

Removing a Server

Same logic in reverse. Remove server-B at 45. Keys that were landing on B now walk further clockwise to server-C. Only the keys that were on B need to move.

The Virtual Nodes Problem (and Solution)

With only three physical positions on the ring, the distribution is uneven — one server might hold 60% of the keys while another holds 5%. To fix this, each physical server gets mapped to multiple positions on the ring, called virtual nodes (vnodes).

Instead of hashing “server-A” once, you hash “server-A-1”, “server-A-2”, …, “server-A-150”. Now server-A has 150 positions scattered around the ring, and the key distribution is much more uniform.

// Python pseudocode
import hashlib

class ConsistentHashRing:
    def __init__(self, nodes, virtual_nodes=150):
        self.ring = {}
        self.sorted_keys = []
        for node in nodes:
            for i in range(virtual_nodes):
                vnode_key = f"{node}-{i}"
                h = int(hashlib.md5(vnode_key.encode()).hexdigest(), 16)
                self.ring[h] = node
        self.sorted_keys = sorted(self.ring.keys())

    def get_node(self, key):
        h = int(hashlib.md5(key.encode()).hexdigest(), 16)
        for ring_key in self.sorted_keys:
            if h <= ring_key:
                return self.ring[ring_key]
        # wrap around
        return self.ring[self.sorted_keys[0]]

Where You’ll See This in the Real World

Amazon DynamoDB / Apache Cassandra: Both use consistent hashing with vnodes to distribute data across storage nodes. Cassandra defaults to 256 vnodes per physical node.
Memcached / Redis Cluster: Client libraries use consistent hashing to route cache key lookups to the right server without a central coordinator.
CDNs (Akamai, Cloudflare): Route requests to the nearest/least-loaded edge server while minimizing cache invalidation when nodes go up or down.
Load balancers (HAProxy, nginx): Consistent hashing on session IDs keeps a user’s requests hitting the same backend (sticky sessions without cookies).

Trade-offs and Follow-up Questions

Interviewers will push here. Know these cold:

Q: What if one server is much more powerful than others?
Give it more vnodes. A server with 2× the capacity gets 2× the vnodes, so it handles roughly 2× the keys.

Q: How do you handle replication?
Instead of storing a key on just the first node clockwise, store it on the first N nodes clockwise (N = replication factor). Cassandra and Dynamo do exactly this.

Q: What about hot spots — a single key getting millions of requests?
Consistent hashing distributes keys across nodes, but it doesn’t help if one key is overwhelmingly popular. You’d handle that separately: local caching, read replicas, or key sharding with a suffix (append a random number 0–9 to the key to spread load, then aggregate on read).

Q: What hashing function should you use?
MD5 or SHA-1 give good distribution. MurmurHash3 or xxHash are faster and equally uniform — better choices in practice. Avoid CRC32 (poor distribution) and cryptographic hashes like SHA-256 (unnecessary overhead).

Q: Consistent hashing vs. rendezvous hashing?
Rendezvous hashing (also called Highest Random Weight) achieves the same goal — minimal remapping when nodes change — but differently: for each key, score every node with hash(key + node) and pick the highest score. Simpler to implement, equally correct, but O(n) per lookup vs O(log n) for the ring. Fine for small clusters; consistent hashing wins at scale.

Summary

Consistent hashing solves the key remapping problem in distributed systems by placing both servers and keys on a hash ring and routing each key to the nearest server clockwise. Virtual nodes fix the uneven distribution problem. The practical result: adding or removing a server only displaces ~1/n of the keys instead of remapping everything.

When you see a distributed cache, database, or CDN in a system design interview, consistent hashing is almost always the right answer for how data gets routed to nodes.