SYSTEM DESIGN:Lesson 9: When Hash Modulo Breaks

The night you added a fourth database shard

"We had three Postgres shards. Traffic grew. We added a fourth. The migration ran for six hours. During that window, half our UPI webhook lookups returned 404 because keys had moved to the wrong shard. Razorpay does not care that you are resharding — they retry, but your reconciliation team does not sleep."

This is what naive hash modulo costs you. hash(key) % N is the first sharding function every engineer writes. It is also the first one that breaks when N changes.

If you read the data layer scaling chapter, you already know why we shard. This chapter answers how to shard without turning every cluster resize into a weekend-long data migration.

Previous context: Data Layer Scaling introduced sharding. This lesson goes one level deeper into the routing math itself.

Keys flying everywhere when you add shard number four

hash(key) % 3 was fine. hash(key) % 4 is a weekend you did not plan for.

Naive sharding: hash(key) % N

The simplest way to pick a shard for a key is to hash the key to an integer, take modulo N (number of shards), and route accordingly.

function getShard(key: string, numShards: number): number {
  const hash = murmurHash(key)  // any stable hash function
  return hash % numShards
}

// Example: 3 shards
getShard("user:9182736450", 3) → shard 1
getShard("order:SW-2024-88421", 3) → shard 0

For a Swiggy order service with 3 shards and 30 crore order records, changing N from 3 to 4 does not move 25% of keys. It moves roughly 75% of keys, because the modulus changed for almost every hash output.

Why hash modulo breaks when N changes

That diagram is the whole problem in one picture: same keys, new N, completely different shard assignments. Every moved key needs a read from the old shard, a write to the new shard, and a delete from the old shard — while production traffic keeps hitting both.

The resharding pain nobody budgets for

Teams treat "add a shard" like adding another EC2 instance to a load balancer. It is not. Data has memory. Keys live on specific machines. Moving them is a distributed copy job with correctness requirements.

What a naive resharding migration actually involves:

1. Put the cluster in dual-write mode (write to old and new shard maps)
2. Scan every key on every shard — full table scan at scale
3. For each key, recompute hash(key) % newN
4. If the shard changed, copy the row to the new shard
5. Verify counts match on source and destination
6. Flip reads to the new map
7. Delete stale copies from old shards
8. Pray your cache invalidation kept up

Naive resharding cost (rough):
  Keys that move ≈ (1 - 1/oldN) × total keys
  3 → 4 shards: ~75% of keys relocate
  10 → 11 shards: ~9% relocate
  10 → 20 shards: ~50% relocate

  Data to copy = moved_keys × avg_row_size
  500M keys × 2 KB × 75% = ~750 TB copied across network

During IPL season, a fantasy sports backend might refuse to resize shards because the migration risk is worse than running hot on three overloaded shards. That is not cowardice — that is what bad hash routing forces you into.

Symptoms you are paying the modulo tax:

• Multi-hour maintenance windows every time you scale storage nodes
• Cache stampedes after shard map changes (keys exist on two shards briefly)
• Cross-shard queries that worked yesterday and fail today
• On-call pages for "record not found" spikes during migrations

Consistent hashing: the idea

Consistent hashing fixes the redistribution problem. When you add or remove a node, only keys that belonged to that node (or its immediate neighbors on the ring) need to move. Everything else stays put.

The core insight: instead of mapping keys directly to shard indices with modulo, map both keys and shards onto the same circular hash space. A key belongs to the first shard you encounter walking clockwise from the key's position.

Consistent hash ring with keys and nodes

Setup in plain language:

1. Hash each shard ID to a point on a ring (0 to 2³²-1, conceptually)
2. Hash each key to a point on the same ring
3. To route a key: start at the key's position, walk clockwise, first shard wins

Ring (simplified to 0–100):

  Shard A at position 10
  Shard B at position 45
  Shard C at position 80

  Key "user:9876543210" hashes to 52
  Walk clockwise from 52 → hit Shard C at 80
  Route key to Shard C

No modulo. No "every key recomputes against a new N." Keys only care about the next shard clockwise — and that relationship is stable unless a shard enters or leaves the ring between them.

Walking the ring: lookup step by step

Here is a minimal TypeScript mental model — not production code, but enough for a whiteboard:

type Shard = { id: string; position: number }

function findShard(key: string, ring: Shard[]): Shard {
  const keyPos = hash(key)
  const sorted = [...ring].sort((a, b) => a.position - b.position)

  for (const shard of sorted) {
    if (shard.position >= keyPos) return shard
  }
  // Wrapped past the end — first shard on the ring
  return sorted[0]
}

In production, the ring is stored in memory on every client (Memcached clients, Redis Cluster proxies, custom routers). Lookup is microseconds — the expensive part is still the network round-trip to the shard.

Compare to modulo: both are fast lookups. The difference shows up only when the cluster membership changes — and at scale, that difference is the difference between a 20-minute rolling add-node and a 20-hour migration.

What happens when you add a shard

Suppose Shard D joins the ring at position 55. Before D existed, keys between 45 (Shard B) and 80 (Shard C) went to Shard C. Now keys between 55 and 80 go to D instead.

Keys that move: only keys whose clockwise "owner" changed from C to D.

Keys that stay: everything else on the ring — including all keys owned by A and B, and keys on C that hash below 55.

Before: 3 shards, 300M keys
  Each shard ≈ 100M keys

After: add Shard D
  Keys moving ≈ 1/N of total (idealized)
  4 shards → ~25% of keys relocate (~75M keys)

Naive hash % 4 from a 3-shard map:
  ~75% relocate (~225M keys)

That 75M vs 225M gap is why Dynamo, Cassandra, Riak, and every serious distributed cache uses consistent hashing instead of modulo. The math gets even better as N grows.

Removing a shard is symmetric. Shard D leaves. Keys that belonged to D get absorbed by the next shard clockwise — usually C. Only D's former key range moves. No global reshuffle.

Minimal redistribution: why interviewers care

When an interviewer asks "how would you shard this?", they are often listening for whether you understand migration cost, not just partition logic.

Say this out loud in interviews: "Consistent hashing bounds resharding to roughly K/N keys when adding or removing K nodes from an N-node ring." That sentence signals you have operated real clusters, not just read a blog post.

Where this shows up in Indian production stacks:

• Memcached client libraries — ketama is consistent hashing under the hood
• Redis Cluster — 16,384 hash slots mapped to nodes (slot-based variant of the same idea)
• Amazon DynamoDB — partition keys hashed to storage partitions
• CDN edge routing — request URLs hashed to edge servers (next chapter)

You do not need to implement the ring yourself. You need to know why your cache client picks the node it picks — and what breaks when ops adds a node at 2 AM.

Consistent hashing vs Redis Cluster slots

Redis Cluster does not expose a literal ring in your application code. It uses 16,384 fixed hash slots. Each key hashes to a slot; each node owns a range of slots. When you add a node, you move slots, not recompute a modulus.

Redis Cluster (simplified):
  CRC16(key) mod 16384 → slot number
  Node A owns slots 0–5460
  Node B owns slots 5461–10922
  Node C owns slots 10923–16383

  Add Node D → move ~4096 slots from existing nodes to D
  Only keys in moved slots relocate

Same principle as consistent hashing: fixed hash space, move boundaries instead of changing the formula. When someone says "Redis Cluster uses hash slots," you can nod and translate — it is consistent hashing adapted for operational tooling.

Worked example: Swiggy delivery zones

Imagine sharding live order tracking by restaurant_id. Three Redis nodes hold in-flight order state. Lunch rush hits Koramangala — you add a fourth node.

With hash % 4:

• 75% of order keys potentially change shard
• Riders see "order not found" for 30–90 seconds during migration
• Support tickets spike; you roll back

With consistent hashing:

• ~25% of keys migrate to the new node
• Background slot migration with dual-read fallback
• Koramangala lunch rush absorbed without a maintenance window

The business outcome is the same either way — more capacity. The operational outcome is completely different. Consistent hashing is an ops win as much as a math win.

Common mistakes

Mistake 1 — using a non-stable hash function.

If your hash changes between app deploys (different seed, different algorithm), every key jumps shards. Pin your hash function and version it.

Mistake 2 — assuming consistent hashing fixes hot keys.

It does not. If every IPL fan hits the same leaderboard key, that key still lands on one shard. Consistent hashing spreads keys evenly, not traffic evenly. Hot keys need application-level sharding or caching — a different problem.

Mistake 3 — too few points on the ring.

Three physical nodes with one ring position each can be uneven. Real systems use virtual nodes (next chapter) to balance load. Mention this before the interviewer asks.

Mistake 4 — resharding without a migration plan.

Even with consistent hashing, moved keys need copying. Plan for dual-read, backfill jobs, and cache invalidation. The algorithm reduces work — it does not eliminate it.

Mistake 5 — sharding before you need to.

A 50 GB Postgres with good indexes does not need a hash ring. Consistent hashing is for when single-node limits are real and proven — not for resume-driven architecture.

Interview talking points

When sharding comes up, structure your answer:

1. Start with the shard key — user_id, tenant_id, geographic region
2. Reject naive modulo — explain the full reshuffle problem when N changes
3. Introduce the hash ring — keys and nodes on same circle, walk clockwise
4. Quantify migration cost — only K/N keys move vs almost everything with modulo
5. Name real systems — Memcached ketama, Redis Cluster slots, Dynamo partitions
6. Acknowledge limits — hot keys, uneven nodes (tease virtual nodes)

If they ask "implement it," sketch the ring lookup with a sorted array and binary search. O(log N) per request is fine. Nobody expects you to write a production ketama library on a whiteboard.

Follow-up questions to expect:

• What if one shard is twice as big as others? → virtual nodes
• How do you handle a node dying mid-request? → replication + failover
• Cross-shard queries? → avoid them; aggregate at app layer or use a scatter-gather
• How does CDN use this? → next chapter

Practice with hands-on labs

Reading about hash rings is not the same as watching keys jump shards. Run these labs:

• Sharding Lab — add a shard, compare hot-spot behavior with different keys
• Consistency Lab — see what happens when reads hit the wrong shard during migration

In the sharding lab, try adding a fourth shard after loading data on three. Note how many keys the lab reports as "relocated." That number is the modulo tax made visible.

What comes next: virtual nodes and production routing

You now know why hash % N fails at scale and how consistent hashing limits resharding to a fraction of your data. The ring concept is the foundation.

The next chapter covers virtual nodes (fixing uneven load when one machine is beefier than others), how Dynamo and CDNs route requests, and how Memcached/Redis Cluster clients actually pick a node in production.

Continue here: Consistent Hashing in Production.