Range Partitioning

Records are kept sorted by key, and each node owns one contiguous range of keys. Neighbouring keys live together, so a query for a range of keys asks only one or two nodes, and a range that grows too big is split in two. The risk is keys that all arrive at one end, such as rising ids or timestamps: every new write lands in the same range. Below, add nodes to watch ranges split, and turn on range queries and sign-ups to see both sides.

Speed1x

The strip in the panel is the key space, oldest ids on the left; each coloured stretch is one node's range. Each dot in a node is one user record, coloured by country. Add a node and the records of the range that splits glide to the new node, ringed so you can count them. A node turns red when it serves well above its share of requests.

How many ranges, and where writes land

Users

Data per userKB

Split a range atMiB

One node holdsGB

Sign-ups a second

1. Total data
users x data per user = 500M x 10 KB = 4.66 TB
2. Ranges
total / split size = 9,537, and up to twice that, since a range is about half full right after it splits: 9,537 to 19.1K ranges
3. Nodes, filled to 70%
total / (one node x 70%), rounded up = 14 nodes, each holding about 681 to 1,362 ranges
4. Adding one node
whole ranges move to it until it holds its share, 1 / (N + 1) of the data: 318 GB, and nothing is rehashed
5. Sign-up writes
with a rising id, all 2,000 a second go to the last range, on one node: 2,000/s on one node. With a key that spreads them, each of the 14 nodes takes about 143/s.
Many small ranges are what make range partitioning easy to rebalance: a node is added by handing it whole ranges. They do nothing for step 5. The usual fix is to start the key with something that spreads, such as a user id before a timestamp.

Where these formulas come from

Step 1 is the storage estimate from the back-of-the-envelope chapter of Alex Xu's System Design Interview, Vol. 1. Step 2 uses the split rule CockroachDB documents: a range that reaches the size limit (512 MiB by default) is split into two, so a range holds between about half the limit and the full limit. Step 4 assumes the system moves ranges until every node holds the same share. Step 5 is plain arithmetic: a rising key sends every new write to the end of the key space.

Limits of range partitioning

Rising keys make one hot range

Auto-increment ids, timestamps and anything else that only grows put every new write at the end of the key space, on one node. Splitting cannot help, because the newest keys always land in the newest range.

Boundaries must follow the data

Equal slices of the key space are rarely equal slices of the data: names cluster on common letters, ids cluster where growth was fast. Systems split by size and by load instead of by key value.

Popular ranges get hot

Even with steady keys, readers may all want the same stretch, such as this week's orders. A busy range can be split, but a single hot key cannot.

Someone must know the boundaries

Unlike a hash, a range boundary cannot be computed from the key. Every router needs the current map of ranges to nodes, and that map changes whenever a range splits or moves.

How Bigtable, CockroachDB and HBase split by range

All three keep rows sorted by key, split ranges as they grow, and warn against rising keys.

Bigtable: tablets

"A Bigtable table is sharded into blocks of contiguous rows, called tablets", and Bigtable "splits busier or larger tablets in half". Its schema guide lists row keys that start with a timestamp among the keys to avoid: "This pattern causes sequential writes to be pushed onto a single node, creating a hotspot."

CockroachDB: ranges

Data is "a sorted map of key-value pairs", divided "into contiguous chunks called ranges". A range that reaches range_max_bytes, 512 MiB by default, is split in two, and load-based splitting splits busy ranges too. Its hotspot guide notes that with a continually increasing key "all writes appear at the index tail", and that load-based splitting does not resolve such moving hotspots.

HBase: regions

"Rows in HBase are sorted lexicographically by row key", and "a region is a contiguous segment of a column family". Its guidance on hotspotting: "it's best to avoid using a timestamp or a sequence (e.g. 1, 2, 3) as the row-key."

Sources and credibility

All are official documentation from Google Cloud, Cockroach Labs and the Apache HBase project. Quoted phrases are short attributed quotations; everything else is described in our words.