Divide and Conquer: Mastering Sharding (Designing Data-Intensive Applications Chapter 7)

In the previous chapters of our journey through Designing Data-Intensive Applications (Second Edition), we explored the internals of storage engines and the complexities of replication. But what happens when your dataset grows so massive or your write throughput soars so high that a single machine, even with replicas, simply cannot keep up?

This is where Chapter 7, "Sharding," comes in. Authors Martin Kleppmann and Chris Riccomini shift the focus from copying the same data (replication) to splitting the data into smaller subsets, known as shards or partitions.

Sharding by Any Other Name

While the authors use the term "sharding," they note that the industry is full of synonyms. Depending on the tool you use, you might hear shards called partitions (Kafka), regions (HBase), tablets (Bigtable), or vnodes (Riak). Regardless of the name, the goal is the same: to break a large database into smaller, self-contained pieces where each record belongs to exactly one shard.

The Core Challenge: Skew and Hot Spots

The fundamental goal of sharding is to spread data and query load evenly across nodes. If the distribution is unfair, you end up with skew, where some shards have significantly more data or queries than others. This leads to hot spots, shards with disproportionately high load that become system bottlenecks. A classic example is a social media site where a celebrity's user ID becomes a hot key, overwhelming the shard responsible for their data.

Choosing Your Strategy: Range vs. Hash

How do you decide which record goes to which shard? The chapter explores two primary methods:

1. Sharding by Key Range: Records are assigned to shards based on contiguous ranges of keys (like volumes of an encyclopedia).

   • Pros: Allows for efficient range scans because keys are kept in sorted order within the shard.
   • Cons: Highly susceptible to hot spots. For example, if you shard by timestamp, all of today's writes will hit the same "today" shard while others sit idle.

2. Sharding by Hash of Key: A hash function is applied to each key to determine its shard.

   • Pros: Distributed load more uniformly, even if the input keys are very similar. This is the basis for consistent hashing.
   • Cons: You lose the ability to perform efficient range queries; keys that were once close together are now scattered across the cluster.

The Secondary Index Headache

Sharding is relatively straightforward for simple key-value lookups, but secondary indexes make things much more complicated. The authors highlight two main approaches:

• Local Secondary Indexes (Document-Partitioned): Each shard maintains its own index for the data it contains. While writes are fast (you only update one shard), reads are "scatter-gather", you must query every single shard to find all records matching a criteria (like "all red cars").
• Global Secondary Indexes (Term-Partitioned): The index is sharded separately from the primary data. A search for "red cars" hits only one index shard, but every write to the primary data might require updating multiple index shards on different nodes, making writes slower and more complex.

Request Routing: Where is My Data?

Once your data is spread across dozens or hundreds of nodes, how does a client know which IP address to connect to for a specific key? This is the request routing problem.

Systems generally take one of three paths:

1. Allowing clients to contact any node, which then forwards the request if it doesn't own that shard.
2. Using a dedicated routing tier (a shard-aware load balancer).
3. Making the client sharding-aware so it connects directly to the right node.

Many distributed systems use a coordination service like Apache ZooKeeper or etcd to maintain the authoritative mapping of which shards live on which nodes.

Conclusion

Sharding is a powerful tool for scalability, but it is not a "magic sauce" you can sprinkle on any application. It introduces significant architectural complexity, especially regarding rebalancing and secondary indexes. As Chapter 7 makes clear, the most successful designs are those that choose a sharding scheme tailored to the specific access patterns and growth requirements of the data they serve. 

Reference 

Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems

Book by Martin Kleppmann and Chris Riccomini

This blog post is a summary of my personal notes and understanding from reading "Designing Data-Intensive Applications" by Martin Kleppmann. All credit for the original ideas belongs to the author.