Published on
|
8 min read

Database Sharding: When Your Single Postgres Can't Handle It

When Instagram's Database Hit the Wall

In 2012, Instagram had a problem. Their single PostgreSQL database held 25 million users and was growing by millions per week. The database server was the most powerful machine AWS offered—and it still wasn't enough.

Queries that took 5ms started taking 500ms. The photos table had billions of rows. Backups took 12 hours. They'd run out of vertical scaling options.

They had two choices: keep throwing money at bigger hardware (which they'd maxed out) or split the database across multiple servers.

They chose sharding. Within months, they'd distributed data across 12 PostgreSQL shards. Query times dropped back to milliseconds. The 3 AM pages stopped.

But it cost them. Years of engineering investment. Cross shard limitations. A lot more operational complexity. Sharding isn't a feature you turn on. It's a fundamental change to how your application works.


Why Single Databases Fail

Every database eventually hits a wall. The question is which wall you hit first.

Storage: disk fills up. Most people hit this around 1-10 TB, depending on what they're storing.

Write throughput: INSERTs start queuing. Single digit thousands of writes per second is usually fine. Once you're north of 10-50K writes/sec, you're in trouble.

Read throughput: SELECTs slow down. This depends heavily on your queries and indexes, but 100K-500K reads/sec is roughly where things get painful.

Connections: "too many connections" errors. PostgreSQL handles maybe 500-5000 concurrent connections before it starts to fall over.

The obvious answer is read replicas. But replicas have limits. All writes still go to one primary. Every replica needs the full dataset. Replication lag means stale reads. If your problem is write throughput or storage, replicas don't help.


What Sharding Actually Is

Sharding splits your data across multiple database servers. Each shard holds a subset of your data.

             ┌──────────────────┐
             │   Application    │
             │  (Shard Router)  │
             └────────┬─────────┘
        ┌─────────────┼─────────────┐
        ▼             ▼             ▼
  ┌───────────┐ ┌───────────┐ ┌───────────┐
  │  Shard 0  │ │  Shard 1  │ │  Shard 2  │
  │ Users 0-33M│ │Users 33-66M│ │Users 66-99M│
  └───────────┘ └───────────┘ └───────────┘

Three shards means 3x write capacity. Each shard only handles its slice of the data. No single database has to store everything.

The catch: your application now needs to know which shard to talk to.

The Shard Key

This is the decision that matters. The shard key determines which shard holds each row. Choose wrong, and you'll be rebuilding everything in a year.

Hash based: hash(user_id) % number_of_shards. Data distributes evenly, but you can't do range queries like "all users from 1-1000."

Range based: user_id 1-1M → Shard 0, 1M-2M → Shard 1. Range queries work, but new data clusters on one shard (the latest range), creating hotspots.

Geographic: region = 'US' → Shard 0. Good for data locality and compliance, but distribution is usually uneven.

Most systems use hash based. It's the simplest and distributes most evenly.


Hash Based Sharding

Here's what the routing looks like:

public class ShardRouter {
    private final int numberOfShards;
    private final Map<Integer, DataSource> shardDataSources;

    public int getShardId(long userId) {
        int hash = Long.hashCode(userId);
        return Math.abs(hash % numberOfShards);
    }

    public Connection getConnection(long userId) throws SQLException {
        int shardId = getShardId(userId);
        return shardDataSources.get(shardId).getConnection();
    }
}

And in your repository:

public Order findByUserIdAndOrderId(long userId, long orderId) {
    String sql = "SELECT * FROM orders WHERE user_id = ? AND order_id = ?";

    try (Connection conn = shardRouter.getConnection(userId);
         PreparedStatement stmt = conn.prepareStatement(sql)) {
        stmt.setLong(1, userId);
        stmt.setLong(2, orderId);
        // execute and map
    }
}

The user ID determines the shard. All of a user's data lives on one shard. Queries by user are single shard (fast). Queries across users need to hit all shards (slow).

The Resharding Problem

Here's the painful part. When you add more shards:

Before: 4 shards → user_id=100 → hash(100) % 4 = 0 → Shard 0
After:  8 shards → user_id=100 → hash(100) % 8 = 4 → Shard 4

Half your data is now on the wrong shard.

This is why production systems use consistent hashing. It minimizes data movement when you add or remove shards. The math is more complex, but the idea is that adding a shard only moves data from that shard's neighbors, not from everywhere.


Cross Shard Queries

This is where sharding hurts. Some queries can't target a single shard.

"Get all orders for user 123" → single shard, fast.

"Get all orders for product 456" → every shard might have orders for that product. You have to query all of them.

public List<Order> findAllOrdersByProductId(long productId) {
    List<CompletableFuture<List<Order>>> futures = new ArrayList<>();

    for (DataSource ds : shardDataSources.values()) {
        futures.add(CompletableFuture.supplyAsync(() ->
            queryOrders(ds, productId)
        ));
    }

    return futures.stream()
        .map(CompletableFuture::join)
        .flatMap(List::stream)
        .collect(Collectors.toList());
}

This is scatter gather. Query all shards in parallel, combine the results. It works, but it's slower than a single shard query, and it doesn't scale as well. Adding more shards means more parallel queries, more network hops, more things that can go wrong.

Design your shard key so that your most frequent queries are single shard. If 90% of your queries are by user, shard by user. If 90% are by product, shard by product. If you need both to be fast... you have a harder problem.


Cross Shard Transactions

Don't.

Distributed transactions are slow and complicated. Two phase commit across shards is a nightmare to get right and a nightmare to debug when it goes wrong.

Use the saga pattern instead. It's a sequence of local transactions with compensating actions if something fails:

public Order createOrderSaga(CreateOrderRequest request) {
    try {
        // Step 1: Reserve inventory (shard A)
        InventoryReservation reservation = inventoryService.reserve(request);

        // Step 2: Charge payment (shard B)
        PaymentResult payment = paymentService.charge(request);

        // Step 3: Create order (shard C)
        Order order = orderRepository.createOrder(request);

        return order;
    } catch (Exception e) {
        // Something failed. Undo in reverse order.
        paymentService.refund(payment);
        inventoryService.release(reservation);
        throw e;
    }
}

Each step is a local transaction. If step 3 fails, you explicitly undo steps 2 and 1. It's more code, but it's easier to reason about than distributed transactions, and it scales better.


ID Generation

Auto increment doesn't work across shards. Shard 0 and Shard 1 will both generate ID 1.

You need globally unique IDs. Twitter's Snowflake is the standard approach:

public class SnowflakeIdGenerator {
    private static final long EPOCH = 1704067200000L; // 2024-01-01
    private final long machineId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    public synchronized long nextId() {
        long timestamp = System.currentTimeMillis();

        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & 4095;
            if (sequence == 0) {
                while (timestamp <= lastTimestamp) {
                    timestamp = System.currentTimeMillis();
                }
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = timestamp;

        // 41 bits timestamp | 10 bits machine | 12 bits sequence
        return ((timestamp - EPOCH) << 22) | (machineId << 12) | sequence;
    }
}

This generates 4,096 unique IDs per millisecond per machine. The IDs are 64 bits, roughly sortable by time (the timestamp is the most significant bits), and guaranteed unique across all shards.

The 10 bit machine ID means you can have up to 1,024 ID generators. The 12 bit sequence means 4,096 IDs per millisecond before you have to wait for the clock to tick.


How Others Do It

Discord shards by channel_id. Messages are always read by channel, never across channels. Makes sense for their access patterns. Within each shard, they bucket messages by time (messages_2024_01, messages_2024_02) and archive old buckets to cold storage.

Notion shards by workspace_id. Users frequently move blocks between documents in the same workspace. Sharding by workspace means cross document search is a single shard query.

Vitess (used by YouTube, Slack, GitHub) is a transparent sharding layer over MySQL. Your application code barely changes—Vitess routes queries based on a VSchema config. If you're on MySQL and want sharding without rewriting everything, Vitess is worth looking at.


When NOT to Shard

Sharding is expensive. In engineering time, in operational complexity, in things that can go wrong at 3 AM. Try everything else first.

Vertical scaling: Have you actually maxed out your hardware? A bigger database server is way simpler than sharding.

Read replicas: If your problem is read throughput, not write throughput, replicas are easier.

Caching: Repetitive queries? Put Redis in front of your database.

Table partitioning: Time series data? PostgreSQL's native partitioning might be enough.

Archival: Old data rarely accessed? Move it to cold storage.

My rule of thumb:

  • Largest table over 100 million rows? Maybe consider sharding.
  • Exhausted vertical scaling? Getting closer.
  • Read replicas not enough? Getting closer.
  • Have a clear shard key that works for 90%+ of queries? Okay, you might actually need to shard.

If you don't have a clear shard key, stop. Rethink your data model. Sharding without a good key is going to hurt.


Migration Strategy

If you decide to shard, don't do a big bang migration. Use the double write pattern:

public void createOrder(Order order) {
    // Phase 1: Write to both. Legacy is source of truth.
    writeToLegacyDatabase(order);
    writeToShard(order);
}

public Order getOrder(long userId, long orderId) {
    // Phase 2: Read from shards, verify against legacy
    Order shardedOrder = readFromShard(userId, orderId);
    Order legacyOrder = readFromLegacy(orderId);

    if (!shardedOrder.equals(legacyOrder)) {
        alertOps("Data mismatch!");
        return legacyOrder;
    }
    return shardedOrder;
}

Phase 1: Write to both databases. Legacy is the source of truth. Shards are getting populated.

Phase 2: Read from shards, but verify against legacy. If they disagree, trust legacy and alert someone.

Phase 3: Cut reads over to shards entirely.

Phase 4: Stop writing to legacy. Wait two weeks. Nothing on fire? Decommission legacy.

This takes months. Plan for it.


The Point

Sharding isn't a feature. It's a fundamental architectural change that affects everything: how you query data, how you generate IDs, how you handle transactions, how you think about your data model.

Before you shard, ask yourself:

  • Have I actually exhausted simpler solutions?
  • Do I have a clear shard key?
  • Am I prepared for 6-12 months of migration?
  • Can my team handle the operational complexity?

Instagram ran a single PostgreSQL database for 25 million users before they sharded. Don't shard prematurely. But also don't wait until your database is on fire at 3 AM.


Further Reading


Mustafiz Kaifee

Mustafiz Kaifee

@mustafiz_kaifee
Share