Consistent Hashing & Distributed Cache Coordination - Ring Algorithm

By the end of this lesson, you will be able to...

• Trace where a cache key goes before and after a node joins a hash ring.

• Explain why stable placement reduces avoidable cache misses but does not guarantee balanced traffic.

• Choose the evidence needed to decide whether a resize problem comes from remapping, a hot key, or inconsistent membership.

Idea in one sentence: Consistent hashing keeps most keys on their previous cache nodes when membership changes, turning a fleet resize into a local movement problem instead of a fleet-wide cache cold start.

Core Insight

A product API has four cache nodes. Its client library sends each key to:

owner = hash(key) % number_of_nodes

The rule is easy to run and looks balanced on an ordinary day. Then the team adds a fifth node before a traffic campaign. The cache hit rate falls sharply and origin-database traffic jumps.

The first model says: adding capacity should only help. The cache data still exists on the first four nodes, and the new node should take a small share of requests.

The missing detail is the routing rule. Changing the divisor changes the answer for most keys. A request now goes to a different node even when the old node still holds a valid, warm copy. For a cache, that routing change behaves like a large synthetic miss event: the origin refills values that were already available somewhere else.

Consistent hashing changes the goal from “spread keys evenly today” to “keep assignments stable while the fleet changes.” It does not preserve every key, and it does not remove the need for cache freshness or capacity controls. It makes the movement explicit and bounded enough to plan.

The Small Situation

Keep one shared cache fleet in view. The catalog database is authoritative; cache nodes hold reusable product-card copies; the client library decides which node receives each key.

client -> routing table / hash function -> cache node -> origin on a miss

key: product:42
cache node: holds a non-authoritative copy
origin: refills the copy when the selected node misses

There are three separate questions:

• Placement: which node should receive product:42?
• Membership: which nodes are currently eligible to receive it?
• Freshness: may the selected node serve its copy?

Consistent hashing addresses placement under a changing membership view. It does not decide whether the product card is fresh, nor does it make every client agree on membership by magic.

The Initial Model: Modulo Hashing Is Stable Enough

Modulo hashing works while the node count stays fixed. Suppose a key hash is 37.

with four nodes: 37 % 4 = 1
with five nodes: 37 % 5 = 2

That key moves. Many other hashes move too, because the partition boundary depends on the total node count. The exact percentage depends on keys and implementation, but the practical observation is clear: a small membership change can redirect a large fraction of a warm working set.

For a stateless request router this can be harmless. For a cache, it creates pressure:

new routing decision
  -> selected node lacks an otherwise valid copy
  -> cache miss
  -> origin read and cache fill
  -> more origin concurrency and tail latency

The problem is not that modulo is illegal or that every cache must use a ring. It is that this rule couples every key's owner to the fleet size. It is a poor fit when a resize must preserve reuse.

The Better Model: A Ring Makes Movement Local

In plain English, a hash ring is one circular address space. Keys and node tokens are placed in that space. A key belongs to the first token encountered while moving clockwise.

hash space, simplified

0 ---- key k=18 ---- A=25 ---- B=55 ---- C=80 ---- D=95 ---- back to 0

owner(k) = A

Now add node E at token 40.

0 ---- k=18 ---- A=25 ---- E=40 ---- B=55 ---- C=80 ---- D=95 ---- back to 0

E becomes owner only for the interval that previously belonged to B: keys after A up to E. Keys owned by A, C, and D keep their owners. That is the core mechanism: inserting or removing a token changes neighboring intervals rather than recalculating every interval from the fleet size.

The numbers are a teaching model, not a production distribution. A real implementation hashes keys and tokens into a much larger space and needs a deterministic, shared algorithm. The original consistent-hashing work describes this stable-placement goal; production systems commonly add more machinery around it.

A Worked Trace: Add Capacity Without Losing Every Warm Copy

At 09:00, four nodes hold the following simplified intervals:

At 09:05, node E joins at 40.

So far, the ring has protected most warm copies. It has not moved the values themselves, guaranteed that E is ready, or made all clients update at once.

Check: Why is “only one interval moves” better than “only one node was added” as an operational statement?

Think first, then reveal.

Answer: Nodes are machines; intervals are sets of keys and therefore the unit that determines miss and refill pressure. A small machine-count change can still move a costly or hot interval. Measure the moved key range, its request rate, and refill cost.

Virtual Nodes Make the Intervals Finer

One physical node placed at one token can own an unlucky large interval. It also makes a node addition take one contiguous slice from one neighbor. A common extension gives each physical node several tokens, called virtual nodes.

With virtual nodes, a new machine takes many small intervals from several existing machines. This can smooth the distribution of keys and make capacity weighting possible by assigning more or fewer tokens under a defined policy. Dynamo's published design uses virtual nodes as part of its partitioning approach.

This improves expected placement balance. It costs a larger routing table, more membership metadata, and more intervals to monitor and warm. It still cannot split one very popular key: all requests for that key follow the same primary placement unless the design adds replication, request coalescing, or a different hot-key strategy.

Where the Ring Stops Helping

Stable placement is not a complete distributed-cache design.

• Hot key: a product campaign can send most requests to one key. Even perfect interval balance leaves its primary owner overloaded.
• Unequal capacity: a large node and a small node should not necessarily receive the same share. Token policy or another capacity-aware approach must encode that choice.
• Membership disagreement: if routers use different ring versions, the same key can be sent to different nodes. Track ring version, propagation lag, and client errors.
• Failure and replicas: a failed owner needs a defined fallback or replica policy. A ring identifies candidate placement; it does not define safe retry semantics or freshness between copies.

Do not call every miss after a resize a hashing failure. Compare the ring version used by the client, moved-range traffic, cache hit rate by range, origin refill rate, and per-node saturation. That evidence distinguishes a deliberate local remap from a hot key or a membership-control problem.

Cost, Limits, and Signals

Consistent hashing improves resize behavior by limiting placement changes. It costs routing complexity and operational coordination. A node can join without a whole-fleet cold start, but the moved ranges still need headroom at the origin and the new node may need bounded warmup.

The trade-off is concrete: more tokens and replicas can spread ordinary work and soften a node failure, but they enlarge the routing state, the warmup surface, and the number of copies whose freshness must be controlled. A simple fixed-size fleet may not need that cost. A changing fleet whose origin cannot absorb broad refills usually does.

For an addition, make an explicit assumption: clients can obtain the same new ring version before significant traffic shifts. If that assumption is false, temporarily routing the same key to old and new owners can lower hit rate even when each client follows its own ring correctly. The control plane therefore deserves the same rollout discipline as the data path: publish a version, observe adoption, and retain a bounded rollback plan.

The boundary appears when a local movement is still too expensive: the moved interval contains high-cost keys, the source cannot absorb refill, or clients are on inconsistent ring versions. The relevant signals are moved-key request rate, hit rate by node or partition, origin reads during the transition, ring-version convergence, and p95/p99 latency.

Choose a ring when stable key placement under membership changes is valuable. Do not choose it as a substitute for cache invalidation, global load balancing, capacity planning, or a failure protocol.

Practice: Review a Resize Plan

A six-node cache fleet will add two nodes. One key, homepage:featured, receives 30% of all cache traffic. The origin can handle a temporary 10% increase in reads but not a full cold-start refill.

Propose a resize plan using the lesson vocabulary. Name one benefit of virtual nodes, one risk that remains, and two signals that decide whether to slow or stop the rollout.

A good answer should mention:

• versioned ring rollout and a bounded moved-range warmup rather than a fleet-wide remap;
• virtual nodes to spread ordinary intervals more smoothly;
• a separate hot-key plan because virtual nodes do not split one key's traffic; and
• origin refill rate, ring-version convergence, per-node saturation, or tail latency as rollout signals.

Connections

The previous lesson explains why each cache node has finite usable memory. Placement that looks balanced by key count can still be poor if one node receives larger values or allocator-heavy churn.

The next lesson returns to cache invalidation. The ring decides where a copy is requested; the invalidation policy decides whether that copy is still safe to serve. Keep placement stability and freshness authority as separate promises.

Resources

• [PAPER] Consistent hashing and random trees — Focus: Read the original framing of stable distributed cache placement and hot-spot pressure.
• [PAPER] Dynamo: Amazon's highly available key-value store — Focus: Examine how virtual nodes extend a basic ring in a production key-value system.
• [DOCS] OpenStack Swift rings — Focus: See partition ranges, replicas, and weighted placement treated as operational configuration.

Key Takeaways

• Modulo hashing is simple but remaps many keys when fleet size changes, which can turn warm cache data into avoidable origin reads.
• A consistent hash ring moves neighboring key intervals when a token changes, preserving most placements across a resize.
• Virtual nodes make intervals finer and can smooth ordinary placement, but they do not solve a single hot key.
• Ring membership must converge across routers; stable placement requires a sufficiently shared membership view.
• Measure moved-range traffic, origin refill, ring-version convergence, and tail latency before calling a resize safe.