$ man sharding # a.k.a. partitioning, horizontal scaling

Sharding

Sharding splits one large dataset into smaller pieces (shards, also called partitions) and puts each piece on a different machine. Every row lives on exactly one shard, so together the machines can store more data and absorb more writes than any single server. The same idea is called partitioning in Kafka, Cassandra, Spark and most data tools.

Sharding is horizontal scaling (add machines). Its alternative is vertical scaling (buy a bigger machine), which is simpler and should usually come first.

The whole game is the shard key

A shard key (or partition key) is the column that decides where a row goes. Two classic ways to map a key to a shard behave very differently.

$ ./route --key user_id --shards 3
Range vs hash partitioning on the same keys
user_id: 7 18 29 44 63 88 RANGE by key order HASH by hash(key) SHARD 1 · 1–33 SHARD 2 · 34–66 SHARD 3 · 67–100 SHARD 1 · h % 3 = 0 SHARD 2 · h % 3 = 1 SHARD 3 · h % 3 = 2 7 18 29 44 63 88 WHERE user_id BETWEEN 20 AND 50 → 2 of 3 shards 96 97 98 99 HOT: every new signup 7 63 18 44 29 88 98 96 99 97 WHERE user_id BETWEEN 20 AND 50 → ask all 3 shards
  1. Six users, three machines. The same keys will be placed two ways: by range and by hash.
  2. Range partitioning: each shard owns a contiguous key range, like volumes of an encyclopedia.
  3. Range queries are cheap: users 20 to 50 live on 2 of 3 shards, and the rest are never touched.
  4. But keys that grow over time (auto-increment IDs, timestamps) all land on the last shard. One machine takes every write: a hot spot.
  5. Hash partitioning: hash(user_id) % 3 scatters keys pseudo-randomly, so new signups spread evenly across all shards.
  6. The price: neighbors are no longer together. The same range query must ask every shard and merge the answers (scatter-gather).

Partitioning strategies

Strategy How a key is placed Good at Bad at Used by
Range Sorted key ranges per shard Range scans, ordered reads Hot spots on increasing keys HBase, Bigtable, CockroachDB, TiDB, MongoDB ranged shards
Hash hash(key) decides the shard Even spread of reads and writes Range queries become scatter-gather Cassandra, DynamoDB, Kafka (default partitioner), Redis Cluster
Consistent hashing Keys and nodes on a hash ring Adding a node moves only ~1/N of keys Uneven without virtual nodes Dynamo-style stores, Cassandra vnodes, CDNs
Directory / lookup A mapping table says where each key lives Moving single tenants, uneven tenants The directory is one more service to keep available Vitess lookup vindexes, many multi-tenant SaaS setups

Plain hash(key) % N has a nasty property: change N from 3 to 4 and almost every key moves. Real systems avoid that with consistent hashing or with many more partitions than nodes (for example 256 partitions on 4 nodes) so rebalancing just moves whole partitions.

Choosing a shard key

A good shard key has high cardinality, spreads writes evenly, and matches how you query:

  • user_id or tenant_id for a SaaS app: most queries are “everything for this user”, so they hit one shard.
  • country is a bad key: a handful of values, and one country may hold half your users.
  • created_at alone is a bad key for range sharding: today’s writes all go to one shard. Combine it with a hashed prefix, or bucket by hash(user_id) first.

The same rule applies to data engineering tools: Kafka keys decide which partition holds an entity’s events (and therefore their order), and Spark or Iceberg partition columns decide which files a query can skip.

Sharding and replication together

Sharding and replication solve different problems and are almost always combined.

Replication Sharding
What each node holds A full copy A slice
Scales Reads, availability Storage, writes, and reads
A node dies Another copy serves the data That slice is gone unless the shard is also replicated
Typical layout 1 leader + 2 followers N shards, each with its own leader + followers

What sharding costs you

  • Cross-shard queries: joins and aggregations across shards need scatter-gather or data shuffling.
  • Cross-shard transactions: atomically updating rows on two shards needs a protocol like two-phase commit. See Distributed Transactions.
  • Secondary indexes: an index on email when you shard by user_id is either local (every shard is searched) or global (writes touch another shard). See Indexing.
  • Operations: rebalancing, resharding and backups across many machines.

Common mistakes

  • Sharding too early. A single PostgreSQL server with good indexes, table partitioning and read replicas handles terabytes. Shard when one machine truly cannot keep up.
  • A monotonic shard key with range partitioning. Creates a permanent hot shard.
  • Ignoring hot keys. Even with hashing, one celebrity user or one huge tenant can overload a shard. Split or salt those keys.
  • % N routing in application code. Makes adding a shard a full data migration.
  • Picking a key that does not match queries. If most queries do not include the shard key, every query is scatter-gather.

Learning Resources

Books

  • Designing Data-Intensive Applications (2nd ed.), Martin Kleppmann and Chris Riccomini: the partitioning (sharding) chapter

Docs and papers

Videos