Data building blocks
Sharding and partitioning
Split data across machines by choosing a shard key, hashing or ranging it, routing requests, handling hot spots, resharding without downtime and generating IDs that stay unique.
Sharding (also called partitioning) splits a data set so that each machine owns only part of it. Replication copies the same data to more machines, which scales reads and survives failures. Sharding divides the data, which is the only way to scale writes and storage beyond what one machine can hold. Real systems do both: each shard is itself a small replicated group.
Sharding is also one of the most expensive decisions you can make. Queries that span shards get slower, transactions across shards get hard, and every schema change and backup happens once per shard. The skill is choosing a key that keeps common queries on one shard, and knowing when not to shard at all.
The core idea
Sharding has two decisions. First, how a key maps to a shard: by range, by hash, or by a consistent ring. Second, which key to use in the first place. The mapping decides how data moves when machines are added. The key decides which queries stay cheap.
Concepts in this topic
| Step | Concept | What it answers |
|---|---|---|
| 1 | Range and hash partitioning | Do you keep neighbors together, or spread the load evenly? |
| 2 | Consistent hashing | How do you add a machine without moving almost every key? |
| 3 | Choosing a shard key | Which key keeps your common queries on one shard? |
| 4 | Secondary indexes when sharded | How do you query by a field that is not the shard key? |
| 5 | Resharding without downtime | How do you move data while traffic keeps flowing? |
| 6 | Unique ID generation | How do you create IDs that are unique across shards? |
Request routing
Something has to know which shard holds a key. There are three common designs.
- Client-side routing. A smart client holds the partition map and connects straight to the right node. It has the lowest latency, but every client must stay current.
- Routing tier. Clients talk to a proxy that knows the map. Clients stay simple, but the proxy adds a hop and must scale.
- Any node as coordinator. A node receives the request and forwards it to the owner. Gossip keeps each node's copy of the map current.
The partition map is small but critical. It usually lives in a consensus store such as ZooKeeper or etcd. See consensus and Raft.
When to avoid sharding
Avoid sharding for as long as you reasonably can. Before you shard, try these:
- Better indexes and queries.
- A bigger machine. Vertical scaling goes a long way.
- Read replicas and caching.
- Moving analytics off the primary.
- Archiving cold data.
- Splitting unrelated tables onto separate databases, which is called functional partitioning.
Many very large systems ran on one primary per database for far longer than people expect.
Real systems
- Vitess started at YouTube to shard MySQL. It adds a routing tier, a topology service and tools for online resharding.
- Citus turns Postgres into a sharded cluster by a distribution column, and keeps tables that share a column on the same node.
- DynamoDB hashes the partition key and splits partitions as they grow. You still choose the key.
- Distributed SQL systems such as Spanner, CockroachDB and YugabyteDB shard by range automatically and offer cross-shard transactions, with some latency cost.
Common mistakes
- Sharding too early. Each shard adds permanent cost to queries, migrations and backups.
- Choosing the key by the schema, not the queries. Start from the queries you run most.
- Assuming a new endpoint is free. A query without the shard key fans out to every shard.
Key takeaways
- Sharding scales writes and storage. Replication scales reads and survives failures.
- Range partitioning keeps scans cheap but hot-spots sequential keys. Hash partitioning spreads load but scatters ranges.
- Consistent hashing moves only a small share of keys when a node is added.
- The shard key matters more than the algorithm: pick it from your most common queries.
- Plan for resharding and for unique IDs from the start.
Further learning
ByteByteGo's short animation is the quickest way to get the consistent hashing ring and virtual nodes into your head.
Hello Interview's session walks through sharding the way an interviewer expects you to discuss it, including shard key choice and hot spots.
Twitter Snowflake ID generator (archived)Snowflake is a network service for generating unique ID numbers at high scale with some simple guarantees. - twitter-archive/snowflakeGitHubRelated
Replication
Keeping copies of the same data on several machines, the three topologies that databases use, and the anomalies that replication lag causes. Start here for the replication map.
Databases and data modeling
Choose between relational, document, wide-column, key-value, graph and analytical stores by listing your access patterns first, then model the data to fit them.
Consistent hashing
Place keys and nodes on the same ring, and each key belongs to the next node clockwise. Adding a node then moves only the keys on its arc, not almost every key as with hash modulo N.
Choosing a shard key
A good shard key has high cardinality, even traffic, query locality and stability. Choose it from your most common queries, and plan for the single hot value that breaks even a good key.
Resharding without downtime
Two ways to add capacity to a sharded system, and a dual-write playbook for moving data while traffic keeps flowing. Each step stays reversible until the final cleanup.
Case study: distributed key-value store
Build a Dynamo-style store from first principles. Consistent hashing places the data, quorums set the consistency, vector clocks detect conflicts, and hints and Merkle trees repair failures.