system-design · intermediate

Consistent Hashing — Rings, Virtual Nodes, and Minimal Rebalancing

Start here

Ordinary hashing to N servers looks like server = hash(key) % N.

When N changes from 4 to 5, almost every key remaps—causing mass cache misses or data movement.

Consistent hashing places both keys and nodes on a circular hash space (a ring). Each key belongs to the first node clockwise (or along a defined direction). When a node joins or leaves, only nearby keys move—roughly \(1/N\) on average for uniform setups.

You should care because distributed caches (and some databases/CDNs) rely on this idea to scale membership without global reshuffles.

What you will learn

1. See why modulo hashing reshuffles everything.
2. Build the ring mental model.
3. Use virtual nodes for balance.
4. Work a complete cache cluster example.
5. Discuss replication along the ring (basic).
6. Know limitations vs explicit shard maps.

What you should know first

Words you need before we begin

Simple story: numbered seats on a round table

People (keys) sit at the next available labeled chair (node) clockwise. If you remove one chair, only people who sat there move to the next chair—not the entire room re-seating randomly.

Virtual nodes: popular hosts get more chair labels so they take fairer share.

The problem with hash % N

N=4 → N=5 remaps nearly all keys. Cache hit ratio collapses; backends melt; or data migration storms.

Step-by-step explanation

Step 1 — Fix a large hash space

Imagine numbers 0 … \(2^128-1\) arranged in a circle.

Step 2 — Assign nodes

Hash each node id to one or more points on the circle.

Step 3 — Assign keys

Hash key; walk clockwise to the first node point; that node owns the key.

Step 4 — Add a node

New node claims keys from its clockwise neighbor’s previous range—only that slice moves.

Step 5 — Remove a node

Its keys fall through to the next node clockwise.

Step 6 — Virtual nodes

Give each physical node many hash positions to smooth uneven ownership arcs.

Step 7 — Optional replicas

Store copies on next R distinct physical nodes for durability/availability (system-specific).

Visual mental model

flowchart TB
  subgraph ring [Hash ring]
    direction LR
    K[key] --> N2[node B]
    N1[node A] --> N2
    N2 --> N3[node C]
    N3 --> N1
  end

Learning question: If node B leaves, which keys move?

Caption: Keys that previously mapped to B now map to the next node—not all keys.

Complete worked example: four-node cache

Starting situation

Cache nodes A–D. Viral product keys thrash after a scale event using modulo hashing.

Decisions

Outcome

Scale events no longer empty the entire cache. Residual imbalance watched via per-node QPS.

Limitations

Without vnodes, random placement can be lumpy. Also, clients must agree on the membership list or use a central proxy.

How it works in production

• Memcached clients historically popularized the idea
• Cassandra-style token rings (with richer partitioners)
• CDNs and load balancers sometimes use related techniques
• Kubernetes and data systems may use different partitioners—concepts transfer

Failure modes

Trade-offs

Compare with related concepts

Common misunderstandings

1. “Consistent hashing means no keys move.” Some move—fewer.
2. “It solves hot keys.” Popular single keys still hit one node.
3. “Only for caches.” Broader, but caches are the teaching example.
4. “Virtual nodes are optional cosmetics.” They matter for balance.
5. “Clients need no shared membership.” They must see the same ring.

Check your understanding

1. Why does modulo remapping hurt caches?
2. How does a key choose its node on a ring?
3. What do virtual nodes improve?
4. Roughly how many keys move when adding one of N nodes?
5. Name one remaining hotspot problem.

Practice

1. Draw a 0–99 ring with 3 nodes and place keys.
2. Add a fourth node; list keys that move.
3. Design vnode counts for 10 physical hosts.
4. Compare client-side hashing vs proxy.
5. Explain remapping to a PM with the coat-check analogy variants.

Deeper production notes

Incremental migration

When changing hash algorithms, use dual-read/dual-write or shadow rings carefully—harder than it sounds.

Security

If keys are attacker-controlled, hash-flooding concerns exist for some hash functions—use appropriate hashes.

Additional teaching scenarios

Scenario A — peak load day

Scenario B — mixed versions

Scenario C — five-sentence teach-back

Scenario D — metrics and alerts

Scenario E — non-goals

Scenario F — ownership

Revision summary

• Consistent hashing puts keys and nodes on a ring.
• Membership changes move about 1/N keys, not all.
• Virtual nodes improve balance.
• Still watch hot keys and membership consistency.

Glossary

Abbreviations and terminology

• vnode — Virtual node
• QPS — Queries per second
• CDN — Content delivery network

What to learn next

1. Database sharding
2. Distributed caching
3. Design URL shortener
4. Load balancing

Extra teaching notes for first-time builders

Write the single bottleneck you are protecting before picking tools. Name the signal that tells you the design is working for users, not only that internal counters move. When reviewing a change related to this lesson, ask what happens when the component is slow for ten minutes, down entirely, or running twice. Prefer small explicit failure modes that operators can understand at 3 a.m.

Document ownership for dashboards, code, and pages. Undocumented mechanisms become folklore and then outages. Prefer designs that tolerate mixed versions for at least one deploy window so rollouts do not require perfect global simultaneity.

Napkin math helps: estimate peak rate, multiply by payload size, and ask whether the design still holds when a dependency is at half capacity. If the answer depends on luck, add bounds, backpressure, or shedding before production traffic arrives.

Extra teaching notes for first-time builders

Write the single bottleneck you are protecting before picking tools. Name the signal that tells you the design is working for users, not only that internal counters move. When reviewing a change related to this lesson, ask what happens when the component is slow for ten minutes, down entirely, or running twice. Prefer small explicit failure modes that operators can understand at 3 a.m.

Document ownership for dashboards, code, and pages. Undocumented mechanisms become folklore and then outages. Prefer designs that tolerate mixed versions for at least one deploy window so rollouts do not require perfect global simultaneity.

Napkin math helps: estimate peak rate, multiply by payload size, and ask whether the design still holds when a dependency is at half capacity. If the answer depends on luck, add bounds, backpressure, or shedding before production traffic arrives.

Extra teaching notes for first-time builders

Write the single bottleneck you are protecting before picking tools. Name the signal that tells you the design is working for users, not only that internal counters move. When reviewing a change related to this lesson, ask what happens when the component is slow for ten minutes, down entirely, or running twice. Prefer small explicit failure modes that operators can understand at 3 a.m.

Document ownership for dashboards, code, and pages. Undocumented mechanisms become folklore and then outages. Prefer designs that tolerate mixed versions for at least one deploy window so rollouts do not require perfect global simultaneity.

Napkin math helps: estimate peak rate, multiply by payload size, and ask whether the design still holds when a dependency is at half capacity. If the answer depends on luck, add bounds, backpressure, or shedding before production traffic arrives.

Extra teaching notes for first-time builders

Write the single bottleneck you are protecting before picking tools. Name the signal that tells you the design is working for users, not only that internal counters move. When reviewing a change related to this lesson, ask what happens when the component is slow for ten minutes, down entirely, or running twice. Prefer small explicit failure modes that operators can understand at 3 a.m.

Document ownership for dashboards, code, and pages. Undocumented mechanisms become folklore and then outages. Prefer designs that tolerate mixed versions for at least one deploy window so rollouts do not require perfect global simultaneity.

Napkin math helps: estimate peak rate, multiply by payload size, and ask whether the design still holds when a dependency is at half capacity. If the answer depends on luck, add bounds, backpressure, or shedding before production traffic arrives.

FAQ from first-time learners

Q: Is consistent hashing the same as encryption hashing?
A: No—here hash means deterministic placement, not password security.

Q: Do I implement the ring myself?
A: Prefer battle-tested libraries/systems.

Q: What about range-based sharding?
A: Different trade-offs (range scans vs hot ranges)—worth comparing in DB designs.

Track: Data, Storage and Messaging

Previous: Connection Pooling — Reusing Expensive Database Sessions

Next: Database Storage Architectures — B-Trees vs. LSM-Trees

By Shubham Jain

All articles · Study paths

Shubham Jain · Learning Lab