Sharding: Scaling Databases Horizontally

From Scaling Up to Scaling Out

As a database grows, you eventually hit the physical limits of a single server. You can't add more RAM, CPU, or disk space. This is the limit of vertical scaling (scaling up). The solution is horizontal scaling (scaling out), which involves adding more machines to your system rather than making one machine more powerful.

Sharding is the primary method for horizontally scaling a database. It involves breaking a large database into many smaller, more manageable pieces called shards, and distributing them across multiple database servers. Each shard is an independent database, containing a unique subset of the total data.

Why Shard? The Core Motivations

Before diving into the "how," let's solidify the "why." Sharding addresses several critical limitations of a single-server architecture.

As the video explained, the key benefits are:

• Increased Throughput: By distributing data and queries across multiple servers, you can handle a much higher volume of both read and write operations in parallel.
• Unlimited Storage Capacity: You are no longer limited by the storage of a single machine. You can keep adding more servers (shards) as your data grows.
• Higher Availability: If one shard goes down, it only affects a subset of the data. The rest of the application can often remain functional, unlike a single primary database failure which takes down everything.

Common Sharding Patterns

The most critical decision in a sharding strategy is choosing how to split the data. This is governed by a shard key, which is a column (or set of columns) in your table whose value determines which shard a particular row belongs to. A poor choice of shard key can lead to hotspots—where one shard receives a disproportionate amount of traffic, negating the benefits of sharding.

Let's explore the most common sharding patterns.

Let's summarize and expand on those patterns:

1. Key-Based (Hashed) Sharding:

   • How it works: You apply a hash function to the shard key (e.g., user_id) and then use the output to determine the shard, often with a modulo operator (e.g., hash(user_id) % num_shards).
   • Pros: Tends to distribute data very evenly, which helps avoid hotspots.
   • Cons: The relationship between the shard key and the shard is arbitrary. Range queries (e.g., "find all users created in the last 24 hours") become very difficult, as they may have to query every single shard. Adding or removing shards is also complex (more on this later).

2. Range-Based Sharding:

   • How it works: Data is sharded based on a range of values of the shard key. For example, users with IDs 1-1,000,000 go to Shard 1, IDs 1,000,001-2,000,000 go to Shard 2, and so on.
   • Pros: Easy to implement and makes range queries efficient, as they often only need to target one or a few shards.
   • Cons: Highly susceptible to hotspots. If the shard key is time-based (like an auto-incrementing ID or a timestamp), all new writes will go to the last shard, creating a massive hotspot.

3. Directory-Based Sharding:

   • How it works: A central lookup table maps a shard key value to a specific shard. For instance, you could have a mapping from region_id to a shard's connection string.
   • Pros: Extremely flexible. You can create complex sharding logic and easily move data between shards by just updating the lookup table.
   • Cons: The lookup table itself can become a performance bottleneck and a single point of failure.

4. Relationship-Based Sharding (Colocation):

   • This is a more advanced strategy where you intentionally place related data on the same shard to optimize queries. For example, in a social media app, you might shard by user_id and ensure that a user's profile, posts, and comments all live on the same physical shard. This makes queries for a user's data extremely fast as they don't require expensive cross-shard joins.

The Hard Parts: Challenges of Sharding

While powerful, sharding introduces significant operational complexity. It is not a free lunch and is often considered a last resort after exhausting other options like replication and caching.

Challenge 1: Routing Requests

Once your data is sharded, your application needs to know which shard to connect to for any given query. How does it figure this out?

The main approaches are:

• Routing Proxy/Tier: The application sends all queries to a stateless proxy (like Nginx, or a custom service). This proxy holds the sharding logic, determines the correct shard for the request, and forwards it. This is a common and clean approach as it isolates the sharding logic from your application code.
• Shard-Aware Client: The sharding logic is embedded directly within the application or a client library. The application itself calculates the target shard and connects to it directly. This can be more performant as it avoids an extra network hop to a proxy, but it couples your application code tightly to the database topology.
• Database-Native Routing: Some modern distributed databases (like Vitess or TiDB) handle this for you. You connect to a "stateless SQL endpoint" that looks like a single database, and it transparently routes your queries to the appropriate backend shards.

Challenge 2: Rebalancing and Consistent Hashing

What happens when you need to add a new shard to handle more data, or remove one? This process is called resharding or rebalancing.

With a naive key-based sharding approach using the modulo operator (hash(key) % N), adding or removing a shard is a catastrophe. If you change N (the number of shards), the result of the modulo changes for almost every single key. This means you would have to move nearly all of your data, causing a massive system-wide disruption.

This is where consistent hashing comes in.

Consistent hashing is a brilliant solution that drastically minimizes data movement during rebalancing. By mapping both servers and keys onto an abstract circle (the "hash ring"), it ensures that when a server is added or removed, only its immediate neighbors on the ring are affected.

Challenge 3: Cross-Shard Queries and Transactions

A sharded architecture works best when most queries can be satisfied by a single shard. However, you will inevitably need to run queries that span multiple shards (e.g., an analytics query that needs to aggregate data across all users).

These cross-shard queries are complex and slow. The routing layer must:

1. Send the query to all relevant shards.
2. Wait for responses from each of them.
3. Aggregate the results in memory before returning them to the client.

Even more complex are distributed transactions—transactions that need to modify data on multiple shards. Since each shard is an independent database, you can't just wrap the operation in a BEGIN/COMMIT block. If a write to Shard A succeeds but a write to Shard B fails, how do you maintain an atomic, consistent state?

As the article describes, the Two-Phase Commit (2PC) protocol is a standard solution. It involves a coordinator that first asks all participating shards to "prepare" to commit. If all shards agree, the coordinator then tells them all to "commit." If any shard fails during the prepare phase, the coordinator tells everyone to "abort." While 2PC provides atomicity, it is slow, complex, and can lead to locking issues, which is why system designers try to avoid distributed transactions whenever possible by using smart sharding strategies (like relationship-based sharding).

Conclusion

Today we've taken a significant step up in our scaling journey, moving from scaling reads with replication to scaling writes and storage with sharding.

Key Takeaways:

• Sharding is Horizontal Scaling: It's the process of splitting a database into smaller, independent databases (shards) to overcome the limits of a single server.
• The Shard Key is Crucial: The choice of a shard key and a sharding pattern (key-based, range-based, etc.) determines how data is distributed and is critical for avoiding hotspots.
• Sharding Introduces Major Challenges: You must solve complex problems, including:
  • Request Routing: How to get a query to the correct shard.
  • Rebalancing: How to add or remove shards without massive data migration, often solved with consistent hashing.
  • Cross-Shard Operations: How to handle queries and transactions that span multiple shards, often requiring mechanisms like two-phase commit.

Because of this complexity, many modern databases, often called "Distributed SQL" or "NewSQL" databases (e.g., Google Spanner, CockroachDB, TiDB), are designed from the ground up to handle sharding automatically, hiding most of this complexity from the developer.

Preview of the Next Lesson

We have now gone incredibly deep into the database layer, covering everything from on-disk storage and indexes to replication and sharding. For the next module, we're going to "zoom out" and move up the stack.

In our next lesson, we will begin to trace the path of a complete request through a typical server infrastructure. We'll start at the edge with the load balancer and web server, and see how a request is received, processed, and ultimately forwarded to our application, bridging the gap between networking and the application code you write.