Lesson · Partitioning and Load Balancing · Skew

Range Partitioning and Hot Ranges

A range partition keeps keys in order, which is what makes a scan read one shard instead of all of them. The cost arrives when the key is monotonic: a timestamp or an auto-increment id sends every write happening now to exactly one range, whatever N is. Over the whole run that range holds its fair share, which is why a lifetime histogram makes the problem invisible.

Open the interactive lesson Practice

monotonic key hottest range takes 100.00% of the writes happening NOW and 12.50% of the writes over the whole run hashed key hottest 16.00% now = 1.28 × an equal share but a one-window scan reads 8 of 8 ranges, not 1 hashed bucket, then timestamp, 4 buckets hottest 30.33% now, and a scan reads 4 of 8

Balance now, ordering now, and the dial between them

Core ideas

What this lesson establishes

The hard idea is a distinction between two histograms of the same writes, and every number on this page is one or the other of them.

A range partition keeps order, and order is what a scan wants

Under range partitioning shard boundaries are key values, so keys that are adjacent stay adjacent. “Everything written in the last hour” is then a read of one range rather than a question asked of every shard. That is the property being bought, and “Scatter-Gather Cost” is the price of not having it.

A monotonic key is perfectly balanced over all time and completely unbalanced at every instant

Both sentences are true of the same run. Every write in a window lands in the one range that currently contains the largest key, so the hottest range takes 100.00% of the current writes. The hot range moves on as the key space advances, and by the end of the run each of the eight ranges has taken 12.50% — a perfect lifetime histogram over a workload that never used more than one shard at a time.

The dial between them is how much of the key you hash

Hash the whole key and the current writes spread over all 8 ranges, at 16.00% for the hottest against an equal 12.50% — but a one-window scan now reads all 8. Hash only a small prefix into 4 buckets and put the timestamp after it: the hottest range takes 30.33% and a scan reads 4. The bucket count is a continuous choice between write balance and read fan-out, and nothing makes both free.

The material

Two histograms of the same writes

What a range partition is for, what a monotonic key does to it, why the lifetime view hides that, and what the two fixes cost.

Definition · Range partitioning

Under range partitioning the key space is cut into contiguous intervals and each interval is a shard. The shard of a key is found by locating the interval that contains it, so ordering is preserved: a scan over an interval of keys touches only the shards whose ranges overlap it. Hash partitioning destroys this property deliberately; range partitioning is chosen when it is needed.

The workload that breaks it is the most common workload there is. Events keyed by arrival time, rows keyed by an auto-increment id, documents keyed by a monotonically increasing version — in all of them the key of the next write is larger than the key of the last one, so the next write goes to whichever range holds the top of the key space.

8 ranges, 2 400 writes, monotonic key window 1 300 · · · · · · · hottest 100.0% window 2 · 300 · · · · · · hottest 100.0% window 3 · · 300 · · · · · hottest 100.0% … window 8 · · · · · · · 300 hottest 100.0% over the whole run every range 300 of 2 400 = 12.50% ranges taking any writes right now: 1 of 8

There is no N in the first column of that table. Doubling the shard count gives sixteen ranges of which one is taking every write, and halving it gives four ranges of which one is taking every write. Splitting the hot range is the same: the write pointer moves into one of the halves immediately and that half is then taking everything. This is the first of the three skews on this course that resharding does not touch.

Why nobody notices until it is in production

The lifetime histogram is flat. Every range ends the run with 12.50% of the writes, which is exactly an equal share, so a dashboard that plots writes-per-shard over a long window reports a perfectly balanced cluster. The measurement that shows the problem is writes-per-shard over the last few minutes, and it reports one shard at 100% and seven idle.

Example · The same fact from the read side

The flip side is the reason to have done this at all. Under the monotonic key, “read everything from one window” touches 1 range of 8. Under a hashed key the writes spread — the hottest range takes 16.00% of a window against an equal 12.50%, which is 1.28 times a fair share rather than 8.00 times it — and the same read now touches 8 of 8. The write hotspot and the scan cost are the same property seen from two directions.

The middle setting, and what it is a dial on

Put a hashed bucket in front of the timestamp and the current writes spread over as many ranges as there are buckets. At four buckets the lab measures the hottest range at 30.33% of the current writes instead of 100%, and a one-window scan reads 4 ranges instead of 1 or 8. Increasing the bucket count moves both numbers in the directions you would expect, and the bucket count is the only thing being chosen.

Notice that even hashing does not deliver the equal share. 16.00% against 12.50% is the imbalance of “Hash Partitioning and Imbalance” showing up in a different measurement, on 300 writes a window rather than 1 200 keys. Hashing moves the problem from a factor of eight to a factor of 1.28; it does not move it to one.

One more caution about the word “hot”. A hot range is a region of the key space that is busy, and splitting the range or hashing the key addresses it. A hot key is a single key that is busy, and neither of those helps at all, because a single key lands in one place under every partitioning function there is. That is the next lesson.

Interactive

Range partitioning and hot ranges

The hottest range's share of the writes happening now, not of the writes ever

Choose what the key is

Start on the monotonic key and read the two hottest-range figures — the one for the current window and the one for the whole run — before changing anything. Then switch the pattern and watch both figures and the scan cost move together, which is the trade this lesson is about.

Key pattern

Ranges (shards)8

Writes in the run2400

Buckets in the prefix4

Seed5

Hottest range, right now—

Hottest range, over the run—

An equal share would be—

The hottest is over it by—

Ranges a one-window scan reads—

Ranges taking writes now—

Every cell is a count of writes that pattern actually put in that range in that window. The trap is the second figure: over the whole run a monotonic key is spread perfectly evenly across the ranges, and at no instant during it was more than one range taking anything. The bucket prefix is the remedy and it costs the scan: one window of time is one range under a timestamp, all N under a hash, and as many as there are buckets under the prefix. The placement is drawn from an LCG with multiplier 16 807, increment 0 and modulus 2³¹ − 1, which is prime — the generator the rest of this path uses has modulus 2³¹, and the low bits of a power-of-two modulus are a cycle, so keys taken modulo 8 or 16 from it come out perfectly level. The seed is mixed before it becomes a state, so seed 4 is not seed 3 rescaled. The same seed draws the same placement every time this page is opened.

Method

Diagnosing a hot range

The first step is the one that is usually skipped, and skipping it is what makes the rest of the diagnosis impossible.

Measure writes per shard over a short window, not over the run

A lifetime histogram of a monotonic key is flat at 1/N per shard and tells you nothing. Take the window down to minutes. If one shard is at or near 100% and the identity of that shard changes over the day, the key is monotonic and you have found it.

Look at the key, and ask whether the next one is larger

Timestamps, auto-increment ids, sequence numbers and version counters all answer yes. A key that answers yes will concentrate current writes on one range under any range partitioning and under any shard count.

Price the scan you would lose

Before hashing the key, find out what reads it in order. If the answer is “a time-range scan, constantly”, hashing turns every one of those into a read of all N shards, and “Scatter-Gather Cost” is what that costs. If nothing scans it, hash it and stop.

If both matter, choose the bucket count deliberately

A hashed prefix over b buckets spreads current writes over b ranges and makes a scan read b of them. At b = 4 the lab measures a hottest range of 30.33% and a scan of 4 of 8. Pick b from the fan-out you can afford on the read side, then check the write balance it leaves.

Hot ranges, now and over the run

Score 0 / 0

Choose the answer you can justify.

The same 2 400 writes under three key designs

Eight ranges throughout, and the only thing that changes is what the key is. Both hottest-range figures are reported each time, because quoting one of them is how this problem stays hidden.

monotonic — a timestamp or an auto-increment id hottest range, current window 100.00% = 8.00 × an equal share hottest range, whole run 12.50% = an equal share exactly ranges taking writes now 1 of 8 a one-window scan reads 1 of 8 hashed — the hash of the id hottest range, current window 16.00% = 1.28 × an equal share hottest range, whole run 13.21% ranges taking writes now 8 of 8 a one-window scan reads 8 of 8 hashed bucket, then timestamp — 4 buckets hottest range, current window 30.33% = 2.43 × an equal share hottest range, whole run 13.92% ranges taking writes now 4 of 8 a one-window scan reads 4 of 8

Read the table down the “whole run” column and all three designs look the same, within a point or two of an equal 12.50%. That column is the one most monitoring reports. Every fact in this lesson is in the other columns.

For a faded rehearsal, keep the monotonic key and take the range count from 8 to 32. The supplied first move is the equal share, which is now 1/32 = 3.125%. Predict the hottest range's share of the current window, predict its share over the whole run, and then predict the multiple of an equal share the first figure represents. Check all three in the lab and say which of the three moved when N did.

Common mistakes

Diagnosing a hot range from a lifetime histogramA monotonic key gives every range exactly 1/N of the writes over a long enough window, so the chart most teams look at is flat while one shard is saturated. The measurement that finds this is writes per shard over minutes, and the tell is that the busy shard keeps changing identity.

Expecting more shards, or a split, to fix itThere is no N in “100% of current writes”. Sixteen ranges give one range at 100%, and splitting the hot range hands the whole load to whichever half contains the top of the key space. Range skew from a monotonic key is a property of the key, and it is fixed on the key.

Hashing the key without pricing the scansHashing brings the hottest range to 1.28 times a fair share and turns every ordered read into a request to all N shards. If the reason for range partitioning was the scans, that trade can be much worse than the hotspot — check what reads the table before changing how it is keyed.

Check your understanding

✓

Finish when you would ask “over what window?” before accepting any writes-per-shard chart.

You should be able to compute the hottest range's share both instantaneously and over a run, explain why they differ for a monotonic key, and state what hashing the key or a hashed prefix does to each of them and to the cost of an ordered scan.

Note: A hot range is a busy region of the key space and can be split, hashed or bucketed. A single key that is busy can be none of those things: it lands in one place under every partitioning function, and “Hot Keys and Salting” shows that the hottest shard's load has a floor no shard count reaches under.