Sharding and Partitioning

Sharding is the thing interviewers love to ask about and beginners love to over use. It is a real tool, and a painful one. The goal of this note is to help you know when you need it, how to do it with the least damage, and how to talk about it without sounding like you memorised a blog post.

When one database is not enough

Start with the good news. One database server is stronger than most people think.

A normal cloud machine can hold a few terabytes of data on its disk. A well tuned Postgres on it can serve several thousand simple queries a second, and handle a few thousand writes a second. Add read replicas (extra copies that only answer reads) and the read side stretches much further.

So when do you actually run out? Usually one of these three things happens.

Size. Say a shop gets 5 million orders a day, and each order with its items takes about 1 KB. That is 5 GB a day, so about 1.8 TB a year. After three years you are near 6 TB, and with indexes closer to 9 TB. The machine may still work, but backups take half a day, restoring takes longer, and adding a column to the table becomes a scary weekend job.

Write rate. Reads can be copied to replicas. Writes cannot, because every write has to go through the one primary machine (the leader). If you need 50,000 writes a second sustained, a single primary will fall over no matter how big you make it.

Memory. Databases are fast when the busy part of the data, the "hot set", fits in RAM. When the hot set outgrows the biggest machine you can buy, every query starts hitting disk.

Notice that 5 million orders a day is only about 58 writes a second on average. That is tiny. So in that example the pressure is size and upkeep, not speed. When you say this out loud in an interview, show the arithmetic. It tells the interviewer you are reasoning, not guessing.

Vertical versus horizontal

There are two ways to grow.

Vertical scaling means buying a bigger machine. More CPU, more RAM, bigger disk. It is like moving your shop to a larger shop.

Horizontal scaling means adding more machines and sharing the work. It is like opening a second and third branch.

Vertical is easier. Your code does not change, and transactions and joins keep working. It has a ceiling and the price rises steeply near the top, and one machine is still one machine that can fail.

Horizontal has almost no ceiling, but your code and your thinking have to change. Sharding is how you scale a database horizontally.

My opinion: go vertical first, add replicas and caching next, and shard last. Sharding is a one way door. Once the data is spread over twelve machines, you rarely get to go back.

What sharding means

Sharding means splitting one big table into smaller pieces, and putting each piece on a different machine. Each piece is a shard. Every row lives on exactly one shard.

You may also hear partitioning. People often use the two words loosely. A useful way to separate them: partitioning is the general idea of cutting data into parts, and sharding is partitioning where the parts live on different machines. Postgres can partition a table on a single server too, which helps with maintenance but not with the size of the machine.

Think of a school with 3,000 students and one registration desk. The queue is out the door. So the school makes three desks: surnames A to H, I to P, Q to Z. Each desk has its own clerk and its own files. A student only visits one desk. The big question in sharding is the same: how do we decide which desk a row goes to?

That router can be a library in your app, a proxy in front of the databases, or the database itself (Cassandra and MongoDB do it for you).

Three ways to decide where a row goes

Range based

You cut the key into ranges. Users with ids 1 to 1,000,000 go to shard 1, the next million to shard 2, and so on. Or orders from January go to one shard and February to another.

It is easy to understand, and range queries are cheap. "Give me all orders from 1 to 7 March" touches one shard, or two at the edges.

The weakness is hot spots. If the key grows over time, like an order id or a timestamp, all new writes land on the last shard. The others sit idle while one machine takes every new order. Ranges can also become uneven, for example when names starting with "S" are far more common than names starting with "X".

Hash based

You run the key through a hash function (a recipe that turns any value into a random looking number) and take the remainder:

shard = hash(user_id) % 8

Rows spread out evenly, because the hash scrambles the keys. A new order from user 5 and one from user 6 go to completely different shards, so no shard gets all the new writes.

The weakness is that you lose order. Neighbouring keys are scattered, so a range query like "all users who signed up this week" has to ask every shard. And the % 8 is fragile. If you move from 8 shards to 9, the answer for most keys changes, so most data has to move. We come back to that below.

Directory based

You keep a lookup table somewhere that says exactly where each key lives.

It is the most flexible. You can move one big customer to its own machine and just update one line. You can mix strategies.

The cost is that the directory is now a critical piece. Every query asks it first, so it has to be fast, cached, and kept alive with replicas. If it dies, everything dies. It also becomes one more thing to keep correct.

Side by side

If someone asks which to use and gives you no clue, hash on a well chosen key is the safest default. Range when you truly need range scans, and directory when you need fine control, like giving a few giant tenants their own shards.

Picking a shard key

This is the most important decision, and the hardest one to undo. The shard key is the column you hash or range on. A good key has three qualities.

It has many different values, so data can spread out. It spreads load evenly, so no shard is busier than the rest. And it matches how you read, so the most common queries touch one shard only.

Good examples for an orders system:

• user_id. A customer looks at their own orders, so one shard answers. Millions of users means a nice even spread.
• tenant_id in a software product that serves companies, if no tenant is giant.
• chat_id for a messaging app. All messages of one chat sit together.

Bad examples:

• created_at. Every new write goes to the newest shard. Classic hot spot.
• country. Only about 200 values, and a few countries are huge. You cannot spread them over 500 shards, and the biggest country will melt one machine.
• status. Maybe 5 values, and "pending" is where all the action is.
• A boolean, or anything with very few values.
• order_id when your main query is "orders for a user". It spreads nicely, but now showing one user's order list asks every shard.

A good question to ask yourself: "What is my most common query, and does it include the shard key?" If the answer is no, think again.

The mistake almost everyone makes is choosing the key that spreads data best, and forgetting how the data is read. Both matter. When they pull in different directions, I would favour the key that keeps the common read on one shard.

Hot shards

Even with a good looking key, one shard can get far more traffic than the rest. This is a hot shard.

The usual cause is that a few keys are much bigger than the others. Say you shard a social app by user_id. Most users have 200 followers. One celebrity has 40 million. Everything about that account, every like and every comment, lands on one shard. The machine holding it is on fire while the other eleven are bored.

Ways to deal with it:

• Give the big key its own shard, or split its data further. Directory based sharding makes this easy.
• Add a small random piece to the key for the hot keys only. Instead of celebrity_id, write to celebrity_id#0 through celebrity_id#9. Writes spread over ten shards. The cost is that reads have to gather from all ten.
• Cache the hot reads so most of them never reach the shard.
• Pick a better key in the first place, which is the cheapest fix and the one nobody can do later.

When you spot a skewed key in an interview design, say so before the interviewer does. It earns real credit.

Cross shard queries

Sharding makes the queries that fit your key cheap, and the ones that do not fit expensive.

Say orders are sharded by user_id, and the restaurant owner opens a page: "all orders for my restaurant today". The data for one restaurant is scattered over every shard. The only way is scatter and gather: send the question to all shards, wait for all the answers, and merge them. If you have 20 shards and one is slow, the whole page is slow. The slowest shard decides the speed.

Joins are the same problem. A join between two tables is cheap when both sit on one machine. If the rows live on different shards, the database has to ship data across the network. Many teams stop joining across shards altogether, and do the join in the application, or copy a bit of data to where it is needed.

Some common fixes:

• Keep a second copy of the data, sharded by a different key, to answer a different question. Orders by user in one place, orders by restaurant in another. Keeping them in step is your job.
• Send heavy reporting questions to a separate analytics store, not to the live shards.
• Keep small, rarely changing tables (like a list of countries or product categories) fully copied on every shard so joins stay local.

Cross shard transactions

A transaction on one machine is simple. The database makes the changes together or not at all.

Now say a customer pays with a wallet, and the wallet row lives on shard 1 while the order row lives on shard 4. You need both changes or neither. There are two options, and neither is nice.

A distributed transaction, usually two phase commit. A coordinator asks every shard "can you commit?", and only when all say yes does it tell them to go. It is correct, but slow, and if the coordinator dies at the wrong moment, shards can be left holding locks and waiting. It also lowers availability, since every shard involved must be up.

A saga. You break the work into steps, each in one shard, and if a later step fails you run an undo step for the earlier ones (refund the wallet). It is faster and keeps working when parts are down, but you have to write the undo logic and accept that, for a moment, the system is half done.

The honest advice is to design so you rarely need either. Choose a shard key so that things which change together live together. For orders, that means keeping an order and its items on the same shard, which is easy because they share the user.

Resharding is painful

You start with 4 shards. A year later they are full, and you need 8. This is resharding, and it is where sharding hurts the most.

Look at what happens with the simple hash recipe. With 4 shards, user 10 goes to 10 % 4 = 2. With 8 shards, it goes to 10 % 8 = 2, lucky, same place. But user 13 goes from 13 % 4 = 1 to 13 % 8 = 5. Moving from N to N plus 1 shards, nearly every key changes home. It is like a shop that reassigns every customer to a new desk because it opened one extra desk. All that data has to move while the system keeps taking orders.

Two ideas help. I will only name them here, since they are their own topic.

Consistent hashing. Machines and keys are placed on a circle, and each key belongs to the next machine around the circle. Add a machine and only the keys right next to it move, roughly 1 in N of the data, instead of nearly everything. There is a separate note on this.

Pre-splitting. Do not hash straight to machines. Hash to many small logical buckets, say 256 or 1,024 right from the start, and keep a map from bucket to machine. Begin with 4 machines holding 64 buckets each. When you need more, move whole buckets to a new machine. The key to bucket rule never changes, so no key is recomputed. Many real systems work this way.

Even with these, moving data live is slow and risky. Plan to copy first, keep the copy up to date, then switch over. That is a lot of work, which is why you should size your shard count for the next couple of years, not the next couple of months.

Worked example: sharding an orders table

Back to the shop: 5 million orders a day, about 9 TB after three years. Time to shard.

First, list how the data is read. We care about three questions:

1. "Show me my orders." Very common, from the customer app.
2. "Show me order 98231." Common, from support tools and links in emails.
3. "Show me all orders for restaurant 55 today." Less common, from the restaurant dashboard.

Choose the key. user_id fits question 1 perfectly, and users are numerous and fairly even. So we hash on user_id, with 64 logical buckets spread over 4 machines to start. Each order and its items share the same user_id, so they stay together and an order plus its items can be saved in one local transaction.

bucket = hash(user_id) % 64
machine = bucket_map[bucket]

Question 2 is a problem, because the order id alone does not tell us the user. Two fixes. Put the bucket number inside the order id, so the id itself tells you where to look (for example, the first 6 bits are the bucket). Or keep a small lookup table from order id to user id. I prefer the first, because it needs no extra lookup.

Question 3 does not fit the key, so we do not fight it. We keep a second table, orders_by_restaurant, sharded by restaurant_id. When an order is saved, an event is published and a small worker writes the copy. The dashboard might be a few seconds behind, which is fine for a dashboard.

Daily revenue reports go to a separate analytics database, so no one runs a giant query over all shards.

What we gave up: the restaurant copy can lag, we have two places to keep right, and any new question needs thinking about which shard it hits. What we got: each customer query touches one machine, the write load is split four ways, and every shard is around 2 TB, which is easy to back up.

Interview talking points

A shape that works:

1. Show the numbers that force sharding. "About 9 TB in three years, and the primary is the only place that can take writes."
2. Say what you tried first. "I would first add replicas and a cache, and only then shard."
3. Name the key and test it against the queries. "User id, since the main read is a user's own orders, and it spreads evenly."
4. Pick a scheme and say why. "Hash into logical buckets, so adding machines later means moving buckets, not rehashing everything."
5. Admit the costs without being asked. "Restaurant queries do not fit this key, so I would keep a second copy. Cross shard transactions I would avoid by keeping an order and its items together."

If the interviewer pushes on hot shards or resharding, you already have your answer ready, because you raised those costs first.

Interview questions to check yourself

"A single database has 6 TB of data and 100 writes a second. Is the problem speed or size, and does it justify sharding?"

It is size and upkeep, not speed. It may justify sharding, but I would try a bigger machine, replicas and archiving old data first.

"Why is created_at a bad shard key?"

New rows all have the newest timestamp, so every write lands on the same shard, and the others sit idle.

"With hash(key) % N, what goes wrong when you change N from 8 to 9?"

Almost every key maps to a different shard, so almost all the data has to move. Consistent hashing or logical buckets avoid this.

"Orders are sharded by user_id. How do you answer "all orders for restaurant 55"?"

A plain query has to ask every shard and merge the results. Better is a second copy of the data sharded by restaurant_id, kept up to date with events.

"Why do cross shard transactions hurt, and what is the usual advice?"

They need slow coordination like two phase commit, and fail awkwardly when a shard is down. Design the key so related data lives on one shard, and use sagas when you cannot.