Skip to main content
Consistent Hashinglesson 4 of 4 · 3 min read

Where It Shows Up

The same ring, different uniforms

Once you know the shape, you start finding the ring everywhere, wearing different uniforms.

Distributed caches were the first customer, and probably where you will meet it. A scheme called ketama brought consistent hashing to cache clients in 2007, so fleets could be resized without emptying themselves. Every serious client library offers an equivalent mode now.

Choose it deliberately when a cache client asks you for a hashing strategy. Ring hashing is the answer that makes changing the node count survivable.

Dynamo-style databases put the ring at the centre of their design. Amazon's paper used it with virtual nodes to divide up the keys, and replication rides on the same structure. A key's copies are simply the next few distinct servers walking clockwise, so placement and redundancy come out of one idea. Cassandra inherited the token ring directly, and several stores you may already run descend from that same paper.

It traces back to CDNs, where it was born. The 1997 paper that introduced consistent hashing was about caching web objects across a pool of servers that kept changing, and a company was founded to commercialise it. When an edge location maps a URL to one of its cache servers today, a ring or a close relative decides.

It turns up in load balancers, where it buys stickiness without storing anything. Hash a user's session and walk the ring. That user lands on the same backend every time while backends come and go, which keeps their cache warm with no session table anywhere.

The trigger in interviews is one of three phrases: shard a cache, partition by key across a pool that changes size, or move as little as possible when we scale out. Say consistent hashing, mention virtual nodes for spreading load, and give the movement number. Those three beats cover what most interviewers are waiting to hear.

Worked example

Rafael's team runs a WebSocket gateway for a trading app: 40 pods, each holding per-user order-book subscriptions in memory. They balance connections round-robin, so every reconnect lands on a random pod that must rebuild the user's subscription state from scratch, about 900 ms of backend fetches per reconnect, and deploys trigger reconnect storms that hammer the subscription service. He switches Envoy to ring-hash balancing on user ID. Now a reconnecting user lands on the pod that already holds their state, rebuild happens only when that specific pod is gone, and during a rolling deploy of 40 pods, each pod's users redistribute in small slices instead of all at once. Reconnect cost drops to 80 ms for the 97 percent of users whose pod survived, and the subscription service's deploy-time load spike shrinks by a factor of 12.

Consistent Hashing: wrapping up

In the real world

  • 01Consistent hashing was introduced in a 1997 paper by Karger and colleagues at MIT for distributed web caching, and Akamai was founded shortly after to build a CDN on it.
  • 02Amazon's Dynamo paper (2007) made a consistent-hashing ring with virtual nodes the partitioning scheme for its key-value store, a design inherited by DynamoDB, Riak, and others.
  • 03Cassandra assigns each node tokens on a ring; it defaulted to 256 virtual nodes per server for even load and reduced the default to 16 in version 4.0 after the operational cost of many token ranges became clear.
  • 04The ketama library brought consistent hashing to memcached clients in 2007 so cache pools could be resized without invalidating nearly the whole working set.
  • 05Envoy and NGINX ship ring-hash load balancing policies that pin a hashed request attribute, like user ID, to a stable backend while the backend pool changes underneath.

Questions people ask

Why not just rehash and move everything when the cluster changes size?

Because the cost is proportional to everything, not to the change. In a cache, a full remap means a near-zero hit rate and an origin overload. In a storage system, it means physically copying most of the dataset over the network. Consistent hashing bounds the movement to roughly 1/N of keys, the minimum any scheme could achieve while giving the new node a fair share.

How many virtual nodes should each server get?

Enough that load evens out, few enough that bookkeeping stays sane. Values from 16 up to a few hundred per server are common; ketama-style clients use around 100 to 160 points, and Cassandra moved its default from 256 to 16. More virtual nodes give smoother distribution and gentler failure spreading, but in storage systems they multiply the token ranges that repairs and rebalancing must track.

Do I need consistent hashing if my server count never changes?

Servers do not only change when you scale on purpose; they fail, get replaced, and cycle through rolling deploys. Any of those is a membership change, and with mod-N placement each one remaps almost every key. If the node set is genuinely static and failures are handled some other way, mod-N is fine, but that describes very few production systems.

Quick review

Problem:
naive hash(key) % N → adding one node reshuffles almost every key (catastrophic for caches)
Solution:
map both servers and keys onto a circular hash ring (0 to 2^32). Each key routes to the nearest clockwise server
Adding a node:
only keys between new node and its predecessor move. All other keys unaffected
Removing a node:
only that node's keys move to its successor. No mass reshuffling
Virtual nodes:
each physical server has K virtual positions on the ring. Improves load distribution dramatically
Used by:
Amazon DynamoDB, Apache Cassandra, Akamai CDN, Discord message storage, Google Network Load Balancer
Without consistent hashing:
adding 1 server to a 10-server cache pool invalidates ~90% of cache keys
the trade-off

Keys spread evenly only with enough virtual nodes, and every virtual node is ring metadata to store and search. You also give up range queries, since neighbouring keys are meant to land on different servers, and adding a node still moves roughly 1/N of the data.

in the room

Distributed caches, database sharding across dynamic server pools, distributed file systems.