Database Sharding

The Core Idea

Database sharding is the practice of splitting a large database into smaller, faster, more manageable pieces called shards. Each shard holds a subset of the data (e.g., users A-M on shard 1, N-Z on shard 2). Sharding enables horizontal scaling — you can add more shards as data grows.

Step-by-Step Walkthrough

A routing layer sits between the application and database. When a query arrives (SELECT * FROM users WHERE user_id = 12345), the router hashes user_id, determines the shard (12345 % 4 = shard 1), and routes the query to shard 1. Each shard is a separate database instance with its own storage, replicas, and backups.

Resharding (adding/removing shards) is the hardest operational challenge. Consistent hashing minimizes data movement. Many teams use managed databases (DynamoDB, CockroachDB) that handle sharding automatically.

Why This Approach Wins

• Shard key: The column used to determine which shard holds a row. Choose carefully — a bad shard key creates hot spots.
• Range-based sharding: Shard by ranges (users 1-1M on shard 1, 1M-2M on shard 2). Simple but can create hot spots if recent data is accessed more.
• Hash-based sharding: Hash the shard key and mod by number of shards. Even distribution but range queries require querying all shards.
• Directory-based sharding: A lookup table maps each key to its shard. Most flexible but the directory is a single point of failure.
• Cross-shard queries: JOINs across shards are expensive or impossible. Design your shard key to keep related data together.

In Production

Instagram shards their PostgreSQL database by user_id. Each shard holds millions of users with their photos, likes, and comments.

Discord shards messages by channel_id + timestamp. This keeps all messages in a channel on the same shard for efficient reads.

Vitess (YouTube's sharding middleware) adds horizontal sharding to MySQL, used by Slack, GitHub, and Square.

Tradeoffs and Limitations

• Complexity vs Scale: Sharding adds enormous operational complexity. Avoid it until you truly need it.
• Shard key choice: Optimizing for one access pattern (shard by user_id) may penalize another (aggregate across all users).
• Transactions: Cross-shard ACID transactions are extremely expensive (2PC). Design to keep transactions within a single shard.

Production Gotchas

1. Choosing a shard key that creates hot spots (e.g., sharding by created_date puts all new data on one shard)
2. Cross-shard JOINs in production — these are orders of magnitude slower
3. Not planning for resharding from the start
4. Sharding too early — start with read replicas and vertical scaling first

The Interview Angle

1. What is database sharding and when do you need it?
2. What are the different sharding strategies?
3. How do you choose a shard key?
4. What are the challenges of cross-shard queries?
5. How do you handle resharding?

Next Up

• consistent-hashing
• database-scaling
• data-replication
• sql-vs-nosql
• database-indexes

The Real-World Incident That Made This Famous

Instagram's sharding story is one of the most cited examples in system design. In 2012, Instagram had 30 million users and was growing fast on a single PostgreSQL database. They needed to shard, and they faced the classic problem: how to generate unique IDs across multiple database shards without coordination.

Auto-incrementing IDs would not work because two shards could generate the same ID. UUIDs were too large (128 bits) and not sortable by time, which hurt index performance. Twitter had recently published their Snowflake ID generator, but Instagram wanted something simpler that did not require a separate service.

They invented a brilliant scheme: a 64-bit ID composed of 41 bits for timestamp (milliseconds since a custom epoch, giving 41 years of IDs), 13 bits for shard ID (8192 logical shards), and 10 bits for auto-incrementing sequence (1024 IDs per millisecond per shard). This was implemented as a PostgreSQL stored function, requiring zero additional infrastructure. Each shard could independently generate globally unique, time-sorted IDs.

The real pain came during resharding. When Instagram later needed to split shards because some grew much faster than others (celebrity users generating massive data), they had to carefully migrate data while keeping the service running. They used logical sharding within physical databases: 8192 logical shards mapped to a smaller number of physical databases, so "resharding" often meant just moving logical shards between physical servers. This is the approach Pinterest, Etsy, and many others later adopted. The lesson: plan for more logical shards than physical shards from the start.

How Senior Engineers Think About This

The most important decision in sharding is choosing the shard key. This single decision determines your entire scaling trajectory. A bad shard key creates hot spots and cross-shard queries. A good shard key distributes data evenly and keeps related data together.

Senior engineers evaluate shard keys on three dimensions. Cardinality: the key must have enough unique values to distribute across many shards (sharding by country is terrible because the US shard will be 50x larger than the Iceland shard). Frequency: requests should be distributed evenly (sharding by user_id works well when users generate similar amounts of data, but fails for celebrity-style distributions). Query patterns: the shard key should be present in your most common queries to avoid scatter-gather (if you shard by user_id but your main query is "find all orders in the last hour," every shard must be queried).

The mental model that matters: sharding is a one-way door. Once you shard your database, you cannot easily undo it or change the shard key. This is why senior engineers delay sharding as long as possible and exhaust other options first (read replicas, vertical scaling, caching). Stack Overflow serves 1.3 billion monthly page views on a single SQL Server instance. You probably do not need sharding yet.

When you do shard, think of it as creating N independent databases that happen to share a schema. Cross-shard joins are either impossible or prohibitively expensive. Cross-shard transactions require two-phase commit and kill your performance. Design your data model so that queries stay within a single shard.

Common Interview Mistakes

Mistake 1: Sharding too early. The first question should always be "do we actually need to shard?" Read replicas, better indexes, caching, and vertical scaling can take you surprisingly far.

Mistake 2: Choosing a bad shard key. Sharding a social media app by post_id means that displaying a user's profile requires querying every shard. Sharding by user_id keeps all of a user's data on one shard.

Mistake 3: Forgetting about cross-shard queries. If your product requires ad-hoc analytics across all data, sharding makes this very hard. Discuss how you would handle analytics (separate OLAP database, data warehouse, read replicas).

Mistake 4: Not discussing resharding. As data grows, some shards will become larger than others. Explain your strategy: consistent hashing, logical-to-physical shard mapping, or vitess-style automated resharding.

Mistake 5: Ignoring the application layer changes. Sharding requires changes throughout your application: connection routing, ID generation, migration tooling. It is not just a database configuration change.

Production Checklist

• Use logical sharding with more logical shards than physical servers (e.g., 1024 logical shards on 16 physical servers) to make future resharding easier
• Implement a shard-aware ID generation scheme (timestamp + shard_id + sequence) so IDs are globally unique and time-sortable
• Build a shard routing layer that maps logical shard IDs to physical database connections
• Monitor per-shard metrics: row count, storage size, query latency, connections — detect hot shards before they cause problems
• Implement cross-shard query capability for admin and analytics use cases, but make it clear this is not the fast path
• Plan your resharding procedure: test it in staging, estimate downtime or implement online migration
• Keep all shards on the same schema version — coordinate schema migrations across all shards with tools like gh-ost or pt-online-schema-change
• Implement a "scatter-gather" pattern for the rare queries that must touch all shards, with proper timeouts
• Back up each shard independently and test restore procedures
• Document your shard key choice and the reasoning behind it — future engineers will need to understand why

Read the original source | Content from System-Design-Overview

Database Sharding with .NET and SQL Server

While most .NET applications start with a single SQL Server database, sharding becomes necessary at scale. Here is how to implement it:

Shard routing in C#: Create a shard resolver that maps entities to database connections:

public class ShardResolver
    private readonly Dictionary<int, string> _shardMap;

    public string GetConnectionString(int userId)
        int shardId = userId % _shardMap.Count;
        return _shardMap[shardId];


// Usage with EF Core
public class ShardedDbContext : DbContext
    private readonly string _connectionString;
    public ShardedDbContext(string connectionString)
        _connectionString = connectionString;
    protected override void OnConfiguring(DbContextOptionsBuilder options)
        options.UseSqlServer(_connectionString);

Azure SQL Elastic Database: Microsoft provides built-in sharding for Azure SQL with the Elastic Database client library. It handles shard map management, data-dependent routing, and multi-shard querying — purpose-built for .NET applications.

Real example: Stack Overflow shards their Tags database separately from their Posts database. Each "site" (Stack Overflow, Server Fault, Super User) has its own SQL Server database — a form of functional sharding. All running on .NET with Dapper for high-performance data access.

Database Sharding in System Design Interviews

Sharding is one of the most frequently discussed scaling techniques in system design interviews, and interviewers have specific expectations about how you bring it up and explain it.

When to bring up sharding. Do not mention sharding as your first scaling strategy. Interviewers want to see that you exhaust simpler options first: vertical scaling (bigger machine), read replicas (offload read traffic), caching (reduce database load), and better indexing (optimize queries). Only propose sharding when you have demonstrated through estimation that these are insufficient. If your back-of-the-envelope math shows 50,000 writes per second to a single table with terabytes of data, that is when sharding becomes necessary.

How to explain your shard key choice. The shard key decision is the most scrutinized part of any sharding discussion. Walk through it systematically: "I would shard by user_id because (1) it has high cardinality — millions of unique values distribute evenly across shards, (2) our most common queries include user_id in the WHERE clause, so we avoid scatter-gather reads, and (3) all data for a single user stays on one shard, so user-scoped transactions remain local." Then proactively address the weakness: "The downside is that queries aggregating across all users — like 'find the most popular post today' — require querying every shard. For those, I would maintain a separate analytics pipeline."

Common follow-up questions:

• "What happens when one shard gets too big?" Explain resharding: consistent hashing minimizes data movement, and logical-to-physical shard mapping (like Instagram's approach of 8192 logical shards on fewer physical servers) lets you redistribute without changing application logic.
• "How do you handle the celebrity problem?" Some users generate disproportionate data. Solutions include sub-sharding (split a hot shard further), dedicated shards for hot keys, or caching the hot data aggressively.
• "How do you generate unique IDs across shards?" Reference Instagram's approach: 41 bits timestamp + 13 bits shard ID + 10 bits sequence, all generated by a PostgreSQL function with no external coordination.

Common Mistakes with Database Sharding

These mistakes consistently cost candidates points in interviews, even when they understand sharding conceptually.

Choosing the wrong shard key. This is the most common and most costly mistake. Sharding a social media application by post_id means that loading a user's profile requires querying every shard to find all their posts. Sharding by user_id keeps all of a user's data together, making profile loads a single-shard query. The rule of thumb: shard by the entity that appears in 80% of your WHERE clauses.

Not planning for hotspots. Even with a good shard key, data and traffic distribution is rarely uniform. If you shard by user_id and one user is a celebrity with 100 million followers, that shard handles orders of magnitude more read traffic. Real solutions: cache celebrity data aggressively, use a secondary index shard for fan-out reads, or implement sub-sharding for known hot keys. Slack solved this by sharding channels separately from users because some channels (like #general in a 50,000-person company) are extremely hot.

Ignoring cross-shard query costs. Many candidates shard their database and then casually propose queries that span all shards. A "find all orders placed today" query on a user-sharded database must scatter to every shard, gather results, and merge them — this gets progressively slower as you add shards. Production systems solve this with dedicated analytics stores (materialized views, data warehouses like BigQuery or Redshift) that aggregate data from all shards.

Underestimating the resharding nightmare. Adding or removing shards in a live system is one of the hardest operational challenges in distributed databases. Naive modular hashing (shard = user_id % N) means changing N redistributes almost all data. Consistent hashing limits redistribution to roughly 1/N of the data. But even with consistent hashing, you need tooling for online migration: dual-write to old and new shards, backfill historical data, verify consistency, then cut over. Companies like Pinterest and Etsy have published detailed accounts of resharding operations that took months to complete safely.

Sharding too early. This is the most expensive mistake because it is hard to reverse. Stack Overflow serves 1.3 billion monthly page views on a single SQL Server instance with good indexing and caching. Shopify ran on a single MySQL primary for years before sharding. Sharding adds complexity to every part of your stack: connection management, schema migrations, backup procedures, and debugging. In an interview, explicitly say "I would start with a single database and scale vertically until we hit the limits, then add read replicas, then shard only when those are insufficient."

Frequently Asked Questions About Database Sharding

When should I shard vs replicate? Replication and sharding solve different problems. Replication (creating read replicas) solves read scalability — you distribute read traffic across multiple copies of the same data. Use it when your database is read-heavy and the primary cannot handle the query volume. Sharding solves write scalability and storage limits — you split data across multiple databases. Use it when a single database cannot handle the write volume or the data no longer fits on one machine. Many production systems use both: each shard has its own read replicas. Instagram, for example, shards by user_id for write distribution and has read replicas per shard for read scaling.

What is consistent hashing and how does it relate to sharding? Consistent hashing maps both data keys and shard identifiers onto a circular hash ring. Each key is assigned to the nearest shard clockwise on the ring. The key benefit: when you add or remove a shard, only the keys between the affected shard and its neighbor need to move — roughly 1/N of the total data, compared to nearly all data with naive modular hashing. Virtual nodes improve distribution further: each physical shard gets multiple positions on the ring, smoothing out imbalances. DynamoDB, Cassandra, and Riak all use variants of consistent hashing for their partitioning schemes.

How do companies like Instagram shard their databases? Instagram uses PostgreSQL sharded by user_id. Each logical shard is a PostgreSQL schema within a larger database. They created 8192 logical shards mapped to a smaller number of physical database servers. This logical-to-physical mapping means "resharding" often just moves a logical shard from one physical server to another, without splitting data. Their ID generation is a PostgreSQL stored function producing 64-bit IDs: 41 bits for timestamp, 13 bits for shard ID, 10 bits for auto-incrementing sequence — globally unique, time-sortable, and requiring no external coordination service.

What are the alternatives to sharding? Before sharding, consider: (1) Vertical scaling — bigger machines with more RAM and faster SSDs can handle surprisingly high loads. (2) Read replicas — offload read traffic to replicas if the workload is read-heavy. (3) Caching — Redis or Memcached can absorb 80-90% of read traffic for hot data. (4) Table partitioning — split a large table into partitions within a single database instance for faster queries without the distributed complexity. (5) Archiving old data — move cold data to cheaper storage to keep the active dataset small. (6) Using a database that handles distribution automatically — CockroachDB, TiDB, and Vitess add horizontal scaling to traditional SQL databases without manual shard management.

How do you handle cross-shard joins? Cross-shard joins are the Achilles heel of sharded databases. There are several strategies: (1) Denormalize data so joins are unnecessary — store redundant data on each shard so queries can be answered locally. (2) Application-level joins — query each relevant shard separately and merge results in the application layer, accepting higher latency. (3) Maintain a separate read-optimized store — replicate data from all shards into a data warehouse (BigQuery, Redshift) or search index (Elasticsearch) for cross-shard queries. (4) Use a sharding middleware like Vitess that can handle cross-shard queries transparently, though with performance overhead. The best approach depends on how frequently cross-shard queries occur and what latency is acceptable.