Reading consistent hashing: moving less data

In March I read Consistent Hashing and Random Trees to understand a deceptively simple scaling problem: if keys are already distributed across servers, what happens when one server is added or removed?

The original paper studies distributed caching and hot spots on the web. The idea later became a common building block for databases, caches and routing layers.

Paper: Consistent Hashing and Random Trees (PDF)

Open full size ↗

Why modulo hashing causes a storm

A straightforward sharding function is:

server = hash(key) % serverCount

It distributes keys reasonably when the server count is fixed. Changing serverCount changes the divisor, so most keys produce a different remainder. Adding one server can invalidate almost the entire cache or force most database partitions to move at once.

The algorithm answered the original question—choose one of N servers—but ignored the lifecycle question—what happens when N changes?

Place keys and servers in one space

Consistent hashing maps both objects and buckets into the same hash space. A common visualization bends that space into a ring.

To place a key:

1. Hash the key to a point on the ring.
2. Walk clockwise.
3. Assign the key to the first server point encountered.

When a new server joins, it takes only the interval between its predecessor and itself. Other intervals keep the same owner. When a server leaves, its interval moves to its successor.

With K keys and N servers, a membership change moves roughly K/N keys rather than nearly all K keys. That bounded disruption is the central property.

A small implementation model

The ring can be represented as sorted tokens:

type Point struct {	Token uint64	Node  string} func owner(points []Point, key string) string {	token := hash64(key)	i := sort.Search(len(points), func(i int) bool {		return points[i].Token >= token	})	if i == len(points) {		i = 0 // wrap around the ring	}	return points[i].Node}

Production code also needs collision handling, stable hashing across versions, membership distribution and a way to prevent every caller from building a different ring.

Balance is not automatic

Giving each physical server one random point can create uneven ranges. One server may own a large interval and another a tiny one. The expected distribution can be fair while a small real cluster remains badly skewed.

A common improvement is virtual nodes: assign many token positions to each physical server. More points make ownership smoother. They also support heterogeneous capacity—a larger machine can receive more tokens—and spread the recovery of one failed machine across several neighbours.

Virtual nodes introduce costs:

• More ring metadata.
• More replica relationships.
• More streams during repair.
• Greater care needed to keep replicas in distinct failure domains.

The number of virtual nodes is therefore an operational parameter, not a magic constant.

Replication on the ring

Partitioning chooses an owner. Durability needs replicas. A typical ring selects the next N-1 distinct nodes clockwise after the primary owner.

The word distinct matters. If a physical machine owns several adjacent virtual tokens, counting token positions could accidentally place multiple replicas on the same machine.

Topology matters too. Three replicas in one rack are not three independent copies when the rack loses power. Real systems extend the preference rule with rack and region awareness.

The paper’s deeper properties

The original work discusses more than minimal movement. It reasons about how different clients can have incomplete or changing views of the available caches.

Useful properties include:

• Balance: objects are spread roughly evenly.
• Monotonicity: adding a bucket moves objects to the new bucket rather than between old buckets.
• Spread: an object maps to only a small set of buckets across different views.
• Load: no bucket receives too many distinct objects across those views.

This is deeper than drawing a circle. Distributed routers rarely update membership at exactly the same instant. The algorithm must behave reasonably while their views temporarily disagree.

Hot keys are a different problem

Consistent hashing balances key ranges, not traffic. One celebrity account, popular video or global configuration key may dominate requests even if every server owns the same number of keys.

Hot-key strategies include:

• Replicating a popular value to more readers.
• Splitting one logical key into write buckets and aggregating later.
• Adding a local cache in front of the owning shard.
• Routing reads adaptively while keeping one authoritative writer.
• Applying admission control so one key cannot exhaust a server.

This distinction prevents a common mistake: using a better partition function to solve a popularity distribution problem.

Membership needs coordination

The ring describes placement only after everyone agrees on the members and tokens. It does not provide failure detection, consensus or safe rebalancing by itself.

A complete system needs answers for:

Who may add or remove a node?How is the new ring version published?Can old and new owners serve at the same time?How is data copied before traffic moves?How are partial transfers resumed?

One safe transition is copy, verify, then switch ownership. Moving traffic before data arrives creates misses or inconsistent reads. Copying while writes continue needs a catch-up mechanism or dual writes.

Where I would use it

Consistent hashing fits systems where membership changes and per-key routing must remain stable:

• Distributed caches.
• Sharded key-value stores.
• Partitioned rate limiter state.
• Sticky routing for stateful workers.
• Peer-to-peer overlays.

It is less useful for fixed-size worker pools where a shared queue naturally balances variable-duration jobs. It is also not a replacement for range partitioning when ordered scans are central to the workload.

What I keep from the paper

The ring is the memorable picture, but the real design principle is minimise disruption when capacity changes.

Before choosing it, I would ask:

• Do keys need stable ownership?
• Is even key count a useful approximation of even load?
• How quickly must membership changes propagate?
• How many failure domains must each replica cross?
• Can the system move data without stopping writes?
• How will it detect and repair placement mistakes?

Hashing chooses a destination. A production distributed system still has to make that destination safe.