Partitioning (or sharding) splits data across machines so that no single machine has to store everything or serve every request. The mechanics are simple: compute a partition from a key and send the data there. The design decisions are all about the key. Choose it badly and either every query has to visit every partition, or one partition ends up doing most of the work while the others idle.
The classic interview illustration is a social app sharded evenly by user id across 16 database partitions. Load looks balanced on paper, until one account with 40 million followers starts posting and the partition holding that account melts.
Choosing the key from your queries
Start with the queries you can’t afford to make slow, not with the data. For a chat app:
- “Load the last 50 messages in conversation X” happens on every screen open.
- “Show all conversations for user Y” happens on app start.
- “Search all messages for a word” is rare and can go to a separate search index.
Partitioning messages by conversation_id makes the first query a single-partition read. Partitioning by message_id would spread writes perfectly but turn every conversation load into a scatter-gather across all partitions, and the slowest partition sets the latency of every request.
Then decide how keys map to partitions:
- Hash partitioning hashes the key and maps the hash to a partition. It spreads keys evenly and destroys ordering, so range queries (“all orders from last week”) have to visit every partition.
- Range partitioning assigns contiguous key ranges to partitions (A to F, G to M, and so on). Range queries stay local, but sequential keys like timestamps send every new write to the last partition.
Many systems combine them: DynamoDB and Cassandra hash the partition key and keep items sorted within a partition by a sort key, so “messages in conversation X, newest first” is one partition read in order.
Why hash mod N hurts when you add a node
The obvious hash scheme is partition = hash(key) % N. It distributes well, and it falls apart the moment N changes. A Node experiment with 200,000 keys going from 10 to 11 nodes:
let movedMod = 0;
for (const x of hashes) if (x % 10 !== x % 11) movedMod++;200,000 keys, growing from 10 to 11 nodes:
hash mod N: 90.9% of keys change nodeAdding one node moves 91% of the data. For a cache, that’s a near-total cold start and a flood of misses on the database. For a database, it’s a migration of almost everything to add 10% more capacity.
Consistent hashing and virtual nodes
Consistent hashing places nodes on a ring of hash values, and each key belongs to the first node clockwise from the key’s hash. Adding a node takes over only the arc just before it, so only the keys in that arc move. The ideal is 1/11, about 9.1%, when going from 10 to 11 nodes.
With one position per node, though, the arcs are random lengths, and some nodes get far more than their share. The fix is virtual nodes: each physical node takes many positions on the ring. Here’s the same experiment with a ring implementation, varying the number of virtual nodes:
ring, 1 vnodes/node: 11.3% move; busiest node holds 2.78x the average, quietest 0.03x
ring, 16 vnodes/node: 7.8% move; busiest node holds 1.40x the average, quietest 0.75x
ring, 256 vnodes/node: 8.6% move; busiest node holds 1.10x the average, quietest 0.93xAll three ring variants move roughly the ideal 9%, a tenth of what hash mod N moved. But with one position per node, the busiest node held 2.78 times the average and one node held almost nothing. With 256 virtual nodes per node, the spread is within about 10% of even. Interviewers often ask why virtual nodes exist; this is the answer: they’re what makes consistent hashing balanced, not just stable.
Many systems get the same effect differently, with a large fixed number of partitions assigned to nodes. Redis Cluster hashes every key into one of 16,384 slots (CRC16(key) mod 16384) and assigns slot ranges to nodes; adding a node moves some slots. Kafka topics and Elasticsearch indexes pick a partition or shard count up front. Moving whole partitions between nodes is simpler to reason about than a ring, at the cost of choosing the count early: Kafka can add partitions but never remove them, and adding them changes which partition a given key hashes to, while Elasticsearch needs a split or reindex to change the primary shard count.
Hot keys: when even distribution isn’t enough
Consistent hashing balances keys. It can’t balance a single key that gets a large share of traffic, because one key always lives on one partition. Simulating 16 partitions where one account receives 20% of all writes:
16 partitions, one account takes 20% of writes:
key = user id: hottest partition at 3.99x the average
key = user id + suffix 0..7: hottest partition at 1.60x the average
key = user id + suffix 0..31: hottest partition at 1.29x the averageWith the plain user id as key, one partition carries four times the average load: its 1/16 share of everything else plus the entire hot account. Adding partitions doesn’t help, since the hot account still lands on one of them.
Key splitting (sometimes called salting) fixes the write side. Writes for the hot account go to celebrity#0 through celebrity#7, chosen randomly or round robin, spreading them over up to 8 partitions. Eight suffixes brought the hottest partition down to 1.6x, and 32 to 1.29x.
The cost moves to reads. Reading “all of the celebrity’s data” now means querying every suffix and merging. That’s why you split only keys known to be hot (keep a small list, or detect them from traffic metrics) rather than every key. For read-heavy hot keys, such as a celebrity’s profile being viewed millions of times, splitting isn’t needed at all: put the value in a cache, replicate it to several cache nodes, or cache it in process memory for a second or two.
Range partitions and the moving hot spot
Range partitioning has its own version of the problem. If the key is a timestamp or an auto-increment id, every new write has the largest key and lands on the last partition. The cluster has ten partitions, and one of them takes all the writes while nine serve only old data.
Fixes include prefixing the key with something that spreads writes (a hash of the device id before the timestamp for IoT readings), or choosing a compound key where the leading part is spread out and the time part orders data within it, such as (sensor_id, timestamp). Systems that split ranges automatically, like Bigtable, HBase and CockroachDB, still struggle with a strictly increasing key, because the split always happens at the hot end and the new partition is immediately the hot one.
Interview practice: the giant group chat
“Messages are partitioned by conversation id across 64 partitions. A creator launches a 500,000-member group chat, and during live events it gets 20,000 messages per second, overloading its partition. Other conversations on that partition become slow. How do you fix it without redesigning everything?”
Answer
The partition key is right for normal conversations, since loading a conversation is a single-partition read. The problem is one conversation with far more write traffic than one partition can take, and hashing can’t spread a single key.
I’d split that conversation’s key into buckets: conv:123#0 through conv:123#15, assigning each message to a bucket by hashing the message id. Writes then spread across up to 16 partitions. Reading recent messages becomes a fan-out to 16 buckets with a merge by timestamp (or by a time-ordered message id), which is acceptable for one conversation and avoids penalising the millions of small ones. I’d apply splitting only to conversations flagged as large, using a small lookup table of “split conversations and their bucket count”, so the default path stays a single-partition read.
Separately, a 500,000-member chat is mostly a read and delivery problem: each message fans out to many clients. I’d make sure delivery goes through a pub/sub layer rather than members polling the partition, and cache the latest page of messages so the read side doesn’t hit the database at all. I’d also isolate this conversation’s write path from its neighbours, so a viral event can’t slow down unrelated chats on the same partition.
Further reading
- System design interview questions
- System design MCQs
- Kafka partitions, offsets and ordering
- DynamoDB access patterns and key design
- Patterns of Distributed Systems on martinfowler.com: Fixed Partitions