GamifiedGamified challengesPracticeRaceLeaderboardPricing

Learn data structures by watching them move, then doing it yourself. Press M anytime to toggle sound.

A product of Amypo Technologies, Coimbatore.

Learn

  • All topics
  • Learning path
  • How it works
  • About dotprep

Practice

  • Practice arena
  • Daily challenge
  • Gamified challenges
  • Race mode
  • Leaderboard

Interview prep

  • Java interview
  • Coding questions
  • Company questions
  • System design
  • Jobs & careers

You

  • Dashboard
  • Settings
  • Pricing
  • Create account

© 2026 dotprep

Content last updated 20 November 2026

GamifiedGamified challengesPracticeRaceLeaderboardPricing
System designSharding and consistent hashing

Sharding and consistent hashing

Splitting data across machines: shard keys, range vs hash partitioning, hot spots and consistent hashing.

intermediate 13 min read 5 interview questions

On this page

1/6
  1. 01Why shard
  2. 02Partitioning strategies
  3. 03Choosing a shard key
  4. 04Consistent hashing
  5. 05Interview questions
  6. 06Quick check
Back to top

Why shard

Replication copies the same data to more machines, which helps reads. When the writes or the data size outgrow one machine, you have to split the data itself: each shard (partition) holds a subset of rows and handles writes for them.

Sharding is a big step: cross-shard joins and transactions become hard, and rebalancing is operational work. Exhaust simpler options first (bigger hardware, caching, read replicas, archiving old data).

Partitioning strategies

StrategyHowProsCons
RangeShard by key ranges (A–F, G–M…) or datesEfficient range queriesHot spots: all new orders land on the latest range
Hashshard = hash(key) mod NSpreads load evenlyRange queries hit every shard; changing N moves most keys
Consistent hashingKeys and nodes on a hash ringAdding a node moves only ~1/N of keysNeeds virtual nodes for even balance
Directory / lookupA service maps each key to a shardFully flexible placementThe directory is another critical component
GeographicShard by user's regionData near users, data residency rulesUneven regions

Choosing a shard key

  • High cardinality: many distinct values, so data can spread out.
  • Even access: no single value gets most of the traffic (a celebrity's user id can be a hot key).
  • Matches queries: the most common queries should include the key, so they touch one shard. For a chat app, conversation_id keeps a conversation's messages together.
  • Stable: changing a row's shard key means moving the row.

Consistent hashing

Picture the hash space as a ring. Each node is hashed to a point on it; each key is hashed too and belongs to the first node clockwise. When a node joins, it takes over only the keys between it and its predecessor. When one leaves, only its keys move to the next node.

With few nodes the arcs are uneven, so each physical node is placed at many points (virtual nodes, often 100–200). That evens out the load and lets a bigger machine take more virtual nodes. DynamoDB, Cassandra and many caches use this scheme.

java
class Ring {
private final TreeMap<Integer, String> ring = new TreeMap<>();
void add(String node) {
for (int v = 0; v < 150; v++) ring.put(hash(node + "#" + v), node);
}
String nodeFor(String key) {
Map.Entry<Integer, String> e = ring.ceilingEntry(hash(key));
return (e != null ? e : ring.firstEntry()).getValue(); // wrap around
}
}

Routing with a consistent-hash ring

1/4
App serverShard routerhash ringShard 1arc 0–33%Shard 2arc 33–66%Shard 3arc 66–100%

Save message for conversation 8812. The router hashes the shard key: hash(8812) lands at 41% of the ring.

See it animated

Hash functionsSeparate chainingBinary search tree

Interview questions

Try answering out loud first, then open the model answer.

Q1What's the difference between replication and sharding?beginner

Replication copies the whole dataset to several machines for availability and read scaling. Sharding splits the dataset so each machine holds part of it, scaling writes and storage. Production systems usually do both: each shard is replicated.

Q2Why does hash mod N rebalance badly?intermediate

Changing N changes almost every key's remainder, so going from 4 to 5 servers moves about 80% of the keys. For a cache that's a near-total miss storm; for a database it's a huge migration. Consistent hashing moves only the keys in the affected arc, about 1/N.

Q3How do you handle a hot shard?advanced

Find out whether it's one hot key or a skewed key range. For a hot key: cache it, replicate it to more readers, or split it by appending a suffix (key#1…key#10) and merging on read. For a skewed range: split the range, or switch to a hashed key. Directory-based sharding lets you move hot data explicitly.

Q4What are virtual nodes?intermediate

Each physical node is hashed onto the ring many times. This smooths the distribution so each node owns roughly equal key space, spreads a failed node's load across many others instead of one neighbour, and lets you weight stronger machines with more points.

Q5How do you query across shards?advanced

Scatter-gather: send the query to every shard and merge results, which is slow and only as fast as the slowest shard. Better to design the shard key so common queries hit one shard, keep secondary indexes (local or global), or denormalise data so it's stored where it's read.

Quick check

Question 1

1.Sharding mainly helps scale…

Question 2

2.Adding a node with consistent hashing moves roughly…

Question 3

3.Which shard key is most likely to create a hot spot?

0 of 3 answered

Databases: SQL, NoSQL and replicationCAP theorem and consistency
Log inStart free