SYSTEM DESIGN:Lesson 10: Virtual Nodes and CDN Routing

Three identical servers, one doing triple the work

"We deployed consistent hashing on our Memcached cluster. Looked great in the diagram. In Grafana, Node 2 was at 92% CPU while Node 1 and Node 3 sat at 30%. Same hardware. Same code. Completely uneven load."

The hash ring from the previous chapter is correct math. Real clusters are messy: nodes differ in capacity, fail without warning, and join at odd hours. Virtual nodes and production routing patterns exist because a naïve one-node-one-point ring is not enough.

If you skipped the basics, read them first: Consistent Hashing Basics. This chapter is about what actually ships in Dynamo-style stores, CDNs, and Redis/Memcached clients.

One server owns half the ring while the others nap

The ring is mathematically correct. The load distribution is emotionally incorrect.

The uneven load problem on a simple ring

Place three physical servers at random points on a hash ring. Each server "owns" the arc clockwise until the next server. In theory, arcs are roughly equal. In practice, random placement creates lopsided arcs — one server might own 45% of the key space while another owns 20%.

Uneven arcs on a hash ring without virtual nodes

During a Flipkart Big Billion Day-style sale, a hot product catalog shard can take down one Redis node while siblings have headroom. The ring did its job — it routed keys consistently. It just routed too many keys to one machine.

Virtual nodes: many points per physical machine

A virtual node (vnode) is a logical placement on the ring. Instead of mapping Server A → one point, map Server A → 150 points spread around the ring. Server B gets 150 points too. Keys still walk clockwise; they now land on one of A's many positions or one of B's.

Physical node A → vnodes: A#0, A#1, A#2, ... A#149
Physical node B → vnodes: B#0, B#1, B#2, ... B#149
Physical node C → vnodes: C#0, C#1, C#2, ... C#149

Each vnode is hashed: hash("A#42") → position on ring
Key routes to nearest vnode → vnode maps back to physical node A

Why this helps:

• Arcs become finer-grained — load evens out statistically
• A beefier machine gets more vnodes (e.g., 300 vs 150) — proportional capacity
• When a node fails, its vnodes scatter to many neighbors — not one unlucky neighbor
• When a node joins, it receives vnodes from multiple neighbors — gradual load shift

Memcached's ketama client typically uses 160 vnodes per server. That number is not magic — it is the trade-off point where arc variance dropped low enough for real workloads in empirical testing.

Weighted virtual nodes for mixed hardware

Not every server in your cluster is the same size. A common pattern: assign vnodes proportional to capacity.

Node A: 64 GB RAM → 256 vnodes
Node B: 64 GB RAM → 256 vnodes
Node C: 32 GB RAM → 128 vnodes

Expected key share ≈ proportional to vnodes
  A: 40%, B: 40%, C: 20%

This is how you avoid the embarrassment of a 32 GB node holding 33% of keys because the ring said so. Ops scales hardware; engineering scales vnode weights to match.

Interview line: "Physical nodes expose capacity through vnode count. Larger boxes get more ring positions." Short, correct, moves the conversation forward.

Dynamo and Cassandra: consistent hashing in the wild

Amazon's Dynamo paper (2007) popularized consistent hashing for always-on distributed storage. Cassandra inherited the model: partition key → hash → token on the ring → replica nodes.

Cassandra write path (simplified):
  1. Client sends PUT with partition key
  2. Coordinator hashes key → finds token on ring
  3. Primary replica + N-1 successors store copies
  4. Tunable consistency (ONE, QUORUM, ALL)

Indian fintech teams using Cassandra for time-series or event logs often pick user_id or account_id as the partition key — same consistent hashing logic, different column family. The interview answer is identical: hash the key, find the token, talk to the coordinator.

DynamoDB abstracts the ring behind partition keys and adaptive capacity, but the mental model holds: hash key → partition → storage node. AWS manages the vnodes; you still need a good partition key.

CDN routing: same math, different payload

A CDN does not store your database rows. It caches HTTP responses at edge PoPs (points of presence). But which edge server handles a cache lookup for https://cdn.example.com/static/app.js? Often: consistent hashing on the URL path.

CDN request routed via consistent hash to edge server

CDN routing (conceptual):
  hash("/static/app.js") → edge server 7 in Mumbai PoP
  hash("/static/logo.png") → edge server 3 in Mumbai PoP

  Edge server 7 fails → only URLs hashing to 7 remap
  Other cached assets stay on their edges

When Hotstar streams an IPL match, millions of clients request the same manifest and segment URLs. CDN layers above the hash ring absorb the viral read — but origin shielding and edge selection still use hash-based routing to avoid one edge server becoming a bottleneck for different assets.

CDN vs database sharding — same tool, different layer:

Mentioning CDN routing when discussing consistent hashing signals breadth — you connect storage partitioning to content delivery, which is exactly what senior engineers do in system design rounds.

Memcached: ketama and client-side routing

Classic Memcached has no server-side cluster protocol. The client library holds the ring and picks a server per key. Ketama is the widely used consistent hashing implementation.

App server (Memcached client):
  ring = buildKetamaRing([mem1, mem2, mem3])
  server = ring.getServer("session:abc123")
  memcached.get(server, "session:abc123")

mem1 dies:
  client removes mem1 from ring
  affected keys redirect to successors
  cache miss storm until keys repopulate

Production realities:

• Every app server rebuilds the ring when topology changes — deploy coordination matters
• Removing a node causes cache miss spike on remapped keys — not data loss, but DB load spike
• No automatic replication — if mem1 had the only copy, the key is gone (cache, not source of truth)

Teams running Memcached in front of a Razorpay-scale API treat cache misses after node failure as a capacity event. They pre-warm, throttle, or temporarily scale read replicas — because consistent hashing moved keys, not because the algorithm failed.

Redis Cluster: slots, MOVED, and ASK redirects

Redis Cluster uses hash slots (16,384 of them) instead of a literal vnode ring in your code. Under the hood, it is the same minimal-redistribution idea.

Client → Redis Cluster:
  slot = CRC16(key) mod 16384
  slot map: slots 0–5460 → node A, etc.

  Wrong node? Server replies:
    MOVED 9821 10.0.0.5:6379   (permanent slot migration done)
    ASK 9821 10.0.0.7:6379     (migration in progress, temporary)

Smart clients (ioredis, redis-py cluster mode) cache the slot map locally — O(1) routing without asking the cluster on every GET. When ops runs redis-cli --cluster reshard, you watch MOVED/ASK rates in monitoring — that is consistent hashing migration happening live.

Redis vs Memcached cluster comparison for interviews:

• Redis Cluster: server-aware, replication, slot migration built in
• Memcached ketama: client-side ring, no replication, simpler but harsher failover
• Both: consistent hashing family — keys don't all move when topology changes

Node failure and graceful add/remove

When a node dies:

1. Health check marks node unhealthy
2. Ring updated — remove dead node's vnodes/slots
3. Keys owned by dead node reassigned to clockwise successors
4. Clients see misses (cache) or failover reads (DB with replicas)
5. Replacement node joins — can reclaim same vnode count to minimize movement

When adding a node (rolling, no downtime):

1. New node joins with empty storage
2. Steal vnodes/slots from existing nodes (one at a time)
3. Background copy key ranges to new node
4. Dual-read or ASK redirects during copy
5. Cut over — only stolen range served from new node

Cassandra calls this stream data to the new node. Redis Cluster calls it resharding. Memcached calls it "remove old server from ketama config and watch your DB catch fire if you were not ready." Different tooling, same choreography.

Worked example: session store behind UPI checkout

A payment gateway keeps 15-minute session state in Redis Cluster: cart ID, UPI intent ID, device fingerprint. Four nodes, homogenous, 150 vnodes each.

Normal traffic: keys spread evenly; p99 GET < 2 ms.

Node 3 disk failure:

• Replica promotes (if configured) or slot range fails over
• ~25% of sessions see one slow redirect (MOVED) then succeed
• No full-cluster invalidation — unlike hash % N rewrite

Diwali prep — add 2 nodes (4 → 6):

• Each new node receives ~1/6 of slots from existing four
• Background migration over hours, not a maintenance blackout
• Checkout flow stays up; ops watches redis_cluster_slots_assigned metric

That story — specific traffic, specific failure, specific metric — beats reciting "consistent hashing minimizes redistribution" alone.

Common mistakes in production

Mistake 1 — too few vnodes on heterogeneous hardware.

One ring point per node on mixed instance sizes guarantees the small node dies first. Weight vnodes by RAM/CPU.

Mistake 2 — ignoring cache miss storms on node removal.

Consistent hashing preserves most keys. The keys that moved still miss. Plan DB headroom for the miss wave.

Mistake 3 — client ring out of sync across app servers.

If half your fleet still routes to a dead Memcached node, you get split-brain cache behavior. Use config propagation (Consul, etcd) or server-managed routing (Redis Cluster).

Mistake 4 — hot partition key on Cassandra/Dynamo.

Consistent hashing does not split a single hot key. Composite keys (device_id#hour_bucket) or write sharding at app layer — separate techniques.

Mistake 5 — resharding during peak without rate limits.

Background migration competes with live traffic for disk and network. Throttle copy bandwidth during IPL hours.

Interview talking points

Layer your answer when they ask about distributed caching or storage:

1. Ring + clockwise lookup (previous chapter)
2. Virtual nodes for even load and weighted capacity
3. Name a real system — ketama, Redis slots, Cassandra tokens
4. CDN angle — URL hashed to edge (shows you think globally)
5. Failure mode — miss storm, MOVED redirects, replication
6. What it does not fix — hot keys, cross-shard queries

If asked to compare Memcached vs Redis Cluster routing: Memcached pushes complexity to clients; Redis Cluster pushes it to servers with a slot protocol. Neither uses naive modulo.

Practice with hands-on labs

• Sharding Lab — simulate adding nodes; watch relocation counts drop vs modulo
• Request Flow Lab — trace cache lookup when the ring changes mid-session

After the sharding lab, write one paragraph comparing your observed relocation count to the theoretical K/N bound. Interviewers love when candidates connect lab numbers to paper math.

What comes next: the simplest database interviewers love

Consistent hashing tells you where a key lives in a distributed cluster. The next question is what lives there — get, put, delete on a single node, then across many.

The next chapter builds a key-value store from scratch: in-memory vs disk, LSM vs B-tree in one paragraph each, API design, and the single-node foundation every distributed KV interview assumes you understand.

Continue here: Key-Value Store Core.