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

CassandraDynamoDBRedis ClusterDistributed Caches (Memcached)

• Uses consistent hashing with vnodes by default
• num_tokens controls vnodes per node (default: 256)
• Murmur3Partitioner is the default hash function

• Internally uses consistent hashing for partition placement
• Abstracted from the user — you set partition key, AWS handles ring

• 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

---