What it is
Partitioning (sharding) splits a dataset across machines so that no single node must store or serve all of it. Useful partitioning requires picking two things: a strategy (how keys map to partitions) and a partition key (which attribute drives the mapping).
When you care
Every system design question that outgrows one machine forces this decision, and it’s usually asked directly: “How would you shard this?” The trap is answering with a strategy but no key — “we’ll use consistent hashing” says nothing until you name what you hash. Interviewers probe the follow-ups: what happens when a partition gets hot, what queries become expensive once data is split, and what moves when you add a node.
The strategies
| Strategy | Mechanism | Range queries | Rebalancing cost | Hot-spot risk |
|---|---|---|---|---|
| Hash (mod N) | hash(key) mod node_count → partition | Lost (keys scattered) | Catastrophic — changing N remaps nearly every key | Low for uniform keys |
| Range | Sorted key ranges assigned to partitions | Preserved (adjacent keys colocate) | Cheap — split/merge ranges at boundaries | High — sequential keys (timestamps) hammer one range |
| Consistent hashing | Keys and nodes hash onto a ring; key belongs to next node clockwise | Lost | Cheap — adding a node moves ~1/N of keys | Low, with virtual nodes |
| Directory (lookup table) | Explicit key→partition map in a metadata service | Whatever the map allows | Flexible — move any key anywhere | Low, but the directory is a SPOF and a hop |
Hash mod N is the strawman. It distributes evenly with zero metadata, but the moment N changes, almost every key’s home changes — a full-cluster data shuffle to add one machine. Fine for fixed-size clusters and stateless routing (picking a queue partition); wrong for storage that grows.
Range partitioning keeps sort order, which is the only way to serve range
scans (messages between t1 and t2) from one partition. The cost is hot
spots: monotonically increasing keys (timestamps, auto-increment IDs) send
all new writes to the last range. Bigtable/HBase work this way and make you
design keys to avoid it (prefix with a salt or a sensible high-cardinality
attribute).
Consistent hashing bounds what moves on topology change: a node joining takes ~1/N of the keyspace from its ring neighbors, and nothing else moves. Virtual nodes (each physical node owns many ring positions) fix the two residual problems — uneven token luck and single-successor recovery — by scattering each node’s ranges so load and re-replication spread across the fleet. This is the Dynamo/Cassandra default and the right answer for point-lookup KV workloads.
Directory-based partitioning trades ring math for explicit control: a metadata service says where every key (or tenant, or chunk) lives, so you can move hot tenants by hand or by policy. The cost is that every request needs the map, and the map must be highly available and cached aggressively.
Picking the partition key
The strategy is half the decision; the key is the other half:
- Partition by the access pattern, not the entity. The question is “what
do my hottest queries filter on?” — that attribute is the key. A chat system
partitions messages by
conversation_id(reads fetch one conversation), notmessage_id. - High cardinality, even spread. A key with few distinct values (country, status) creates a handful of giant partitions.
- One access pattern per table. If two hot queries need different keys (who follows me vs whom I follow), denormalize into two tables, each partitioned for its caller — secondary indexes across partitions are scatter-gather queries.
- Compound keys cap partition growth. Unbounded per-key data (a user’s
events over years) needs a time bucket in the key:
(user_id, month).
When to pick what
- Point lookups by key, elastic cluster: consistent hashing with virtual nodes.
- Range scans required: range partitioning, with key design that breaks up sequential writes.
- Fixed partition count, stateless spreading (queue partitions, connection routing): hash mod N is fine.
- Per-tenant placement control (move noisy tenants, pin big customers): directory-based.
- Hot partition anyway? Split the key (append a shard suffix), cache in front, or isolate the hot entity — see the hot-key reference below.
Related
- Walkthrough: Designing a Distributed Key-Value Store — consistent hashing built out in full: rings, preference lists, virtual nodes, and what moves when topology changes.
- Reference: NoSQL Hot Key Mitigation Patterns — what to do when a well-chosen partition key still produces a hot partition.
- Walkthrough: Designing a News Feed — four tables, each partitioned for exactly one caller’s access pattern.