Skip to content

12 · Consistent Hashing — Distribute Keys Across Rotating Nodes

Performance & Distribution · Topic 12 of 13


The Problem with Simple Hashing

With shard = hash(key) % N, adding or removing a node changes N — causing almost all keys to remap. In a cache cluster, this causes a cache stampede.


Consistent Hashing

Map both keys and nodes onto the same hash ring (0 to 2³²). A key is assigned to the first node clockwise from its hash position.

graph TD
    Ring["Hash Ring (0 → 2³²)"]
    Ring --> N1["Node A @ 100"]
    Ring --> N2["Node B @ 300"]
    Ring --> N3["Node C @ 700"]
    Ring --> K1["Key X @ 150 → Node B"]
    Ring --> K2["Key Y @ 400 → Node C"]

Adding a node: only keys between the new node and its predecessor remap. Removing a node: only keys on that node remap to the next node.

On average, only K/N keys remap (K = total keys, N = nodes).


Virtual Nodes (vnodes)

A single physical node maps to multiple points on the ring. This:

  • Ensures even distribution even with heterogeneous nodes
  • Reduces the impact of a single node's failure

Cloud Implementations

  • Uses consistent hashing with vnodes by default
  • num_tokens controls vnodes per node; defaults vary by Cassandra release and configuration
  • Murmur3Partitioner is the default hash function
  • Hashes partition-key values to managed partitions
  • Internal placement is not a public ring API; do not infer today's implementation from the original Amazon Dynamo paper
  • 16,384 hash slots distributed across nodes
  • Key → CRC16(key) % 16384 → slot → node
  • Hash tags {user}.session force co-location of related keys
  • Client-side consistent hashing (e.g., ketama algorithm)
  • Adding nodes remaps minimal keys

Key Takeaways

Aspect Simple Hashing Consistent Hashing
Keys remapped on node change ~All ~K/N
Even distribution Yes With vnodes
Complexity Low Medium

Placement Does Not Solve Ownership Changes

For N equal-capacity nodes, adding one node moves about 1/(N+1) of keys in expectation; removing one moves about 1/N. This assumes a balanced hash distribution. Virtual nodes smooth key counts but cannot split a single hot key's traffic. Replication adds a separate rule for selecting distinct failure domains.

During a ring change, clients may hold different membership views. A durable database needs migration, forwarding or versioned routing to avoid lost writes; cache clients may instead tolerate misses. Redis Cluster's fixed slots are a related indirection strategy, not a literal clockwise hash ring.

Check Your Understanding

#

Question 1

Does consistent hashing guarantee balanced CPU usage?

#

Question 2

Why use virtual nodes?