Consistent Hashing

Consistent hashing is a technique for distributing data across a cluster of nodes such that adding or removing a node only requires remapping a small fraction of the keys, rather than reshuffling everything.

What It Really Means

In traditional hashing (e.g., hash(key) % N), every key's assignment depends on N — the number of nodes. When you add or remove a node, N changes, and nearly every key maps to a different node. For a system with a billion keys, this means moving almost a billion entries. That is catastrophic.

Consistent hashing solves this by mapping both nodes and keys onto a circular hash space (a "ring" from 0 to 2^32 - 1). Each key is assigned to the first node encountered when walking clockwise around the ring from the key's hash position. When a node joins or leaves, only the keys between it and its predecessor on the ring need to be remapped — typically 1/N of the total keys.

The technique was formalized in the 1997 paper by David Karger et al. at MIT, originally motivated by web caching. It has since become foundational in distributed databases, CDNs, and load balancers. Systems like Amazon DynamoDB, Apache Cassandra, Akamai's CDN, and Discord's message routing all rely on consistent hashing.

How It Works in Practice

The Hash Ring

Imagine a circle representing the hash space 0, 2^32). Each node gets hashed to a position on this ring. Each data key also gets hashed to a position. The key is stored on the first node found by walking clockwise from the key's position. [blocked]

Example with 3 nodes:

• Node A hashes to position 100
• Node B hashes to position 400
• Node C hashes to position 700
• Key "user:1234" hashes to position 350 → stored on Node B (first node clockwise)
• Key "order:5678" hashes to position 500 → stored on Node C

When Node D joins at position 250, only keys between positions 100 and 250 (previously assigned to Node B) move to Node D. Keys assigned to Node A and Node C are not affected.

Virtual Nodes (Vnodes)

With only a few physical nodes, the distribution can be uneven — one node might own 60% of the ring while another owns 10%. Virtual nodes solve this by mapping each physical node to multiple positions on the ring (typically 128-256 vnodes per physical node).

How Cassandra uses vnodes: Each Cassandra node claims 256 tokens (positions) on the ring by default. This creates fine-grained partitions and ensures that when a node joins, it takes a proportional share of data from all existing nodes, not just its ring neighbors.

Real-World: Amazon DynamoDB

DynamoDB partitions data across storage nodes using consistent hashing on the partition key. When a table grows and needs more partitions, DynamoDB splits a partition by dividing its hash range — only the data in that range migrates. Other partitions are unaffected. This is why choosing a good partition key (high cardinality, uniform distribution) is critical for DynamoDB performance.

Real-World: Discord

Discord routes messages to the correct Elixir process using consistent hashing on guild (server) IDs. When a new process node is added, only a subset of guilds are rehomed. This minimizes disruption to active voice and text sessions.

Implementation

Trade-offs

Advantages

• Minimal redistribution: Adding or removing a node only moves ~1/N of the keys, where N is the number of nodes
• Decentralized: No central directory needed; any node can compute key ownership independently
• Horizontal scaling: Nodes can join and leave without a global reshuffle
• Flexible replication: Walk further clockwise to find replica nodes (e.g., store on the next 2 nodes for RF=3)

Disadvantages

• Load imbalance without vnodes: A small number of physical nodes can create hot spots. Virtual nodes are essential in practice.
• Hash function dependency: A poor hash function leads to clustering. Use cryptographic hashes (MD5, SHA-1) or xxHash for uniform distribution.
• Range queries are expensive: Consistent hashing scatters sequential keys across nodes. Systems that need range queries (like HBase) use range-based partitioning instead.
• Node heterogeneity: If nodes have different capacities, you need weighted vnodes, which adds complexity.

Common Misconceptions

• "Consistent hashing guarantees perfect load balance" — Without virtual nodes, load distribution can be highly skewed. Even with vnodes, you may see 10-15% variance. True uniformity requires careful tuning of vnode counts and occasional rebalancing.

• "Consistent hashing is the same as rendezvous hashing" — Rendezvous (highest random weight) hashing is a different algorithm that also achieves minimal disruption. It computes a score for each node-key pair and picks the highest score. It avoids the ring abstraction entirely.

• "Adding a node moves exactly 1/N of all keys" — This is the expected average with many vnodes. In practice, the actual number depends on where the vnodes land on the ring. With few vnodes or an unlucky hash distribution, the variance can be significant.

• "You need consistent hashing for any distributed system" — Many systems use simpler range-based partitioning (e.g., HBase, CockroachDB) or directory-based sharding. Consistent hashing is most valuable when nodes frequently join and leave.

• "Consistent hashing handles replication automatically" — The ring determines primary ownership. Replication requires additional logic: walking the ring to find distinct physical nodes for replicas, handling consistency levels, and managing anti-entropy.

How This Appears in Interviews

Consistent hashing is a top-tier system design interview topic. Expect to draw the ring on a whiteboard:

• "Design a distributed cache" — use consistent hashing for key routing, explain vnodes for load balance, discuss cache invalidation strategies. Check our interview questions on caching.
• "How does Cassandra distribute data?" — explain the ring, vnodes, replication factor, and consistency levels. See system design guides.
• "A node goes down. What happens to its data?" — explain how keys remap to the next node clockwise, how replication ensures availability, and how hinted handoff works during recovery.
• "How would you handle hot keys?" — discuss replication of hot partitions, caching layers, or key-splitting strategies. This goes beyond consistent hashing into sharding and caching design.

Related Concepts

• Database Sharding — Broader strategies for distributing data across nodes
• CAP Theorem — The trade-offs that consistent hashing operates within
• Eventual Consistency — The consistency model often paired with consistent hashing
• Gossip Protocol — How nodes in a consistent hash ring discover each other
• System Design Interview Guide — Framework for answering design questions
• Algoroq Pricing — Practice distributed systems interview questions