Sharding and consistent hashing
Replication copies all the data to more machines; it doesn't help when the data, or the writes, are too much for one machine. Sharding splits the data so each machine holds and handles only part of it. It's the main way to scale writes and storage, and also the decision hardest to undo, because the way you split shapes every query afterwards.
1. The idea
- Partitioning splits a table into pieces. On one machine (PostgreSQL's table partitioning by month, say) it makes big tables manageable and lets you drop old data quickly.
- Sharding puts those pieces on different machines, each a full database for its slice. It multiplies storage and write capacity: ten shards, roughly ten times the writes, if the load spreads evenly.
- The shard key (partition key) decides which shard a row lives on. A good one has many distinct values, spreads load evenly, and keeps each common query on one shard.
Three ways to map keys to shards
| Strategy | How | Good | Bad |
|---|---|---|---|
| Hash | shard = hash(key), mapped onto shards (ideally with consistent hashing) | Even spread; the usual default | Range queries across keys hit every shard |
| Range | Key ranges per shard: users A–F, or IDs 1–1M | Efficient range scans; easy to reason about | Hot spots when traffic clusters (all new rows at the end of the range) |
| Directory | A lookup table maps each key (or tenant) to a shard | Fully flexible; can move one big customer to its own shard | Every request needs a lookup; the directory must be fast and highly available |
2. How it works
Three ways to decide where a row lives
Every sharded system needs a rule that turns a key into a shard. There are three basic rules, and each one makes a different kind of query cheap. Take a bookshop marketplace with three shards for its orders, and switch between the rules:
Many real systems combine them: Cassandra and DynamoDB hash the partition key to pick a node, then keep rows inside each partition sorted so "this customer's orders, newest first" is one ordered read. The table in Under the hood lists which databases use which rule.
Sharding vs federation
Sharding splits one kind of data by rows: all orders, spread across several databases. Federation (also called functional or vertical partitioning) splits by feature: customers in one database, orders in another, the catalogue in a third. It's usually the first split a growing product makes, because it's simple: each database is smaller, busy with one kind of work, and can be tuned and scaled on its own.
Why hash(key) % N is a trap
The simplest hash sharding is "hash the key, take the remainder by the number of shards". It spreads keys evenly, until you add a shard. Press Play.
Consistent hashing
Picture the hash values arranged in a circle (in practice 0 to 232 − 1). Each node is hashed to a point on the ring; each key is hashed too, and belongs to the first node clockwise from it.
- Adding a node takes over only the keys between it and the previous node: about 1/N of the data moves.
- Removing a node hands only its own keys to the next node clockwise.
- Virtual nodes: with one point per node, arcs are uneven and a failed node dumps all its load on one neighbour. Giving each node many points (Cassandra's default is 16 tokens per node) evens out the arcs and spreads a failed node's load across many others. Bigger machines can take more points.
- Hash slots are a simpler variant: Redis Cluster hashes each key to one of 16,384 slots (CRC16 of the key, mod 16384) and assigns slot ranges to nodes. Moving a slot moves exactly its keys.
Try both in section 3.
Hot spots: keys spread evenly, traffic doesn't
Hashing evens out keys, not requests. A celebrity's account or a viral post lives on one shard and can overload it. Fixes, from simplest:
- Cache the hot reads in front (Module 09), or add read replicas of that shard.
- Split the key: write a hot counter as
post:42#0…post:42#9on different shards and sum on read (works for countable things: likes, views). - Isolate the hot tenant on its own shard (easy with directory sharding). Managed stores do some of this automatically: DynamoDB's adaptive capacity isolates frequently accessed items.
What gets harder
- Cross-shard queries: "top 10 posts worldwide" must ask every shard and merge. Precompute such results in the background, or keep a separate index.
- Cross-shard transactions: moving money between users on different shards can't use one local transaction. Keep data that changes together on the same shard (shard by account, by tenant), or use a saga (Module 22).
- Resharding: moving data while serving traffic: copy in the background, write to both old and new locations, switch reads, then clean up. Plan the shard count with room to grow.
3. Try it yourself
Hash ring simulator
10,000 keys on a ring. Add or remove a node and see how many keys move, then raise the virtual nodes and watch the load even out.
Pick the shard key
4. Trade-offs
Shard late, but plan early
One big database with replicas carries most products for years (Module 02's numbers). Shard when the math says so, but pick IDs and data boundaries early that make sharding possible later.
Locality vs spread
Sharding by user keeps a user's data together (fast, transactional) but a power user becomes a hot shard. Sharding by something finer spreads load but scatters queries.
Many small shards
Starting with many logical shards (hundreds), mapped onto a few machines, lets you rebalance by moving whole shards instead of splitting them later.
Buy it rather than build it
DynamoDB, Cassandra, MongoDB, Spanner, CockroachDB and Vitess or Citus (for MySQL and PostgreSQL) shard and rebalance for you. Your job is still the key.
5. In real systems
- Cassandra places data on a consistent hash ring with virtual nodes (
num_tokens, default 16) and replicates each key to the next nodes clockwise; failures are handled by those replicas, not by moving data. - Redis Cluster and Valkey use 16,384 hash slots. A multi-key command must stay within one slot; hash tags (
{user:42}:cartand{user:42}:profile) force related keys into the same slot. - DynamoDB hashes the partition key; each partition serves at most 3,000 reads and 1,000 writes a second, which is why a skewed key throttles a table that looks under-provisioned.
- Vitess (sharded MySQL, created at YouTube) and Citus (distributed PostgreSQL) route queries to shards and support resharding online.
- Kafka partitions topics by key the same way, so all events for one key stay in order on one partition (Module 18).
The technologies up close
user_id, because every main query is per userhash, with consistent hashing), the cost (
global trending needs a scatter-gather, so I precompute it), and the hot-key plan. And don't build it yourself:
DynamoDB with user_id as partition key, or Vitess/Citus for SQL, is a complete answer.Hash sharding with consistent hashing
The default · once the numbers demand itHash the shard key and map it onto shards with a ring (or fixed hash slots), so keys spread evenly and adding a shard moves only a fraction of them.
How it works
Covered above. Choosing the key is the real decision: high cardinality, even load, and common queries hit one shard. Good: user_id for user-centric apps, order_id for orders. Bad: a boolean like is_premium (two shards), created_at on a growing table (every new write hits the newest shard), country (skewed). The key is close to permanent.
Status today
How Cassandra, DynamoDB, Redis Cluster, Kafka and most distributed caches place data. Failures are handled by replicas, not by moving data; data moves only for planned changes.
Use it when
- One database can't keep up with storage, writes or reads, and you've shown it with numbers
- Most queries are scoped to one entity (a user, a tenant, a channel)
Skip it when
- Before the math says so: one large PostgreSQL holds far more than most prompts need (Module 02)
- Range-heavy queries across keys
In the interview
Four steps: The limit is 50k writes a second at peak. Queries are per user, so shard key
Add the growth plan: user_id. Hash with consistent hashing. Global trending needs every shard, so I precompute it in a background job.start with 64 shards; consistent hashing moves only a fraction when we add more.
- Sharding on day one. Premature sharding is the most common mistake interviewers see.
- Naming a shard key without checking the queries: if the main page hits every shard, the key is wrong.
- Confusing the two problems: virtual nodes fix uneven keys; replication, caching and salting fix uneven traffic.
Range sharding
Situational · range scans, tenantsEach shard owns a contiguous range of keys: IDs 1–1M on shard 1, or one range per customer.
How it works
Range scans stay on one shard and data is easy to reason about. But traffic clusters: with time or sequential IDs, all new writes land on the last range. Systems that use ranges (HBase, Bigtable, CockroachDB, MongoDB's ranged sharding) split hot ranges automatically.
Status today
Common inside databases that auto-split; less common as a hand-built scheme.
Use it when
- Multi-tenant SaaS (a range or shard per customer)
- Archives and analytics partitioned by time
Skip it when
- Write-heavy data keyed by time or a sequence: one hot shard takes every write
In the interview
Partition the archive by month for cheap range scans and drops; live writes stay hash-sharded by user.
- Time-range sharding for write-heavy data. The newest shard melts while the rest idle.
Directory sharding
Rare · flexibility at a costA lookup table maps each key or tenant to a shard.
How it works
Every request first asks the directory (usually cached), then goes to the shard. Any tenant can be moved by changing one row, so a huge customer can get a shard of its own.
Status today
Used for large multi-tenant products; rarely the interview answer.
Use it when
- A few tenants are vastly bigger than the rest and need isolating
Skip it when
- Uniform workloads: hashing needs no lookup
In the interview
Only for tenant isolation: A directory maps each tenant to a shard, so the biggest customers get their own.
- Forgetting the directory is on every request's path: it must be cached and highly available.
Vertical partitioning
Situational · different access patternsSplit data by how it's used, each part in a store tuned for it, rather than splitting rows.
How it works
For posts: post_content (written once, read many → a B-tree database), post_metrics (counters updated constantly → an in-memory counter store), post_analytics (append-only events → a time-series or columnar store). Inside one database, the same idea moves rarely used or large columns out of a hot table.
Status today
Standard practice in large products, often combined with horizontal sharding.
Use it when
- One entity has parts with very different read/write patterns
- A hot table is slowed by big, rarely read columns
Skip it when
- Small systems: one table is simpler
In the interview
Like counts change thousands of times a second, so they live in Redis counters flushed periodically; the post itself stays in PostgreSQL.
- Sharding everything when only one part (the counters) is write-hot.
Two-phase commit (2PC)
Rare · usually the wrong answerA protocol to commit one transaction across several databases: a coordinator asks everyone to prepare, then tells them all to commit.
How it works
Participants hold locks between prepare and commit. If the coordinator dies after prepare, participants are stuck holding those locks until it recovers. Every transaction pays extra round trips.
Status today
Exists (XA transactions), and is used inside some distributed databases (Spanner runs 2PC over consensus groups, so the coordinator can't simply vanish). Across services and third-party APIs it's impractical: payment providers don't take part in your transactions.
Use it when
- Inside a database that does it for you (distributed SQL)
Skip it when
- Across microservices or external APIs: use a saga (Module 22)
- Anything on a hot path
In the interview
A user's data stays on one shard so transactions are local; across services we use a saga with compensations rather than 2PC.
- Proposing 2PC across microservices. Expect: what happens when the coordinator crashes after prepare?
- Needing cross-shard transactions often: a sign the shard key or service boundaries are wrong.
Three-phase commit (3PC)
Rare · know why nobody uses itA variant of two-phase commit that adds a "pre-commit" phase so participants can finish without a crashed coordinator.
How it works
Phases: can-commit, pre-commit, do-commit. If the coordinator dies after pre-commit, participants can time out and commit on their own. But it assumes bounded network delays: under a network partition, two groups can decide differently. Real systems instead run 2PC over consensus-replicated participants (Spanner) or use sagas.
Status today
A textbook protocol, rarely deployed.
Use it when
- Answering "how would you fix 2PC's blocking?" in a theory question
Skip it when
- Any real design
In the interview
3PC removes blocking only if delays are bounded, which networks don't guarantee; I'd replicate the coordinator with consensus, or use a saga.
- Proposing 3PC as the fix for distributed transactions in a product design.
Sharded counters
Situational · hot countsOne logical counter (likes on a viral post, views of a video) stored as N sub-counters, so writes spread out and reads add them up.
How it works
Each increment goes to a random sub-counter (likes:42#0 … #15) on different shards (the scene in section 5). Reads sum all N, usually cached for a few seconds. Choose N from the peak write rate divided by what one shard handles; start small and add sub-counters only to hot items. Combine with batching (Module 18) to collapse many increments into one write.
Status today
A well-known pattern (Google's App Engine documentation popularised the name); Twitter, Instagram and YouTube-style counts work this way, often with approximate, eventually consistent totals.
Use it when
- Likes, views, votes, inventory counters under heavy write load
Skip it when
- Counters that must be exact at every read, or that change rarely
In the interview
Like counts are sharded counters, 16 sub-counters for hot posts, summed and cached for 5 seconds.
- One row per post updated 100,000 times a second.
- Sharding every counter, including the millions that get one like an hour.
6. Remember it
How this hook works: what "Split by how you ask; ring it so growth moves little" means
What the slogan means, phrase by phrase
- "Split by how you ask"
- The shard key comes from the dominant access pattern: if every request is about one user, shard by user so each request touches one shard.
- "ring it"
- Map keys with consistent hashing (or hash slots), not with
% N. - "so growth moves little"
- Adding a node moves about 1/N of the keys instead of nearly all of them; virtual nodes spread that movement and the load evenly.
Why this picture fits: a library splits branches by how people look books up, and opening a new branch should only move the books it takes over, not reshelve the whole city.
The story → the concept
| Library branches | Sharding |
|---|---|
| Branches | Shards (separate databases) |
| "Authors A–F go north" | The shard key and mapping |
| A famous author's swamped branch | A hot spot |
| "Every book from 2026" across all branches | A scatter-gather query |
| Opening a new branch | Adding a node: consistent hashing moves only its share |
| Each branch covering several small areas | Virtual nodes |
Watch it on an example
- An orders table reaches 40 TB and 30,000 writes a second: one database can't keep up.
- Most queries are "this customer's orders", so shard by
customer_id, hashed onto 256 logical shards on 8 machines. - Black Friday doubles traffic: add 8 machines and move 128 logical shards, about half the data, in the background, with no key remapping.
- The finance team's "all orders yesterday" report runs on the warehouse, not across shards.
The trap it saves you from
Sharding by a key that matches no query (or a skewed one, like country), and then paying for scatter-gather and hot shards on every request.
It still works when…
You assign WebSocket connections or cache entries to servers (Modules 08, 19): the same ring sends each user or key to a predictable server, and resizing the pool disturbs only a slice.
7. Common mistakes
country, status or is_premium give a few huge shards. Use high-cardinality keys like user or order IDs.hash(device_id) + day) or use time only for archives.% N mappingChanging N remaps almost everything. Use consistent hashing, slots, or many logical shards.8. Design exercise (25 minutes)
- Choose keys for: a chat app's messages, a multi-tenant SaaS app's data, a ride-hailing app's trips, a metrics system's time series. Say what each key makes easy and what it makes hard.
- Size it: 120,000 writes a second at peak, each shard comfortable at 10,000. How many shards, with headroom? How many logical shards would you start with?
- Plan a hot key: one tenant produces 30% of all traffic. Describe two ways to handle it.
- Reshard on paper: write the steps to move from 8 to 16 physical machines without downtime.
- Write it down: the three properties of a good shard key, and why
% Nfails.
9. Self-check quiz
With consistent hashing, roughly what fraction of keys move when you add the Nth node?
Almost every query in a social app is per user. Which shard key?
What do virtual nodes fix?
One viral post's like counter overloads its shard. A common fix?
Which is the worst shard key for a busy orders table?
A viral post's like counter overloads one shard. What helps most?
10. Go deeper
| Resource | Time | Why |
|---|---|---|
| Designing Data-Intensive Applications, chapter 6 (Partitioning) | 1.5 h | Key-range vs hash partitioning, secondary indexes across partitions, rebalancing and routing. |
| Redis Cluster specification | 30 min | Hash slots, hash tags, redirections and resharding in a real system. |
| Dynamo paper (sections 4.1–4.3) | 30 min | Consistent hashing with virtual nodes, as first used at scale. |
| Sharding (Hello Interview) | 20 min | How to raise sharding in an interview, and the follow-ups to expect. |
11. Under the hood (optional)
How data is really split across machines, moved when machines change, and found again. Not needed for most interviews; open it when you want to know how the products really do it. All the deep dives are listed on the Under the hood page.
Partitioning and shardingRange vs hash vs directory, consistent hashing variants with a live lab, splitting, hot keys, routing, resharding, 10 products comparedabout 35 min
Sharding is three decisions: how a key maps to a shard, how shards move when you add machines, and how a request finds the right one. Each product makes them differently, and the consequences show up as hot spots, painful resharding and slow cross-shard queries.
Mapping keys to shards
| Scheme | How | Strength | Weakness | Examples |
|---|---|---|---|---|
| Range | Contiguous key ranges per shard | Range scans stay on one shard; easy to split | Sequential keys (timestamps, increasing IDs) all hit the last shard | Bigtable, HBase, CockroachDB, TiDB, Spanner, MongoDB ranged keys |
| Hash | A hash of the key picks the shard | Even spread, no hot tail | Range queries hit every shard | Cassandra, DynamoDB, Redis Cluster, Citus, Kafka |
| Hash then range | Hash the partition key; keep rows inside a partition sorted by a second key | Spread plus ordered reads within one entity ("a user's messages by time") | One huge or hot partition is still one place | Cassandra (partition + clustering key), DynamoDB (partition + sort key) |
| Directory | A lookup table says where each key or tenant lives | Move any key anywhere; pin big tenants | The directory must be fast, cached and highly available | Vitess lookup vindexes, tenant routing tables, MongoDB zones |
Consistent hashing and its relatives
With hash(key) mod N, adding one server changes N, so almost every key moves. Consistent hashing schemes move only about 1/N of the keys. Add a node and compare:
| Scheme | How it picks | Notes | Used in |
|---|---|---|---|
| Ring with virtual nodes | Each server owns many points on a hash ring; a key goes to the next point clockwise | More virtual nodes give a more even spread; removal and weights are easy | Cassandra (16 tokens per node by default since 4.0), Dynamo, many caches |
| Fixed slots | Hash to one of a fixed number of slots; a table maps slots to servers | Rebalancing moves whole slots; the table is small and explicit | Redis Cluster (16,384 slots), Couchbase vBuckets, Elasticsearch shards |
| Rendezvous (highest random weight) | Score every server with hash(key, server); take the highest | No ring, perfectly even on average, O(N) per lookup | Load balancers, CDNs choosing caches, client-side sharding |
| Jump consistent hash | A few lines of arithmetic map a key to bucket 0…N−1 | No memory, very even, but servers must be numbered and only the last can be removed | Storage and cache layers with numbered shards (from Google, 2014) |
| Maglev hashing | A fixed-size lookup table filled by each backend's preference order | Very fast lookups, small disruption when backends change | Google's Maglev load balancer, Envoy's Maglev policy |
| Bounded loads | Consistent hashing, but a server above (1 + ε) × average load passes keys on | Caps hot servers while keeping most keys in place | HAProxy and some cache tiers |
Fixed partitions vs splitting
- Many fixed partitions from day one (Kafka partitions, Elasticsearch primary shards, Redis slots, Citus's default of 32 shards per table): adding a machine moves whole partitions, never re-hashes keys. The count is hard to change later: Kafka can only add partitions (which remaps keys), Elasticsearch needs split, shrink or reindex.
- Split as you grow (Bigtable and HBase regions, CockroachDB ranges up to 512 MiB by default, TiDB regions, Spanner splits, MongoDB chunks): a range that gets too big or too busy splits in two, and a balancer moves pieces around. No up-front guess, but each split and move is work the system must do safely online.
- DynamoDB does both automatically: partitions split when they pass about 10 GB or sustained heat ("split for heat"), and adaptive capacity lends throughput to busy partitions. Each partition still serves at most about 3,000 reads and 1,000 writes per second, so a single hot key can't go faster.
Choosing a shard key, and hot keys
- High cardinality, even frequency, not monotonic: user or tenant ID, order ID. Not country (few values), not created_at (all new writes on one shard), not status.
- Matches the main query: the key in the WHERE clause of the busiest request, so it hits one shard.
- Hot keys (a celebrity, a flash sale item) beat any key choice. Fixes: cache the reads; salt the writes across several sub-keys and merge on read; split a hot range; or give the hot entity its own shard.
Routing, rebalancing and secondary indexes
| Who finds the shard | How | Examples |
|---|---|---|
| Smart client | The driver caches the shard map and goes direct; redirects (MOVED) correct it | Redis Cluster clients, Cassandra token-aware drivers, Kafka producers |
| Proxy / router | A stateless tier knows the map and forwards | MongoDB mongos, Vitess VTGate, Citus coordinator, Twemproxy |
| Any node | Whichever node receives the request coordinates it | Cassandra coordinators, CockroachDB gateway nodes, Elasticsearch |
- Resharding without downtime follows one recipe: copy existing data to the new layout while streaming ongoing changes (Vitess VReplication, MongoDB's online resharding), verify, then switch reads and writes over, with a way back.
- Local secondary indexes live on each shard with its data: writes stay single-shard, but a query by that column asks every shard (Elasticsearch, Cassandra SAI, DynamoDB local secondary indexes). Global secondary indexes are partitioned by the indexed column: one-shard reads, but every write updates another shard, usually asynchronously (DynamoDB GSIs, CockroachDB indexes).
- Scatter-gather is as slow as the slowest shard: with 50 shards, a 1-in-100 slow response hits about 40% of queries. Co-locate data that's queried together (Citus co-location, Spanner interleaved tables) and keep cross-shard queries off the hot path.
Product by product
| Product | How a key finds its shard | Splitting and rebalancing | The detail worth knowing |
|---|---|---|---|
| MongoDB | Ranged or hashed shard key; mongos routers consult config servers | A balancer moves chunks; collections can be resharded online (since 5.0) | An increasing ranged key sends every insert to one shard |
| Cassandra | Murmur3 hash of the partition key onto a token ring with virtual nodes | A new node takes over token ranges and streams their data | No cross-partition queries by design: one table per query |
| DynamoDB | Hash of the partition key | Automatic splits by size and heat; adaptive capacity | About 1,000 writes and 3,000 reads per second per partition |
| Vitess (MySQL) | Vindexes map a column to a keyspace ID; shards own ranges of IDs | Copy with VReplication, then switch traffic | Grows an unmodified MySQL application past one server |
| Citus (PostgreSQL) | Hash of a distribution column into a fixed number of shards | Shards move between worker nodes | Co-located tables join locally; small tables are copied to every node |
| CockroachDB / TiDB | Key ranges, each its own Raft group | Automatic splits by size and load, then rebalancing | Sequential keys make a hot range; hash-sharded indexes spread them |
| Spanner | Key ranges (splits), each a Paxos group | Automatic | Interleaved tables keep a parent with its children |
| Elasticsearch / OpenSearch | Hash of the routing value modulo the primary shard count | Fixed per index; split, shrink, reindex or roll over time-based indexes | Too many small shards waste memory; too few cap parallelism |
| Redis Cluster | CRC16 of the key modulo 16,384 slots | Slots migrate; clients follow MOVED and ASK | Hash tags keep related keys in one slot |
| Kafka | Hash of the message key modulo the partition count | Partitions can be added, never split; adding remaps keys | Order holds only within a partition |
Say it in the interview
- "What happens when you add a shard?" With modulo hashing nearly everything moves; with consistent hashing or fixed slots about 1/N moves, copied in the background while the old owner keeps serving, then switched over.
- "Your shard key is a timestamp. Problem?" Every new write goes to the newest range: one hot shard. Hash it, prefix it with a high-cardinality value, or use a hash-sharded index.
- "How would you handle a celebrity's like counter?" Salt the key into, say, 16 sub-counters on different shards, increment one at random, sum on read (and cache the sum).
With consistent hashing and N servers, roughly what fraction of keys move when one server is added?
Why are queries on a local secondary index expensive in a sharded store?
DynamoDB splits hot partitions automatically. Why can a single hot key still throttle?
Sources
- MongoDB: sharding
- MongoDB: reshard a collection
- Cassandra: Dynamo-style architecture
- DynamoDB: key range throughput exceeded (hot partitions)
- Vitess: shards
- Citus: choosing a distribution column
- CockroachDB: distribution layer
- CockroachDB: hash-sharded indexes
- Elasticsearch: size your shards
- Redis Cluster specification
- Spanner: schema and data model
- Jump consistent hash (Lamping and Veach, 2014)
- Maglev load balancer (Google, 2016)