Skip to content

Consistent Hashing

1. What is it? (2-3 lines)

Consistent Hashing is a distributed hashing technique where both storage nodes and data keys are mapped onto a logical 360-degree circular ring (hash ring). Adding or removing a node requires remapping only \(k/n\) keys (where \(k\) is total keys and \(n\) is total nodes), preventing cluster-wide data reshuffling.

2. Why does it exist?

Traditional modulo hashing (hash(key) % N) causes catastrophic data churn when scaling a cluster. Adding or removing 1 node changes \(N\), causing nearly 100% of keys to hash to new nodes, destroying cache hit ratios and thrashing storage networks. Consistent Hashing minimizes key movement to \(1/N\) of total keys.

3. Where is it used?

  • Distributed Caches: Memcached (ketama hash ring), Redis Cluster.
  • Distributed NoSQL Stores: Amazon DynamoDB, Apache Cassandra (Token Ring).
  • Load Balancers & Gateways: HAProxy, Nginx consistent hashing for sticky session routing.

4. How does it work? (simple flow)

  1. Hash Ring Construction: Define a 32-bit integer hash space (\(0\) to \(2^{32}-1\)) conceptually mapped as a continuous circular ring.
  2. Node Placement: Hash node IP addresses/identifiers onto the ring (e.g. hash("NodeA") = 100, hash("NodeB") = 500).
  3. Key Placement: Hash incoming keys onto the ring (e.g. hash("user_123") = 300).
  4. Clockwise Routing: To locate a key's server, walk clockwise on the ring from the key's hash position to find the first node encountered (hash("user_123") = 300 routes to NodeB = 500).
  5. Virtual Nodes (vnodes): Map each physical node to 100-250 virtual positions on the ring (NodeA_1, NodeA_2) to ensure uniform data distribution and prevent hot spots.

5. Advantages

  • Minimizes key movement during scaling to \(O(K/N)\) keys.
  • Virtual nodes eliminate hot spots and ensure uniform load distribution across heterogeneous hardware.
  • Decouples storage cluster topology from client routing logic.

6. Limitations

  • Cascading failures: If a node fails without virtual nodes, its entire load shifts to its single clockwise neighbor.
  • Requires maintaining node-to-ring topology state (Gossip protocol or Coordinator) across clients/nodes.

7. Common interview questions (10)

  1. Why does traditional modulo hashing (hash(key) % N) fail when scaling distributed caches?
  2. How do Virtual Nodes (vnodes) solve the Hot Spot / Non-Uniform Data Distribution problem?
  3. What is the mathematical proportion of keys remapped when adding 1 node to an \(N\)-node ring?
  4. How does Apache Cassandra use Consistent Hashing Token Rings for data partitioning and replication?
  5. What hash functions (e.g., MurmurHash3, MD5) are preferred for Consistent Hashing and why?
  6. How do you implement replication (Replication Factor = 3) on a Consistent Hashing ring?
  7. What happens if 1 physical server with 200 vnodes crashes suddenly?
  8. How does Ketama hashing work in Memcached client libraries?
  9. How does Consistent Hashing differ from Rendezvous Hashing (Highest Random Weight)?
  10. How do load balancers use Consistent Hashing for sticky session persistence without storing session state?

8. Common misconceptions

  • Misconception: Physical nodes are placed sequentially on the ring. Fact: Nodes are hashed onto random ring coordinates; virtual nodes scatter positions evenly across the \(2^{32}\) space.
  • Misconception: Adding a node causes zero key movement. Fact: Adding a node remaps a minimal fraction (\(\approx 1/N\)) of total keys from its immediate clockwise neighbor.

10. 30-second cheat sheet

  • Core Concept: Hash both Nodes and Keys onto a \(2^{32}\) Circular Hash Ring.
  • Routing: Walk Clockwise from hash(key) to the first hash(node).
  • Scaling Gain: Adding/removing a node remaps only \(1/N\) of keys (vs 100% in modulo hashing).
  • Virtual Nodes (vnodes): Scatter 100+ virtual copies per physical node to prevent load skew.