Partitioning & Consistent Hashing

Partitioning vs replication

Keep these separate in your head, because interviewers will deliberately blur them:

• Replication — the same data on several machines. Buys availability and read capacity.
• Partitioning — different data on different machines. Buys storage and write capacity.

Real systems do both: each partition is replicated. A "shard" in production usually means one partition plus its replica set. When you say "we shard by user ID," you're describing partitioning; the availability story is a separate answer.

Range partitioning

Assign contiguous key ranges to partitions: A–F here, G–M there.

Good: range scans stay on one node. "All events for user X between two dates" is a single-partition query. This is why HBase and Bigtable use it.

Bad: sequential keys create hot spots. Partition by timestamp and every write today lands on the same node while the rest of the cluster idles. The usual patch is prefixing the key with something high-cardinality — <user_id>:<timestamp> — which restores write spread but means a global time-range scan now hits every partition.

Hash partitioning, and why mod N betrays you

Hash the key, and the hash decides the partition. Uniform distribution, no hot spots from sequential keys, and you lose efficient range scans.

The naive form is hash(key) % N. It works beautifully until N changes. The fraction of keys that keep their home when going from N to N+1 servers is only about 1/(N+1):

It gets worse as you grow. That's the opposite of what a scaling strategy should do.

Consistent hashing

Map both servers and keys onto the same circular hash space. A key belongs to the first server it meets walking clockwise. Now adding a server only steals keys from its immediate neighbour: about K/N keys move, not all of them.

Add and remove nodes below and watch the "keys moved" counter. Compare it against the ideal reshuffle — the fraction a perfectly balanced system would have to move.

Two things to notice while you play:

With 1 virtual node per server, the balance is terrible. Random points on a circle clump. You'll routinely see one server holding 2–3× its fair share — the "worst node vs fair share" stat. Hashing gave you uniformity of keys, but the server positions are just as random, and few of them.

Drag the virtual-node slider up and the imbalance collapses. Give each server 100–200 positions on the ring instead of 1 and the law of large numbers takes over; the worst node converges toward 1.05× fair share. This is the entire reason virtual nodes exist.

They also make failure recovery smoother. When a physical node with 200 vnodes dies, its load scatters across all remaining servers rather than dumping entirely onto one unlucky clockwise neighbour — which is how a single failure becomes a cascading one.

What consistent hashing does not fix

Hot keys. One key lives on one partition, full stop. If a celebrity account is read a million times a second, no hashing scheme spreads that — the key is the unit of placement. Fixes are application-level:

• Salt the key into key:0 … key:9 and fan out reads across the copies. Now you own the consistency problem between them.
• A dedicated cache tier in front of the hot partition.
• Request coalescing — collapse concurrent identical misses into one origin fetch.

This distinction — "consistent hashing fixes rebalancing, not skew" — is a reliable way to show depth in an interview.

Rebalancing strategies

Three approaches you should be able to name:

The fixed-count approach is the easiest to reason about and the most common choice for a design interview — but say the number out loud, because picking it is the whole trick. Too few and you can never grow past that many nodes; too many and you pay per-partition overhead on every one. "1024 partitions, so we can scale to 1024 nodes and today each node holds 64" is a concrete, defensible answer.

Request routing

Once data moves, who knows where it is? Three designs:

1. Any node can forward — client hits any node; it proxies to the right one. Simple clients, extra hop. (Cassandra, with gossip spreading membership.)
2. A routing tier — a proxy that knows the partition map. (Redis Cluster proxies, Vitess.)
3. Partition-aware clients — client holds the map and connects directly. Fastest, but every client language needs the logic and stale maps cause redirects.

All three need a source of truth for membership: ZooKeeper/etcd (authoritative, one more system to operate) or gossip (no dependency, eventually consistent membership).

Secondary indexes — the part most candidates miss

Partitioning by primary key is easy. Querying by something else is where it gets interesting:

• Local (document-partitioned) index — each partition indexes only its own documents. A write touches one partition. A query by that secondary field must ask every partition and merge — scatter-gather. Read cost scales with partition count, and your p99 becomes the slowest of N.
• Global (term-partitioned) index — the index itself is partitioned by the indexed term. Reads hit one partition. But a single document write now updates multiple index partitions, which means a distributed write, usually made asynchronous — so the index is stale.

There's no free option. Elasticsearch uses local indexes and eats scatter-gather; DynamoDB GSIs are global and eventually consistent. Naming this tradeoff unprompted is a strong signal.

Worked numbers: resharding without downtime

100 M users, 2 KB profile each = 200 GB. Target 500 GB usable per node with headroom.

• Start: 1024 virtual partitions over 4 nodes = 256 partitions/node, 50 GB/node.
• Growth to 1 TB total → move to 8 nodes: 128 partitions each, and only the partitions that move get copied — 50% of data, not 100%.
• With % N instead: ~87% of keys relocate, and every one is a cache miss during the move.

The migration itself: double-write to old and new placement, backfill in the background, verify with checksums, flip reads, then decommission. The double-write window is the part worth mentioning — it's where the bugs live.

What to take away

• Partitioning buys write and storage capacity; replication buys availability. Different axes, combined in practice.
• hash(key) % N is fine until N changes, and then it's an outage.
• Consistent hashing moves ~K/N keys on membership change. Virtual nodes are not optional — without them, balance is genuinely bad.
• Consistent hashing fixes rebalancing, not skew. Hot keys need application-level answers.
• Secondary indexes force a choice: scatter-gather reads or asynchronous global index writes.