Archprimer
ConceptAdvanced 8 min read

Consistent Hashing

A hashing scheme that maps keys and nodes onto a ring so that adding or removing a node remaps only a small fraction of keys, avoiding the mass reshuffle of modulo hashing.

distributed-systemshashingshardingcaching

By Ratish Jain · Updated

Diagram with 5 components: Client, Hash Ring, Node A, Node B, Node C. Connections: Client → Hash Ring (1 key); Hash Ring → Node A (clockwise); Hash Ring → Node B (next); Hash Ring → Node C (wraps).
ClientService
A key hashes onto the ring and is served by the next node clockwise.

Definition

Consistent hashing maps both keys and nodes onto the same fixed circular hash space (the ring, e.g. 0 to 2³²−1). A key is owned by the first node encountered when walking clockwise from the key's position on the ring.

Its defining property: when a node is added or removed, only the keys between that node and its neighbor move — on average K/N keys — instead of nearly all of them.

Why It Exists

Naive sharding uses hash(key) % N. It distributes keys evenly, but the moment N changes — a node is added or one crashes — the modulus changes and almost every key remaps to a different node. In a cache that means a mass miss storm; in a database it means moving nearly all the data.

Consistent hashing was designed (by Karger et al. for web caching) precisely to make membership changes cheap, so clusters can scale elastically without reshuffling the world.

How It Works

Each node is hashed to one or more points on the ring. To store or fetch a key, hash the key to a point and walk clockwise to the first node — that node owns it. Adding a node only steals the arc between it and the previous node; removing a node hands its arc to the next clockwise node.

A single point per node causes uneven load and big gaps. Virtual nodes fix this: each physical node is placed at many points (e.g. 100–200 vnodes), smoothing distribution and letting more powerful machines take proportionally more of the ring. Replication is easy too — store a key on the next R distinct nodes clockwise.

What It's Used For

  • Distributed caches (Memcached client rings, Redis Cluster's 16384 hash slots).
  • Partitioning in Dynamo-style databases: Cassandra, DynamoDB, Riak, ScyllaDB.
  • Load balancers doing sticky routing without a central session store.
  • Sharded storage systems that must add/remove nodes with minimal data movement.
  • Choosing replica placement by taking the next R nodes clockwise on the ring.

The Hash Ring

Diagram with 4 components: Node A, Node B, Node C, key user:42. Connections: Node A → Node C (ring); Node C → Node B (ring); Node B → Node A (ring); key user:42 → Node A (1 · clockwise).
ServiceClient
Keys map clockwise to the next node; virtual nodes even out the load.

Tradeoffs

Pros
  • Only ~K/N keys move when membership changes — elastic scaling is cheap.
  • Virtual nodes give even distribution and heterogeneous node weights.
  • Decentralized: any node or client can compute ownership from the ring.
Cons
  • More complex to implement and reason about than modulo hashing.
  • Without enough virtual nodes, load skews and hot spots appear.
  • A single hot key still lands on one node — hashing doesn't split it.
  • Ring membership must be propagated consistently (gossip/coordination).

When to Use / Avoid

Use when
Nodes join and leave frequently and you must minimize data movement or cache invalidation on membership change.
Avoid when
The node set is fixed and small, or a single key concentrates load (consistent hashing won't relieve a hot key).
Real-world
Amazon DynamoDB and Cassandra partition by a consistent-hash ring; Redis Cluster uses 16384 slots mapped to nodes.

Interview Questions

Why not just use hash(key) % N?

Because changing N (adding or removing a node) changes the modulus, remapping almost every key to a new node. For caches that triggers a mass miss and thundering-herd on the backing store; for databases it means moving nearly all the data. Consistent hashing moves only ~K/N keys.

What problem do virtual nodes solve?

With one ring position per node, arcs between nodes are uneven, so load is unbalanced, and removing a node dumps its entire arc onto a single neighbor. Assigning each physical node many virtual positions smooths the distribution and lets a departing node's load spread across all remaining nodes; weights let bigger machines own more vnodes.

60-Second Revision
  • →Keys and nodes share a hash ring; a key goes to the next node clockwise.
  • →Adding/removing a node remaps only ~K/N keys, not all of them.
  • →Virtual nodes balance load and support weighted, heterogeneous nodes.
  • →Solves modulo hashing's mass-reshuffle problem on membership change.
  • →Used by Dynamo, Cassandra, Redis Cluster, and distributed caches.

Related

Everything on Archprimer is connected — follow the graph.