System design guide
Sharding and consistent hashing for system design interviews
Once your estimates show the data or write rate won't fit on one machine, you shard. The interviewer then wants to know how: what key, what scheme, what happens to queries that span shards, and how you add capacity later without downtime.
When to shard
Shard when one machine can't hold the data, can't take the write rate, or can't serve the read rate even with replicas. Say the trigger out loud, based on your estimates: "90 TB and 3,500 writes a second at peak, so we'll shard by short code." Before sharding, mention the cheaper steps: vertical scaling, read replicas, and caching. Sharding adds real complexity, and interviewers like to see that you know it.
Sharding schemes
| Scheme | How keys map to shards | Good for | Watch out for |
|---|---|---|---|
| Range | Contiguous key ranges (A–F, G–M, ...) or time ranges | Range scans, time-series | Hot spots (all new writes hit the latest range) |
| Hash (mod N) | hash(key) mod N | Even distribution | Changing N remaps almost every key |
| Consistent hashing | Keys and servers on a hash ring; key goes to next server clockwise | Even distribution plus cheap rebalancing | Range scans are impossible across the ring |
| Directory / lookup | A lookup service maps key (or tenant) → shard | Flexible placement, moving big tenants | The directory is a dependency that must be fast and highly available |
| Geographic | By user region | Latency, data residency | Uneven region sizes; cross-region users |
Consistent hashing
Place servers at points on a ring of hash values (say 0 to 232−1). Hash each key onto the same ring; it belongs to the first server clockwise. When a server is added, it takes over only the keys between it and its predecessor; when one is removed, only its keys move to the next server. On average only about 1/N of keys move, compared with nearly all of them when you change N in hash mod N.
Virtual nodes give each physical server many points on the ring (often 100 or more). That smooths out uneven ranges, spreads a failed server's load across many others instead of one neighbour, and lets bigger machines take proportionally more points.
Replication on the ring: store each key on the next R distinct servers clockwise. This is how Dynamo-style stores such as Cassandra and Riak place replicas.
Choosing a shard key
- Matches the main access pattern, so common queries hit one shard. If most queries are "get a user's data", shard by user ID.
- High cardinality and even spread: country code is a bad key (a few huge values); user ID is usually good.
- Keeps related data together when you need transactions or joins: shard orders and order lines by the same customer ID.
- Avoids monotonic hot spots: a timestamp as a range key sends all writes to the newest shard. Hash it, or prefix it with a bucket number.
Problems sharding creates
Hot partitions
A celebrity user, a viral post, or a huge tenant can overload one shard even with a good key. Options: split that key's data with a suffix (post_123#0..9) and combine on read, cache it aggressively, or move the tenant to a dedicated shard via a directory.
Cross-shard queries
Queries that don't include the shard key must scatter to every shard and gather results, which gets slower as shards grow. Fixes: maintain a secondary index sharded by the other key (a second table keyed by email for "find user by email"), or send analytical queries to a warehouse instead.
Cross-shard transactions
Atomic updates across shards need two-phase commit or a saga (a sequence of local transactions with compensating actions). Better: choose the shard key so most transactions stay on one shard.
Resharding
Plan for growth from day one. Common approaches: start with many logical shards (say 1,024) mapped to a few physical machines, then move logical shards to new machines as you grow; or use consistent hashing so adding a node moves only a slice of data. Moving data live means copying, then dual-writing or replaying a change log, then cutting over per shard.
How to talk about it in an interview
- State why sharding is needed, with a number.
- Name the shard key and why it fits the access pattern.
- Name the scheme (usually hash or consistent hashing) and how you'll add capacity.
- Name one problem it creates in this design (hot key, cross-shard query) and how you'll handle it.
Worked examples: URL shortener (shard by code), chat (shard by conversation), and distributed cache (consistent hashing with virtual nodes).
FAQ
What's the difference between sharding and partitioning?
They're used almost interchangeably. Partitioning is the general idea of splitting data into parts; sharding usually means those parts live on different machines. Replication is different: it copies the same data to several machines.
How do I choose a shard key?
Pick the key that most queries filter by (so they hit one shard) and that spreads load evenly (high cardinality, no single value that's much hotter than others). User ID is a common choice for user-centric apps; for chat, conversation ID; for a URL shortener, the short code.
Why use virtual nodes in consistent hashing?
With one point per server, the ring splits unevenly and a removed server dumps all its keys on one neighbour. Giving each server many points spreads its key ranges around the ring, which evens out load and spreads the impact of adding or removing a server.