Partitioning & the Physics of Hot Keys

How to split: range, hash, and the ring

Range partitioning keeps keys sorted and splits by boundaries (A–F on shard 1, G–M on shard 2). Range scans are cheap (“all orders in March” hits one shard), but sequential keys — timestamps, auto-increment IDs — pile every new write onto the last shard. Hash partitioning scatters keys by hash(key), which spreads writes evenly but destroys range scans (adjacent keys land anywhere). The catch with the naive version, hash(key) % N: change N and almost every key remaps — resharding becomes a full data migration, i.e. an outage.

Consistent hashing fixes the resharding problem. Place nodes and keys on a ring; each key belongs to the next node clockwise. Add or remove a node and only the keys in that node’s arc move — about K/N of them, not all. Drag the fleet size below and watch how few keys move, versus what modulo would do:

The Skew Budget: distribution is a number, not a vibe

“Evenly distributed” is not a yes/no. It’s a ratio you measure and bound. The Skew Budget is the most-loaded partition’s load divided by the average, and the maximum value you’re willing to tolerate before you act. Pick the number up front (say 1.5×), measure it continuously, and treat a breach as a signal — not a surprise during an incident.

The Hot-Key Triage tree

When the Skew Budget says “one partition, spiking,” run this. The first branch — read-hot vs write-hot — splits the whole solution space, because a hot read is a caching/replication problem and a hot write is a sharding/data-model problem.

1// A single hot counter ("likes on the viral post") serializes every
2// increment onto one partition. Split it into K shards, each on its own
3// partition, and sum on read. Writes fan out; reads pay a small gather.
4const shards = 16
5 
6func incrementLikes(postID string) {
7  shard := rand.Intn(shards)
8  db.Incr(fmt.Sprintf("likes:%s#%d", postID, shard)) // lands on K partitions
9}
10 
11func readLikes(postID string) int64 {
12  var total int64
13  for s := 0; s < shards; s++ {
14    total += db.Get(fmt.Sprintf("likes:%s#%d", postID, s))
15  }
16  return total // the read got K× more expensive; the write stopped melting one shard
17}

What this sounds like in an interview

Exercises

1func (r *Ring) AddAndReshard(node string) {
2  // add the new node's vnodes to the live ring, in place
3  for i := 0; i < r.replicas; i++ {
4    pos := hashKey(strconv.Itoa(i) + "#" + node)
5    r.sorted = append(r.sorted, pos)   // mutates the slice Get() is reading
6    r.owner[pos] = node                // mutates the map Get() is reading
7  }
8  sort.Slice(r.sorted, ...)            // Get() may observe a half-sorted ring
9  migrateData(node)                    // ...and data hasn't moved yet anyway
10}