Ch. 13 · System Design

System Design Partitioning and Hot Keys

Choosing a partition key, why hash mod N moves 91% of keys when you add a node, how consistent hashing fixes it, and how to split a hot key.

~8 min readintermediateupdated Nov 1, 2026

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.

Picture 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. The Node 22 script below runs three experiments, and its output is shown section by section. It hashes keys with MD5, so every run prints the same numbers. The first experiment takes 200,000 keys from 10 nodes to 11:

import { createHash } from 'node:crypto';
const hash = (s) => createHash('md5').update(s).digest().readUInt32BE(0); // 32-bit hash, same on every run
const pct = (x) => (x * 100).toFixed(1) + '%';

// 1. hash mod N, growing from 10 to 11 nodes
const keys = Array.from({ length: 200_000 }, (_, i) => 'key:' + i);
const hashes = keys.map(hash);
let movedMod = 0;
for (const x of hashes) if (x % 10 !== x % 11) movedMod++;
console.log('200,000 keys, growing from 10 to 11 nodes:');
console.log('  hash mod N:              ', pct(movedMod / keys.length), 'of keys change node');

// 2. consistent hashing ring with virtual nodes
function ring(nodes, vnodes) {
  const points = [];
  for (let n = 0; n < nodes; n++)
    for (let v = 0; v < vnodes; v++) points.push([hash(`node-${n}#${v}`), n]);
  points.sort((a, b) => a[0] - b[0]);
  return (x) => { // first point clockwise from x (binary search), wrapping to the start
    let lo = 0, hi = points.length;
    while (lo < hi) { const mid = (lo + hi) >> 1; if (points[mid][0] < x) lo = mid + 1; else hi = mid; }
    return points[lo % points.length][1];
  };
}
for (const v of [1, 16, 256]) {
  const before = ring(10, v), after = ring(11, v);
  const load = new Array(10).fill(0);
  let moved = 0;
  for (const x of hashes) { const b = before(x); load[b]++; if (b !== after(x)) moved++; }
  const avg = keys.length / 10;
  console.log(`  ring, ${String(v).padStart(3)} vnodes/node:  ${pct(moved / keys.length)} move;`,
    `busiest node holds ${(Math.max(...load) / avg).toFixed(2)}x the average, quietest ${(Math.min(...load) / avg).toFixed(2)}x`);
}

// 3. one hot account on 16 partitions
const P = 16, WRITES = 1_000_000;
console.log(`\n${P} partitions, one account takes 20% of writes:`);
for (const suffixes of [1, 8, 32]) {
  const load = new Array(P).fill(0);
  for (let i = 0; i < WRITES; i++) {
    const key = i % 5 === 0
      ? (suffixes === 1 ? 'celebrity' : `celebrity#${(i / 5) % suffixes}`)   // round robin over suffixes
      : 'user:' + ((i * 7919) % 100_000);                                    // everyone else
    load[hash(key) % P]++;
  }
  const label = suffixes === 1 ? 'key = user id:' : `key = user id + suffix 0..${suffixes - 1}:`;
  console.log(`  ${label.padEnd(30)} hottest partition at ${(Math.max(...load) / (WRITES / P)).toFixed(2)}x the average`);
}
JavaScript
200,000 keys, growing from 10 to 11 nodes:
  hash mod N:               90.9% of keys change node
Text

Adding 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. The second experiment repeats the move with a ring, varying the number of virtual nodes, and measures how evenly the 10-node ring spreads the keys:

  ring,   1 vnodes/node:  11.4% 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.5% move; busiest node holds 1.10x the average, quietest 0.91x
Text

All 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. That’s the reason virtual nodes exist, and the short answer if you’re asked: they make 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. The third experiment sends a million writes to 16 partitions, with one account receiving 20% of them:

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.59x the average
  key = user id + suffix 0..31:  hottest partition at 1.19x the average
Text

With 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.59x, and 32 to 1.19x. Eight suffixes don’t give 8 distinct partitions, because some of them hash to the same partition; that’s why the result is worse than the ideal 1.2x.

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

More in System Design

read ✓System Design · hard

System Design: Bloom Filters

Size a Bloom filter from item count and target error rate, see why it never gives false negatives, and know when it's the wrong tool.

~8 min readread →
read ✓System Design · hard

System Design: Presence Tracking

Build online indicators for 10 million users: heartbeats with TTLs, why the TTL must cover lost beats, and fan-out only to who's watching.

~7 min readread →
esc