Step 2 of 16 · 1 min

First, the cheaper split

Before splitting one table across many machines, try splitting different tables onto different machines. This is called functional partitioning (or vertical partitioning).

Chirp's database held everything: users, posts, follows, likes, notifications, the outbox, sessions for a while. Several of those are never joined with the others in a query. Notifications are read by user and time (lesson 3.2). Likes, since lesson 4.5, are mostly inserted and counted by a background consumer.

So the team moved notifications to their own Postgres cluster and likes to another. No application logic changed beyond which database each table lived in. It took about three weeks, mostly to move the data without downtime, and it cut the main database's write load by more than half.

That's the first lesson: split by feature before you split by row. It's much simpler, it keeps every query on one database, and it often buys a year or more.

Chirp got about eight months out of it. Then posts and follows alone were too much for one machine.

Step 3 of 16 · 1 min

Splitting rows across machines

Sharding means splitting one table's rows across several databases, called shards. Each shard holds a subset of the rows and handles the reads and writes for them. Each shard still has its own replicas for availability (lesson 2.5); sharding and replication do different jobs, and you need both.

The core decision is the partition key (or shard key): the column that decides which shard a row lives on. Every row with the same key value lives on the same shard.

Once the key is chosen, two rules follow, and everything else in this lesson comes from them:

• A query that includes the partition key can go straight to one shard. Fast, simple, and it scales: adding shards adds capacity.
• A query that doesn't has to ask every shard and combine the answers. That's slower, gets worse as shards are added, and is often the bottleneck you sharded to get away from.

So, like lesson 3.1, you choose by writing down the access patterns and asking which key keeps the important ones on one shard.

Step 4 of 16 · 2 min

Choosing Chirp's keys

Here's what the team worked through for posts:

With the post ID as the key, rows spread perfectly evenly, but the profile page has to ask every shard. With the author's user ID, a user's posts all live together: the profile page is one query on one shard, already sorted, like a wide-column partition from lesson 3.1.

The cost of the author's ID: to load a post by its ID alone, you need to know who wrote it. Chirp solved that neatly with lesson 4.3's IDs. Post IDs were Snowflake-style, so the team gave up a few bits to encode the author's shard inside the post ID. Any service holding a post ID can work out which shard has it without a lookup. Instagram described a similar trick in a well-known 2012 engineering post, putting a logical shard number inside every ID.

Then the other tables:

• Users: by user ID. Obvious.
• Posts: by author's user ID, so they live on the same shard as the author. Keeping related data on the same shard by giving it the same key is called co-location, and it means a user and their posts can still be joined and updated in one transaction.
• Likes: here the obvious key, post ID, would put all 40,000-a-second likes on a viral post onto one shard, the hot-row problem of lesson 4.5 at the scale of a whole database. Chirp keyed likes by the liker's user ID, matching lesson 4.5's choice for events. "Has Priya liked this post?" (asked for every post on every feed) stays on one shard. "Who liked this post?" (asked rarely) becomes a query across shards, served from a separate copy maintained by events.
• Follows: the hardest one, next.

Data that needs two keys

Follows are asked about in both directions: "who do I follow?" (for the feed) and "who follows me?" (for fan-out, lesson 4.4, and mutual friends, lesson 3.1). Whichever key you pick, one direction becomes a query across every shard.

The usual answer is to store it twice: a follows_by_follower table sharded by the follower, and a follows_by_followee table sharded by the person being followed. One follow becomes two rows, often on two different shards.

Now a follow can't be a single transaction. Chirp made follows_by_follower the source of truth. Writing a follow inserts that row and an outbox event (lesson 4.2) in one transaction on the follower's shard, and a consumer writes the other direction a moment later. For a second or so, Meera might follow Priya without appearing in Priya's follower list. Nobody notices a second. A nightly check (lesson 3.3's reconciliation) compares the two copies.

This pattern (one table as the source of truth, other copies derived through events) is how most sharded systems handle data with more than one natural key.

Step 5 of 16 · 2 min

What gets harder

Sharding changes what's easy. It's worth listing honestly what Chirp gave up.

Queries across shards

Anything that doesn't include the partition key has to go to every shard: "the 20 most-liked posts this hour," "all users in Pune," admin searches. The app sends the query to every shard in parallel and merges the results. This is called scatter-gather.

It works for occasional queries, but it has a nasty property you saw in lesson 1.2: the query is as slow as the slowest shard. With 32 shards, the chance that at least one is having a slow moment is high, so scatter-gather queries have poor tail latency even when every shard is healthy.

Chirp's rules became: anything users do often must hit one shard. Search goes to the search index (lesson 3.4), which is built for scatter-gather across its own shards. Analytics, reports and admin queries go to a separate analytics warehouse, fed from every shard by change data capture.

Transactions across shards

Transactions that stay inside one shard work exactly as before. Transactions that need two shards don't, unless you add a distributed transaction protocol, which is slow and complicated (lesson 4.2 explained why most people avoid two-phase commit).

So you design so that things that must change together live on the same shard (co-location), and handle the rest with events and eventual consistency, as with follows. If you find yourself needing many cross-shard transactions, the partition key is probably wrong.

Uniqueness across shards

Usernames must be unique across all of Chirp. A UNIQUE constraint only works within one database. With 32 shards, two people could claim @meera on two different shards at the same moment.

Chirp kept a small, separate, unsharded usernames table on its own database, mapping each username to a user ID. Signing up claims the username there first (the unique constraint does the work), then creates the user on their shard. It's a tiny table with modest traffic, so one database handles it easily, and its replicas handle the lookups.

The general rule: anything that must be globally unique or globally ordered needs a single place that decides. Keep that place small.

IDs

Lesson 4.3 already covered this, and now it pays off. With 32 databases, auto-increment would give every shard its own post 1, 2, 3. Snowflake-style IDs were generated outside the database, so sharding didn't change them at all.

Step 6 of 16 · 1 min

Hot shards

Even with a good key, load is rarely perfectly even.

The cricket commentator from lesson 2.1 now had 30 million followers. Their user ID put their profile, their posts and every reply to them on shard 14. During matches, shard 14 handled six times the load of an average shard. The other 31 shards were fine; shard 14 was the bottleneck for everyone whose data happened to share it.

A few ways to deal with a hot shard:

• Cache harder. Most of shard 14's extra load was reads of the same few posts, which lesson 4.5's local caches absorbed.
• Give heavy users their own shard. With a lookup-based routing scheme (below), you can move one very heavy user to a dedicated shard without touching anyone else.
• Split the hot shard. If one logical shard is consistently overloaded, split it into two. Lesson 5.2 is about doing this without downtime.

Step 7 of 16 · 1 min

Range or hash?

There are two basic ways to turn a key into a shard:

By range. Shard 1 holds user IDs 1 to 1 million, shard 2 holds the next million, and so on. Range queries ("all keys between A and B") stay on few shards, and splitting a busy range is natural. The danger is that sequential keys put all new writes on the last shard: if the key is a timestamp, or an ID that grows with time, today's shard does all the writing while the others sit idle.

By hash. Run the key through a hash function and pick a shard from the result. Writes spread evenly regardless of the key's order. But neighbouring keys end up on random shards, so range queries across keys must ask every shard.

Chirp's Snowflake IDs grow with time, so range partitioning by user ID would have sent all new users' writes to the newest shard. The team hashed the user ID. Within a shard, rows were still sorted by time, so "a user's newest posts" was a fast range query inside one shard. Hash to pick the shard, then sort within it is a very common combination, and it's exactly what Cassandra's partition key and clustering columns do (lesson 3.1).

Step 8 of 16 · 1 min

Finding the right shard

Something has to know which shard holds which key. Three common approaches:

• In the application. A small library computes the shard from the key, using a shard map loaded from configuration. Simple and fast, with no extra network hop, but every service must use the same library and the same map.
• A proxy in front of the databases. Applications connect to the proxy as if it were one database, and it routes each query. Vitess does this for MySQL; the Citus extension turns Postgres into a coordinator plus worker nodes, distributed by a column you choose. Less code in the app, but another layer to run.
• A database that shards itself. Distributed SQL databases such as CockroachDB, Spanner and YugabyteDB split tables into ranges and move them automatically, and support transactions across them. They hide most of this lesson, at the cost of extra latency on writes (they coordinate between machines) and a very different system to operate.

Chirp used a routing library, with a two-step map: user ID hashes to one of 4,096 logical shards, and a small table maps each logical shard to one of 32 physical databases. Lesson 5.2 explains why that indirection is so valuable: it's what makes adding databases later possible without moving everything.

Step 9 of 16 · 1 min

Migrating to shards

Chirp moved posts and follows to 32 shards over four months, with no downtime. In outline:

1. Change the code first. Every query on these tables had to include the partition key or go through a cross-shard path. This was most of the work, and it could be done while everything still lived in one database: the "shards" were all the same database to begin with.
2. Copy the data. For each shard, copy its rows from the old database, then keep it up to date by streaming changes through change data capture (lesson 3.4).
3. Switch over, a slice at a time. For one logical shard at a time, briefly pause writes to it, let the copy catch up, switch the routing map to the new database, and resume. Each pause was under a second.
4. Keep the old copy for a few weeks, in case anything needed to be compared or rolled back.

Step 10 of 16 · 1 min

From the real world: Foursquare's eleven hours

In October 2010, Foursquare, the check-in app, was down for about eleven hours, and its postmortem became a classic lesson in how shards go wrong.

A couple of months earlier, Foursquare had split its check-ins database across two MongoDB shards, by user ID. MongoDB divided the data into chunks and balanced them so that each shard had the same number of chunks. For a while, each shard's data fit comfortably in memory, which was what kept reads fast.

But the users on one shard checked in more than the users on the other. The chunk counts stayed even, while the data size didn't. Nothing alerted on the difference. When the busier shard's data outgrew its RAM, queries started going to disk, slowed by orders of magnitude, requests piled up, and the site went down.

The obvious fix, adding a third shard and moving data onto it, barely helped, for a reason most people wouldn't guess. Check-ins were small documents, around 300 bytes, stored in 4 KB pages. Moving some check-ins off the overloaded shard left holes in pages that still held other check-ins, so the pages stayed in memory, and the shard used nearly as much RAM as before. Freeing the memory needed an offline compaction, which took more hours.

What it teaches about partitioning in general:

• Balance on what actually runs out: bytes, memory, requests per second. Item counts are a proxy, and proxies drift.
• Alert on headroom per shard, not just for the cluster as a whole. "Shard 1 is at 85% of RAM" is the alert that would have mattered.
• Moving data is slow, and doesn't always free what you expect. Rehearse it on a quiet day, at real size, so you know how long it takes before you need it in an emergency.

Step 11 of 16 · 1 min

Going deeper: the key that always lands on the last shard

The "range or hash?" section covered the basic trade-off. There's one case that catches nearly every team that chooses range partitioning, and it's worth seeing on its own: a key that always increases.

Suppose Chirp stores events in a range-partitioned table keyed by created_at, or by an auto-increment ID. Each new row has a larger key than every row before it. So every insert, from every server, lands in the last range. One machine takes all the writes while the others sit idle. Splitting that range doesn't help: the new last range immediately takes all the writes again.

This is why Google's Bigtable and Spanner documentation, and HBase's, warn against keys that begin with a timestamp or a sequence number. The common fixes:

• Lead with something that spreads: the user ID, the device ID, or a short hash of one of them, then the timestamp. Rows for one user stay together and in time order, which is usually what queries want anyway.
• Salt the key: prefix it with a small number of buckets (hash(id) % 16). Writes spread across 16 ranges; a time-window query becomes 16 smaller queries merged together.
• Reverse the bits of sequence numbers. Spanner supports bit-reversed sequences for exactly this reason: consecutive numbers end up far apart in key space, while still being unique integers.
• Use hash partitioning for the table instead, if you don't need range scans on that key.

The choice follows the queries, as always. If the important query is "this user's events, newest first," lead with the user. If it's "everything in the last five minutes," salt it and pay for the merge, or keep recent data in something built for that (a log, lesson 4.1).

Step 12 of 16 · 1 min

What Chirp changed

• Moved notifications and likes to their own databases first.
• Sharded users and posts by user ID (hashed), and co-located each user's posts with them. Post IDs carry the author's logical shard.
• Keyed likes by the liker's user ID, with "who liked this post" as a derived copy.
• Stored follows in both directions, one as the source of truth and the other derived through the outbox.
• Kept usernames in a small, unsharded database.
• Moved reports and admin queries to an analytics warehouse fed by change data capture.
• Routed with a library: user ID → one of 4,096 logical shards → one of 32 databases.

Step 13 of 16 · 1 min

In the simulation

Stage 4's decision D7 is the sharding key, and the simulation's numbers match this lesson: shard posts by post ID and the profile page becomes a scatter-gather across every shard; shard by user ID and the celebrity's shard runs hot; shard by region and one region's shard carries most of the load. There's no option without a trade-off. The aim is to pick the one whose problems you can handle.

Open the simulation →

Step 14 of 16 · 1 min

If you're here for an interview

Sharding comes up in nearly every large-scale design. A strong answer:

• Justifies it with numbers (lesson 1.3): this many writes a second won't fit on one machine.
• Tries the cheaper steps first: vertical scaling, replicas for reads, splitting by feature.
• Chooses the key from the access patterns, and says which queries become cross-shard.
• Names the costs: scatter-gather, no cross-shard transactions, global uniqueness, hot shards.
• Mentions logical shards, or consistent hashing, so it's possible to add capacity later. That's lesson 5.2.

Step 15 of 16 · 1 min

Try these yourself

Step 16 of 16 · 1 min

Further reading

• Martin Kleppmann, Designing Data-Intensive Applications, Chapter 6, "Partitioning."
• Instagram Engineering, "Sharding & IDs at Instagram" (2012).
• Citus documentation on distributed tables and co-location, and Vitess documentation on keyspaces and sharding.
• Jeffrey Dean and Luiz André Barroso, "The Tail at Scale," for why scatter-gather latency gets worse with more shards.
• Eliot Horowitz (10gen), "Foursquare outage post mortem," mongodb-user mailing list, October 2010; and "Troubles With Sharding – What Can We Learn From The Foursquare Incident?" on High Scalability.
• Google Cloud Spanner documentation, "Schema design best practices" (hotspots, and bit-reversed sequences); Apache HBase reference guide, "Monotonically Increasing Row Keys / Timeseries Data."