DDIA Chapter 7 — Sharding (Part 1)

In DDIA Chapter 6 — Replication (Part 1), we discussed how distributed databases spread data across multiple machines by copying it to multiple nodes. Replication improves availability, helping prevent a single machine failure from taking down the entire system. It can also distribute read requests across replicas, reducing the load on any one machine.

Sharding is another way to distribute data across machines, but it works differently from replication and addresses a different set of problems. In this chapter's guide, we'll explore what sharding is, its benefits and costs, and the choices involved in implementing it.

What Is Sharding?

As we discussed in DDIA Chapter 6 — Replication (Part 1), replication stores the same data on multiple machines. Sharding, by comparison, stores different data on different machines. Instead of placing the entire dataset on every machine, it divides the data into smaller subsets, called shards, and places those shards on different machines.

For example, imagine a membership system with hundreds of millions of members. We could shard the member data by storing member IDs 1 through 10,000,000 in shard 1, IDs 10,000,001 through 20,000,000 in shard 2, and so on. Under this scheme, member 12,345,678 belongs to shard 2. To look up that member, the system can go straight to shard 2 without searching every machine.

In practice, replication and sharding are often used together. Each record is assigned to a shard, and that shard is replicated across multiple machines. The record still belongs to a single shard, while the replicas improve its availability. Although the record exists on several machines' disks, it belongs to just one logical subset of the dataset.

In our example, if shard 2 lives on only one machine, its data becomes temporarily unavailable when that machine fails. With replication, other machines holding replicas of the same shard can continue serving client requests.

What Are the Benefits and Costs of Sharding?

Both replication and sharding distribute data across machines. Replication can improve availability and reduce latency, while sharding serves a different purpose. Its biggest benefit is scalability.

As a system grows and accumulates more data, there are generally two ways to scale: vertically and horizontally. Vertical scaling means upgrading a single machine, such as adding more memory or using larger disks. But there is a limit to how much storage one machine can hold. With a sufficiently large dataset, even the most powerful machine may fall short.

Horizontal scaling means adding more machines, and sharding is one way to achieve it. As the dataset grows, it can be divided into multiple shards, with each machine responsible for a portion of the data. As data volume or load continues to increase, the system can expand its storage and processing capacity by adding nodes, splitting shards, or moving shards between nodes.

Should Every System Use Sharding?

Although sharding offers scalability benefits in theory, it isn't something every data system needs, especially early on when the system is still small.

Replication can improve availability regardless of dataset size. Even a machine with very little data can fail, and replicas, combined with appropriate failure detection and failover, help keep the service running when a node goes down. Sharding has a different tradeoff. If a system's data volume and read/write load fit comfortably within a single node's capacity, and it has no special requirements such as tenant isolation, the benefits may be too small to justify the additional development and operational costs.

Hardware improvements have also raised the limits of what a single machine can handle. Unless data volume or write load clearly exceeds a single node's capacity and is expected to keep growing, sharding may not be necessary.

What Makes Sharding Difficult in Practice?

The first challenge is choosing a partition key.

A partition key is the field, or combination of fields, that determines which shard a record belongs to. A member ID is one example. This choice has a major impact on query performance. When a query includes the partition key, the system can locate the data much more efficiently. In our example, knowing that member 12,345,678 belongs to shard 2 lets the system fetch the record directly from that shard.

The problem is that many queries don't align with the partitioning scheme. They may need to scan many shards, substantially reducing query efficiency and speed. This becomes especially challenging with a relational data model: users, orders, products, and payments are related, and spreading them across shards can make queries more expensive.

If orders are also sharded by member ID, a request for a particular member's orders can go directly to the relevant shard, avoiding a cross-shard query. But retrieving every purchase of a particular product across the platform is a different story. Without a suitable global index or another query structure, the system may have to query multiple shards and combine the results. Conversely, sharding by product ID makes product-based queries efficient, but retrieving a user's complete purchase history may become expensive.

The first major challenge, then, is often how well you understand the system. Before choosing a partition key, you need to understand how the data is related, which queries are common, which are most important, and which are rarely used. That broader understanding is what makes a suitable choice possible.

The second challenge is handling database transactions. Transactions are relatively straightforward within a single database. After sharding, however, transferring money from account A to account B becomes a cross-shard operation if the accounts live on different shards. That makes the operation slower and more complex than it would be within a single database.

For example, ensuring that the debit from account A and the credit to account B happen atomically requires transaction coordination across shards. With two-phase commit, a coordinator first confirms that all participating shards are prepared, then decides whether to commit or abort. Node failures or communication outages make recovery more complicated as well.

This is why choosing a partition key also involves considering which records frequently need to be updated together. Keeping those records on the same shard can reduce the need for cross-shard transactions.

Support ExplainThis

If you found this content helpful, please consider supporting our work with a one-time donation of whatever amount feels right to you through this Buy Me a Coffee page.

Creating in-depth technical content takes significant time. Your support helps us continue producing high-quality educational content accessible to everyone.