Partitioning: Range or Hash, Where Secondary Indexes Live, and How to Rebalance

Replication keeps the same data on several machines; partitioning (also called sharding) splits the data so each machine holds only a part — when the dataset won’t fit on one node, or one node can’t take the write throughput, it’s the only way out. The two are almost always used together: data is first cut into partitions, and each partition then does its own leader-follower replication. You’ve already met several partitioned systems: Redis Cluster’s 16384 slots, Kafka’s partitions, the shards of an MPP database — what this chapter gives you is the three hard problems they all share: how to split, where the index lives, and how to rebalance.

Problem one: how to split — range keeps order, hash breaks up hot spots

The goal of partitioning is to spread data and load evenly; the enemy is skew — everything crowding into one partition (a hot spot), so the split achieves nothing. The two mainstream ways of splitting are exactly a pair of trade-offs:

Range partitioning is like the volumes of an encyclopedia: keys are ordered, so a range scan like "all orders in July" reads one contiguous stretch and is extremely efficient; but if the key is a timestamp, today's writes all hit the last volume — a hot spot. Hash partitioning sprays adjacent keys evenly: load is flat, but order is gone, and a range scan has to ask every partition. The compromise is a compound primary key (hash picks the partition, the remaining columns sort within it). And one thing nobody can save: a single extremely hot key (a celebrity's post, a viral product) — however even the hash, the same key lands in the same partition, and the only fix is to "salt" it in the application and split it up, a cousin of the cache breakdown problem

Problem two: where secondary indexes live — local or global

Primary-key lookups are easy (key → partition); the trouble is secondary indexes: “find all the red cars” — red cars are scattered across every partition, so where does the index go? Two answers, and again a pair of trade-offs:

Local index: each partition indexes only its own data — a write touches one partition and is cheap; but "find all the red cars" needs scatter/gather: ask every partition, each searches its own, then merge — the more partitions, the costlier the read. Global index: partition the index itself, but by term — the complete list for "red" is owned by one partition, and a query asks only that one; the price is that a write touching several terms has to update the index on several partitions (so in practice it's mostly asynchronous, like DynamoDB's GSI — the index lags half a beat). Local charges the bill to reads, global charges it to writes — the same multiple-choice question as "when do you pay the organising fee" in the storage-engines post

Problem three: nodes came and went — how do you rebalance

Add a machine, replace a machine, and partitions have to move with it — rebalancing has one iron rule: never use hash mod N. Change N and nearly every key’s home changes, which is a whole-database move. The mainstream solution you’ve already seen live in the Redis Cluster post:

A fixed number of partitions: create far more partitions than nodes from the start (Redis Cluster’s 16384 slots, Kafka’s partitions, Elasticsearch’s shards); when nodes come and go, only whole partitions change ownership, and key→partition never changes. Add a level of indirection, and moving becomes moving tidy boxes.
Dynamic partitioning: a partition splits when it grows past a threshold and merges when it shrinks (HBase) — the partition count grows with the data.
Automatic vs manual: fully automatic rebalancing is tempting, but DDIA warns of its dark side — when a node is merely overloaded and slow, automation that misjudges it as dead and starts moving data adds the load of the move itself on top, the exact script of a cascading failure. So mature systems mostly “propose automatically, a human presses confirm”.

Finally, routing: how does a request find the right partition? Three ways — ask any node and let it forward, put a routing tier in front (with the partition table in ZooKeeper), or the client knows itself (Redis Cluster’s MOVED is this type, letting the client cache the slot table).

Reflections

”Keep order” and “break up hot spots” can’t both be had — the compound key is my favourite compromise

I’ve hit the range-vs-hash trade-off in real data: time-series data partitioned by time range, with the result that all current writes forever hit the last partition — ten partitions, nine of them sunbathing. Only after this chapter did I see the beauty of Cassandra’s compound primary key: hash decides “which partition” (scattering hot spots), the remaining columns sort “within” it (preserving range scans) — each requirement gets half, but each half in the right dimension. It also explains why Kafka’s key→partition and Redis’s hash tags look the way they do: first divide the household fairly by hash, then keep order inside the house. Faced with a “must be both even and ordered” requirement, first ask “can the two requirements be split across two levels” — it often solves it.

The same “where do you pay” question, for the third time

Local vs global index — I laughed halfway through: isn’t this LSM vs B-tree, the same question all along: the same cost, do you pay it at write time or at read time? A local index is cheap to write (touch only your own partition) and hangs the bill on every read’s scatter/gather; a global index reads precisely and hangs the bill on cross-partition writes (which is why it mostly dares only to be asynchronous, the index half a beat behind). The criterion is the same as before too: the read/write ratio decides everything — reads far outnumber writes with a concentrated query pattern, global pays off; write-heavy with queries that can tolerate scatter, local is simple and reliable. A pattern that shows up three times in one book isn’t a fact to learn, it’s the gravity of the field — internalise it and you’ll skim new tools’ docs ten lines at a time.

Automatic migration under overload is the classic script of good intentions gone wrong

The warning about “fully automatic” rebalancing hit my SRE nerve: node overloaded and slow → automation misjudges it dead → starts moving its partitions away → the move eats more bandwidth and I/O → other nodes slow down too → more misjudgement, more moving — a textbook cascading failure, and every step is “for your own good”. Same root as “a false positive costs more than doing nothing” in the Sentinel post, but the data-migration version is nastier, because moving data is itself heavy load. So my position on “automation in the data tier” is one notch more conservative than for the stateless tier: a dead Pod replaced automatically, fine; but a decision to move data at scale gets proposed by the machine and confirmed by a human — in the most chaotic moment, keep the right to “hit the gas” with a person. This chapter used one mechanism design to explain an entire operations philosophy.