Partitioning by Key Range

The previous post ended on a strawman: scatter records across nodes at random and the distribution is perfect, but you can no longer find anything without asking every node. The problem it exposed is that placement and lookup are the same decision. Wherever you put a record, you have to be able to work out where you put it.

Key ranges are the most direct way to satisfy both.

Ranges of Keys

Give each partition a continuous range of keys, from some minimum to some maximum. If you know the boundaries between the ranges, you know which partition holds any given key. If you also know which node holds that partition, you can send your request straight there.

Key-range partitioning: boundaries that follow the data

A key space runs left to right with an uneven density of keys along it. Four partition boundaries are placed so that each partition holds a similar number of keys, which makes them different widths. A range query over one span of the key space is highlighted, touching a single partition.

Kleppmann’s image for this is a print encyclopedia — twelve volumes, each spanning a stretch of the alphabet, and you find an entry by pulling the right book off the shelf. The lookup is the same mechanical step in both cases: compare the key against the boundaries. No index to consult, no directory service to ask, no round trip. Just arithmetic on the key you already have.

The Boundaries Follow the Data

The ranges are not evenly spaced, and they cannot be.

One volume per two letters of the alphabet would give you a slim book for X, Y and Z and a bursting one for S. To hold a similar amount in each partition, the boundaries have to adapt to how the keys are actually distributed — which is why, in the diagram above, the partitions covering the dense stretches of the key space are narrow and the sparse ones are wide.

Somebody has to choose those boundaries, and there are two answers:

An administrator sets them. Workable when you know the distribution up front and it does not move — but you are now maintaining a piece of configuration that silently degrades as the data changes shape underneath it.
The database chooses them, and adjusts as partitions grow past a threshold by splitting them in two. This is what Bigtable and HBase do, and it is why they can absorb a dataset whose distribution nobody predicted.

The second option is obviously better and quietly expensive: a partition that splits has to be moved, which is the rebalancing problem, and rebalancing is its own subject later in this sub-series.

This strategy is used by Bigtable, its open source equivalent HBase, RethinkDB, and MongoDB before version 2.4.

What Sorting Buys You

Inside a partition, keys are kept in sorted order. That is worth more than it sounds, and the reason reaches down into the storage engine.

Sorted-on-disk storage — SSTables and LSM-trees, the structures behind Bigtable, HBase, Cassandra and RocksDB — stores records physically adjacent when their keys are adjacent. So a query for a contiguous span of keys is a sequential read of one region of one file, not a scattered set of seeks. On any storage medium, sequential beats random by an order of magnitude or more.

That gives you two things:

Cheap range scans. Order the feed store’s records by timestamp and “everything posted in September” is one contiguous run of rows on one node. No fan-out, no merge, no coordination.

A concatenated index for free. A compound key sorts lexicographically by its columns in order, so the key doubles as a multi-column index. Kleppmann’s example is a sensor network keyed on year-month-day-hour-minute-second: because that key sorts chronologically, fetching every reading in a particular month is a single range query. You did not build an index for that. The partitioning scheme handed it to you.

For an application that reads in time-ordered slices, this is close to ideal.

The Timestamp Trap

It is also how you build a cluster with one working node.

A timestamp key sends every write to one partition

The key is a timestamp, so the partitions are days. Every incoming write carries the current time, so all of them land in today's partition, which is drawn saturated while the three earlier days sit idle. The partition taking the load moves at midnight, but there is still only ever one of them.

If the key leads with a timestamp, the partitions are effectively days. Writes carry the current time, so every write goes to today’s partition. That one partition absorbs the entire write load while the others sit idle, and at midnight the saturation moves to the next one.

The sensor network makes the failure vivid. The measurements are written as they happen, so all of today’s readings from every sensor in the fleet land in the same partition — one node taking the full ingest of the entire network while the rest of the cluster does nothing.

This is not a tuning problem, and it is not a sign that the boundaries were chosen badly. It is what the scheme does when the key increases monotonically and the writes are always at the leading edge. Better boundaries cannot help: there is only ever one partition containing “now”.

Prefixing, and What It Costs

The fix is to stop leading with the timestamp. Put something with many concurrent values first — the sensor name in Kleppmann’s example, user_id in the feed store — so the key becomes (user_id, timestamp).

Prefixing spreads the writes and scatters the reads

The same store keyed on user id first and timestamp second. Writes from four different users now spread across all four partitions instead of piling onto today's. The cost is on the read side: one query for a time window across many users becomes one range query per user, fanning out to every partition.

What you get: writes spread across however many users or sensors are active at once. If a thousand sensors are reporting, a thousand different key prefixes are in play, and the write load distributes across the cluster instead of stacking on one node.

What you pay: the time-window query that used to be a single sequential scan is now one range query per prefix, issued in parallel and merged by the client. Want the last hour across all thousand sensors? That is a thousand range queries. You have not removed the cost; you have moved it from the write path to the read path, and chosen which one you would rather pay.

That trade is the shape of the whole chapter. Sorted keys make range scans cheap because related records sit next to each other — and records sitting next to each other is precisely what concentrates writes on one partition. The property that gives you the good reads is the property that gives you the hot spot. You cannot keep one and discard the other.

Unless, of course, you are willing to give up the sort order entirely.

Key Takeaways

A key-range partition owns a continuous span of the key space, so a client can route itself from the key alone — no index lookup, no directory service.
Boundaries must adapt to the data’s distribution; evenly spaced ranges give badly uneven partitions. Letting the database choose them costs you rebalancing.
Sorted keys within a partition make range scans sequential rather than scattered, and let a compound key act as a concatenated index at no extra cost.
A monotonically increasing key — a timestamp above all — concentrates every write on one partition, and no choice of boundaries fixes it.
Prefixing with a high-cardinality column spreads the writes and turns one range scan into one per prefix. The cost moves from the write path to the read path; it does not disappear.

Next: hash the key, get an even spread for free, and find out what the sort order was worth.

References

Martin Kleppmann, Designing Data-Intensive Applications, chapter 6 — the treatment of partitioning this sub-series works through.
Fay Chang et al., Bigtable: A Distributed Storage System for Structured Data — the origin of the tablet model and automatic range splitting.
Apache HBase Reference Guide — regions, region splitting, and the hot-spotting section on monotonically increasing row keys.
MongoDB — Ranged Sharding — range partitioning as a configurable shard strategy, and when the docs advise against it.
Patrick O’Neil et al., The Log-Structured Merge-Tree — the sorted-on-disk structure that makes range scans sequential.
RocksDB — Leveled Compaction — how a modern LSM engine keeps keys sorted in practice.