Database Sharding and Shard Keys
Sharding splits rows across databases by a shard key. Compares hash mod N, ranges and consistent hashing with measured key movement (80% vs 20%), skew and hot-shard results.
Database sharding splits one logical table across several databases by a shard key, so storage and write capacity scale past one machine. The detail interviewers expect: hash mod N remaps most keys when N changes, about 80 percent going from 4 to 5 shards, while consistent hashing with virtual nodes moves only about 1/N.
Sharding splits one logical table across several databases by a shard key, so that storage and writes scale past a single machine. The key choice, the placement rule (hash, range or consistent hashing) and handling hot keys decide whether it works, and each has numbers measured below.
- Replication copies the same data to several servers for reads and availability, while sharding splits different rows across servers so storage and writes scale.
- A good shard key has high cardinality, spreads both data and traffic evenly, and appears in the common query's WHERE clause so the router hits one shard.
- With hash mod N placement, going from 4 shards to 5 moved 80.1 percent of 100,000 keys to a different shard in a measured test.
- Consistent hashing with 100 virtual nodes per shard moved 19.8 percent of keys when going from 4 to 5 shards, close to the expected 1/N.
- Range sharding on auto-increment ids sends every new insert to the shard holding the highest range; the last 10,000 inserts in a test all landed on one shard.
- Hashing spreads keys, not requests: when 20 percent of reads hit one celebrity key, the shard owning it served 40 percent of traffic.
01Why shard at all
Replication copies the same data to several servers. It helps with read capacity and availability, but every replica still stores everything and every write still goes through one primary. When the dataset or the write rate outgrows one machine, you split the rows: each shard holds a different subset, and each can accept writes.
The cost is real. Queries that touch several shards need fan-out and merging, transactions across shards need coordination, and changing the number of shards means moving data. Most teams exhaust cheaper options first: better indexes, a bigger machine, read replicas, caching, archiving old rows. Shard when those no longer fit.
02The shard key decides everything
Every row carries a shard key, such as user_id or tenant_id, and a rule turns it into a shard number. Three properties make a key good: high cardinality (many distinct values), even spread of both data and traffic, and presence in the common query's WHERE clause so the router can send it to one shard.
MongoDB's documentation, which is a clear public description of these ideas, distinguishes ranged sharding, where contiguous key ranges live together, from hashed sharding, where a hash of the key decides placement. The same two families exist in nearly every sharded system.
A poor key is hard to undo. Re-sharding a live table on a different key means rewriting nearly every row, so choose it from your query patterns before launch.
03Hash mod N versus ranges
The simplest rule is shard = hash(key) % N. I hashed 100,000 user keys with MD5 across 4 shards and got 24,902 / 25,162 / 24,770 / 25,166 rows, close to even.
Range sharding assigns key intervals to shards, for instance ids 0 to 249,999 on shard 0. It makes range scans cheap, but with auto-increment ids every new insert lands on the shard holding the highest range. In my run, the last 10,000 inserts (ids 750,000 to 759,999) all went to shard 3 under ranges, and under hash mod 4 they split 2,490 / 2,463 / 2,473 / 2,574.
So: hash for even write spread and point lookups, ranges when range queries on the key matter more than write spread, and a composite or time-bucketed key if you need both.
04Adding a shard: why consistent hashing exists
With hash mod N, changing N changes the shard for almost every key. Going from 4 shards to 5, I measured 80.1 percent of 100,000 keys landing on a different shard. Moving four fifths of your data to add one machine is a poor deal.
Consistent hashing places both shards and keys on a circular hash space. A key belongs to the first shard point clockwise from it. Adding a shard only claims the keys between its points and their predecessors, so roughly 1/N of keys move.
import hashlib, bisect
def h(s): return int(hashlib.md5(str(s).encode()).hexdigest(), 16)
class Ring:
def __init__(self, nodes, vnodes=100):
self.ring = sorted((h(f"{n}#{v}"), n) for n in nodes for v in range(vnodes))
self.points = [p for p, _ in self.ring]
def get(self, key):
i = bisect.bisect(self.points, h(key)) % len(self.ring)
return self.ring[i][1]With 100 virtual nodes per shard, going from 4 to 5 shards moved 19.8 percent of keys. Virtual nodes matter for balance: with a single point per shard, the same 100,000 keys split 45,069 / 1,774 / 26,711 / 26,446, while 100 points per shard gave 24,710 / 25,916 / 23,891 / 25,483.
05Hot keys and skew
Hashing spreads keys evenly, not requests. I simulated 200,000 reads where 20 percent went to one celebrity key and the rest were uniform over 10,000 users. Shard read counts were 40,224 / 40,505 / 79,968 / 39,303 under hash mod 4: the shard owning the celebrity served 40 percent of traffic: 1.6 times its fair share of 25 percent, and about twice the load of each of the other three shards.
Common fixes are caching the hot key in front of the database, splitting it into several sub-keys (celebrity#0 to celebrity#9) and reading one at random, or giving the hottest tenants dedicated shards. A directory (lookup table) mapping keys to shards allows that kind of manual placement at the cost of an extra lookup and a table that must itself be reliable.
06Replication, cross-shard queries and what you give up
Sharding and replication are layered, not alternatives: each shard normally has a primary and replicas, so losing one machine does not lose a slice of data. See the replication and lag topic for what replicas can and cannot guarantee.
What you give up: a join across shards means fetching from several and merging in the application or a router. A multi-shard transaction needs two-phase commit or a saga, both slower and more complex than a single-node transaction. A UNIQUE constraint holds only inside a shard unless the unique column is the shard key. Auto-increment ids need a coordinated generator or ids with a shard prefix. Aggregations such as COUNT(*) become scatter-gather queries.
Systems like Vitess and MongoDB's balancer handle routing and rebalancing, but they do not remove these trade-offs.
07Common interview questions
Q: Sharding versus replication?
A: Replication copies the same data to many nodes for reads and availability. Sharding splits different data across nodes for storage and write capacity.
Q: How do you choose a shard key?
A: High cardinality, even load, and present in the main queries so each request hits one shard. Example: user_id for a user-centric app.
Q: Why is hash mod N a problem?
A: Changing N remaps most keys; in a 4 to 5 test about 80 percent moved.
Q: How does consistent hashing help?
A: Only about 1/N of keys move when a node is added, and virtual nodes keep load balanced.
Q: What is a hot shard and what causes it?
A: One shard getting disproportionate traffic, from a monotonic key under range sharding or from a single very popular key.
Q: How do you run a query that spans shards?
A: Scatter to all relevant shards, gather and merge, accepting extra latency; or denormalise so the common query hits one shard.