💍 Consistent Hashing

Architecture Diagram — Hash Ring

How It Works

Imagine a ring (circle) representing the entire hash space [0, 2³²). Both nodes and keys are hashed onto this ring. Each key is assigned to the first node encountered clockwise from the key's position.

The Problem with Naive Hashing

With simple hash(key) % N, adding or removing a server changes N, causing nearly all keys to be remapped. For a cache cluster, this means a near-100% miss rate — catastrophic.

Consistent Hashing Solution

When a node is added, only keys between the new node and its predecessor (counter-clockwise) need to move — roughly K/N keys (where K = total keys, N = total nodes). When a node is removed, only its keys move to the next node clockwise.

Virtual Nodes (Vnodes)

With few physical nodes, the ring can be unbalanced (one node owns a huge arc). Virtual nodes solve this: each physical node creates 100–200 virtual nodes spread around the ring. This gives near-uniform distribution.

• Physical Node A → vnode_A_0, vnode_A_1, ..., vnode_A_149 (spread evenly)
• More vnodes = better balance but more memory for the ring map
• Heterogeneous servers: give more vnodes to more powerful nodes

Redistribution Math

With N nodes and a new node added:

• Naive hashing: ~(N-1)/N keys remapped → for N=10, 90% move
• Consistent hashing: ~K/N keys remapped → for N=10, 10% move
• With virtual nodes (150 per node): standard deviation of load ≈ 5–10% of mean

Key Design Decisions

When to Use

Consistent hashing comes up whenever the interviewer asks about distributed data partitioning or scaling a cluster.

• "Design a distributed cache" — How do you decide which cache node holds which key?
• "Design a key-value store" — Data partitioning across nodes
• "How does Cassandra/DynamoDB partition data?" — Consistent hashing with vnodes
• "Scale a CDN" — Map content to edge servers
• "Design a load balancer with session affinity" — Hash client IP to backend server

Interview signal: The interviewer wants to see you understand why naive modulo hashing fails and how consistent hashing minimizes disruption during scaling events.

Real-World Examples

• Amazon DynamoDB — Uses consistent hashing for partition assignment. Described in the Dynamo paper (2007) that popularized the concept in industry.
• Apache Cassandra — Each node owns token ranges on the ring. Vnodes (default 256) allow automatic rebalancing when nodes join/leave.
• Akamai CDN — Invented consistent hashing (Karger et al., 1997). Used to map URLs to edge servers with minimal disruption.
• Discord — Uses consistent hashing to route messages to the correct guild (server) process across thousands of Elixir nodes.
• Memcached clients — libmemcached and most client libraries use consistent hashing (ketama algorithm) for server selection.

Back-of-Envelope Numbers